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

1.1     Математическая формулировка экстремальной задачи однокритериального выбора

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

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

     Ч внешние параметры, характеризующие внешнюю по отношению к объекту среду и оказывающие влияние на его функционирование;

     Ч внутренние параметры, характеризующие свойства отдельных элементов объекта.

В определении конкретных значений внутренних параметров, так же называемых правляемыми переменными, фактически состоит акт принятия решения.

Объединенную совокупность внешних и внутренних параметров будем называть множеством входных параметров.

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

Управляемые переменные аи характеристики аопределяют существенные свойства исследуемого объекта, внешние параметры аявляются, как правило, константами и характеризуют внешнюю среду. При этом внутренние параметры аиграют роль независимых переменных, выходные параметры аявляются зависящими от них величинами. Будем считать, что соотношения, выражающие эти зависимости, заданы в виде Учерного ящика, который имеет n входов x_i,

и s выходов _i,

В процессе принятия решения значения правляемых переменных амогут варьироваться в некоторых пределах, определяемых системой неравенств:

(1.1)

где а<-нижнее и верхнее предельно-допустимые значения, соответственно, для i-ой переменной и j-ой характеристики. Область правляемых переменных, в которой выполняется система ограничений (1.1), будем называть областью поиска D, любой вектор допустимым решением.

Для выбора из области поиска D одного или нескольких Улучших допустимых решений часто приходится вводить критерий оптимальности Q - количественный показатель, посредством которого осуществляется объективное измерение в некоторой числовой шкале Y какого-либо одного наиболее важного для задачи принятия решения выходного параметра j_i. Здесь под измерением по шкале Y понимается отображение Q, которое каждому решению аставит в соответствие числовую оценку таким образом, чтобы отношения между числами сохраняли бинарные отношения предпочтения между решениями:

1)  Упредпочтительнее атогда и только тогда, когда Q( 2)  Уне менее предпочтительнее тогда и только тогда, когда Q(аQ( 3)  Уэквивалентно тогда и только тогда, когда Q(

(1.2)

Из соотношений (1.2) следует, что механизм выбора лучшего решения сводится к отбору тех и только тех решений, которые доставляют наименьшее значение критерию оптимальности Q в области поиска D :

(1.3)

где оптимальное решение; а<- наименьшее значение критерия оптимальности, получаемое при принятии оптимального решения

Выражение (1.3) является математической записью модели принятия оптимального решения, называемой экстремальной задачей однокритериального выбора. В том случае, когда решение задачи (1.3) можно свести к анализу значений критерия оптимальности Q для конечного числа решений а(например, заданных числом перестановок nаили просто дискретным множеством допустимых вариантов) экстремальная задача однокритериального выбора относится к классу экстремальных задач переборного типа [1].

1.2   

Минимизируемая многопараметрическая функция а, может быть как унимодальной, так и многоэкстремальной функцией. Независимо от вида функции оптимальное решение должно довлетворять условию:

адля всех

(1.4)

В случае нимодальной функции (одно-экстремальной функции, которая может быть разрывной, не дифференцируемой и т.д.) оптимальное решение задачи (1.3) является единственным и достигается в точке локального минимума

для всех

(1.5)

где

В случае многоэкстремальной функции (функции ав области поиска D) оптимальное решение задачи (1.3) является глобальным минимумом - наименьшим из всех локальных минимумов:

(1.6)

где а<- к-ый локальный минимум функции

l - число локальных минимумов в области поиска D.

В общем случае оптимальное решение задачи (1.3) может достигаться на некотором подмножестве допустимых решений W Í D, довлетворяющих словию:

* для всех

(1.7)

Тогда, в зависимости от постановки задачи однокритериального выбора, требуется либо перечислить все решения, принадлежащие подмножеству W, либо казать любое одно из решений этого подмножества.

1.3   

Пусть имеется 4 некоторых множеств X, Y, Z, W функциональных элементов, реализующих различные части схемы стабилизаторов напряжения, Х={х₁, х₂,..., х_m}, Y<={y₁, y₂,..., y_n}, Z={z₁, z₂, ..., z_o}, W={w₁, w₂,..., w_p} (банк схемотехнических решений).

Пусть каждый элемент содержит 4 характеристики, закодированные двоичным кодом:

                       

                        _СТ.ИОН. (1 - хорошее, 0 - плохое);

                       

                       

1.8

Стабилизатором напряжения (Х₁, Y₂, Z₃, W₄) будем называть регулярную структуру (1.8), в которой элементы x, y, z и w описывают источник опорного напряжения, сравнивающее стройство, регулирующий элемент, датчик соответственно.

В качестве критерия оптимальности будем рассматривать количество положительных и отрицательных характеристик.

Тогда оптимальный стабилизатор является оптимальным решением (Х₁, Y₂, Z₃, W₄) следующей экстремальной задачи однокритериального выбора:

(1.12)

где К является суммой всех положительных характеристик для всех элементов стабилизатора.

Задача 1.12 относится к экстремальным задачам переборного типа, т.к. общее число допустимых решений равно произведению количества элементов множеств X, Y, Z, W.

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

2.     СИМВОЛЬНАЯ МОДЕЛЬ И ИНТЕРПРЕТАЦИЯ ЕЕ ЭЛЕМЕНТОВ В ТЕРМИНАХ ПОПУЛЯЦИОННОЙ ГЕНЕТИКИ

2.1     Представление допустимых решений экстремальной задачи в виде бинарных строк

Допустимое решение аэкстремальной задачи однокритериального выбора (1.3) является n-мерным векторома авектора а

(2.1)

где (K_i+1)- число возможных дискретных значений i-ой правляемой переменной в области поиска D. Это позволяет поставить во взаимно однозначное соответствие каждому вектору авектор с целочисленными компонентами:

(x1,..., xn)л(b1,..., bn),

(2.2)

где для каждой компоненты b_i,аобластью возможных значений являются целые числа от 0 до К_i .

Введем алфавит В₂, содержащий только два символа 0 и 1: В₂={0,1}. Для того, чтобы представить целочисленный вектор 1,...,b_n) в алфавите В₂ необходимо определить максимальное число двоичных символов q, которое достаточно для представления в двоичном коде любого значения b_i из области его допустимых значений [0,K_i]. Нетрудно видеть, что параметр символьной модели q должен довлетворять неравенству:

К<2q,

(2.3)

где .

Запись произвольного целого неотрицательного числа ас помощью q двоичных символов определяется соотношением :

(2.4)

где a_l<-двоичное число, равное 0 или 1;

q<-длина двоичного слова, кодирующего целое число b_i .

Тогда символьная запись целочисленного кода b_i для фиксированного значения правляемой переменной х_i в обычном двоичном коде запишется в виде следующей бинарной комбинации:

еq(bi):	a1	a2	...	aq		(2.5)
	м<¾¾¾ а

где a_l, а<- двоичные символы (0 или 1), полученные из соотношения (2.4).

Пример 2.1.

Пусть аi=19. Тогда согласно соотношения (2.4) можем записать: 19₁₀ = 1´2⁴ + 0´2³ + 0´2² + 1´2¹ + 1´2⁰ = 10011₂, т.е., бинарная комбинация е₅(19) целого числа 19 в алфавите В₂ будет иметь вид: 10011.

Для представления допустимого решения экстремальной задачи (1.3) в алфавите В₂ объединим символьные записи е_q(b_i), описывающие все n компонент вектора а, в виде линейной последовательности из бинарных комбинаций (2.5):

(2.6)

Записи (2.6) соответствует (n<´

	eq(b1)	eq(b2)		eq(bn)
		...			...		...		...			(2.7)
	n<´

Таким образом, символьная модель экстремальной задачи переборного типа (1.3) может быть представлена в виде множества бинарных строк (2.7), которые описывают конечное множество допустимых решений принадлежащих области поиска D.

Необходимо отметить, что выбор символьной модели исходной экстремальной задачи во многом определяет эффективность и качество применяемых генетических алгоритмов. Для каждого класса задач переборного типа должна строиться своя символьная модель, отражающая специфику и особенности решаемой задачи. В качестве примера приведем символьную модель для задачи (1.12) оптимального дихотомического разбиения графа G(X,V,W).

Представим дихотомическое разбиение (X₁,X₂) графа G(X,V,W) порядка n в виде бинарной строки E (X₁,X₂), состоящей из n бит, расположенных в порядке возрастания их номеров. Каждому номеру бита поставим в взаимнооднозначное соответствие номер вершины графа (1-ый бит соответствует вершине x₁, 2-ой бит - вершине x₂,..., n-ый бит - вершине x_n). Потребуем, чтобы бинарное значение a_l

1-ого бита казывало, какому подмножеству вершин (X₁ или X₂) принадлежит вершина x_l :

		1, если l-ая вершина xl<ÎX входит в состав подмножества вершин X1;
l =			(2.8)
		0, если l-ая вершина xl<ÎX входит в состав подмножества вершин X2

При этом каждая бинарная строка E(X₁,X₂) должна довлетворять дополнительному требованию, связанному с сутью дихотомического разбиения: число битов, содержащих УФ в бинарной строке E (X₁,X₂), должно равняться мощности подмножества вершин подграфа G₁(X₁,V₁,W₁), равной порядку этого подграфа n₁Ф.

Так, разбиения (X₁,X₂) и

E(X1,X2):	1	0	0	0	0	0	1	1	0	1	1	0
E(X1*,X2*):	0	1	1	1	1	1	0	0	0	0	0	0
	1	2	3	4	5	6	7	8	9	10	11	12	-номер бита
	x1	x2	x3	x4	x5	x6	x7	x8	x9	x10	x11	x12	-номер вершины

Сравнивая построенную символьную модель экстремальной задачи (1.12) с общей символьной моделью (2.7), видим, что допустимый вектор авключает в качестве компонент все вершины графа G, каждой из которых соответствует целое число b_i, принимающее только два значения 0 или 1 (т.е. К_i =1 для всех

Это приводит к тому, что бинарная комбинация е_q(b_i) состоит из единственного бита, т.к. неравенство (2.3) выполняется при q<=1. Однако, линейная последовательность (2.6) принимается в качестве бинарной строки ₁,X₂), только в том случае, если число УФ в ней равно порядку n₁ графа G₁.

2.2    вариабиальные признаки

Наименьшей неделимой единицей биологического вида, подверженной действию факторов эволюции, является особь а(индекс k обозначает номер особи, индекс t - некоторый момент времени эволюционного процесса). В качестве аналога особи ав экстремальной задаче однокритериального выбора (1.3) примем произвольное допустимое решение ₁, ..., x_n) - это наименьшая неделимая единица, характеризующая в экстремальной задаче (1.3) внутренние параметры на каждом t-ом шаге поиска оптимального решения, которые изменяют свои значения в процессе минимизации критерия оптимальности Q(

В задаче оптимального дихотомического разбиения (1.12) в качестве особи авыступает конкретное дихотомическое разбиение (X₁,X₂), довлетворяющее условиям (1.8) - (1.9), что позволяет интерпретировать сам процесс решения экстремальной задачи (1.12) как эволюционный процесс, связанный с перераспределением вершин x_i<ÎX графа G по двум подграфам G₁ и G₂, соответственно, порядка n₁ и n₂, с целью отыскания глобального минимума критерия оптимальности (1.11). В этом и заключается в данном случае цель эволюционного развития (эволюции) особей.

Для описания особей введем два типа вариабельных признаков, отражающих качественные и количественные различия между особями в степени их выраженности:

     качественные признаки - признаки, которые позволяют однозначно разделять совокупность особей на четко различимые группы;

     количественные признаки - признаки, проявляющие непрерывную изменчивость, в связи с чем степень их выраженности можно охарактеризовать числом.

Качественные признаки особи аопределяются из символьной модели экстремальной задачи (1.3) как соответствующая точке ас именем абинарная строка E(q(b₁), ..., e_q(b_n).

Приведем интерпретацию этих признаков в терминах хромосомной теории наследственности [4].

В качестве гена - единицы наследственного материала, ответственного за формирование альтернативных признаков особи, примем бинарную комбинацию e_q(b_i) из (2.5), которая определяет фиксированное значение целочисленного кода b_i правляемой переменной x_i в обычном двоичном коде. Одна особь абудет характеризоваться n генами, каждый из которых отвечает за формирование целочисленного кода соответствующей правляемой переменной. Тогда структуру бинарной строки E(хромосомой, содержащей n сцепленных между собой генов, которые расположены в линейной последовательности слева - направо. Согласно хромосомной теории наследственности передача качественных признаков e_q(b_i),

Местоположение определенного гена в хромосоме называется локусом, альтернативные формы одного и того же гена, расположенные в одинаковых локусах хромосомы, называются аллелями (аллелеформами):

	ген 1	ген 2		ген n
	eq(b1)	eq(b2)	...	eq(bn)		(2.9)
	локус 1	локус 2		локус n
	хромосома

где e_q(b_i) - аллель i-го гена, находящаяся в локусе i.

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

При взаимодействии особи ас внешней средой ее генотип E(i ), включающих степень приспособленности m(ак внешней среде и ее фенотип f(

Приняв в качестве внешней среды критерий оптимальности ааявляется численное значение функции ас именем аможно задать с помощью следующего выражения:

		Q2(x), если решается задача максимизации функции
m(			(2.10)
		1/(Q2(

Из выражения (2.10) следует, что чем больше численное значение степени приспособленности m(априспособлена к внешней среде. Следовательно, цель эволюции особей заключается в повышении их степени приспособленности.

Фенотипом f(ав рамках экстремальной задачи (1.3) являются численные значения вектора правляемых переменных аи соответствующих ему характеристика

Для задачи оптимального дихотомического разбиения графа G, сформулированной как экстремальная задача (1.18), в качестве особи авыступает конкретное дихотомическое разбиениеа (Х₁,X₂), удовлетворяющее словиям (1.8)- (1.9). В этом случае геном является бит в бинарной строке Е(Х₁,X₂), который определяет, к какой части разбиения Х₁ или Х₂ принадлежит вершина графа G, соответствующая этому биту. Линейная последовательность всех n битов составляет хромосому, в которой каждый ген определяет принадлежность вершины, соответствующей этому гену, одной из частей Х₁ или Х₂. Введенные гены обладают свойством диморфизма, т.к. каждый ген может иметь только две различающиеся формы аллели: УФ, если вершина х_i принадлежит части Х₁ и УФ, если вершина х_i принадлежит части Х₂.

Степень приспособленности m(₁,X₂) - общей суммой весов ребер, входящих в подграфы G₁ и G₂: m(₁,X₂).

В состав фенотипа f(₁,X₂), входят следующие количественные признаки:

     ₁,X₂) из (1.11);

     ₁,X₂) из (1.13);

     ₁ f₁(Х₁) из (1.16);

     а

     ₂ f₂(X₂) из (1.17).

2.3   

В качестве ареала - области, в пределах которой только и могут встречаться особи, частвующие в эволюционном процессе, будем рассматривать область поиска D. В задаче дихотомического разбиения ареал полностью определяется структурой граф G(X,V,W), заданной множеством вершин X и множеством ребер V, также порядком подграфа G₁ (или подграфа G₂ ).

Совокупность особей популяцию P^t. Число n, характеризующее число особей численностью популяции. В общем случае экстремальной задачи (1.3) популяция P^t=асоответствуют совокупности допустимых решений

t представляет собой набор из n дихотомических разбиений

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

Так, в задаче оптимального дихотомического разбиения (1.11) для дифференциации особейа апо количественному признаку может быть выбрано, например, словие, что в локальную популяцию авключаются только те особи, у которых значение веса разреза Q(Х₁,X₂) не превосходит некоторой заданной величины Q⁺: Q(Х₁,X₂)асоставят все те особи ₁,X₂)

В том случае, когда для дифференциации особей аиспользуется качественный признак, например, генотип E(Х₁,X₂), в качестве меры Ублизости особей аи апо этому признаку можно использовать Хэммингово расстояние, которое определяется как число несовпадающих по своим значениям битов в n<´аи E

d[E EаE<ÅE

(2.11)

где Å<- операция суммирования по mod.2 Тогда в локальную популяцию будем включать только те особи, у которых Хэммингово расстояние меньше заданного неотрицательного целого числа d<³0, в локальную популяцию а<- те особи, для генотипов которых это словие не выполняется. При d<=0 в локальную популяцию абудут включены только те особи, генотипы которых совпадают между собой.

Будем считать, что во времени популяции P^t состоят из дискретных, не перекрывающихся между собой поколений, - групп особей, одинаково отдаленных в родственном отношении от общих предков, т.е. каждое последующее поколение P^t+1 является совокупностью из n особей, которые отбираются только из особей предыдущего t-го поколения. Будем отождествлять номер поколения (верхний индекс t в обозначениях особи аи популяции P^t) с моментом времени t=0,1,...,Т, где Т - жизненный цикл популяции, определяющий период ее эволюции.

В дальнейшем эволюцию популяции P^t будем понимать в ограниченном смысле как чередование поколений, в процессе которого особи изменяют свои вариабельные признаки таким образом, чтобы каждая следующая популяция проявляла лучшую степень приспособленности к внешней среде, например, в смысле обеспечения наибольшего значения средней степени приспособленности по популяции P^t:

mср(t)=

(2.12)

Совокупность из n генотипов всех особей

t, образует хромосомный набор, который полностью содержит в себе генетическую информацию о популяции P^t в целом. Наличие изменчивости хромосомного набора от поколения к поколению является необходимым словием эволюции популяции P^t на генетическом ровне. Для оценки разнообразия генотипов популяции P^t введем в рассмотрение функцию диаллейного разнообразия по каждому биту хромосомного набора:

Di=1-4´

(2.13)

где n_i-число нулей в i-ом бите хромосомного набора популяции P^t; n<- численность популяции P^t. Тогда побитовое разнообразие популяции P^t определим как среднее значение диаллельных разнообразий по всем (n<´

DБ(t)=

(2.14)

При D_Б(t)=1 имеема максимальное разнообразие генотипов в популяции P^t; при D_Б(t)=0 все генотипы в хромосомном наборе совпадают между собой.

Обобщением побитового разнообразия на общий случай экстремальной задачи (1.3) является генетическое разнообразие популяции P^t по всем n локусам:

(2.15)

где

(2.16)

- функция аллельного разнообразия в i-ом локусе;

q(k) ав i-ом локусе;

n_i - число генотипов в хромосомном наборе популяции P^t , в которыха

n - численность популяции P^t;

m_i<- число форм аллелей в i-м локусе (1£i<£

Когда все n генотипов имеют в i-м локусе одну и ту же аллельную форму аD_l(i)=0; если аллельные формы в i-м локусе всех генотипов хромосомного набора отличаются друг от друга (n_i=1), то D_l(i)=1.

По хромосомному набору популяции P^t можно также определить частоту генотипа P(E(

t.

3.     ВЗАИМОДЕЙСТВИЕ ОСНОВНЫХ ФАКТОРОВ ЭВОЛЮЦИИ ПОПУЛЯЦИИ В ТЕЧЕНИЕ ЖИЗНЕННОГО ЦИКЛА

3.1     Размножение особей, поддерживающее наследственную преемственность потомками признаков родителей

Будем считать, что популяция апредставляет собой репродукционную группу - совокупность из n особей, любые две из которых амогут размножаться, выступая в роли родителей (а<- мать; а<- отец). Здесь под размножением апонимается свойство особей <Î

tа воспроизводить одного или нескольких себе подобных непосредственных потомков (Удетей)

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

В терминах экстремальной задачи однокритериального выбора (1.3) воспроизводство себе подобных можно интерпретировать как возможность построения по заданным допустимым решениям анового допустимого решенияа Фнепрерывность и наследственную преемственность - как возможность использования аллельных форм в виде бинарных комбинаций а содержащихся в генотипах родителей E(

Рассмотрим механизм размножения двух родительских особей путем сигнамии (оплодотворения) их репродуктивных клеток - Фматеринской гаметы (яйцеклетки) E(галоидом (одинарным набором непарных хромосом E(

В процессе сигнамии образуется Уродительская зигота - оплодотворенная клетка, способная развиваться в новую особь с передачей наследственных признаков (генетической информации) от родителей их потомкам. Зигота, в отличие от гамет, является диплоидом, содержащим одну пару из двух неотличимых одна от другой хромосом, которые происходят от родительских гамет: одна от материнской гаметы, другая от Уотцовской гаметы. Такие хромосомы называются гомологичными хромосомами. В гомологичных хромосомах для всех признаков имеется по два гена, называемых аллельными генами. Аллельные гены принадлежат одному и тому же локусу. В этом смысле локус принадлежит же не отдельной хромосоме, совокупности из двух гомологичных хромосом. Каждый локус содержит не менее двух аллелей, которые могут быть как одинаковыми, так и различными. Необходимо заметить, что гены родительских гамет могут существовать более чем в двух аллельных формах, хотя каждая зигота может быть носителем только двух форм аллелей (А или а).

Зиготы, содержащие в аллельных генах гомологичных хромосом одинаковые аллели ( или ), называются гомозиготами, содержащие разные аллели ( или ), называются гетерозиготами. Очевидно, что введенные понятия гомозигота и гетерозигота определяются относительно конкретного локуса, содержащего аллельный ген.

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

    

    

     происходит взаимный обмен генами между материнской и отцовской хромосомами;

    

ЗИГОТЫ

Фматеринская

Ч

"отцовская"

i-ый аллельный ген

i-ый аллельный ген

i-ый аллельный ген

i-ый аллельный ген

гомозиготы, соответствую соответствующие чистым, нерасщепляющимся особям

гетерозиготы, соответствую соответствующие гибридным особям

Рис. 3.1. Ситуации образования зигот (а, А - аллели, содержащиеся в i-ом локусе, соответственно, материнской и отцовской гамет).

Таким образом, при образовании зигот происходит независимое и случайное расхождение родительских генов по аллельным генам гомологичных хромосом зиготы независимо от того, у какой из родительских гамет они присутствовали до оплодотворения.

Заключительным этапома размножения особей является акт мейоза - процесс образования гамет из родительской зиготы путем независимого расхождения гомологичных хромосом по дочерним гаметам, воспроизводящим потомство. Одна диплоидная зигота может дать начало четырем галоидным гаметам (гамете, тождественно воспроизводящей отцовскую гамету; гамете, тождественно воспроизводящей материнскую гамету; гамете, являющейся отцовской гаметой, в которой в i-ом локусе находится аллель i-го гена из Уматеринской гаметы; гамете, являющейся материнской гаметой, в которой в i-ом локусе находится аллель i-го гена из отцовской гаметы).

Процесс размножения двух особей должен довлетворять следующим законам наследственности Менделя [4].

1. Первому закону Менделя (закону расщепления) о наследовании альтернативных проявлений одного и того же признака, который формулируется следующим образом:

Два гена, определяющие тот или иной признак, не сливаются и не растворяются один в другом, но остаются независимыми друг от друга, расщепляясь при формировании гамет.

Согласно этому закону гены (или соответствующие им признаки Уродителей), имеющие одинаковые аллели а, передаются потомку по наследству с вероятностью, равной 0,5, т.е. половина гамет оказывается носителем аллели

2. Второму закону Менделя (закону независимого расщепления) о независимости комбинирования признаков, который формулируется следующим образом:

Родительские гены, определяющие различные признаки, наследуются независимо друг от друга.

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

Подробно вопросы реализации процесса размножения особей будут рассмотрены в разделе 5.

3.2   

В результате размножения воспроизводятся потомки, обладающие свойством преемственности наследственных признаков (генов) родителей. При этом генотипы потомков, как правило, содержат новые сочетания аллельных форм генов родителей, ведущие к новым количественным признакам потомков (фенотипу и степени приспособленности). Однако, генетическая информация, содержащаяся в хромосомном наборе родителей и потомков, не меняется, т.к. в результате размножения особей путем сигнамии и мейоза частоты аллелей остаются постоянными, меняются только частоты генотипов. Источником генетической изменчивости особей являются мутации - изменения качественных признаков особей в результате появления новых аллельных форм в отдельных генах или целиком во всей хромосоме. Тем самым в каждом поколении мутации поставляют в хромосомный набор популяции множество различных генетических вариаций, присущих особям, которых в дальнейшем будем называть мутантами

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

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

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

Эволюция популяции в течение смены нескольких поколений в смысле изменения генетической наследственности представляет из себя процесс одновременного и постепенного изменения как частот, так и форм аллелей в различных локусах хромосомы. При этом аллели действуют на количественные признаки не изолированно друг от друга. Так, влияние того или иного аллеля на степень приспособленности особи зависит от присутствия или отсутствия в его генотипе других аллелей. Набор аллелей каждого локуса взаимно приспособлен (кодаптирован) с набором аллелей других локусов. Поэтому изменение частот аллелей в одном локусе влечет за собой изменение частот аллелей и в других локусах.

Наиболее простым видом мутаций является точечная мутация, связанная с изменением аллеля родительского гена в одном из q бит генной информации

(0 заменяется на 1 или 1 заменяется на 0).

Определим интенсивность процесса мутагенеза в t-м поколении как среднее число точечных мутацийа M_T(t), которые могут произойти в хромосомном набореа t:

Mт(t)=n<´(n<´m,

(3.1)

где n<- численность популяции P^t;

n<´

P_m - вероятность точечной мутации, определяемая как число возможных однобитовых изменений на 100 бит генетической информации.

Обычно вероятность точечной мутации в популяции очень мала (P_m=0.01 или P_m=0.001), что приводит к невысокому темпу возникновения мутаций. Например, при n<=10, n=12, q<=32 и P_m=0.01 получаем, что в среднем в каждом поколении будет приходить 38 точечных мутаций.

Подробно вопросы реализации процесса мутагенеза будут рассмотрены в разделе 6.

3.3   

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

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

(3.3)

При этом генотипы особей

     наследственности, которая закрепляет у потомков лучшие признаки, полученные от Уродителей в результате их размножения;

     изменчивости, которая служит основой образования новых признаков за счет изменения генетического состава популяции в результате мутаций;

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

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

Большую роль в развитии генетических алгоритмов сыграли I. Holland [5], D. Goldberg [6] и L. Davis [7], которые заложили и развили теоретические основы генетического подхода к решению задач оптимизации. Не останавливаясь на обзоре этих работ, приведем обобщенную схему генетического алгоритма, структура которого является типичной для широкого круга публикаций по этому вопросу.

Базовая структура Генетического алгоритма :

1.                ⁰ из n особей

1.1.        

1.2.         аи вычисление степени приспособленности m(

1.3.         аобразуют начальную популяцию P^tа для поколения t=0.

2.               

2.1.         адля частия в процессе размножения.

2.2.        

2.3.         а

2.4.         ав соответствующие векторы управляемых переменных и вычисление степени приспособленности потомков, обладающих генотипами E(

2.5.        

3.               

3.1.        

3.2.         <Î

t генотипа аособи - Фмутанта ас помощью конкретного типа мутации.

3.3.        

3.4.        

4.               

4.1.        

4.2.        

4.3.         аиз особей, принадлежащих репродукционной группе.

5.               

Если словия окончания процесса эволюции не выполнены, то происходит смена поколений и все вычисления для популяции следующего (t+1) - го поколения

t+1 повторяются с шага 2.

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

t<>T

(3.4)

или

DБ(t)=0.

(3.5)

Выполнение неравенства (3.4) означает, что эволюция популяции закончена в связи с тем, что она исчерпала свой жизненный цикл; окончание эволюции популяции при равенстве побитового разнообразия текущей популяции P^t нулю означает, что все генотипы в хромосомном наборе популяции P^t совпадают между собой.

В заключение данного раздела приведем отличия генетических алгоритмов от поисковых методов оптимизации [6].

1. Генетические алгоритмы осуществляют прямое манипулирование бинарными строками E(

2. Генетические алгоритмы в каждом t-ом поколении оперируют одновременно со всей совокупностью из n допустимых решений

t , с целью получения хромосомного набора популяции следующего поколения P^t+1.

Таким образом генетические алгоритмы на каждой итерации, совпадающей с текущим поколением, позволяют определять n новых допустимых решений, в то время как классические методы поиска [8] на каждой итерации определяют единственное новое допустимое решение. Например, градиентный метод минимизации реализуется с помощью рекуррентного выражения:

(3.6)

где а<- начальное приближение;

а<- градиент минимизируемой функции;

l - шаг вдоль градиента.

3. Генетические алгоритмы основаны на вероятностных схемах преобразования бинарных строк E(

t, которые моделируют биологические механизмы популяционной генетики [4].

4. Генетические алгоритмы - это методы нулевого порядка, стратегия поиска, ва которых построена только на вычислении значений критерия оптимальности Q и не требует знания дополнительной информации о производных, константе Липшица и т.д., что характерно для градиентных и квази-ньютоновских методов [8].

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

4.     СХЕМЫ РАЗМНОЖЕНИЯ ОСОБЕЙ

4.1     Рекомбинация генов

Пусть особи аи ас различающимися между собой генотипами E(аявляются "родительской" парой, которая образована из особей популяции P^t по одной из рассмотренных в разделе 4 систем скрещивания.

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

По своей сути рекомбинация генов ведет к появлению новых сочетаний "родительских" генов, так как аллель любого гена "родительской" гомологичной хромосомы, согласно первого закона Менделя, целиком передается "потомку" по наследству. При этом гомологичные хромосомы "родителей" сравниваются по содержанию каждого гена. Если аллели в i-ом локусе одинаковы у "отцовской" и "материнской" хромосом q(i) сохраняется в i-ом гене "потомка". В противном случае ав i-ый локус гаметы "потомка" заносится с вероятностью (1/2) либо аллель

     аили "матери"

     аллелеформы другого "родителя".

На рис. 5.1. приведен пример воспроизводства двух гибридных гамет "потомков" (ас помощью рекомбинации генов.

	"Отцовская" гамета		"Материнская" гамета
E(	eq(1)		eq(3)		E(	eq(1)		eq(3)
	1	2	3	4		1	2	3	4

	Гибридные гаметы потомков аи
	eq(1)		eq(3)
	1	2	3	4

	Гибридные гаметы потомков аи
E(	eq(1)		eq(3)
	1	2	3	4

Рис. 4.1. Воспроизводство "потомства" путем рекомбинации генов

(гены 1 и 3 являются гомозиготами, гены 2 и 4 - гетерозиготами).

В некоторых случаях какие-то аллели могут оказывать более сильное влияние на соответствующий признак особи и в процессе рекомбинации генов им необходимо отдавать большее предпочтение при формировании генов в гаметах "потомков".

Будем называть рецессивным аллелем аллельную форму a , которая проявляется лишь в гомозиготе (aa), когда "родители" имеют одинаковые аллели в рассматриваемом локусе аллельного гена доминантным аллелем - аллельную форму A, которая проявляется не только в гомозиготе (AA), но и в гетерозиготах (Aa или aA).

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

"Отцовская" гамета

E(

" Материнская " гамета

E(

а_{1 1}

Гамета "потомка"

	)доминантный аллель A принадлежит "отцовской гамете		б)доминантный аллель A принадлежит" материнскойУ гамете

Рис.5.2. Доминирование доминантного аллеля A над рецессивным аллелем a.

Для чета доминантности некоторых из аллельных форм e_q(k), q(k), находящейся в i-м локусе хромосомного набора популяции P^t :

(4.1)

где t ;

i - число генотипов в хромосомном наборе популяции P^t, в которых i-ый локус содержит аллельную форму e_q(k);

i - число форм аллелей в i-м локусе (1£ m_i £

Тогда, если P(e_q(k),i) > P(e_q(j),i), то аллель e_q(k) считается доминантным аллелем; это приводит к тому, что при наличии в i-м аллельном гене двух аллелей e_q(k) и e_q(j),в i-ый локус гаметы "потомка" заносится доминантный аллель e_q(k) с вероятностью 1 вместо вероятности (1/2), принятой для рекомбинации генов без доминирования.

В качестве иллюстрации приведем реализацию схемы размножения особей путем рекомбинации генов для задачи оптимального разбиения графа G(X,V,W) порядка n на два подграфа G₁(X₁ ,V₁,W₁ ) и G₂ (X₂,V₂ ,W₂ ) порядка n₁ и n₂, соответственно.

Обозначим символами аи а<- аллельные формы i-го гена гамет "отца", "матери" и "потомка".

лгоритм рекомбинации генов

1.                1 :=I₂ :=0; 1(t):=n₂(t):=0.

2.               

2.1.         ₁:=I₁È<{i<}; n₁(t):=n₁(t)+1};

2.2.         ₂:=I₂È<{i<}; n₂(t):=n₂(t)+1};

3.                ₁È I₂} - множество гетерозиготных генов.

4.                <çI ç) выбирается j-ый гетерозиготныйа ген (j<ÎJ).

5.                аили а("1" или "0");

6.                а ₁(t): = n₁(t)+1 иначе n₂(t): =n₂(t)+1.

6.1.        

7.               

нет

₁(t)=n₁ или Vn₂(t) = n₂]?

да

8.                ₁(t)=n₁, то а для всех k<ÎI (гамета "потомка" асформирована ).

Для чета доминантности аллельных форм п.5 рассмотренного алгоритма должен быть заменен следующей процедурой:

5.1. Случайным образом с вероятностью (n_j /n) в j-ый локус "потомка" заносится "1" и с вероятностью (1 - n_j /n) заносится "0" (Здесь n_j - число единиц в j-м локусе хромосомного набора популяции P^t численностью n).

Введенная процедура позволяет определить доминантный аллель A с помощью частот аллелей хромосомного набора текущей популяции P^t, т.к. каждый ген имеет всего две формы аллелей "1" или "0".

Пример 4.1.

Пусть для графа, приведенного на рис.1.1. задано два дихотомических разбиения (

₂, x₄, x₅, x₇, x₉}, а<= { x₁, x₃, x₆, x₈, x₁₀, x₁₁, x₁₂} и

₁, x₂, x₅, x₈, x₁₀} а<= { x₃, x₄, x₆, x₇, x₉, x₁₀, x₁₂}.

Будем считать, что (₁=5[1]< :

"отцовская" гамета E(	0	1	0	1	1	0	1	0	1	0	0	0	(13)
	1	2	3	4	5	6	7	8	9	10	11	12
"материнская" гамета E(	1	1	0	0	1	0	0	1	0	1	0	0	(19)
	1	2	3	4	5	6	7	8	9	10	11	12

Для приведенных "родительских" гамет гомозиготные гены находятся во 2, 3, 5, 6, 11 и 12 локусах; локусы, которые занимают гетерозиготные гены, помечены крестиками:

		x	1	0	x	1	0	x	x	x	x	0	0
		1	2	3	4	5	6	7	8	9	10	11	12

В результате рекомбинации генов может быть получена, например, следующая гамета "потомка":

	1			1			0	0	0	1			(18)
	1	2	3	4	5	6	7	8	9	10	11	12

которой соответствует разбиение (X₁, X₂ ):

X₁ = { x₁, x₂, x₄, x₅, x₁₀}, X₂ = { x₃, x₆, x₇, x₈, x₉, x₁₁, x₁₂}.

В генотипе "потомка" агены 2, 3, 5, 6, 11 и 12 (заштрихованные биты) совпадают с гомозиготными генами "родителей", сохраняя их аллели по наследству; аллели генов "потомка" 1, 7, 9 и 10 получены от соответствующих генов "материнского" генотипа (эти биты помечены символом а 8 получены от соответствующих генов "отцовского" генотипа (эти биты помечены символом

4.2   

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

ген 1 ген 2 ген 3 ген 4

Родительский генотип E( 0 1 1 0 1 0 1 1 1 0 1 1

1 2 3 4 5 6 7 8 9 10 11 12

Генотип мутант E( 0 1 1 0 0 0 1 1 1 0 1 1

1 2 3 4 5 6 7 8 9 10 11 12

локус 1 локус 2 локус 3 локус 4

Рис. 4.1. Точечная мутация в пятом бите гена 2 изменяет аллель этого гена в генотипе "мутанта", оставляя гены 1, 3 и 4 без изменений

Одну из схем воспроизводства из родительской" гаметы E() мутанта ас помощью точечной мутации можно представить в виде следующей процедуры:

1.

2. В генотипе аслучайным образом с вероятностью (1/n) определяется j-ый ген (j<Î[1,n]), в котором аллель "родительского" гена будет подвержена мутации.

3. Для выбранного гена случайным образом с вероятностью (1/q) в j-м локусе выбирается i-ый бит, в котором должна произойти точечная мутация.

4. В i-м бите j-ого локуса генотипа адвоичное число b

Генотип "мутанта" асформирован.

Более глубокие изменения генной информации происходят в результате генной мутации, когда в i-м гене "родительского" генотипа E()а аллель, находящаяся в i-м локусе, полностью заменяется новой аллельной формой (рис.6.2).

ген 1 ген 2 ген 3 ген 4

Родительский генотип E( 0 1 1 0 1 0 1 1 1 0 1 1

1 2 3 4 5 6 7 8 9 10 11 12

Генотип мутант E( 0 1 1 0 0 0 1 1 1 0 1 1

1 2 3 4 5 6 7 8 9 10 11 12

локус 1 локус 2 локус 3 локус 4

Рис. 4.2. Генная мутация во 2 гене изменяет аллель этого гена в генотипе "мутанта", оставляя гены 1, 3 и 4 без изменений

Очевидно, что новые аллели должны принадлежать генофонду гена, подвергающегося мутации, и, как правило, отличаются от аллельных форм, уже имеющихся в хромосомном наборе популяции P^t для соответствующего локуса.

Очевидно, что новые аллели должны принадлежать генофонду гена, подвергающегося мутации, и, как правило, отличаются от аллельных форм, уже имеющихся в хромосомном наборе популяции Pt для соответствующего локуса.

Одна из схем реализации генной мутации в "родительском" генотипе E() может быть представлена следующим образом:

1.

2. В генотипе аслучайным образом с вероятностью (1/n) определяется j-ый ген (j Î[1,n]), в котором аллель "родительского" гена будет подвержена мутации.

3. Из генофонда j-ого гена Г(j) исключаются все аллели хромосомного набора популяции Pt, находящиеся в j-м локусе:

Г (

4. Если Г(j): = Æ, то Г(j):= а.

5. Случайным образом с вероятностью (1/êГ(j)ê) из множества аллелей Г(j) выбирается альтернативный аллель .

6. В j-м локусе генотипа ллель "родительского" генотипа азаменяется новой аллельной формой .

Генотип "мутанта" асформирован.

Для задачи оптимального разбиения графа G на два подграфа G1и G2 порядка n1 и n2, соответственно, точечная и генная мутации совпадают, т.к. локусы для каждого гена содержат по одному биту (q<=1). С другой стороны, к формируемым генотипам E() предъявляется требование, чтобы число "I" в них равнялось порядку n1подграфа G1. В связи с этим генная мутация для рассматриваемого случая сводится к изменению аллельных форм в двух случайно выбранных генах "родительского" генотипа E(): в одном гене аллель, равная УI" заменяется "0", в другом гене аллель, равная "0" заменяется на "1".

Схема, реализующая генную мутацию генотипа E(), который характеризует допустимое дихотомическое разбиение (X1, X2 ), имеет следующий вид:

1.

2. По генотипу аобразуется список номеров локусов I1, содержащих "I", и список номеров локусов I0, содержащих "0".

3. Случайным образом с вероятностью (1/½ I1½) выбирается номер локуса i<ÎI1, который будет подвержен генной мутации.

4. Случайным образом с вероятностью (1/êI0 ê) выбирается номер локуса j ÎI, который будет подвержен генной мутации.

5. Аллель "1", находящаяся в i-м локусе генотипа азаменяется "0", аллель "0", находящаяся в j-м локусе генотипа азаменяется "1".

Генотип "мутанта" асформирован.

Рассмотренный алгоритм генной мутации описывает операцию однократного обмена вершинами между подмножествами X1 и X2, которая заключается в том, что только одна вершина xi<Î X1 перемещается на другую сторону разреза в часть X2, вместо вершины

а<= [X1{xi<}] <È {vj<};

(6.1)

₂{v_j<}] <È {x_i<}.

Пример 6.1.

Пусть "родительский" генотип E() задает дихотомическое распределение

X1 = {x1, x3, x4, x10, x12}, X2 = {x2, x5, x6, x7, x8, x9, x11} :

		*										*
"Родительский" генотип E():	1	0	1	1	0	0	0	0	0	1	0	1
	1	2	3	4	5	6	7	8	9	10	11	12

ас генотипом аследующего вида:

: 1 1 1 1 0 0 0 0 0 1 0 0 (25)

1 2 3 4 5 6 7 8 9 10 11а 12

---

[1]< В скобках указаны степени приспособленности