Генетический алгоритм (Genetic Algorithm — GA) представляет собой вариант стохастического лучевого поиска, в котором состояния-преемники формируются путем комбинирования двух родительских состояний, а не посредством модификации единственного состояния. В нем просматривается такая же аналогия с естественным отбором, как и в стохастическом лучевом поиске, за исключением того, что теперь мы имеем дело с половым, а не бесполым воспроизводством.

Как и при лучевом поиске, работа алгоритмов GA начинается с множества k сформированных случайным образом состояний, называемых популяцией. Каждое состояние, или индивидуум, представлено в виде строки символов из конечного алфавита, чаще всего в виде строки из нулей (0) и единиц (1). Например, состояние задачи с восемью ферзями должно определять позиции восьми ферзей, каждый из которых стоит на вертикали с 8 клетками, и поэтому для его представления требуется бита. Иным образом, каждое состояние может быть представлено в виде восьми цифр, каждая из которых находится в диапазоне от 1 до 8. (Как будет показано ниже, эти две кодировки проявляют себя в ходе поиска по-разному.) На рис. 4.10, а показана популяция из четырех восьмисимвольных строк, представляющих состояния с восемью ферзями.

Процесс выработки следующего поколения состояний показан на рис. 4.10, б— д. На рис. 4.10, б каждое состояние классифицируется с помощью функции оценки, или (в терминологии GA) функции пригодности. Функция пригодности должна возвращать более высокие значения для лучших состояний, поэтому в задаче с восемью ферзями используется количество неатакующих друг друга пар ферзей, которое в любом решении имеет значение 28. Для этих четырех состояний соответствующие значения равны 24, 23, 20 и 11. В данном конкретном варианте генетического алгоритма вероятность выбора для воспроизводства прямо пропорциональна оценке пригодности; соответствующие вероятности в процентах показаны рядом с исходными оценками.

Рис. 4.10. Генетический алгоритм: начальная популяция (а); функция пригодности (б); отбор (в); скрещивание (г); мутация (д). Начальная популяция классифицируется с помощью функции пригодности, в результате чего формируются пары для скрещивания. Эти пары производят потомков, которые в конечном итоге подвергаются мутации