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

1. Конструируется начальная популяция. Вводится начальная точка отсчета поколений t = 0. Вычисляются приспособленность хромосом популяции (целевая функция) и средняя приспособленность всей популяции.
2. Устанавливается значениеВыбираются два роди­теля (хромосомы) для кроссинговера. Выбор осуществляется случайным образом пропорционально жизнеспособности хромосом, которая характеризуется значениями целевой функции.
3. Формируется генотип потомка. Для этого с заданной веро­ятностью над генотипами выбранных хромосом производится операция кроссинговера. Случайным образом выбирается один из потомковкоторый сохраняется как член новой популя­ции. Далее к потомкупоследовательно с заданными вероят­ностями применяются операторы инверсии и мутации. Получен­ный в результате генотип потомка сохраняется как
4. Обновление текущей популяции путем замены случайно выбранной хромосомы на
5. Определение приспособленностии пересчет средней приспособленности популяции.
6. Если— заданное число шагов, то переход к этапу 7, в противном случае — переход к этапу 2.
7. Конец работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Выбор начальной популяции можно выполнять произволь­ным образом, например подбрасыванием монеты.
2. Репродукция осуществляется на основе моделирования движения колеса рулетки.
3. Оператор кроссинговера реализуется как взаимный об­мен короткими фрагментами двоичных строк гомологичных хромосом.
4. Вероятность оператора кроссинговера принимается равной
5. Вероятность оператора мутации принимается равной