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

Согласно репродуктивному плану Холланда генетиче­ские схемы поиска оптимальных решений включают следующие этапы процесса эволюции:

Таблица 1.

Анализ начальной популяции на первом шаге

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

1. Конструируется начальная популяция. Вводится начальная точка отсчета поколений t = 0. Вычисляются приспособленность хромосом популяции (целевая функция) и средняя приспособленность всей популяции.

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

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

4. Обновление текущей популяции путем замены случайно выбранной хромосомы на

5. Определение приспособленности и пересчет средней приспособленности популяции.

6. Если — заданное число шагов, то переход к этапу 7, в противном случае — переход к этапу 2.

7. Конец работы.

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

Простой генетический алгоритм [23, 26] включает операцию случайной генерации начальной популяции хромосом и ряд опе­раторов, обеспечивающих генерацию новых популяций на осно­ве начальной. Этими операторами являются репродукция, крос-синговер и мутация.

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

Рассмотрим пример применения простого генетического ал­горитма для максимизации функции на целочисленном интервале [0, 31]*.

Значения аргумента функции f{x)=x², изменяющегося в ин­тервале от 0 до 31, можно представить пятиразрядными двоичны­ми числами. Первоначальная популяция, состоящая из четырех строк пятиразрядных чисел, полученная с помощью процедуры генерации случайных чисел, приведена во втором столбце табл. 1. Значение целевой функции для каждой хромосомы опредляется путем возведения в квадрат значения двоичного числа, ко­дирующего решение х. Претенденты для скрещивания (кроссин-говера) могут выбираться из начальной популяции или после вы­полнения оператора репродукции.

Репродукция начального множества заключается в четырех­кратном вращении колеса рулетки (4 — мощность популяции), в результате чего состав исходной популяции может измениться (рис. 6.5). Вероятность выбора i-й хромосомы вычисляется по формуле Значение N для первой хромосомы будет равно 0.14x4—0.56 копий, для второй — 0.49 х 4 —1.96 копий, для третьей — 0.06 х 4 = = 0.24 и для четвертой — 0.31x4=1.24. В результате репродукции в новой популяции (второй столбец в табл. 6.2) будут присутство­вать по одной копии первой и четвертой хромосомы и две копии второй, а третья хромосома будет исключена. Таким способом опе­ратор репродукции отбирает лу/ших представителей популяции.

Таблица 6.2.

Результаты операций репродукции и кроссинговера в простом генетическом алгоритме

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

После репродукции выполняется оператор кроссинговера, который может повторяться несколько раз. При этом каждый раз будет осуществляться выбор двух кандидатур из множества хро­мосом. Затем каждая пара хромосом (стрингов) пересекается. Место пересечения К выбирается случайным образом на интервале (1, L-\), где L — длина хромосомы, определяемая количест­вом значащих цифр в ее двоичном коде. В нашем случае L = 5. Две новые хромосомы создаются путем взаимного обмена всех значений после точки пересечения, т.е. между позициями (К + 1) и L. При выборе двух первых хромосом из популяции (см. табл.1) и значения К = 4 до применения оператора кроссинговера имеем описание:

апосле применения оператора кроссинговера получаем описа­ние

Аналогично были получены потомки от третьей и четвертой хромосом.

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

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

Этап 1. В хромосоме случайным образом определяют две позиции, например, 2 и _-1.

Этап 2. Гены, соответствующие выбранным позициям, ме­няют местами и формируют новую хромосому

Если длина обрабатываемых последовательностей невелика, то в процессе мутации можно осуществить полный перебор воз­можных перестановок генов и найти комбинацию с максималь­ным значением целевой функции. При длине хромосомы _=50 — 200 полный перебор вариантов становится затруднитель­ным, поэтому здесь производится случайно-направленный по­иск, который может быть реализован на основе простого генетического алгоритма. Рассмотрим этот механизм на исследуемой задаче.

Выберем третью хромосому из пятого столбца табл. 2 со зна­чением целевой функции и применим операцию мута­ции к позициям 3 и 4:

У новой хромосомы значение целевой функции равно Сделаем еще одну перестановку 4 и 5 генов в хромо­соме 3':

Значение целевой функции для хромосомы равно 900, что соответствует квазиоптимальному решению задачи нахождения максимального значения функции на интервале [0,31].

В генетических алгоритмах и эволюционном программирова­нии используют два основных механизма воспроизводства хро­мосом:

• воспроизводство без мутаций, соответствующее митозу, результатом которого являются потомки — копии родителей;

• воспроизводство потомков, имеющих большие отличия отродителей. Этот механизм соответствует половому размножению.

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

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

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

2. Репродукция осуществляется на основе моделирования
движения колеса рулетки.

3. Оператор кроссинговера реализуется как взаимный об­
мен короткими фрагментами двоичных строк гомологичных
хромосом.

4. Вероятность оператора кроссинговера принимается равной

5. Вероятность оператора мутации принимается равной