Как работает генетический алгоритм

Схема алгоритма

Следующая схема подводит итог, как генетический алгоритм работает:

Алгоритм начинается путем создания случайной начальной генеральной совокупности.
Алгоритм затем создает последовательность нового населения. На каждом шаге алгоритм использует людей в текущей генерации, чтобы создать следующую генеральную совокупность. Чтобы создать новую генеральную совокупность, алгоритм выполняет следующие шаги:
1. Очки каждый член текущей генеральной совокупности путем вычисления ее значения фитнеса. Эти значения называются необработанными очками фитнеса.
2. Масштабирует необработанные очки фитнеса, чтобы преобразовать их в более применимую область значений значений. Эти масштабированные значения называются значениями ожидания.
3. Выбирает участников, названных родительскими элементами, на основе их ожидания.
4. Некоторые люди в текущей генеральной совокупности, которые имеют более низкий фитнес, выбраны в качестве элиты. Эти элитные люди передаются следующей генеральной совокупности.
5. Производит дочерние элементы из родительских элементов. Дочерние элементы производятся или путем внесения случайных изменений в единый объект-родитель — мутацию — или путем объединения векторных записей пары родительских элементов — перекрестное соединение.
6. Заменяет текущую генеральную совокупность на дочерние элементы, чтобы сформировать следующее поколение.
Алгоритм останавливается, когда одному из критерия остановки соответствуют. Смотрите Останавливающиеся Условия для Алгоритма.

Начальная генеральная совокупность

Алгоритм начинается путем создания случайной начальной генеральной совокупности, как показано в следующей фигуре.

В этом примере начальная генеральная совокупность содержит людей 20. Обратите внимание на то, что все люди в начальной генеральной совокупности лежат в верхнем правом квадранте изображения, то есть, их координаты находятся между 0 и 1. В данном примере Initial range в опциях Population является [0;1].

Если вы знаете приблизительно, где минимальная точка для функции находится, необходимо установить Initial range так, чтобы точка нашлась около середины той области значений. Например, если вы полагаете, что минимальной точкой для функции Рэстриджина является около точки [0 0], вы могли установить Initial range быть [-1;1]. Однако, когда этот пример показывает, генетический алгоритм может найти минимум даже с меньше, чем оптимальный выбор для Initial range.

Создание следующего поколения

На каждом шаге генетический алгоритм использует текущую генеральную совокупность, чтобы создать дочерние элементы, которые составляют следующее поколение. Алгоритм выбирает группу людей в текущей генеральной совокупности, названной родительскими элементами, кто вносит их гены — записи их векторов — их дочерним элементам. Алгоритм обычно выбирает людей, которые имеют лучшие значения фитнеса как родительские элементы. Можно задать функцию что использование алгоритма, чтобы выбрать родительские элементы в поле Selection function в опциях Selection.

Генетический алгоритм создает три типа дочерних элементов для следующего поколения:

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

Следующая принципиальная схема иллюстрирует три типа дочерних элементов.

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

Следующие разделы объясняют, как алгоритм создает дочерние элементы перекрестного соединения и мутации.

Перекрестные дочерние элементы

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

Дочерние элементы мутации

Алгоритм создает дочерние элементы мутации путем случайного изменения генов отдельных родительских элементов. По умолчанию для неограниченных проблем алгоритм добавляет случайный вектор от Распределения Гаусса до родительского элемента. Для ограниченных или линейно ограниченных проблем дочерний элемент остается выполнимым.

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

Графики более поздних поколений

Следующие данные показывают население в итерациях 60, 80, 95, и 100.

Как количество увеличений поколений, люди в генеральной совокупности становятся ближе вместе и приближаются к минимальной точке [0 0].

Остановка условий для алгоритма

Генетический алгоритм использует следующие условия определить, когда остановиться:

Generations — Алгоритм останавливается, когда количество поколений достигает значения Generations.
Time limit — Остановки алгоритма после выполнения для количества времени в секундах равняются Time limit.
Fitness limit — Алгоритм останавливается, когда значение функции фитнеса для лучшей точки в текущей генеральной совокупности меньше чем или равно Fitness limit.
Stall generations — Алгоритм останавливается, когда среднее относительное изменение в значении функции фитнеса по Stall generations является меньше, чем Function tolerance.
Stall time limit — Алгоритм останавливается, если нет никакого улучшения целевой функции в течение интервала времени в секундах, равных Stall time limit.
Stall test — Условием останова является или average change или geometric weighted. Для geometric weighted функция взвешивания является 1/2ⁿ, где n является количеством поколений до тока. Оба условия останова применяются к относительному изменению в функции фитнеса по Stall generations.
Function tolerance — Выполнения алгоритма до среднего относительного изменения в значении функции фитнеса по Stall generations являются меньше, чем Function tolerance.
Constraint tolerance — Constraint tolerance не используется в качестве останавливающегося критерия. Это используется, чтобы определить выполнимость относительно нелинейных ограничений. Кроме того, max(sqrt(eps),ConstraintTolerance) определяет выполнимость относительно линейных ограничений.

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

Когда вы запускаете генетический алгоритм, панель Run solver and view results отображает критерий, который заставил алгоритм останавливаться.

Опции Stall time limit и Time limit препятствуют тому, чтобы алгоритм запускался слишком долго. Если алгоритм останавливается из-за одного из этих условий, вы можете улучшить свои результаты путем увеличения значений Stall time limit и Time limit.

Выбор

Функция выбора выбирает родительские элементы для следующего поколения на основе их масштабированных значений от функции масштабирования фитнеса. Масштабированные значения фитнеса называются значениями ожидания. Человек может быть выбран несколько раз как родительский элемент, в этом случае он вносит свои гены больше чем в один дочерний элемент. Опция выбора по умолчанию, Stochastic uniform, размечает строку, в которой каждый родительский элемент соответствует разделу строки длины, пропорциональной ее масштабированному значению. Алгоритм проходит строка на шагах равного размера. На каждом шаге алгоритм выделяет родительский элемент от раздела, на который это приземляется.

Более детерминированной опцией выбора является Remainder, который выполняет два шага:

В первом шаге функция выбирает родительские элементы детерминировано согласно целой части масштабированного значения для каждого человека. Например, если масштабированное значение человека 2.3, функция выбирает того человека дважды как родительский элемент.
На втором шаге функция выбора выбирает дополнительные родительские элементы с помощью дробных частей масштабированных значений, как в стохастическом универсальном выборе. Функция размечает строку в разделах, длины которых пропорциональны дробной части масштабированного значения людей, и проходит строка на равных шагах, чтобы выбрать родительские элементы.
Обратите внимание на то, что, если дробные части масштабированных значений весь равный 0, как это может произойти с помощью масштабирования Top, выбора, совершенно детерминированы.

Для получения дополнительной информации и больше опций выбора, см. Опции Выбора.

Опции воспроизведения

Опции воспроизведения управляют, как генетический алгоритм создает следующее поколение. Опции

Elite count — Количество людей с лучшими значениями фитнеса в текущей генерации, которые, как гарантируют, выживут к следующему поколению. Эти люди называются элитными дочерними элементами. Значением по умолчанию Elite count является 2.
Когда Elite count - по крайней мере 1, лучшее значение фитнеса может только уменьшиться от одной генерации до следующего. Это - то, что вы хотите произойти, поскольку генетический алгоритм минимизирует функцию фитнеса. Установка Elite count к высокому значению заставляет самых подходящих людей доминировать над генеральной совокупностью, которая может сделать поиск менее эффективным.
Crossover fraction — Часть людей в следующем поколении, кроме элитных дочерних элементов, которые создаются перекрестным соединением. Установка Перекрестной Части описывает, как значение Crossover fraction влияет на производительность генетического алгоритма.

Мутация и перекрестное соединение

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

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

Оба процесса важны для генетического алгоритма. Перекрестное соединение позволяет алгоритму извлечь лучшие гены от различных людей и повторно объединить их в потенциально превосходящие дочерние элементы. Мутация добавляет к разнообразию генеральной совокупности и таким образом увеличивает вероятность, что алгоритм сгенерирует людей с лучшими значениями фитнеса.

Смотрите Создание Следующего поколения для примера того, как генетический алгоритм применяет мутацию и перекрестное соединение.

Можно задать, сколько из каждого типа дочерних элементов алгоритм создает можно следующим образом:

Elite count, в опциях Reproduction, задает количество элитных дочерних элементов.
Crossover fraction, в опциях Reproduction, задает часть генеральной совокупности кроме элитных дочерних элементов, которые являются перекрестными дочерними элементами.

Например, если Population size является 20, Elite count является 2, и Crossover fraction является 0.8, количества каждого типа дочерних элементов в следующем поколении следующие:

Существует два элитных дочерних элемента.
Существует 18 человек кроме элитных дочерних элементов, таким образом, алгоритм округляется 0.8*18 = 14.4 к 14, чтобы получить количество перекрестных дочерних элементов.
Остающиеся четыре человека, кроме элитных дочерних элементов, являются дочерними элементами мутации.

Документация