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). В первом реализуется эволюция ЯН, а во втором ИНЬ. Лучшие или заданные хромосомы (решения) мигрируют из ГА ЯН в ИНЬ и наоборот. Кроме этого, после каждой генерации лучшее решение идет в третий ГА, где собирают все наилучшие хромосомы. Над ними также происходит процесс эволюции. Применение такой структуры оптимизационной задачи позволяет частично избегать предварительной сходимости алгоритма.