Пример 9.2

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

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

сh₁ = [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₇ характеризуются наибольшими значениями функции принадлежности. В этой популяции они считаются наилучшими кандидатами на решение задачи. Если в соответствии с блок-схемой генетического алгоритма (рис.9.1) условие остановки алгоритма не выполняется, то на следующем шаге производится селекция хромосом из текущей популяции.

Селекция хромосом.Селекция производится методом рулетки. На основании формул (9.2) и (9.3) для каждой из 8 хромосом текущей популяции (в нашем случае – исходной популяции, для N = 8) получаем секторы колеса рулетки, выраженные в процентах (рис.9.2).

v(ch₁) = 15,22 v(ch₅) = 8,70

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

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

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

Рис. 9.2. Колесо рулетки для селекции в примере 6.4.

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

79 44 9 74 44 86 48 23

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

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

Как видно, хромосома 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₃ с ch₃ и ch₄ с ch₇ вместо ch₃ с ch₄ и ch₃ с ch₇, а другие пары остались без изменения, то скрещивание ch₃ с ch₃ дало бы две такие же хромосомы независимо от разыгранной точки скрещивания. Это означало бы получение двух потомков, идентичных своим родителям. Заметим, что такая ситуация наиболее вероятна для хромосом с наибольшим значением функции приспособленности, т.е. именно такие хромосомы получают наибольшие шансы на переход в новую популяцию.

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

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

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

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

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

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

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

Значения функций приспособленности хромосом этой попу­ляции составляют

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

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

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

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

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