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

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

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

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

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

+=========================================+
|>>>>>>>>>>>  Algorithm GA  <<<<<<<<<<<<<<|
+=========================================+
| ИНИЦИАЛИЗАЦИЯ t := 0                    |
+=========================================+
| ИНИЦИАЛИЗАЦИЯ P(t)                      |
+=========================================+
| вычислить ПРИСПОСОБЛЕННОСТЬ P(t)        |
+=========================================+
| пока не выполняется УСЛОВИЕ ОСТАНОВКИ   |
|   +-------------------------------------+
|   | P'(t)  := СКРЕЩИВАНИЕ{P(t)}         |
|   +-------------------------------------+
|   | P''(t) := МУТАЦИЯ{P'(t)}            |
|   +-------------------------------------+
|   | P(t+1) := СЕЛЕКЦИЯ{P''(t) + P(t)}   |
|   +-------------------------------------+
|   | вычислить ПРИСПОСОБЛЕННОСТЬ P''(t)  |
|   +-------------------------------------+
|   | t := t + 1                          |
+===+=====================================+