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

<span Times New Roman",«serif»;mso-ansi-language:EN-US">1.<span Times New Roman"">    <span Times New Roman",«serif»">Краткаятеория<span Times New Roman",«serif»; mso-ansi-language:EN-US"><span Times New Roman",«serif»">1.1<span Times New Roman"">     <span Times New Roman",«serif»">Математическая формулировкаэкстремальной задачи однокритериального выбора

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

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

·<span Times New Roman"">    

<img src="/cache/referats/5067/image002.gif" v:shapes="_x0000_i1025"> — внешние параметры, характеризующие внешнюю по отношению к объектусреду и оказывающие влияние на его функционирование;

·<span Times New Roman"">    

<img src="/cache/referats/5067/image004.gif" v:shapes="_x0000_i1026"> — внутренние параметры, характеризующие свойства отдельных элементовобъекта.

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

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

Величины, характеризующие свойства объекта в целом каксистемы, будем называть выходнымипараметрами (характеристиками), которые можно только измерять иливычислять, но непосредственно изменять нельзя. Обозначим их вектором <img src="/cache/referats/5067/image006.gif" v:shapes="_x0000_i1027">

Управляемые переменные <img src="/cache/referats/5067/image008.gif" v:shapes="_x0000_i1028"> и характеристики <img src="/cache/referats/5067/image010.gif" v:shapes="_x0000_i1029"> определяют существенныесвойства исследуемого объекта, а внешние параметры <img src="/cache/referats/5067/image012.gif" v:shapes="_x0000_i1030"> являются, как правило,константами и характеризуют внешнюю среду. При этом внутренние параметры <img src="/cache/referats/5067/image008.gif" v:shapes="_x0000_i1031"><img src="/cache/referats/5067/image014.gif" v:shapes="_x0000_i1032"> играют роль независимыхпеременных, а выходные параметры <img src="/cache/referats/5067/image010.gif" v:shapes="_x0000_i1033"><img src="/cache/referats/5067/image014.gif" v:shapes="_x0000_i1034"> являются зависящими от них величинами.Будем считать, что соотношения, выражающие эти зависимости, заданы в виде“черного ящика”, который имеет nвходов xi,<img src="/cache/referats/5067/image016.gif" v:shapes="_x0000_i1035">

 и sвыходов <img src="/cache/referats/5067/image018.gif" v:shapes="_x0000_i1036">i,<img src="/cache/referats/5067/image020.gif" v:shapes="_x0000_i1037">

В процессе принятия решения значения управляемых переменных <img src="/cache/referats/5067/image008.gif" v:shapes="_x0000_i1038"> могут варьироваться внекоторых пределах, определяемых системой неравенств:

<img src="/cache/referats/5067/image022.gif" v:shapes="_x0000_i1039"><img src="/cache/referats/5067/image016.gif" v:shapes="_x0000_i1040"><img src="/cache/referats/5067/image024.gif" v:shapes="_x0000_i1041">

(1.1)

где <img src="/cache/referats/5067/image026.gif" v:shapes="_x0000_i1042"> -нижнее и верхнеепредельно-допустимые значения, соответственно, для i-ой переменной и j-ойхарактеристики. Область управляемых переменных, в которой выполняется системаограничений (1.1), будем называть областьюпоиска D, а любой вектор <img src="/cache/referats/5067/image008.gif" v:shapes="_x0000_i1043">допустимым решением.

Для выбора из области поиска D одного или нескольких“лучших” допустимых решений часто приходится вводить критерий оптимальности Q — количественный показатель, посредствомкоторого осуществляется объективное измерение в некоторой числовой шкале Yкакого-либо одного наиболее важного для задачи принятия решения выходногопараметра <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">j

i. Здесь под измерениемпо шкале Y понимается отображение Q, которое каждому решению <img src="/cache/referats/5067/image028.gif" v:shapes="_x0000_i1044"> ставит в соответствиечисловую оценку  <img src="/cache/referats/5067/image030.gif" v:shapes="_x0000_i1045">  таким образом, чтобыотношения между числами сохраняли бинарные отношения предпочтения междурешениями:

1)<span Times New Roman""> 

<img src="/cache/referats/5067/image032.gif" v:shapes="_x0000_i1046"> “предпочтительнее” <img src="/cache/referats/5067/image034.gif" v:shapes="_x0000_i1047"><img src="/cache/referats/5067/image014.gif" v:shapes="_x0000_i1048"><img src="/cache/referats/5067/image036.gif" v:shapes="_x0000_i1049"> тогда и только тогда, когда Q(<img src="/cache/referats/5067/image032.gif" v:shapes="_x0000_i1050"><img src="/cache/referats/5067/image034.gif" v:shapes="_x0000_i1051"><img src="/cache/referats/5067/image014.gif" v:shapes="_x0000_i1052">

2)<span Times New Roman""> 

<img src="/cache/referats/5067/image032.gif" v:shapes="_x0000_i1053">  “не менее предпочтительнее” <img src="/cache/referats/5067/image034.gif" v:shapes="_x0000_i1054"><img src="/cache/referats/5067/image014.gif" v:shapes="_x0000_i1055"><img src="/cache/referats/5067/image038.gif" v:shapes="_x0000_i1056">  тогда и только тогда, когда Q(<img src="/cache/referats/5067/image032.gif" v:shapes="_x0000_i1057"><img src="/cache/referats/5067/image040.gif" v:shapes="_x0000_i1058"> Q(<img src="/cache/referats/5067/image034.gif" v:shapes="_x0000_i1059">

3)<span Times New Roman""> 

<img src="/cache/referats/5067/image032.gif" v:shapes="_x0000_i1060"> “эквивалентно” <img src="/cache/referats/5067/image034.gif" v:shapes="_x0000_i1061"><img src="/cache/referats/5067/image014.gif" v:shapes="_x0000_i1062"><img src="/cache/referats/5067/image042.gif" v:shapes="_x0000_i1063">  тогда и только тогда, когда Q(<img src="/cache/referats/5067/image032.gif" v:shapes="_x0000_i1064"><img src="/cache/referats/5067/image034.gif" v:shapes="_x0000_i1065">

(1.2)

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

<img src="/cache/referats/5067/image044.gif" v:shapes="_x0000_i1066"><img src="/cache/referats/5067/image046.gif" v:shapes="_x0000_i1067">

(1.3)

где <img src="/cache/referats/5067/image048.gif" v:shapes="_x0000_i1068">оптимальное решение;<img src="/cache/referats/5067/image050.gif" v:shapes="_x0000_i1069">  — наименьшее значениекритерия оптимальности, получаемое при принятии оптимального решения <img src="/cache/referats/5067/image052.gif" v:shapes="_x0000_i1070">

Выражение (1.3) являетсяматематической записью модели принятия оптимального решения, называемой экстремальной задачей однокритериальноговыбора. В том случае, когда решение задачи (1.3) можно свести к анализу значенийкритерия оптимальности Q для конечного числа решений <img src="/cache/referats/5067/image054.gif" v:shapes="_x0000_i1071"> (например, заданныхчислом перестановок n<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">!

, числом сочетаний <img src="/cache/referats/5067/image056.gif" v:shapes="_x0000_i1072"> или просто дискретныммножеством допустимых вариантов) экстремальная задача однокритериального выбораотносится к классу экстремальных задач переборноготипа [1]. 1.2<span Times New Roman"">   

Минимизируемая многопараметрическая функция <img src="/cache/referats/5067/image057.gif" v:shapes="_x0000_i1073"><img src="/cache/referats/5067/image008.gif" v:shapes="_x0000_i1074"> , может быть какунимодальной, так и многоэкстремальной функцией. Независимо от вида функции <img src="/cache/referats/5067/image057.gif" v:shapes="_x0000_i1075">  оптимальное решение <img src="/cache/referats/5067/image052.gif" v:shapes="_x0000_i1076">  должно удовлетворятьусловию:

<img src="/cache/referats/5067/image060.gif" v:shapes="_x0000_i1077"> для всех <img src="/cache/referats/5067/image054.gif" v:shapes="_x0000_i1078">

(1.4)

В случае унимодальнойфункции (одно-экстремальной функции, которая может быть разрывной, недифференцируемой и т.д.) оптимальное решение задачи (1.3) является единственными достигается в точке локального минимума<img src="/cache/referats/5067/image048.gif" v:shapes="_x0000_i1079">

<img src="/cache/referats/5067/image060.gif" v:shapes="_x0000_i1080">          для всех <img src="/cache/referats/5067/image062.gif" v:shapes="_x0000_i1081">

(1.5)

где  <img src="/cache/referats/5067/image064.gif" v:shapes="_x0000_i1082"><span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">e

-окрестность точки локального минимума <img src="/cache/referats/5067/image052.gif" v:shapes="_x0000_i1083">

В случае многоэкстремальнойфункции (функции <img src="/cache/referats/5067/image057.gif" v:shapes="_x0000_i1084"><img src="/cache/referats/5067/image066.gif" v:shapes="_x0000_i1085"> в области поиска D)оптимальное решение задачи (1.3) является глобальнымминимумом — наименьшим из всех локальных минимумов:

<img src="/cache/referats/5067/image068.gif" v:shapes="_x0000_i1086"><img src="/cache/referats/5067/image070.gif" v:shapes="_x0000_i1087">

(1.6)

где  <img src="/cache/referats/5067/image072.gif" v:shapes="_x0000_i1088">  — к-ыйлокальный минимум функции <img src="/cache/referats/5067/image057.gif" v:shapes="_x0000_i1089">

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

В общем случае оптимальное решение задачи (1.3) можетдостигаться на некотором подмножестве допустимых решений <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">W

<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">ÍD, удовлетворяющих условию:

<img src="/cache/referats/5067/image057.gif" v:shapes="_x0000_i1090">* для всех <img src="/cache/referats/5067/image074.gif" v:shapes="_x0000_i1091">

(1.7)

Тогда, в зависимости от постановки задачи однокритериальноговыбора, требуется либо перечислить все решения, принадлежащие подмножеству <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">W

,либо указать любое одно из решений этого подмножества.<span Arial",«sans-serif»;mso-fareast-font-family:«Times New Roman»;mso-bidi-font-family: «Times New Roman»;mso-ansi-language:RU;mso-fareast-language:RU;mso-bidi-language: AR-SA">
1.3<span Times New Roman"">   

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

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

<span Times New Roman"">                       

<span Times New Roman"">                       

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

<span Times New Roman"">                       

<span Times New Roman"">                       

<img src="/cache/referats/5067/image076.gif" v:shapes="_x0000_i1092">

1.8

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

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

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

<span Arial",«sans-serif»; mso-bidi-font-family:«Times New Roman»;position:relative;top:17.0pt; mso-text-raise:-17.0pt"><img src="/cache/referats/5067/image078.gif" v:shapes="_x0000_i1093">

<span Arial",«sans-serif»;mso-bidi-font-family:«Times New Roman»">

(1.12)

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

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

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

<span Times New Roman",«serif»">2.<span Times New Roman"">     <span Times New Roman",«serif»">СИМВОЛЬНАЯ МОДЕЛЬ И ИНТЕРПРЕТАЦИЯЕЕ ЭЛЕМЕНТОВ В ТЕРМИНАХ ПОПУЛЯЦИОННОЙ ГЕНЕТИКИ<span Times New Roman",«serif»">2.1<span Times New Roman"">     <span Times New Roman",«serif»">Представление допустимых решенийэкстремальной задачи в виде бинарных строк

Допустимое решение  <img src="/cache/referats/5067/image080.gif" v:shapes="_x0000_i1094"> экстремальной задачиоднокритериального выбора (1.3) является n-мерным вектором  <img src="/cache/referats/5067/image082.gif" v:shapes="_x0000_i1095"><img src="/cache/referats/5067/image084.gif" v:shapes="_x0000_i1096"> вектора <img src="/cache/referats/5067/image080.gif" v:shapes="_x0000_i1097"> <img src="/cache/referats/5067/image014.gif" v:shapes="_x0000_i1098">

<img src="/cache/referats/5067/image087.gif" v:shapes="_x0000_i1099">

(2.1)

где (Ki+1)- число возможных дискретных значенийi-ой управляемой переменной в области поиска D. Это позволяет поставить вовзаимно однозначное соответствие каждому вектору <img src="/cache/referats/5067/image080.gif" v:shapes="_x0000_i1100"> вектор <img src="/cache/referats/5067/image090.gif" v:shapes="_x0000_i1101">  с целочисленными компонентами:

(x<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">1

, ..., xn)<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">«(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">b1,..., <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">bn),

(2.2)

где для каждой компоненты <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">b

i,<img src="/cache/referats/5067/image092.gif" v:shapes="_x0000_i1102"> областью возможныхзначений являются целые числа от 0 до Кi.

          Введемалфавит В2, содержащий только два символа 0 и 1: В2={0,1}.Для того, чтобы представить целочисленный вектор <img src="/cache/referats/5067/image090.gif" v:shapes="_x0000_i1103"><span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">b

1,...,<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">bn) в алфавите В2 необходимо определитьмаксимальное число двоичных символов <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">q, которое достаточно дляпредставления в двоичном коде любого значения <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">biиз области его допустимых значений [0,Ki]. Нетрудно видеть, чтопараметр символьной модели <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">q должен удовлетворять неравенству:

К<2<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">q

,

(2.3)

где  <img src="/cache/referats/5067/image094.gif" v:shapes="_x0000_i1104">.

Запись произвольного целого неотрицательного числа <img src="/cache/referats/5067/image096.gif" v:shapes="_x0000_i1105"> с помощью <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">q

двоичных символов определяется соотношением :

<img src="/cache/referats/5067/image098.gif" v:shapes="_x0000_i1106">

(2.4)

где <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">a

l<img src="/cache/referats/5067/image014.gif" v:shapes="_x0000_i1107">-двоичное число, равное 0 или 1;

<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">q

-длинадвоичного слова, кодирующего целое число <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">bi.

Тогда символьная запись целочисленного кода <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">b

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

е<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">q

(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">bi):

<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">a

1

<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">a

2

...

<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">a

<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">q

(2.5)

<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">¬

<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">¾¾¾  <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">q  <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">¾¾¾<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">®

где <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">a

l, <img src="/cache/referats/5067/image100.gif" v:shapes="_x0000_i1108">  — двоичные символы (0или 1), полученные из соотношения (2.4).

Пример 2.1.<img src="/cache/referats/5067/image014.gif" v:shapes="_x0000_i1109">

Пусть  <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">q

=5 и <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">bi=19.Тогда согласно соотношения (2.4) можем записать: 1910 = 1<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">´24+ 0<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">´23+ 0<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">´22+ 1<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">´21+ 1<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">´20= 100112, т.е., бинарная комбинация е5(19) целого числа 19 в алфавите В2будет иметь вид: 10011.

Для представления допустимого решения <img src="/cache/referats/5067/image080.gif" v:shapes="_x0000_i1110">  экстремальной задачи(1.3) в алфавите В2 объединим символьные записи е<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">q

(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">bi), описывающие все nкомпонент вектора <img src="/cache/referats/5067/image008.gif" v:shapes="_x0000_i1111"> , в виде линейнойпоследовательности из бинарных комбинаций (2.5):

<img src="/cache/referats/5067/image103.gif" v:shapes="_x0000_i1112">

(2.6)

Записи (2.6) соответствует (n<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">´

<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">q)-битоваястрока из двоичных символов (0,1):

<img src="/cache/referats/5067/image104.gif" " v:shapes="_x0000_s1032"><img src="/cache/referats/5067/image105.gif" " v:shapes="_x0000_s1035"><img src="/cache/referats/5067/image104.gif" " v:shapes="_x0000_s1040"><img src="/cache/referats/5067/image105.gif" " v:shapes="_x0000_s1043"><img src="/cache/referats/5067/image106.gif" " v:shapes="_x0000_s1030"><img src="/cache/referats/5067/image107.gif" " v:shapes="_x0000_s1028">

e<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">q

(<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">b1)

e<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">q

(<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">b2)

e<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">q

(<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">bn)

<img src="/cache/referats/5067/image109.gif" v:shapes="_x0000_i1113">

<img src="/cache/referats/5067/image111.gif" v:shapes="_x0000_i1114">

...

<img src="/cache/referats/5067/image113.gif" v:shapes="_x0000_i1115">

<img src="/cache/referats/5067/image115.gif" v:shapes="_x0000_i1116">

...

<img src="/cache/referats/5067/image117.gif" v:shapes="_x0000_i1117">

...

<img src="/cache/referats/5067/image119.gif" v:shapes="_x0000_i1118">

...

<img src="/cache/referats/5067/image121.gif" v:shapes="_x0000_i1119">

(2.7)

<img src="/cache/referats/5067/image122.gif" v:shapes="_x0000_s1027"><img src="/cache/referats/5067/image123.gif" v:shapes="_x0000_s1026">

n<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">´

<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">q

Таким образом, символьнаямодель экстремальной задачи переборного типа (1.3) может бытьпредставлена в виде множества бинарных строк (2.7), которые описывают конечное множество допустимых решений <img src="/cache/referats/5067/image125.gif" v:shapes="_x0000_i1120">принадлежащих областипоиска D.

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

Представим дихотомическое разбиение (X1,X2)графа G(X,V,W) порядка n в виде бинарной строки E (X1,X2),состоящей из n бит, расположенных в порядкевозрастания их номеров. Каждому номеру бита поставим в взаимнооднозначноесоответствие номер вершины графа (1-ый бит соответствует вершине x1,2-ой бит — вершине x2,…, n-ый бит — вершине xn). Потребуем, чтобы бинарноезначение <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">a

l

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

<img src="/cache/referats/5067/image126.gif" v:shapes="_x0000_s1033"><img src="/cache/referats/5067/image127.gif" " v:shapes="_x0000_s1031">

1, если l-ая вершина xl<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">Î

X входит в состав подмножества вершин X1;

<img src="/cache/referats/5067/image128.gif" v:shapes="_x0000_s1036 _x0000_s1037 _x0000_s1038"><span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">a

l =

(2.8)

<img src="/cache/referats/5067/image129.gif" " v:shapes="_x0000_s1029"><img src="/cache/referats/5067/image130.gif" v:shapes="_x0000_s1041">

0, если l-ая вершина xl<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">Î

X входит в состав подмножества вершин X2

При этом каждая бинарная строкаE(X1,X2) должна удовлетворять дополнительному требованию,связанному с сутью дихотомического разбиения: “число битов, содержащих “<st1:metricconverter ProductID=«1”» w:st=«on»>1”</st1:metricconverter> вбинарной строке E (X1,X2), должно равняться мощности подмножества вершин подграфа G1(X1,V1,W1), равной порядку этого подграфа n1”.

Так, разбиения (X1,X2) и <img src="/cache/referats/5067/image132.gif" v:shapes="_x0000_i1121">

E(X1,X2):

1

1

1

1

1

 

E(X1*,X2*):

1

1

1

1

1

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), видим, что допустимый вектор <img src="/cache/referats/5067/image125.gif" v:shapes="_x0000_i1122"> включает в качествекомпонент все вершины графа G, каждой из которых соответствует целое число <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">b

i, принимающее только два значения 0 или 1 (т.е.Кi =1 для всех <img src="/cache/referats/5067/image016.gif" v:shapes="_x0000_i1123">

Это приводит к тому, что бинарная комбинация е<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">q

(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">bi) состоит из единственного бита, т.к.неравенство (2.3) выполняется при <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">q=1. Однако, линейная последовательность (2.6)принимается в качестве бинарной строки <img src="/cache/referats/5067/image135.gif" v:shapes="_x0000_i1124">1,X2),только в том случае, если число “<st1:metricconverter ProductID=«1”» w:st=«on»>1”</st1:metricconverter>в ней равно порядку n1 графа G1.2.2<span Times New Roman"">   вариабиальныепризнаки

Наименьшей неделимой единицей биологического вида,подверженной действию факторов эволюции, является особь <img src="/cache/referats/5067/image137.gif" v:shapes="_x0000_i1125"> (индекс k обозначает номер особи, а индекс t — некоторый момент времени эволюционного процесса). В качестве аналога особи <img src="/cache/referats/5067/image137.gif" v:shapes="_x0000_i1126"> в экстремальной задачеоднокритериального выбора (1.3) примем произвольное допустимое решение <img src="/cache/referats/5067/image080.gif" v:shapes="_x0000_i1127"><img src="/cache/referats/5067/image137.gif" v:shapes="_x0000_i1128">1,..., xn) — это наименьшая неделимаяединица, характеризующая в экстремальной задаче (1.3) внутренние параметры накаждом t-ом шаге поиска оптимального решения, которыеизменяют свои значения в процессе минимизации критерия оптимальности  Q(<img src="/cache/referats/5067/image008.gif" v:shapes="_x0000_i1129">

В задаче оптимального дихотомического разбиения (1.12) вкачестве особи <img src="/cache/referats/5067/image137.gif" v:shapes="_x0000_i1130"> выступает конкретноедихотомическое разбиение (X1,X2), удовлетворяющееусловиям (1.8) — (1.9), что позволяет интерпретировать сам процесс решенияэкстремальной задачи (1.12) как эволюционный процесс, связанный сперераспределением вершин xi<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">Î

Xграфа G по двум подграфам G1 и G2, соответственно,порядка n1 и n2, с целью отыскания глобального минимумакритерия оптимальности (1.11). В этом и заключается в данном случае цель эволюционногоразвития (эволюции) особей.

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

·<span Times New Roman"">    

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

·<span Times New Roman"">    

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

Качественные признаки особи <img src="/cache/referats/5067/image137.gif" v:shapes="_x0000_i1131"> определяются изсимвольной модели экстремальной задачи (1.3) как соответствующая точке <img src="/cache/referats/5067/image008.gif" v:shapes="_x0000_i1132"> с именем <img src="/cache/referats/5067/image137.gif" v:shapes="_x0000_i1133"> бинарная строка E(<img src="/cache/referats/5067/image008.gif" v:shapes="_x0000_i1134">e<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">q

(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">b1),..., e<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">q(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">bn).

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

В качестве гена — единицы наследственного материала, ответственного за формированиеальтернативных признаков особи, примем бинарную комбинацию e<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">q

(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">bi) из (2.5), которая определяет фиксированноезначение целочисленного кода <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">bi управляемойпеременной xi в обычном двоичном коде.Одна особь <img src="/cache/referats/5067/image137.gif" v:shapes="_x0000_i1135"> будетхарактеризоваться n генами, каждый из которыхотвечает за формирование целочисленного кода соответствующей управляемой переменной.Тогда структуру бинарной строки E(<img src="/cache/referats/5067/image008.gif" v:shapes="_x0000_i1136">хромосомой, содержащей n сцепленных междусобой генов, которые расположены в линейной последовательности “слева — направо”. Согласно хромосомной теории наследственности передача качественныхпризнаков e<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">q(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">bi), <img src="/cache/referats/5067/image016.gif" v:shapes="_x0000_i1137">

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

ген 1

ген 2

ген n

<img src="/cache/referats/5067/image109.gif" v:shapes="_x0000_i1138">

e<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">q

(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">b1)

e<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">q

(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">b2)

...

e<span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">q

(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">bn)

(2.9)

локус 1

локус 2

локус n

<img src="/cache/referats/5067/image139.gif" " v:shapes="_x0000_s1047"><img src="/cache/referats/5067/image140.gif" " v:shapes="_x0000_s1048">

хромосома

где e<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">q

(<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">bi) — аллель i-го гена, находящаяся в локусе i.

Хромосому (2.9), содержащую в своих локусах конкретныезначения аллелей, будем называть генотипом(генетическим кодом) Е(<img src="/cache/referats/5067/image137.gif" v:shapes="_x0000_i1139"><img src="/cache/referats/5067/image137.gif" v:shapes="_x0000_i1140">генофонд. Для дихотомического разбиения мощность генофонда равна<img src="/cache/referats/5067/image142.gif" v:shapes="_x0000_i1141">

При взаимодействии особи <img src="/cache/referats/5067/image137.gif" v:shapes="_x0000_i1142"> с внешней средой еегенотип E(<img src="/cache/referats/5067/image137.gif" v:shapes="_x0000_i1143"><span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">j

i ), включающих сте
еще рефераты
Еще работы по биологии