4.5. Иллюстрация выполнения классического генетического алгоритма

Рассмотрим выполнение описанного в предыдущем разделе классического генетического алгоритма на как можно более простом примере [19]. Проследим последовательность выполнения его этапов, соответствующих блок-схеме на рис. 4.3.

Пример 4.4

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

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

                       

                     

                     

                     

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

   

   

   

   

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

Селекция хромосом. Селекция производится методом рулетки. На основании формул (4.2) и (4.3) для каждой из 8 хромосом текущей популяции (в нашем случае - исходной популяции, для которой ) получаем секторы колеса рулетки, выраженные в процентах (рис. 4.5)

         

         

         

          

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

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

79        44        9          74        44        86        48        23

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

                                   

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

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

 и                    и                    и                    и

Для первой пары случайным образом выбрана точка скрещивания , для второй , для третьей , для четвертой . При этом процесс скрещивания протекает так, как показано на рис. 4.6. В результате выполнения оператора скрещивания получаются 4 пары потомков.

Рис. 4.6. Процесс скрещивания хромосом в примере 4.4.

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

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

                     

                     

                     

                     

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

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

              

              

              

              

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