«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