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

Основные принципы работы ГА заключены в следующем (см. также схему 1):

1. Генерируем начальную популяцию из n хромосом.

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

3. Выбираем пару хромосом-родителей с помощью одного из способов отбора.

4. Проводим кроссинговер двух родителей с вероятностью p_c, производя двух потомков.

5. Проводим мутацию потомков с вероятностью p_m.

6. Повторяем шаги 3-5, пока не будет сгенерировано новое поколение популяции, содержащее n хромосом.

7. Повторяем шаги 2-6, пока не будет достигнут критерий окончания процесса.

Схема 1. Простой генетический алгоритм

Критерием окончания процесса может служить заданное количество поколений или схождение (convergence) популяции.

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

Пример основных принципов работы генетических алгоритмов:

Пусть требуется найти глобальный минимум функции

на отрезке [0; 7] (рис. 1).

На этом отрезке функция принимает минимальное значение в точке = 1. Очевидно, что в точке = 6 функция попадает в локальный минимум. Если для нахождения глобального минимума использовать градиентные методы, то в зависимости от начального приближения можно попасть в данный локальный минимум.

Для простоты положим, что x принимает только целые значения, т.е. {0,1,2,3,4,5,6,7}. Это предположение существенно упростит изложение, сохранив все основные особенности работы генетического алгоритма.

Выберем случайным образом несколько чисел на отрезке [0;7]: {2,3,5,4}. Будем рассматривать эти числа в качестве пробных решений нашей задачи.

Рис. 1. График целевой функции с выбранными значениями пробных решений

Основной идеей генетических алгоритмов является организация «борьбы за существование» и «естественного отбора» среди этих пробных решений. Запишем пробные решения в двоичной форме: {010,011,101,100}. Поскольку генетические алгоритмы используют биологические аналогии, то и применяющаяся терминология напоминает биологическую. Так, одно пробное решение, записанное в двоичной форме, обычно называют особью или хромосомой, а набор всех пробных решений - популяцией. Как известно, принцип естественного отбора заключается в том, что в конкурентной борьбе выживает наиболее приспособленный. В нашем случае приспособленность особи определяется целевой функцией: чем меньше значение целевой функции, тем более приспособленной является особь, т.е. пробное решение, использовавшееся в качестве аргумента целевой функции (см. табл. 1).

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

Например: пусть скрещиваются две хромосомы 111111 и 000000. Определяем случайным образом точку разрыва хромосомы, пусть, это будет 3: 111|111 000|000. Теперь хромосомы обмениваются частями, стоящими после точки разрыва, и образуют двух новых потомков: 111000 и 000111.

Таблица 1

Исходная популяция

Для нашей популяции процесс создания первого поколения потомков показан в таблице 2.

Таблица 2

Одноточечный кроссинговер

Следующим шагом в работе генетического алгоритма являются мутации, т.е. случайные изменения полученных в результате скрещивания хромосом. Пусть вероятность мутации равна 0,3. Для каждого потомка возьмем случайное число на отрезке [0;1], и если это число меньше 0,3, то инвертируем случайно выбранный ген (заменим 0 на 1 или наоборот) (см. табл. 3).

Таблица 3

Мутация потомков

Как видно на примере, мутации способны улучшить (первый потомок) или ухудшить (четвертый потомок) приспособленность особи-потомка. В результате скрещивания хромосомы обмениваются «хвостами», т.е. младшими разрядами в двоичном представлении числа. В результате мутаций изменению может подвергнуться любой разряд, в том числе, старший. Таким образом, если скрещивание приводит к относительно небольшим изменениям пробных решений, то мутации могут привести к существенным изменениям значений пробных решений (см. рис. 2).

Рис. 2. Изменение популяции в процессе естественного отбора

Теперь из четырех особей-родителей и четырех полученных особей потомков необходимо сформировать новую популяцию. В новую популяцию отберем четыре наиболее приспособленных особей из числа «старых» особей и особей-потомков (см. табл. 4).

Таблица 4

Формирование новой популяции из особей-родителей и особей-потомков

В результате получим новое поколение, которое представлено на рис. 3.

Получившуюся популяцию можно будет вновь подвергнуть кроссинговеру, мутации и отбору особей в новое поколение. Таким образом, через несколько поколений мы получим популяцию из похожих и наиболее приспособленных особей. Значение приспособленности наиболее «хорошей» особи (или средняя приспособленность по популяции) и будет являться решением нашей задачи. Следуя этому, в данном случае, взяв наиболее приспособленную особь 001 во втором поколении, можно сказать, что минимумом целевой функции является значение -5,42, соответствующее аргументу = 1. Тем самым попадания в локальный минимум удалось избежать.

Рис. 3. Особи новой популяции

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