Анализ работы генетического алгоритма

Эволюционные алгоритмы — семейство алгоритмов, реализующих принципы естественного отбора. Данные алгоритмы часто применяются для решения оптимизационных задач или для решения NP-полных задач (задача коммивояжера). Генетический алгоритм — один из примеров эволюционных алгоритмов. Данный подход внедряет несколько новых определений:

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

Популяция — набор генотипов.

Фитнес-функция — функция от генотипа, вычисляющая выживаемость (приспособляемость) данного генотипа.

Схема работы генетического алгоритма состоит из нескольких простых этапов:

Генерация начальной популяции.

Вычисление значения фитнес функции для каждого генотипа в популяции.

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

Генерация новых генотипов для популяции:

Случайная генерация генотипа.

Скрещивание нескольких выживших генотипов.

Мутация выжившего или нового генотипа.

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

Результатом работы алгоритма является наиболее приспособленный генотип (на основе фитнес-функции) из текущей популяции.

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

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

Селекция выживших особей также может быть выполнена различными способами. Наиболее простым способом является упорядочивание всех особей согласно значению фитнес-функции, после чего в живых остается только заданное количество особей. Кроме данного метода существует также метод турнирной селекции. От наивной реализации отличается тем, что сначала из популяции случайным образом выбирается несколько особей (как правило — две), после чего из выбранных особей выбирается наиболее приспособленная. Это также позволяет разнообразить генетический фонд популяции.