Лекция: Анализ начальной популяции на первом шаге простого генетического алгоритма.

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

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

Рi =fi(x))/sum f(x)

где fi(x) — значение целевой функции i-й хромосомы в популяции;

sum f(x) — суммарное значение целевой функции всех хромосом в попу­ ляции.

Ожидаемое число копий i-й хромосомы после оператора репродукции равно

N=пPi,

где п — число анализируемых хромосом.

Число копий хромосомы, переходящих в следующее поколение, определяют по формуле

Аi= fi(x) ,

Fcp(X)

где fcp(X) — среднее значение целевой функции.

0,31

Рис. 10.36. Колесо рулетки

Значение Nдля первой хромосомы будет равно 0,14 х 4=0,56 копий, для второй – 0,49 х 4 = 1,96 копий, для третьей – 0,06 х 4 = 0,24 и для четвертой – 0,31 х 4 = 1,24. В результате репродукции в новой популяции (второй столбец в табл. 10.7.) будут присутство­вать по одной копии первой и четвертой хромосомы и две копии второй, а третья хромосома будет исключена. Таким способом опе­ратор репродукции отбирает лучших представителей популяции.

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

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

После репродукции выполняется оператор кроссинговера, который может повторяться несколько раз. При этом каждый раз будет осуществляться выбор двух кандидатур из множества хро­мосом. Затем каждая пара хромосом (стрингов) пересекается. Место пересечения Квыбирается случайным образом на интер­вале

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

хромосома 1: 0110|1

родители хромосома 2: 1100|0

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

хромосома 1: 0110|0

потомкихромосома 2: 1100|1

.

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

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

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

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

Э т а п 2. Гены, соответствующие выбранным позициям, ме­няют местами и формируют новую хромосому А = {а1, aL-1, а3,..., aL-2, а2, aL}.

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

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

хромосома 3: 11011 ® хромосома 3': 11101.

у новой хромосомы 3' значение целевой функции равно (29)2=841. Сделаем еще одну перестановку 4 и 5 генов в хромо­соме 3':

хромосома 3': 11101®xpoмocoмa 3": 11110.

Значение целевой функции для хромосомы 3" равно 900, что

соответствует квазиоптимальному решению задачи нахождения максимального значения функции f(х)=х2 на интервале [0,31].

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

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

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

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

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

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

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

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

4. Вероятность оператора кроссинговера принимается равной P(CO)£1,0.

5. Вероятность оператора мутации принимается равной P(MO)³ 0,001