Генетические алгоритмы
Генетический алгоритм (Genetic Algorithm — GA) представляет собой вариант стохастического лучевого поиска, в котором состояния-преемники формируются путем комбинирования двух родительских состояний, а не посредством модификации единственного состояния. В нем просматривается такая же аналогия с естественным отбором, как и в стохастическом лучевом поиске, за исключением того, что теперь мы имеем дело с половым, а не бесполым воспроизводством.
Как и при лучевом поиске, работа алгоритмов GA начинается с множества Тс сформированных случайным образом состояний, называемых популяцией. Каждое состояние, или индивидуум, представлено в виде строки символов из конечного алфавита, чаще всего в виде строки из нулей (0) и единиц (1). Например, состояние задачи с восемью ферзями должно определять позиции восьми ферзей, каждый из которых стоит на вертикали с 8 клетками, и поэтому для его представления требуется 8х1од28=24 бита. Иным образом, каждое состояние может быть представлено в виде восьми цифр, каждая из которых находится в диапазоне от 1 до 8. (Как будет показано ниже, эти две кодировки проявляют себя в ходе поиска по-разному.) На рис. 4.10, а показана популяция из четырех восьмисимвольных строк, представляющих состояния с восемью ферзями.
Процесс выработки следующего поколения состояний показан на рис. 4.10, б— д. На рис. 4.10, б каждое состояние классифицируется с помощью функции оценки, или (в терминологии GA) функции пригодности. Функция пригодности должна возвращать более высокие значения для лучших состояний, поэтому в задаче с восемью ферзями используется количество неатакующих друг друга пар ферзей, которое в любом решении имеет значение 28. Для этих четырех состояний соответствующие значения равны 24, 23, 20 и 11. В данном конкретном варианте генетического алгоритма вероятность выбора для воспроизводства прямо пропорциональна оценке пригодности; соответствующие вероятности в процентах показаны рядом с исходными оценками.
Как показано на рис. 4.10, для воспроизводства случайным образом выбираются две пары в соответствии с вероятностями, показанными на рис. 4.10, б. Обратите внимание на то, что один индивидуум выбирается дважды, а один вообще остается не выбранным11. Для каждой пары, предназначенной для воспроизводства, среди позиций в строке случайным образом выбирается точка скрещивания. На рис. 4.10 точки скрещивания находятся после третьей цифры в первой паре и после пятой цифры во второй паре.
Как показано на рис. 4.10, г, сами потомки создаются путем перекрестного обмена подстроками родительских строк, разорванных в точке скрещивания. Например, первый потомок первой пары получает три первые цифры от первого родителя, а остальные цифры — от второго родителя, тогда как второй потомок получает первые три цифры от второго родителя, а остальные — от первого родителя. Состояния задачи с восемью ферзями, участвующие в этом этапе воспроизводства, показаны на рис. 4.11. Данный пример иллюстрирует тот факт, что если два родительских состояния являются весьма различными, то операция скрещивания способна выработать состояние, которое намного отличается и от одного, и от другого родительского состояния. Часто происходит так, что популяция становится весьма разнообразной на самых ранних этапах этого процесса, поэтому скрещивание (как и эмуляция отжига) в основном обеспечивает выполнение крупных этапов в пространстве состояний в начале процесса поиска и более мелких этапов позднее, когда большинство индивидуумов становятся весьма похожими друг на друга.
Наконец, на рис. 4.10, д показано, что каждое местонахождение подвергается случайной мутации с небольшой независимой вероятностью. В нервом, третьем и четвертом потомках мутация свелась к изменению одной цифры. В задаче с восемью ферзями эта операция соответствует выбору случайным образом одного ферзя и перемещению этого ферзя на случайно выбранную клетку в его столбце. В листинге 4.4 приведен алгоритм, который реализует все эти этапы.
Листинг 4.4. Генетический алгоритм. Этот алгоритм аналогичен тому, который показан схематически на рис. 4.10, за одним исключением: в этой более широко применяемой версии алгоритма каждое скрещивание двух родителей приводит к получению только одного потомка, а не двух
function Genetic-Algorithm{population, Fitness-Fn) returns индивидуум
individual inputs: population, множество индивидуумов (популяция)
Fi tness-Fn, функция, которая измеряет пригодность индивидуума
Repeat new_jDopulation <— пустое множество
loop for i from 1 to Size{population) do x
function Reproduce(х, у) returns индивидуум individual inputs: х, у, индивидуумы-родители
п <— Length(х) с <— случайное число от 1 до л
return Append(Substring(х, 1, с), Substring(y, с+1# л))