Скачать реферат, курсовой Реферат Генетические алгоритмы бесплатно

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

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

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

ген 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() 1), если решается задача минимизации функции ;

Из выражения (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() в данном случае просто совпадает с критерием оптимальности F(Х1,X2) - общей суммой весов ребер, входящих в подграфы G1 и G2: m() = F(Х1,X2).

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

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

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

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

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

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

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

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

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

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

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

d[E,E]= EÅ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-м локусе (1fmifn).

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗИГОТЫ

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

А

а

А

а

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

—

"отцовская"

А

а

а

А

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Назад | Далее
В начало реферата

Если у вас есть аналогичные работы Реферат "Генетические алгоритмы " сообщите нам об этом. Также нам будет интересны рефераты, дипломные работы по теме Реферат "Генетические алгоритмы ", а также курсовые работы. Присылайте их нам, помогите в учебе другим людям.

Скачайте и откройте один из архивов. После этого вам будет доступен для скачивания файл: Скачать реферат, курсовой Реферат Генетические алгоритмы бесплатно . Если файл не скачивается, воспользуйтесь дополнительной ссылкой и распакуйте следующий архив.
	Скачать реферат, курсовой Реферат Генетические алгоритмы бесплатно
	Зеркало: Скачать реферат, курсовой Реферат Генетические алгоритмы бесплатно
	Зеркало 2: Скачать реферат, курсовой Реферат Генетические алгоритмы бесплатно
	Файл: Скачать реферат, курсовой Реферат Генетические алгоритмы бесплатно - был проверен антивирусом Kaspersky Antivirus . Вирусов не обнаружено!