1.3   

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где  .

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

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

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

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

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

Пример 2.1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

·     ₁,X₂) из (1.11);

·     ₁,X₂) из (1.13);

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

·      

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

2.3   

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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

·    

·    

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

·    

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

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

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

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

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

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

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

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

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

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

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

3.2   

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3   

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

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

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

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

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

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

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

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

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

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

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

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

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

2.               

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

2.2.        

2.3.          

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

2.5.        

3.               

3.1.        

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

3.3.        

3.4.        

4.               

4.1.        

4.2.        

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

5.               

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

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

или

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

                                            _{1                                           1}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6.1.         j } .

7.               

да

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

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

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

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

Пример 4.1.

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

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

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

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

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

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

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

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

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

4.2   

В зависимости от величины структурных изменений в генах и хромосомах мутации делятся на несколько типов. В разделе 3.2. был введен простейший тип мутаций - точечная мутация, которая в общем случае 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