«1. Введение

Целью этой серии статей является объяснение идеи генетических алгоритмов.

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

Давайте начнем с объяснения концепции этих алгоритмов на примере простейшего бинарного генетического алгоритма.

2. Как работают генетические алгоритмы

Генетические алгоритмы являются частью эволюционных вычислений, быстро растущей области искусственного интеллекта.

Алгоритм начинается с набора решений (представленных отдельными лицами), называемого популяцией. Берутся решения из одной популяции и используются для формирования новой популяции, так как есть шанс, что новая популяция будет лучше старой.

Особи, отобранные для образования новых растворов (потомков), отбираются в соответствии с их приспособленностью — чем они более приспособлены, тем больше у них шансов на размножение.

3. Бинарный генетический алгоритм

Давайте рассмотрим основной процесс простого генетического алгоритма.

3.1. Инициализация

На этапе инициализации мы генерируем случайную популяцию, которая служит первым решением. Во-первых, нам нужно решить, насколько велика будет популяция и какое окончательное решение мы ожидаем: 

SimpleGeneticAlgorithm.runAlgorithm(50,
  "1011000100000100010000100000100111001000000100000100000000001111");

В приведенном выше примере размер популяции равен 50, а правильное решение представлено двоичной битовой строкой. что мы можем измениться в любое время.

На следующем шаге мы собираемся сохранить желаемое решение и создать случайную популяцию: 

setSolution(solution);
Population myPop = new Population(populationSize, true);

Теперь мы готовы запустить основной цикл программы.

3.2. Проверка пригодности

В основном цикле программы мы будем оценивать каждого Индивидуума по фитнес-функции (проще говоря, чем лучше Индивидуум, тем большее значение фитнес-функции он получает): 

while (myPop.getFittest().getFitness() < getMaxFitness()) {
    System.out.println(
      "Generation: " + generationCount
      + " Correct genes found: " + myPop.getFittest().getFitness());
    
    myPop = evolvePopulation(myPop);
    generationCount++;
}

~~ ~ Давайте начнем с объяснения того, как мы получаем наиболее подходящего человека: 

public int getFitness(Individual individual) {
    int fitness = 0;
    for (int i = 0; i < individual.getDefaultGeneLength()
      && i < solution.length; i++) {
        if (individual.getSingleGene(i) == solution[i]) {
            fitness++;
        }
    }
    return fitness;
}

Как мы видим, мы сравниваем два отдельных объекта по крупицам. Если мы не можем найти идеальное решение, нам нужно перейти к следующему шагу, который представляет собой эволюцию населения.

3.3. Потомство

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

if (elitism) {
    newPopulation.getIndividuals().add(0, pop.getFittest());
    elitismOffset = 1;
} else {
    elitismOffset = 0;
}

Чтобы выбрать два лучших индивидуальных объекта, мы собираемся применить стратегию выбора турнира: 

private Individual tournamentSelection(Population pop) {
    Population tournament = new Population(tournamentSize, false);
    for (int i = 0; i < tournamentSize; i++) {
        int randomId = (int) (Math.random() * pop.getIndividuals().size());
        tournament.getIndividuals().add(i, pop.getIndividual(randomId));
    }
    Individual fittest = tournament.getFittest();
    return fittest;
}

Победитель каждого турнира (тот, у кого лучшая физическая форма) выбирается для следующего этапа, который называется кроссовером: 

private Individual crossover(Individual indiv1, Individual indiv2) {
    Individual newSol = new Individual();
    for (int i = 0; i < newSol.getDefaultGeneLength(); i++) {
        if (Math.random() <= uniformRate) {
            newSol.setSingleGene(i, indiv1.getSingleGene(i));
        } else {
            newSol.setSingleGene(i, indiv2.getSingleGene(i));
        }
    }
    return newSol;
}

В кроссовере мы обмениваем биты от каждого выбранного индивидуума в случайно выбранном месте. Весь процесс проходит внутри следующего цикла: 

for (int i = elitismOffset; i < pop.getIndividuals().size(); i++) {
    Individual indiv1 = tournamentSelection(pop);
    Individual indiv2 = tournamentSelection(pop);
    Individual newIndiv = crossover(indiv1, indiv2);
    newPopulation.getIndividuals().add(i, newIndiv);
}

Как мы видим, после кроссовера мы помещаем новое потомство в новую популяцию. Этот шаг называется Принятие.

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

private void mutate(Individual indiv) {
    for (int i = 0; i < indiv.getDefaultGeneLength(); i++) {
        if (Math.random() <= mutationRate) {
            byte gene = (byte) Math.round(Math.random());
            indiv.setSingleGene(i, gene);
        }
    }
}

Все типы мутации и кроссовера хорошо описаны в этом уроке.

Затем мы повторяем шаги из подразделов 3.2 и 3.3, пока не достигнем условия завершения, например, наилучшего решения.

4. Советы и хитрости

Чтобы реализовать эффективный генетический алгоритм, нам нужно настроить набор параметров. В этом разделе должны быть даны некоторые основные рекомендации, как начать с наиболее важных параметров:

    Частота кроссовера – она должна быть высокой, около 80%-95% Частота мутаций – она должна быть очень низкой, около 0,5% -1%. Размер популяции — хороший размер популяции составляет около 20-30, однако для некоторых задач лучше подходят размеры 50-100. Отбор — можно использовать базовый выбор колеса рулетки с концепцией элитарности. о кодировке и проблеме

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

5. Заключение

Это руководство знакомит с основами генетических алгоритмов. Вы можете узнать о генетических алгоритмах без каких-либо предварительных знаний в этой области, имея только базовые навыки компьютерного программирования.

Полный исходный код фрагментов кода в этом руководстве доступен в проекте GitHub.

Также обратите внимание, что мы используем Lombok для генерации геттеров и сеттеров. Вы можете проверить, как правильно настроить его в своей IDE, в этой статье.

Дополнительные примеры генетических алгоритмов см. во всех статьях нашей серии:

    Как разработать генетический алгоритм? (этот) Задача коммивояжера в Java