Программированное обучение и контроль по физиологии

2. Задача синтеза стабилизатора напряжения как экстремальная задача переборного типа

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

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

1. Влияние на петлевое усиление (1 - хорошее, 0 - плохое);

2. Влияние на К_СТ.ИОН. (1 - хорошее, 0 - плохое);

3. Мощность множества узлов (1 - большая, 0 - малая);

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.

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

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

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

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

(2.1)

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

(x, ..., xn)(1,..., n),

(2.2)

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

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

К<2>

(2.3)

где .

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

,

(2.4)

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

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

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

е(i):	1	2	...			(2.5)
	  

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

Пример 2.1.

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

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

(2.6)

Записи (2.6) соответствует (n)-битовая строка из двоичных символов (0,1):

	e(1)	e(2)		e(n)
		...			...		...		...			(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). Потребуем, чтобы бинарное значение _l

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

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

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

Так, разбиения (X₁,X₂) и , приведенные в Таблице 1.1., имеют следующие представления в виде бинарных строк:

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, каждой из которых соответствует целое число _i, принимающее только два значения 0 или 1 (т.е. К_i =1 для всех ).

Это приводит к тому, что бинарная комбинация е(_i) состоит из единственного бита, т.к. неравенство (2.3) выполняется при =1. Однако, линейная последовательность (2.6) принимается в качестве бинарной строки , соответствующей допустимому разбиению (X₁,X₂), только в том случае, если число “1” в ней равно порядку n₁ графа G₁.

1. Особи и их вариабиальные признаки

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

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

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

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

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

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

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

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

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

	ген 1	ген 2		ген n
	e(1)	e(2)	...	e(n)		(2.9)
	локус 1	локус 2		локус n
	хромосома

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

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

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

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

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

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

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

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

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

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

• вес разреза Q(Х₁,X₂) из (1.11);

• коэффициент разбиения K(Х₁,X₂) из (1.13);

• сумма весов ребер подграфа G₁ f₁(Х₁) из (1.16);

• сумма весов ребер подграфа

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

1. Популяции и поколения

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

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

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

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

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

d[E, E]= EE,

(2.11)

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

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

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

ср(t)=.

(2.12)

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

Di=1-4,

(2.13)

где _i-число нулей в i-ом бите хромосомного набора популяции P^t; - численность популяции 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-ом локусе;

- частота аллельной формы e(k) в i-ом локусе;

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

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

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

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

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

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

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

Будем считать, что популяция представляет собой репродукционную группу - совокупность из  особей, любые две из которых могут размножаться, выступая в роли “родителей” ( - “мать”; - “отец”). Здесь под размножением понимается свойство особей P^t воспроизводить одного или нескольких себе подобных непосредственных “потомков” (“детей”) , i1 и обеспечивать у них непрерывность и наследственную преемственность качественных признаков “родителей”.

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

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

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

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

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

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

• ген из “отцовской“ хромосомы переходит в “материнскую” хромосому;

• ген из “материнской” хромосомы переходит в “отцовскую” хромосому;

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

• “отцовская” и “материнская” хромосомы остаются без изменения.

ЗИГОТЫ

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

А

а

А

а

гомологичные хромосомы

—

"отцовская"

А

а

а

А

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

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

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

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

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

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

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

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

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

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

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

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

Согласно этому закону гены (или соответствующие им признаки “родителей”), имеющие одинаковые аллели , сохраняют свои значения в “потомстве”, т.е. передаются с вероятностью, равной 1, “потомку” по наследству. Гены “родителей”, имеющие разные аллели , передаются “потомку” по наследству с вероятностью, равной 0,5, т.е. половина гамет оказывается носителем аллели , а другая половина - аллели .

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

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

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

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

1. Приобретение особями новых качественных признаков

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

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

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

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

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

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

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

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

Mт(t)=(n)Pm ,

(3.1)

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

n- длина хромосомы, равная числу битов в бинарной строке ;

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

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

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

1. Базовая структура генетического алгоритма, моделирующего эволюционное развитие популяции

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

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

(3.3)

При этом генотипы особей , t=0,1,2, ...,T, заданные с помощью бинарных строк E(), в процессе своего преобразования в результате факторов эволюционного развития популяции по Дарвину в каждом поколении должны обладать следующими свойствами:

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

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

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

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

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

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

1. Формирование начальной популяции P⁰ из  особей :

   1. Генерация хромосомного набора из  бинарных строк E(), удовлетворяющих требованиям, предъявляемым к символьной модели исходной экстремальной задачи.

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

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

2. Воспроизводство “потомков” с наследственными признаками “родителей”:

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

   2. Выбор схемы размножения.

   3. Построение по выбранной схеме из генотипов “родителей” E(),генотипов их “потомков” , сохраняющих наследственные признаки “родителей”.

   4. Преобразование бинарных строк в соответствующие векторы управляемых переменных и вычисление степени приспособленности “потомков”, обладающих генотипами E().

   5. Вычисления повторяются с шага 2.1. до тех пор, пока не будет воспроизведено заданное число “потомков”.

3. Мутагенез, приводящий к генетическим изменениям “родительских” признаков:

   1. Выбор типа мутации.

   2. Построение по генотипу E() одной из особей P^t генотипа особи - ”мутанта” с помощью конкретного типа мутации.

   3. Преобразование бинарной строки в соответствующий вектор управляемых переменных и вычисление степени приспособленности особи - ”мутанта” , обладающей генотипом E().

   4. Вычисления повторяются с шага 3.1. до тех пор, пока не будет создано заданное число “мутантов”.

4. Естественный отбор:

   1. Определение среди “родителей”, “потомков” и “мутантов” особей, образующих репродуктивную группу, которая примет участие в естественном отборе.

   2. Выбор схемы естественного отбора.

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

5. Проверка условий окончания процесса эволюции популяции P.

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

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

tT

(3.4)

или

DБ(t)=0.

(3.5)

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

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

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

2. Генетические алгоритмы в каждом t-ом поколении оперируют одновременно со всей совокупностью из  допустимых решений , образующих популяцию P^t , с целью получения хромосомного набора популяции следующего поколения P^t+1.

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

, k=0,1,2,...

(3.6)

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

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

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

3. Генетические алгоритмы основаны на вероятностных схемах преобразования бинарных строк E(), составляющих хромосомный набор популяции P^t, которые моделируют биологические механизмы популяционной генетики [4].

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

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

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

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

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

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

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

• копию одной из "родительских" гамет ("отца" или "матери" );

• гамету одного из "родителей", в которой некоторые гены имеют аллелеформы другого "родителя".

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

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

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

	Гибридные гаметы “потомков” и
E():	e(1)		e(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(k), , можно воспользоваться частотой аллели e(k), находящейся в i-м локусе хромосомного набора популяции P^t :

, ,

(4.1)

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

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

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

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

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

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

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

1. I:= {1,2,...n} ; I₁ :=I₂ :=0; n₁(t):=n₂(t):=0.

2. Для всех i I формируются гомозиготные гены "потомка":

   1. Если ==1, то {:=1; I₁:=I_1{i}; n₁(t):=n₁(t)+1};

   2. Если ==0, то {:=0; I₂:=I_2{i}; n₂(t):=n₂(t)+1};

3. I: = I\ { I_1 I₂} - множество гетерозиготных генов.

4. 4. Случайным образом с вероятностью (1/I ) выбирается j-ый гетерозиготный ген (jJ).

5. Случайным образом с вероятностью (1/2) в j-ый локус гаметы "потомка" заносится или ("1" или "0");

6. Если =1, то n₁(t): = n₁(t)+1 иначе n₂(t): =n₂(t)+1.

   1. I: = I\{ j } .

7. 8. [n₁(t)=n₁ или Vn₂(t) = n₂]?

   нет

да

1. Если n₁(t)=n₁, то : = 0 для всех k I иначе :=1 для всех kI (гамета "потомка" сформирована ).

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

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

Введенная процедура позволяет определить доминантный аллель 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₉, x₁₀, x₁₂} .

Будем считать, что () соответствует особи , а разбиение () - особи , которые образуют "родительскую" пару с генотипами, удовлетворяющими условию, что число "1" в каждом из них равно n₁=5¹ :

"отцовская" гамета 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 получены от соответствующих генов "материнского" генотипа (эти биты помечены символом ); гены "потомки" 4 и 8 получены от соответствующих генов "отцовского" генотипа (эти биты помечены символом ).

1. Краткая теория

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

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

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

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

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

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

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

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

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

и s выходов _i,.

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

,; ,

(1.1)

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

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

“предпочтительнее” тогда и только тогда, когда Q()#); “не менее предпочтительнее” тогда и только тогда, когда Q() Q(); “эквивалентно” тогда и только тогда, когда Q() = Q().

(1.2)

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

,

(1.3)

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

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

1. Понятие “оптимальное решение”

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

для всех .

(1.4)

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

для всех ,

(1.5)

где -  -окрестность точки локального минимума .

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

,

(1.6)

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

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

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

=Q* для всех .

(1.7)

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