Символьная модель и интерпретация ее элементов в терминах популяционной генетики

Контрольная работа

на тему:

Символьная модель и интерпретация ее элементов в терминах популяционной генетики

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

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

(2.1)

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

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

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

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

К<2, (2.3)

где .

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

(2.4)

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

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

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

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

Пример 2.1

Пусть =5 и i=19. Тогда согласно соотношения (2.4) можем записать: 1910 = 124 + 023 + 022 + 121 + 120 = 100112 , т.е., бинарная комбинация е5(19) целого числа 19 в алфавите В2 будет иметь вид: 10011.

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

 (2.6)

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

(2.7)

Таким образом, символьная модель экстремальной задачи переборного типа (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). Потребуем, чтобы бинарное значение l

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

(2.8)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(2.10)

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

Фенотипом () особи в рамках экстремальной задачи (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.

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

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

вес разреза Q(Х1,X2) из (1.11);

коэффициент разбиения K(Х1,X2) из (1.13);

сумма весов ребер подграфа G1 f1(Х1) из (1.16);

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

G2 f2(X2) из (1.17).

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

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

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

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

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

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

[E, E]= EE, (2.11)

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

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

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

ср(t)=. (2.12)

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

Di=1-4, (2.13)

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

DБ(t)=. (2.14)

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

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

, (2.15)

где

(2.16)

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

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

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

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

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

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

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