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

Рассмотрим в качестве примера простой генетический алгоритм, устроенный следующим образом [Гладков и др., 2006]. Допустимое решение задачи, кортеж параметров, кодируется двоичной строкой фиксированной длины, называемой хромосомой. Решения могут быть оценены при помощи функции приспособленности (целевой функции). Оптимальное решение должно обеспечивать получение наибольшего (наименьшего) значения целевой функции.

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

Мутация — изменяется случайный двоичный символ или группа символов (ген) в некоторой хромосоме.

Кроссинговер — выбирается случайное натуральное число k меньшее длины хромосомы, после чего в двух хромосомах фрагменты, содержащие первые k символов, заменяются один на другой.

Репродукция — хромосома копируется без изменений.

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

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

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

Мутация представляет собой случайный поиск, позволяющий добавлять в популяцию новые элементы множества допустимых решений, обеспечивая таким образом исследование новых областей. Кроссинговер предполагает «обмен информацией» между потенциальными решениями на промежуточных этапах. Соединение в новом решении фрагментов наилучших хромосом, полученных ранее, должно обеспечивать направленный поиск за счет конструирования хромосом с высокой приспособленностью. Репродукция позволяет избежать потери лучших решений. Селекция обеспечивает постепенное (эволюционное) улучшение популяции за счет преимущественного сохранения наиболее приспособленных хромосом.