Классический генетический алгоритм

Основной (классический) генетический алгоритм со­стоит из следующих шагов:

1) инициализация, или выбор исходной популяции хромосом;

2) оценка приспособленности хромосом в популяции;

3) проверка условия остановки алгоритма;

4) селекция хромосом;

5) применение генетических операторов;

6) формирование новой популяции;

7) выбор «наилучшей» хромосомы.

Блок-схема основного генетического алгоритма изображена на рис.1. Рассмотрим конкретные этапы этого алгоритма более по­дробно.

Инициализация, т.е. формирование исходной популяции, за­ключается в случайном выборе заданного количества хромосом (осо­бей), представляемых двоичными последовательностями фиксиро­ванной длины.

Оценивание приспособленности хромосом в популяции сос­тоит в расчете функции приспособленности для каждой хромосомы этой популяции. Чем больше значение этой функции, тем выше «ка­чество» хромосомы. Форма функции приспособленности зависит от характера решаемой задачи.

 

Рис.1. Блок-схема генетического алгоритма

 

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

Селекция хромосом заключается в выборе (по рассчитанным на втором этапе значениям функции приспособленности) тех хромо­сом, которые будут участвовать в создании потомков для следующей популяции, т.е. для очередного поколения. Такой выбор производится согласно принципу естественного отбора, по которому наибольшие шансы на участие в создании новых особей имеют хромосомы с наи­большими значениями функции приспособленности. Существуют раз­личные методы селекции. Наиболее популярным считается так назы­ваемый метод рулетки (roulette wheel selection), который свое назва­ние получил по аналогии с известной азартной игрой. Каждой хромо­соме может быть сопоставлен сектор колеса рулетки, величина кото­рого устанавливается пропорциональной значению функции приспо­собленности данной хромосомы. Поэтому, чем больше значение функции приспособленности, тем больше сектор на колесе рулетки. Все колесо рулетки соответствует сумме значений функции приспособленности всех хромосом рассматриваемой популяции, каждой хромосоме, обозначаемой ch _i для i =1,2,.... N (где N обозначает чис­ленность популяции) соответствует сектор колеса v (ch _i), выраженный в процентах согласно формуле

(2)

где

(3)

причем F (ch _i) - значение функции приспособленности хромосомы ch _i, a p_s (ch _i) - вероятность селекции хромосомы ch _i. Селекция хромосо­мы может быть представлена как результат поворота колеса рулетки, поскольку «выигравшая» (т.е. выбранная) хромосома относится к вы­павшему сектору этого колеса. Очевидно, что чем больше сектор, тем больше вероятность «победы» соответствующей хромосомы. Поэто­му вероятность выбора данной хромосомы оказывается пропорцио­нальной значению ее функции приспособленности. Если всю окруж­ность колеса рулетки представить в виде цифрового интервала [0, 100], то выбор хромосомы можно отождествить с выбором числа из интервала [a, b], где a и bобозначают соответственно начало и окон­чание фрагмента окружности, соответствующего этому сектору коле­са; очевидно, что 0 ≤ а < b ≤ 100. В этом случае выбор с помощью ко­леса рулетки сводится к выбору числа из интервала [0, 100], которое соответствует конкретной точке на окружности колеса.

В результате процесса селекции создается родительская попу­ляция, также называемая родительским пулом (mating pool) с чис­ленностью N, равной численности текущей популяции.

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

В классическом генетическом алгоритме применяются два ос­новных генетических оператора: оператор скрещивания (crossover) и оператор мутации (mutation). Однако следует отметить, что опера­тор мутации играет явно второстепенную роль по сравнению с опера­тором скрещивания. Это означает, что скрещивание в классическом генетическом алгоритме производится практически всегда, тогда как мутация - достаточно редко. Вероятность скрещивания, как правило, достаточно велика (обычно 0,5 ≤ р_с ≤ 1), тогда как вероятность мута­ции устанавливается весьма малой (чаще всего 0 ≤ p_m ≤ 0,1). Это сле­дует из аналогии с миром живых организмов, где мутации происходят чрезвычайно редко

В генетическом алгоритме мутация хромосом может выпол­няться на популяции родителей перед скрещиванием, либо на популя­ции потомков, образованных в результате скрещивания.

Оператор скрещивания. На первом этапе скрещивания выби­раются пары хромосом из родительской популяции (родительского пула). Это временная популяция, состоящая из хромосом, отобран­ных в результате селекции и предназначенных для дальнейших пре­образований операторами скрещивания и мутации с целью формиро­вания новой популяции потомков. На данном этапе хромосомы из ро­дительской популяции объединяются в пары. Это производится слу­чайным способом в соответствии с вероятностью скрещивания p_c. Да­лее для каждой пары отобранных таким образом родителей разыгры­вается позиция гена (локус) в хромосоме, определяющая так называ­емую точку скрещивания. Если хромосома каждого из родителей со­стоит из L генов, то очевидно, что точка скрещивания l_k представляет собой натуральное число, меньшее L. Поэтому фиксация точки скре­щивания сводится к случайному выбору числа из интервала [1, L -1] В результате скрещивания пары родительских хромосом получается следующая пара потомков:

1) потомок, хромосома которого на позициях от 1 до l_k состоит из генов первого родителя, а на позициях от l_k + 1 до L - из генов вто­рого родителя;

2) потомок, хромосома которого на позициях от 1 до l_k состоит из генов второго родителя, а на позициях от l_k + 1 до L - из генов пер­вого родителя.

Оператор мутации с вероятностью p_m изменяет значение гена в хромосоме на противоположное (т.е. с 0 на 1 или обратно). Напри­мер, если в хромосоме [100110101010] мутации подвергается ген на позиции 7, то его значение, равное 1, изменяется на 0, что приводит к образованию хромосомы [100110001010]. Как уже упоминалось вы­ше, вероятность мутации обычно очень мала, и именно от нее зави­сит, будет данный ген мутировать или нет. При выборе вероятности p_m мутации можно применять, например, случайные числа из ин­тервала [0, 1] для каждого гена и отбор для выполнения этой опе­рации тех генов, для которых разыгранное число оказывается мень­шим или равным значению p_m.

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

Выбор «наилучшей» хромосомы. Если условие остановки алгоритма выполнено, то следует вывести результат работы, т.е. представить искомое решение задачи. Лучшим решением считается хромосома с наибольшим значением функции приспособленности.

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

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

Операция скрещивания заключается в обмене фрагментами цепочек между двумя родительскими хромосомами. Пары родителей для скрещивания выбираются из родительского пула случайным об­разом так, чтобы вероятность выбора конкретной хромосомы для скрещивания была равна вероятности p_c. Например, если в качестве родителей случайным образом выбираются две хромосомы из роди­тельской популяции численностью N, то p_c = 2/ N. Аналогично, если из родительской популяции численностью N выбирается 2z хромосом (z ≤ N / 2), которые образуют z пар родителей, то p_c = 2z/ N. Обратим внимание, что если все хромосомы текущей популяции объединены в пары до скрещивания, то p_c = 1. После операции скрещивания роди­тели в родительской популяции замещаются их потомками.

Операция мутации изменяет значения генов в хромосомах с за­данной вероятностью p_m способом, представленным при описании соответствующего оператора. Это приводит к инвертированию значе­ний отобранных генов с 0 на 1 и обратно. Значение p_m, как правило, очень мало, поэтому мутации подвергается лишь небольшое количе­ство генов. Скрещивание - это ключевой оператор генетических алго­ритмов, определяющий их возможности и эффективность. Мутация играет более ограниченную роль. Она вводит в популяцию некоторое разнообразие и предупреждает потери, которые могли бы произойти вследствие исключения какого-нибудь значимого гена в результате скрещивания.

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

Задание

В ходе выполнения лабораторной работы необходимо познакомиться с теорией генетических алгоритмов, а также реализовать описанный ниже алгоритм на одном из языков программирования.

Описание алгоритма.

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

Инициализация, или выбор исходной популяции хромо­сом. Необходимо случайным образом сгенерировать 8 двоичных по­следовательностей длиной 12 битов. Таким образом можно сформировать исходную популяцию:

ch1 = [111001100101]	ch5 = [010001100100]
ch2 = [001100111010]	ch6 = [010011000101]
ch3 = [011101110011]	ch7 = [101011011011]
ch4 = [001000101000]	ch8 = [000010111100]

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

F(ch1) = 7	F(ch5) = 4
F(ch2) = 6	F(ch6) = 5
F(ch3) = 8	F(ch7) = 8
F(ch4) = 3	F(ch8) = 5

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

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

Рис.2. Колесо рулетки для селекции

v(ch1) = 15,22	v(ch5) = 8,70
v(ch2) = 13,04	v(ch6) = 10,87
v(ch3) = 17,39	v(ch7) = 17,39
v(ch4) = 6,52	v(ch8) = 10,87

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

Допустим, что разыграны следующие 8 чисел:

79 44 9 74 44 86 48 23

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

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

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

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

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

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

Первая пара родителей		Первая пара потомков
[001100111010] [101011011011] lk = 4	скрещивание →	[001111011011] [101000111010]
Вторая пара родителей		Вторая пара потомков
[111001100101] [101011011011] lk = 3	скрещивание →	[111011011011] [101001100101]
Третья пара родителей		Третья пара потомков
[011101110011] [001000101000] lk = 11	скрещивание →	[011101110010] [001000101001]
Четвертая пара родителей		Четвертая пара потомков
[011101110011] [101011011011] lk = 5	скрещивание →	[011101011011] [101011110011]

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

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

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

Ch1 = [001111011011]	Ch5 = [011101110010]
Ch2 = [101000111010]	Ch6 = [001000101001]
Ch3 = [111011011011]	Ch7 = [011101011011]
Ch4 = [101001100101]	Ch8 = [101011110011]

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

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

F(Ch1) = 8	F(Ch5) = 7
F(Ch2) = 6	F(Ch6) = 4
F(Ch3) = 9	F(Ch7) = 8
F(Ch4) = 6	F(Ch8) = 8

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