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

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

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

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

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

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

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

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. Будем рассматривать эти числа как номера членов популяции. Процесс размножения (рекомбинация) заключается в обмене участками хромосом между родителями.