Geneti c Алгоритм - какая структура данных мне нужна? - PullRequest
Новая
       22

Geneti c Алгоритм - какая структура данных мне нужна?

4 голосов
/ 18 июня 2020

Надеюсь, здесь разрешен такой открытый вопрос. Я работаю над простым GA, который будет развивать вывод String в соответствии с заданной целевой строкой. Следовательно, в каждом поколении будет создаваться популяция из N строк, каждой из которых будет назначена пригодность на основе ее расстояния Хэмминга от целевой строки. Затем мне нужен способ хранения и сортировки этой информации. Я работаю в обработке, но решения на Java почти всегда могут использоваться на этом языке с импортом.

Поскольку то, что мне нужно, является неопределенной структурой "ключ-значение", я инстинкт подсказывает, что мне нужна какая-то словаря, но у меня очень мало опыта работы с ними. Есть также некоторые сложности, которые уводят нас от моего понимания того, как работают словари. Я хочу сделать следующее:

  1. Сохранять каждую строку вместе с соответствующей пригодностью. Дубликаты обоих из них должны быть возможны .

  2. Сортировать структуру по значению, т.е. перечислить совокупность в порядке убывания их пригодности.

  3. Обрезать нижние 50% населения. Вероятно, самым простым методом было бы заменить непригодную популяцию потомком подходящей популяции.

Время доступа / эффективность вычислений не имеет особого значения.

I прошлой ночью пытался решить эту проблему с помощью HashMap, но я продолжал сталкиваться с такими проблемами, как дублирование ключей, недопустимое в этой структуре, и я не мог найти простой способ перебрать HashMap и изменить только нижние X% записей по значению.

Подводя итог, мне нужна структура, в которой каждая запись состоит из строки и целого числа , можно хранить дубликатов каждой , структура можно отсортировать в порядке убывания по целочисленному значению , и, таким образом, верхний или нижний X% записей можно оперировать с , не затрагивая остальные.

Большое спасибо на ваше время, любая помощь будет принята с благодарностью.

1 Ответ

8 голосов
/ 18 июня 2020

Есть много способов решить эту проблему. Лично я бы попробовал самое простое решение. Я не знаю всего контекста вашего проекта и его видения, однако, основываясь на информации, которую вы нам предоставили, я публикую решение, которое я бы выбрал.

Примечание : Следующие классы могут быть неполными. Возможно, вам придется добавить больше методов, чтобы их было легче использовать. Это просто идея решения, изложенная в коде, которая может сработать для вас.

Класс Pair моделирует пару строки и ее значение пригодности. Класс Population моделирует популяцию определенного поколения. Он сохраняет свои элементы в списке и предоставляет методы для управления списком. Это также позволяет дублировать пары. Вы можете выбрать верхних или нижних X членов популяции и оперировать с ними. 

public class Pair implements Comparable<Pair>{
    private final String value;
    private final int fitness;

    public Pair(String value, int fitness) {
        this.value = value;
        this.fitness = fitness;
    }

    public String getValue() {
        return value;
    }

    public int getFitness() {
        return fitness;
    }

    @Override
    public int compareTo(Pair pair) {
        return -Integer.compare(this.fitness, pair.fitness);
    }

    @Override
    public String toString() {
        return "Pair{" + "value='" + value + '\'' + ", fitness=" + fitness + '}';
    }
}

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

public class Population {
    private final List<Pair> members = new ArrayList<>();

    public void addMember(Pair pair) {
        members.add(pair);
    }

    public List<Pair> getTop(int x) {
        return members.stream().sorted().limit(x).collect(Collectors.toList());
    }

    public List<Pair> getBottom(int x) {
        return  members.stream().sorted(Comparator.reverseOrder()).limit(x).collect(Collectors.toList());
    }
}

А вот неполный тестовый класс: 

import static org.junit.jupiter.api.Assertions.assertEquals;
import static org.junit.jupiter.api.Assertions.assertTrue;

import java.util.List;

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

class PopulationTest {
    Population population = new Population();

    @BeforeEach
    void populate() {
        population.addMember(new Pair("test", 5));
        population.addMember(new Pair("abc", 13));
        population.addMember(new Pair("xyz", 8));
        population.addMember(new Pair("abc", 20));
    }

    @Test
    void testSortDescending() {
        List<Pair> members = population.getTop(4);
        for (int i = 0; i < members.size() - 1; i++) {
            assertTrue(members.get(i).getFitness() >= members.get(i + 1).getFitness());
        }
    }

    @Test
    void testGetTop() {
        List<Pair> top = population.getTop(2);

        assertEquals(20, top.get(0).getFitness());
        assertEquals(13, top.get(1).getFitness());
    }

    @Test
    void testGetBottom() {
        List<Pair> bottom = population.getBottom(2);

        assertEquals(5, bottom.get(0).getFitness());
        assertEquals(8, bottom.get(1).getFitness());
    }
}
...