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

Загрузить архив:
Файл: vdv-1132.zip (144kb [zip], Скачиваний: 87) скачать

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

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

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

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

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

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

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

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

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

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

и sвыходов i,

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

(1.1)

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

Для выбора из области поиска D одного или нескольких “лучших” допустимых решений часто приходится вводить критерий оптимальности Q - количественный показатель, посредством которого осуществляется объективное измерение в некоторой числовой шкале Y какого-либо одного наиболее важного для задачи принятия решения выходного параметра ji. Здесь под измерением по шкале 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)

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

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

(1.6)

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

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

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

* для всех

(1.7)

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


1.3

Пусть имеется 4 некоторых множеств X, Y, Z, W функциональных элементов, реализующих различные части схемы стабилизаторов напряжения, Х={х1, х2, ... , хm}, Y={y1, y2, ... , yn}, Z={z1, z2, ... , zo}, W={w1, w2, ... , wp} (банк схемотехнических решений).

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

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

1.8

Стабилизатором напряжения (Х1, Y2, Z3, W4) будем называть регулярную структуру (1.8), в которой элементы x, y, z и w описывают источник опорного напряжения, сравнивающее устройство, регулирующий элемент, датчик соответственно.

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

Тогда оптимальный стабилизатор является оптимальным решением (Х1, Y2, Z3, W4) следующей экстремальной задачи однокритериального выбора:

(1.12)

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

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

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

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

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

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

(2.1)

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

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

(2.2)

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

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

К<2q,

(2.3)

где.

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

(2.4)

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

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

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

еq(bi):

a1

a2

...

aq

(2.5)

¬¾¾¾ q¾¾¾®

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

Пример 2.1.

Пусть q=5 и bi=19. Тогда согласно соотношения (2.4) можем записать: 1910 = 1´24 + 0´23 + 0´22 + 1´21 + 1´20 = 100112 , т.е., бинарная комбинация е5(19) целого числа 19 в алфавите В2 будет иметь вид: 10011.

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

(2.6)

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

eq(b1)

eq(b2)

eq(bn)

...

...

...

...

(2.7)

n´q

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

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

Представим дихотомическое разбиение (X1,X2) графа G(X,V,W) порядка n в виде бинарной строки E (X1,X2), состоящей из n бит, расположенных в порядке возрастания их номеров. Каждому номеру бита поставим в взаимнооднозначное соответствие номер вершины графа (1-ый бит соответствует вершине x1, 2-ой бит - вершине x2, ... , n-ый бит - вершине xn). Потребуем, чтобы бинарное значение al

1-ого бита указывало, какому подмножеству вершин (X1 или X2) принадлежит вершина xl :

1, если l-ая вершина xlÎX входит в состав подмножества вершин X1;

al =

(2.8)

0, если l-ая вершина xlÎX входит в состав подмножества вершин X2

При этом каждая бинарная строка E(X1,X2) должна удовлетворять дополнительному требованию, связанному с сутью дихотомического разбиения: “число битов, содержащих “1” в бинарной строке E (X1,X2), должно равняться мощности подмножества вершин подграфа G1(X1,V1,W1), равной порядку этого подграфа n1”.

Так, разбиения (X1,X2) и

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

Это приводит к тому, что бинарная комбинация еq(bi) состоит из единственного бита, т.к. неравенство (2.3) выполняется при q=1. Однако, линейная последовательность (2.6) принимается в качестве бинарной строки 1,X2), только в том случае, если число “1” в ней равно порядку n1 графа G1.

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

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

В задаче оптимального дихотомического разбиения (1.12) в качестве особи выступает конкретное дихотомическое разбиение (X1,X2), удовлетворяющее условиям (1.8) - (1.9), что позволяет интерпретировать сам процесс решения экстремальной задачи (1.12) как эволюционный процесс, связанный с перераспределением вершин xiÎX графа G по двум подграфам G1 и G2, соответственно, порядка n1 и n2, с целью отыскания глобального минимума критерия оптимальности (1.11). В этом и заключается в данном случае цель эволюционного развития (эволюции) особей.

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

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

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

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

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

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

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

ген 1

ген 2

ген n

eq(b1)

eq(b2)

...

eq(bn)

(2.9)

локус 1

локус 2

локус n

хромосома

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

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

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

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

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

m(

(2.10)

1/(Q2(

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

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

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

Степень приспособленности m(1,X2) - общей суммой весов ребер, входящих в подграфы G1 и G2: m(1,X2).

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

· 1,X2) из (1.11);

· 1,X2) из (1.13);

· 1 f1(Х1) из (1.16);

·

· 2 f2(X2) из (1.17).

2.3

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

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

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

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

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

d[E          EEÅE

(2.11)

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

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

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

mср(t)=

(2.12)

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

Di=1-4´

(2.13)

где ni-число нулей в i-ом бите хромосомного набора популяции Pt; n- численность популяции Pt. Тогда побитовое разнообразие популяции Pt определим как среднее значение диаллельных разнообразий по всем (n´q) битам хромосомного набора:

DБ(t)=

(2.14)

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

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

(2.15)

где

(2.16)

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

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

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

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

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

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

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

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

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

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

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

В терминах экстремальной задачи однокритериального выбора (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-м поколении как среднее число точечных мутацийMT(t), которые могут произойти в хромосомном наборе  t-ой популяции Pt:

Mт(t)=n´(n´q)´Pm ,

(3.1)

где n- численность популяции Pt;

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

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

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

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

3.3

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

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

(3.3)

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

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

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

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

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

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

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

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

1.1. n бинарных строк E(

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

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

2.

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

2.2.

2.3.

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

2.5.

3.

3.1.

3.2. ÎPt генотипа особи - ”мутанта” с помощью конкретного типа мутации.

3.3.

3.4.

4.

4.1.

4.2.

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

5.

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

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

t>T

(3.4)

или

DБ(t)=0.

(3.5)

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

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

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

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

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

(3.6)

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

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

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

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

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

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

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

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

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

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

По своей сути рекомбинация генов ведет к появлению новых сочетаний "родительских" генов, так как аллель любого гена "родительской" гомологичной хромосомы, согласно первого закона Менделя, целиком передается "потомку" по наследству. При этом гомологичные хромосомы "родителей" сравниваются по содержанию каждого гена. Если аллели в i-ом локусе одинаковы у "отцовской" и "материнской" хромосом eq(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.

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

(4.1)

где    n - численность популяции Pt ;

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

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

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

В качестве иллюстрации приведем реализацию схемы размножения особей путем рекомбинации генов для задачи оптимального разбиения графа G(X,V,W) порядка n на два подграфа G1(X1 ,V1 ,W1 ) и G2 (X2 ,V2 ,W2 ) порядка n1 и n2 , соответственно.

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

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

1. n} ;   I1 :=I2 :=0;   n1(t):=n2(t):=0.

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

2.1. 1:=I1È{i}; n1(t):=n1(t)+1};

2.2. 2:=I2È{i}; n2(t):=n2(t)+1};

3. 1È I2} - множество гетерозиготных генов.

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

5. j-ый локус гаметы "потомка" заносится или ("1" или "0");

6. 1(t): = n1(t)+1 иначе n2(t): =n2(t)+1.

6.1. j } .

7.

нет
1(t)=n1 илиVn2(t) = n2]?

да

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

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

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

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

Пример 4.1.

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

     2, x4, x5, x7, x9},      = { x1, x3, x6, x8, x10, x11, x12}   и

     1, x2, x5, x8, x10}      = { x3, x4, x6, x7, x9, x10, x12} .

Будем считать, что (1=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

которой соответствует разбиение (X1, X2 ):

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

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

4.2

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

                                                           ген 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-ого локуса генотипа двоичное число bi принимает противоположное значение (0 заменяется на 1 или 1 заменяется на 0).

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

Более глубокие изменения генной информации происходят в результате генной мутации, когда в 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 без изменений

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

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

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

1.

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

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

Г ( j ) := Г ( 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, вместо вершиныvjÎX2, которая, в свою очередь, перемещается в часть X1 :

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

(6.1)

2{vj}] È {xi}.

Пример 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   1112


[1] В скобках указаны степени приспособленностиm особей, имеющих данный генотип.