Пример работы классического генетического алгоритма

Рассмотрим выполнение классического генетического алгоритма на простом примере: требуется найти хромосомы с максимальным количеством единиц. Допустим, что хромосомы состоят из 12 генов, а популяция насчитывает 8 хромосом. Понятно, что наилучшей будет хромосома, состоящая из 12 единиц. Рассмотрим, как протекает процесс решения этой тривиальной задачи с помощью генетического алгоритма.

Инициализация, или выбор исходной популяции хромосом. Необходимо случайным образом сгенерировать 8 двоичных последовательностей длиной 12 битов. Это можно достигнуть, например, подбрасыванием монеты 96 раз (при выпадении «орла» ставится 1, а в случае «решки» – 0). Таким образом, можно сформировать исходную популяцию:

ch₁ = [111001100101] ch₅ = [010001100100]

ch₂ = [001100111010] ch₆ = [010011000101]

ch₃ = [011101110011] ch₇ = [101011011011]

ch₄ = [001000101000] ch₈ = [000010111100]

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

F (ch₁) = 7 F (ch₅) = 4

F (ch₂) = 6 F (ch₆) = 5

F (ch₃) = 8 F (ch₇) = 8

F (ch₄) = 3 F (ch₈) = 5

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

Селекция хромосом. Селекция производится методом рулетки. Для каждой из 8 хромосом текущей популяции получаем секторы колеса рулетки, выраженные в процентах (см. рис. 7.2):

v(ch₁) = 15,22% (ch₅) = 8,7%

v(ch₂) = 13,04% (ch₆) = 10,87%

v(ch₃) = 17,39% (ch₇) = 17,39%

v(ch₄) = 6,52% ch₈) = 10,87%

Розыгрыш с помощью колеса рулетки сводится к случайному выбору числа из интервала [0, 100], указывающего на соответствующий сектор на колесе, т.е. на конкретную хромосому. Пусть разыграны следующие 8 чисел:

79 44 9 74 44 86 48 23

Это означает выбор хромосом

ch₇ ch₃ ch₁ ch₇ ch₃ ch₇ ch₄ ch₂

- Рис. 7.2. Колесо рулетки для селекции хромосом

Как видно, хромосома ch₇ была выбрана трижды, а хромосома ch₃ –дважды. Заметим, что именно эти хромосомы имеют наибольшее значение функции приспособленности. Однако выбрана и хромосома ch₄ с наименьшим значением функции приспособленности. Все выбранные таким образом хромосомы включаются в так называемый родительский пул.

Применение генетических операторов. Допустим, что ни одна из отобранных в процессе селекции хромосом не подвергается мутации, и все они составляют популяцию хромосом, предназначенных для скрещивания. Т.е. вероятность скрещивания р_с= 1, а вероятность мутации р_m =0. Допустим, что из этих хромосом случайным образом сформированы пары родителей

ch₂ и ch₇ ch₁ и ch₇ ch₃ и ch₄ ch₃ и ch₇

Для первой пары случайным образом выбрана точка скрещивания l _k = 4, для второй l _k = 3, для третьей l _k = 11, для четвертой l _k = 5. При этом процесс скрещивания хромосом протекает следующим образом.

В результате выполнения скрещивания получаются 4 пары потомков.

Формирование новой популяции. После выполнения операции скрещивания получаем следующую популяцию потомков:

Ch₁ = [001111011011] Ch₅ = [011101110010]

Ch₂ = [101000111010] Ch₆ = [001000101001]

Ch₃ = [111011011011] Ch₇ = [011101011011]

Ch₄ = [101001100101] Ch₈ = [101011110011]

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

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

F(Ch₁)= 8 F(Ch₅) = 7

F(Ch₂) = 6 F(Ch₆) = 4

F(Ch₃) = 9 F(Ch₇) = 8

F(Ch₄) = 6 F(Ch₈) = 8

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