55.2. Генетические алгоритмы

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

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

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

Рисунок 55.1. Структура генетического алгоритма


Как сказано в ответах на вопросы в группе comp.ai.genetic, нельзя не отметить, что ГА реализует не чисто случайный поиск решения проблемы. В ГА происходят вероятностные процессы, но результат явно оказывается не случайным (лучше случайного).