59.2. Генетические алгоритмы
Генетический алгоритм (ГА) реализует метод эвристической оптимизации, построенный на случайном поиске. В данном контексте множество возможных решений проблемы оптимизации называется популяцией особей. Степень адаптации особи к среде определяет функция приспособленности.
Координаты особи в пространстве поиска представляются хромосомами, которые по сути являются символьными строками. Фрагмент хромосомы, кодирующий значение одного оптимизируемого параметра, называется геном. Обычно ген кодируется в виде двоичного или целочисленного значения.
В результате симуляции эволюционных операций (скрещивания, мутации и селекции) данный алгоритм формирует новые поколения особей, у которых приспособленность в среднем будет выше, чем у их предшественников.
Как сказано в ответах на вопросы в группе comp.ai.genetic, нельзя не отметить, что ГА реализует не чисто случайный поиск решения проблемы. В ГА происходят вероятностные процессы, но результат явно оказывается не случайным (лучше случайного).
Рисунок 59.1. Диаграмма структуры генетического алгоритма
P(t) | поколение предков на момент t |
P''(t) | поколение потомков на момент t |
+=========================================+ |>>>>>>>>>>> Алгоритм ГА <<<<<<<<<<<<<<| +=========================================+ | ИНИЦИАЛИЗАЦИЯ 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 | +===+=====================================+