1. Введение
Целью этой серии статей является объяснение идеи генетических алгоритмов .
Генетические алгоритмы предназначены для решения проблем с использованием тех же процессов, что и в природе — они используют комбинацию отбора, рекомбинации и мутации для развития решения проблемы.
Давайте начнем с объяснения концепции этих алгоритмов на примере простейшего бинарного генетического алгоритма.
2. Как работают генетические алгоритмы
Генетические алгоритмы являются частью эволюционных вычислений , которые представляют собой быстрорастущую область искусственного интеллекта.
Алгоритм начинается с набора решений (представленных индивидуумами ), называемого населением . Берутся решения из одной популяции и используются для формирования новой популяции , так как есть шанс, что новая популяция будет лучше старой.
Особи, выбранные для образования новых растворов ( потомков ), отбираются в соответствии с их приспособленностью — чем они более приспособлены, тем больше у них шансов на размножение.
3. Бинарный генетический алгоритм
Давайте взглянем на основной процесс простого генетического алгоритма.
3.1. Инициализация
На этапе инициализации мы генерируем случайную популяцию , которая служит первым решением . Во-первых, нам нужно решить, насколько большим будет Population и какое окончательное решение мы ожидаем:
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. Потомство
На этом шаге нам нужно создать новый Population . Во-первых, нам нужно выбрать два родительских отдельных объекта из совокупности в соответствии с их пригодностью. Пожалуйста, обратите внимание, что лучше позволить лучшей Индивидуальности из текущего поколения перейти в следующее поколение в неизменном виде. Эта стратегия называется элитизмом:
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