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

Номер хромосомы	Двоичный код хромосомы	Значение х (десятичный код)	Значение целевой функцииf (x)	Нормированное значениеf (x)/sum f(x)	Ожидаемое Количество копий хромосомы в следующем поколении.	Реальное количество копий хромосомы в следующем поколении.
				0.14	0.56
				0.49	1.96
				0.06	0.24
				0.31	1.24
Суммарная целевая функция		1,00	4.00
Среднее значение целевой функции		0.25	1.00
Максимальное значение целевой функции		0,49	1.97

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

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

Р_i =f_i(x))/sum f(x)

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

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

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

N=пPi,

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

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

А _i = fi(x),

Fcp(X)

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

0,31

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

Номер хромосомы	Популяция после репродукции	Случайно выбранные пары	Точка разрыва кроссигвера	Популяция после кроссигвера	Значение х (десятичный код)	Значение f(х)
	0 1 1 0 |1	1-2
	1 1 0 0 |0	1-2
	1 1 |0 0 0	3-4
	1 0 |0 1 1	3-4
Суммарное значение целевой функции sum f(х)=1754
Среднее значение целевой функции fcр(х)=439
Максимальное значение целевой функции maxf(x)=729

Значение 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. В хромосоме А = {а₁, а₂, а₃,..., a_L-2, a_L-1, a_L} случайным образом определяют две позиции, например, 2 и L-1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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