3.2. Простой генетический алгоритм
Эволюционный процесс реализуется за счет способности «лучших» хромосом оказывать большее влияние на состав новой популяции посредством длительного выживания и более многочисленного потомства. Основные этапы процесса эволюции, на основе которого создаются нужные схемы генетического поиска, согласно Д. Холланду следующие:
1. Конструирование начальной популяции. Ввести точку отчета поколений t — 0. Вычислить приспособленность хромосом популяции, а затем среднюю приспособленность популяции.
2. Установление t = t + 1. Выбрать двух родителей (хромосом) для крое-
синговера. Он выполняется случайным образом пропорционально приспособляемости родителей.
3. Формирование генотипа потомка. С заданной вероятностью произвести над генотипами выбранных хромосом кроссинговер. Выбрать с вероятностью 0,5 один из потомков p{t) и сохранить его как члена новой популяции. Последовательно применить к p(t) оператор инверсии, а затем мутации с заданными вероятностями. Полученный генотип потомка сохранить как p'{t).
4. Отбор хромосомы случайным образом для исключения ее из популяции. Обновление текущей популяции заменой отобранной хромосомы на pl(t).
5. Определение приспособленности (целевой функции) pl(t) и пересчет средней приспособленности популяции.
6. Если t = Заданному, то переход к 7, если нет, то переход к 2.
7. Конец работы.
Мы привели так называемый репродуктивный план Д. Холланда в несколько упрощенном виде. Заметим, что в технических задачах оптимизации часто вместо понятия «приспособленность» используют понятие «целевая функция». Биологи называют эту функцию — fitness function. Простой генетический алгоритм (ПГА) был впервые описан Д. Гольдбергом на основе работ Д. Холланда [88, 89]. Его механизм несложен. Он копирует последовательности и переставляет их части. Предварительно ПГА случайно генерирует популяцию последовательностей — хромосом (альтернативных упорядоченных и неупорядоченных решений). Затем он применяет множество простых операций к начальной популяции и генерирует новые популяции.
ПГА состоит из трех операторов:
• репродукции;
• кроссинговера (ОК);
• мутации (ОМ).
Репродукция — процесс, в котором хромосомы копируются пропорционально их ЦФ. Копирование хромосом с «лучшим» значением ЦФ имеет большую вероятность для попадания в следующую генерацию. Рассматривая эволюцию Ч. Дарвина, можно отметить, что оператор репродукции, конечно, является искусственной версией натуральной селекции «выживания сильнейших». Оператор репродукции представляется в алгоритмической форме различными способами. Самый простой — создать колесо рулетки, в котором каждая хромосома имеет поле, пропорциональное его ЦФ. Рассмотрим пример Д. Гольдберга [89]: необходимо найти значение максимума функции f(x) = х2 на целочисленном интервале [0,31]. Традиционными методами мы будем изменять значения переменной ж, пока не получим max/(ж).
Для объяснения и реализации ПГА построим следующую таблицу (табл. 3.1).
Хромосомы столбца 2 в табл. 3.1 сгенерированы случайным образом. Значение ЦФ для каждой хромосомы определим как квадрат значения десятичного кода двоичного числа, которое приведено для хромосом в вто-
ром столбце таблицы. Тогда суммарное значение ЦФ = 890. Для селекции хромосом используется оператор репродукции на основе колеса рулетки. На рис. 3.2 поля колеса рулетки соответствуют значениям ЦФ в процентах. В одной генерации колесо рулетки вращается, и после останова ее указатель определяет хромосому, выбранную для следующего оператора. Очевидно, не всегда хромосома с большой ЦФ в результате оператора репродукции будет выбрана для следующего оператора. Будем считать для упрощения, что 16,2 = 16; 49,5 = 50;
5,5 = 5; 28,8 = 29.
Оператор репродукции выбирает хромосомы для применения ОК. После выполнения оператора репродукции оператор кроссинговера может выполниться в 3 шага одним из ОК, описанных выше. Точка разрыва к выбирается случайно между 1 и длиной хромосомы минус единица, т. е. в интервале (1, L — 1). Длина хромосомы L — это число значащих цифр в ее коде. Длина всех хромосом в табл. 3.1 равна пяти (L = 5). Две новых хромосомы создаются путем обмена частей хромосом между позициями (к + 1) и L соответственно. Например, рассмотрим хромосомы 1 и 2 из начальной популяции (табл. 3.1). Пусть к = 1. Тогда получим:
Данные реализации ПГА для нахождения значения максимума функции f(x) = х2 на целочисленном интервале [0,31] приведены в табл. 3.2.
Работа ГА начинается с репродукции. Мы выбираем хромосомы для следующей генерации, вращая колесо рулетки 4 раза, что соответствует мощности начальной популяции.
Величину отношения fi(x)/sum fi(x) называют вероятностью выбора копий (хромосом) при операторе репродукции и обозначают [88, 89]:
где fi(x) — значение ЦФ і-й хромосомы в популяции, sum fi(x) — суммарное значение ЦФ всех хромосом в популяции. Величину Р? (ОР) также называют нормализованной вероятностью выбора. Ожидаемое число копий г-й хромосомы после оператора репродукции определяют так:
где Np — число анализируемых хромосом.
Число копий хромосомы Рі, переходящее в следующее поколение, также иногда определяют на основе выражения (столбец 6 табл. 3.2):
где f(x) — среднее значение ЦФ по всей популяции.
Тогда для нашего примера ожидаемое число копий для первой хромосома из табл. 3.2 равно 0,16 • 4 = 0,64 копий, для второй — 0,29 • 4 = 1,16 копий, для третьей — 0,05 • 4 = 0,2 и, наконец, для четвертой — 0,5*4 = = 2. Смоделировать этот процесс можно, например, используя бросание монеты. В результате хромосомы р\ и р2 получают 1 копию, хромосома Р4 — 2 копии, и хромосома 3 не получает копий. Сравнивая этот результат с ожидаемым числом копий, получаем то, что ожидали: «лучшие» хромо™ сомы дают большее число копий, «средние» остаются и плохие «умирают» после оператора репродукции (табл. 3.3).
Применяя к популяции после оператора репродукции (столбец 2 табл. 3.3) оператор кроссинговера, получим новую популяцию хромосом (5 столбец табл. 3.3). В принципе можно применять ОК заданное число раз.
Например, если в столбце 5 табл. 3.3 выбрать хромосомы р2 и р^ и между ними провести ОК (точка ОК выбрана случайно и равна 3), то можно получить:
Решение р14 случайно дало искомый наилучший результат.
После проведения одной генерации ПГА улучшились все показатели: среднее и максимальное значение ЦФ. Далее, согласно схеме классического ПГА выполняется оператор мутации.
Заметим, что ОК и ОМ соответствуют перестановкам элементов внутри заданного множества. Очевидно, что при небольшой длине хромосомы L (порядка 10 “т" 20) можно выполнить полный перебор за приемлемое время и найти наилучшие решения. При увеличении L до 50 200 и выше, полный перебор произвести затруднительно, и необходимы другие механизмы поиска. Здесь как раз и приходит на помощь направленно-случайный поиск, который можно реализовать на основе ПГА.
Применим, например, ОМ к хромосоме р2 с ЦФ = 23 (столбец 5 табл. 3.3). Выберем позиции 2 и 3 и после ОМ получим: р2 : (11011), выполняя далее ОМ получим р2 : (11101). Как видно, хромосома р2 имеет ЦФ = 29. Снова применим ОМ к хромосоме р2. Тогда при случайном выборе позиций можно выбрать гены 4 и 5 и после ОМ получим: р' : (11101) ^ : (11110).
Хромосома р2 имеет ЦФ = 30. Итак, найдено квазиоптимальное значение ж, равное 30 для решения задачи нахождения максимального значения функции / (ж) = ж2 на интервале [0,31].
Как отмечалось выше, в ГА можно выделять два основных механизма воспроизводства хромосом:
• потомки являются точными копиями родителей (неполовое воспроизводство без мутации);
• потомки имеют большие отличия от родителей.
В эволюционном программировании и ГА в основном используют комбинации этих, механизмов, причем согласно [91], в эволюционном программировании и ЭМ в основном используют механизмы родительского воспроизводства с мутацией, а в ГА — механизм родительского воспроизводства с рекомбинацией и мутацией.
Отметим, что в прикладных задачах начальная популяция может выбираться любым образом, например, бросанием монеты (орел = 1, другая сторона монеты = 0). Репродукция выполняется через моделирование движения колеса рулетки. ОК в задачах вычислительного характера обычно выполняется через двоичное декодирование двух положений монеты. В комбинаторно-логических задачах применяют другие типы ОК и другие технологии его выполнения. Вероятность ОК допускается равной Р(ОК) = = 1,0 и меньше, вероятность ОМ допускается равной Р(ОМ) = 0,01 и больше. Как видно из табл. 3.2, лучшая хромосома в первой генерации (10101) получает 2 копии, потому что у нее высокая ЦФ.
Приведем вариант реализации алгоритма, описанный в [90]:
1. Инициализация популяции хромосом.
2. Оценка каждой хромосомы в популяции.
3. Создание новых хромосом посредством спаривания текущих хромосом; применение мутации и рекомбинации.
4. Устранение хромосом из популяции, чтобы освободить место для новых хромосом.
5. Оценка новых хромосом и вставка их в популяцию.
6. Если время исчерпано, то останов и возврат к наилучшей хромосоме; если нет, то переход к 3.
7. Конец работы алгоритма.
Сравнивая описание ПГА Д. Гольдберга, Д. Холланда и [90], видно, что в них реализована одна основная идея моделирования эволюции с некоторыми модификациями. Заметим, что эти изменения могут существенно влиять на окончательное качество решения.
Приведем пример одной из модифицированных базовых структур ПГА (см. [17]):
1. Создание начальной популяции решений для оптимизационной задачи.
2. Моделирование популяции (определение ЦФ для каждой хромосомы).
3. Пока оптимум заданного критерия не достигнут или в случае, когда не проведено необходимое число генераций:
а) выбор элементов для репродукции;
б) применение ОК для создания потомков (итерации);
в) применение ОМ (итерации);
г) применение оператора инверсии (итерации);
д) применение оператора транслокации (итерации);
е) применение оператора сегрегации (итерации);
ж) применение оператора удаления вершин (итерации);
з) применение оператора вставки вершин (итерации);
и) рекомбинация родителей и потомков для создания новой генерации.
4. Реализация новой генерации.
На рис. 3.3 приведен пример модифицированной структуры ПГА. Новые модификации моіут строиться путем объединения, например, пунктов а)-з) или их частичного устранения, или их перестановок, а также на основе применения адаптационных принципов управления генетическим поиском.
При разработке архитектуры ГА авторы предлагают использовать некоторые положения и принципы древних учений [51-56, 80]. Основной закон существования — это наличие противоположностей. Это всеобщий принцип ИНЬ-ЯН. Согласно аналогии Гермеса: «Что наверху, то и внизу». Поэтому в генетическом поиске будем использовать основные принципы микро- макро- и метаэволюции. Различают также два вида специальной эволюции:
• эволюция напряжения (ЯН);
• эволюция расслабления (ИНЬ).
Эволюция ЯН происходит скачкообразно, аналогично эволюции де Фриза. Для эволюции ИНЬ характерно плавное развитие, аналогично эволю
циям Ч. Дарвина, Ж. Ламарка и К. Поппера. Поэтому реализация ГА в общем случае может состоять из бесконечного числа генераций. В этой связи предлагается новая схема параллельного поиска из двух ГА (рис 3.4). В первом реализуется эволюция ЯН, а во втором ИНЬ. Лучшие или заданные хромосомы (решения) мигрируют из ГА ЯН в ИНЬ и наоборот. Кроме этого, после каждой генерации лучшее решение идет в третий ГА, где собирают все наилучшие хромосомы. Над ними также происходит процесс эволюции. Применение такой структуры оптимизационной задачи позволяет частично избегать предварительной сходимости алгоритма.