Реферат: Программированное обучение и контроль по физиологии - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Программированное обучение и контроль по физиологии

Банк рефератов / Медицина и здоровье

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 227 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

1.1 1.2 Задача синтеза стабилизатора напряжения как экстремал ьная задача переборного типа Пусть имеется 4 некоторых множеств X , Y , Z , W функциональных элементов , реализующих различные части схемы стабилизаторов напряжения , Х = х 1 , х 2 , ... , х m , Y = y 1 , y 2 , ... , y n , Z= z 1 , z 2 , ... , z o , W= w 1 , w 2 , ... , w p (банк с хемотехнических решений ). Пусть каждый элемент содержит 4 характеристики , закодированные двоичным кодом : Влияние на петлевое усиление (1 - хорошее , 0 - плохое ); Влияние на К СТ.ИОН. (1 - хорошее , 0 - плохое ); Мощность множества узлов (1 - больш ая , 0 - малая ); Мощность множества связей (1 - большая , 0 - малая ); 1.8 Стабилизатором напряжения (Х 1 , Y 2 , Z 3 , W 4 ) будем называть регулярную стру ктуру (1.8), в которой элементы x , y , z и w описывают источник опорного напряжения , сравнивающее устройство , регулирующий элемент , датчик соответственно . В качестве критерия оптимальности будем рассматривать количество положительных и отрицательных характ еристик. Тогда оптимальный стабилизатор является оптимальным решением (Х 1 , Y 2 , Z 3 , W 4 ) следующей экстремальной задачи однокритериального выбора : , (1.12) где К является суммой всех положительных характеристик для всех элементов стабилизатора. Задача 1.12 относится к экстремальным задачам переборного типа , т.к . общее число допустимых решений равно произведению количества элементов множеств X , Y , Z , W . В дальнейшем все илл юстрации применения генетических алгоритмов к решению экстремальных задач переборного типа будут рассматриваться на примере задачи построения оптимального стабилизатора напряжения. 2. СИМВОЛЬНАЯ МОДЕЛЬ И ИНТЕРПРЕТАЦИЯ ЕЕ ЭЛЕМЕНТОВ В ТЕРМИНАХ ПОПУЛЯЦИОННО Й ГЕНЕТИКИ 2.1 Представление допустимых решений экстремальной задачи в виде бинарных строк Допустимое решение экстремальной задачи однокритериального выбора (1.3) явля ется n-мерным вектором . В том случае , когда задача (1.3) принадлежит классу задач переборного типа , имеется конечное множество допустимых решений , в которых каждая ко мпонента вектора может быть закодирована с помощью целого неотрицательного числа : (2.1) где (K i +1)- число возможных дискретных зна чений i-ой управляемой переменной в области поиска D. Это позволяет поставить во взаимно однозначное соответствие каждому вектору вектор с целочисленными компонентами : (x , ..., x n ) ( 1 ,..., n ), (2.2) где для каждо й компоненты i , областью возможных значений являются целые числа от 0 до К i . Введем алфавит В 2 , содержащий только два символа 0 и 1: В 2 = 0,1 . Для того , чтобы представить целочисленный вектор =( 1 ,..., n ) в алфавите В 2 необходимо определить максима льное число двоичных символов , которое достаточно для представления в двоичном коде любого значения i из области его допустимых значений [0,K i ]. Нетрудно видеть , что параметр символьной модели должен удовлетворять неравенству : К <2 , (2.3) где . Запись произвольного целого неотрицательного числа с помощью двоичных символов определяется соотношением : , (2.4) где l -двоичное число , равное 0 или 1; -длина двоичного слова , кодирующего целое число i . Тогда символьная запись целочисленного кода i для фиксированного значения управляемой переменной х i в обычном двоичном коде запишется в виде следующей бинарной комбинации : е ( i ): 1 2 ... (2.5) где l , - двоичные символы (0 или 1), полученные из соотношения (2.4). Пример 2.1. Пусть =5 и i =19. Тогда согласно соотношения (2.4) можем записать : 19 10 = 1 2 4 + 0 2 3 + 0 2 2 + 1 2 1 + 1 2 0 = 10011 2 , т.е ., бинарная комбинация е 5 (19) целого числа 19 в алфавите В 2 будет иметь вид : 10011. Для представления допустимого решения экстремальной задачи (1.3) в алфавите В 2 объединим символьные записи е ( i ), описывающие все n компонент вектора , в виде линейной последовательности из бинарных комбинаций (2.5): (2.6) Записи (2.6) соответствует (n )-битовая строка из двоичных символов (0,1): e ( 1 ) e ( 2 ) e ( n ) ... ... ... ... (2.7) n Таким образом , символьная модель экстремальной задачи переборного типа (1.3) может быть представлена в виде множества бина рных строк (2.7), которые описывают конечное множество допустимых решений , принадлежащих области поиска D. Необходимо отметить , что выбор символьной модели исходной эк стремальной задачи во многом определяет эффективность и качество применяемых генетических алгоритмов . Для каждого класса задач переборного типа должна строиться своя символьная модель , отражающая специфику и особенности решаемой задачи . В качестве примера приведем символьную модель для задачи (1.12) оптимального дихотомического разбиения графа G(X,V,W). Представим дихотомическое разбиение (X 1 ,X 2 ) графа G(X,V,W) порядка n в виде бинарной строки E (X 1 ,X 2 ), состоящей из n бит , расположенных в порядке возрастан ия их номеров . Каждому номеру бита поставим в взаимнооднозначное соответствие номер вершины графа (1-ый бит соответствует вершине x 1 , 2-ой бит - вершине x 2 , ... , n-ый бит - вершине x n ). Потребуем , чтобы бинарное значение l 1 -ого бита указывало , какому подмножеству вершин (X 1 или X 2 ) принадлежит вершина x l : 1, если l-ая вершина x l X входит в состав подмножества вершин X 1 ; l = (2.8) 0, если l-ая вершина x l X входит в состав подмножества вершин X 2 При этом каждая бинарная строка E(X 1 ,X 2 ) должна удовлетворять дополнительному требованию , связанному с сутью дихотомического разбиения : “число битов , содержащих “ 1” в бинарной стр оке E (X 1 ,X 2 ) , должно равняться мощности подмножества вершин подграфа G 1 (X 1 ,V 1 ,W 1 ) , равной порядку этого подграфа n 1 ”. Так , разбиения (X 1 ,X 2 ) и , приведенные в Таблице 1.1., имеют следующие представления в виде бинарных строк : E(X 1 ,X 2 ): 1 0 0 0 0 0 1 1 0 1 1 0 E(X 1 * ,X 2 * ): 0 1 1 1 1 1 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 -номер бита x 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9 x 10 x 11 x 12 -номер вершины Сравнива я построенную символьную модель экстремальной задачи (1.12) с общей символьной моделью (2.7), видим , что допустимый вектор включает в качестве компонент все вершины гра фа G, каждой из которых соответствует целое число i , принимающее только два значения 0 или 1 (т.е . К i =1 для всех ). Это приводит к тому , что бинарная комбинация е ( i ) состоит из единственного бита , т.к . неравенство (2.3) выполняется при =1. Однако , линейная последовательность (2.6) принимается в качес тве бинарной строки , соответствующей допустимому разбиению (X 1 ,X 2 ), только в том случае , если число “ 1” в ней равно порядку n 1 графа G 1 . 2.2 Особи и их вариабиальные п ризнаки Наименьшей неделимой единицей биологического вида , подверженной действию факторов эволюции , является особь (индекс k обозначает номер особи , а индекс t - некото рый момент времени эволюционного процесса ). В качестве аналога особи в экстремальной задаче однокритериального выбора (1.3) примем произвольное допустимое решение , которому присвоено имя . Действительно , вектор управляемых переменных (x 1 , ..., x n ) - это наименьшая неделимая единица , характеризующая в экстремальной задаче (1.3) внутренние параметры на каждом t-ом шаге поиска оптимального решения , которые изменяют свои значения в процессе минимизации критерия оптимальности Q( ). В задаче оптимального дихотомического разбиения (1.12) в качестве особи выступает конкретное дихотомиче ское разбиение (X 1 ,X 2 ), удовлетворяющее условиям (1.8) - (1.9), что позволяет интерпретировать сам процесс решения экстремальной задачи (1.12) как эволюционный процесс , связанный с перераспределением вершин x i X графа G по дву м подграфам G 1 и G 2 , соответственно , порядка n 1 и n 2 , с целью отыскания глобального минимума критерия оптимальности (1.11). В этом и заключается в данном случае цель эволюционного развития (эволюции ) особей. Для описания особей введем два типа вариабельных признаков , отражающих качественные и количественные различия между особями в степени их выраженности : · качественные признаки - признаки , которые позволяют однозначно разделять совокупность особей на четко различимые группы ; · количественные признаки - признаки , проявляющие непрерывную изменчивость , в связи с чем степень их выраженности можно охарактеризовать числом. Качественные признаки особи определяются из символь ной модели экстремальной задачи (1.3) как соответствующая точке с именем бинар ная строка E( ) и составляющие ее бинарные комбинации e ( 1 ), ..., e ( n ). Приведем интерпретацию этих признаков в терминах хромосомной теории наследственности [4]. В качестве гена - единицы наследственного материала , ответственного за формирование альтернативных признаков особи , примем бинарную комбинацию e ( i ) из (2.5), которая определяет фиксированное значение целочисленного кода i управляемой переменной x i в обычном двоичном коде . Одна особь будет характеризоваться n генами , каждый из которых отвечает за формирование целочисленного кода соответствующей управляемой переменной . Тогда структуру бинарной строки E( ) из (2.7) можно интерпретировать хромосомой , содержащей n сцепленных между собой генов , которые расположены в линейной последовательности “слева - направо” . Согласно хромосомной теории на следственности передача качественных признаков e ( i ), , закодированных в генах , будет осуществляться через х ромосомы от “родителей” к “потомкам”. Местоположение определенного гена в хромосоме называется локусом , а альтернативные формы одного и того же гена , расположенные в одинаковых локусах хромосомы , называются аллелями (аллелеформами ) : ген 1 ген 2 ген n e ( 1 ) e ( 2 ) ... e ( n ) (2.9) локус 1 локус 2 локус n хромосома где e ( i ) - аллель i-го гена , находящаяся в локусе i. Хромосому (2.9), содержащую в своих локусах конкретные значения аллелей , будем называть генотипом (генетическим кодом ) Е ( ), который содержит всю наследственную генетическую информацию об особи , получаемую от “предков” и передаваемую затем “потомкам” . Конечное множество всех допустимых генотипов образует генофонд . Для дихотомического разбиения мощность генофон да равна . При взаимодействии особи с внешней средой ее генотип E( ) порождает совокупность внешне наблюдаемых количественных признаков (характеристик i ), включающих степень приспособленности ( ) особи к внешней среде и ее фенотип ( ). Приняв в качестве внешней среды критерий оптимальности , мы можем говорить , что сте пенью приспособленности ( ) каждой особи является численное значение функции , вычисленное для допустимого решения с именем . В общем случае степень приспособленности можно задать с помощью следующего выражения : Q 2 (x), если решается задача максимизации функции ; ( )= (2.10) 1/(Q 2 ( )+1), если решается задача минимизации функции ; Из выражения (2.10) следует , что чем больше численное значение степени приспособленности ( ), тем лучше особь приспособлена к внешней среде . Следовательно , цель эволюции особей заключается в повышении их с тепени приспособленности. Фенотипом ( ) особи в р амках экстремальной задачи (1.3) являются численные значения вектора управляемых переменных и соответствующих ему характеристик . Для задачи оптимального дихотомического разбиения графа G, сформулированной как экстремальная задача (1.18), в качестве особи выступает конкретное дихотомическое разбиение (Х 1 ,X 2 ), удовлетворяющее условиям (1.8)- (1.9). В этом случае геном является бит в бинарной строке Е (Х 1 ,X 2 ), который определяет , к какой части разбиения Х 1 или Х 2 принадлежит вершина графа G, с оответствующая этому биту . Линейная последовательность всех n битов составляет хромосому , в которой каждый ген определяет принадлежность вершины , соответствующей этому гену , одной из частей Х 1 или Х 2 . Введенные гены обладают свойством диморфизма , т.к . кажд ый ген может иметь только две различающиеся формы аллели : “ 1” , если вершина х i принадлежит части Х 1 и “0” , если вершина х i принадлежит части Х 2 . Степень приспособленности ( ) в данном случае просто совпадает с критерием оптимальности F(Х 1 ,X 2 ) - общей суммой весов ребер , входящих в подграфы G 1 и G 2 : ( ) = F(Х 1 ,X 2 ). В состав фенотипа ( ) особи , кроме разбиения (Х 1 ,X 2 ), входят следующие количественные признаки : · вес разреза Q(Х 1 ,X 2 ) из (1.11); · коэффициент разбиения K(Х 1 ,X 2 ) из (1.13); · сумма весов ребер подграфа G 1 f 1 (Х 1 ) из (1.16); · сумм а весов ребер подграфа · G 2 f 2 (X 2 ) из (1.17). 2.3 Популяции и поколения В качестве ареала - области , в пределах которой только и могут встречаться особи , участвующие в эволюционном процессе , будем рассматривать область поиска D. В задаче дихотомическог о разбиения ареал полностью определяется структурой графа G(X,V,W), заданной множеством вершин X и множеством ребер V, а также порядком подграфа G 1 (или подграфа G 2 ). Совокупность особей , принадлежащих ареалу , образует популяцию P t . Число , характеризующее число особей , которые образуют популяцию , будем называть численностью популяции. В общем случае экстремальной задачи (1.3) популяция P t = соответствуют совокупности допустимых решений , . Для задачи оптимальн ого разбиения графа G популяция P t представляет собой набор из дихотомических разбиений , , удовлетворяющих условиям (1.8) - (1.9). Очевидно , что в популяции P t может иметь место наличие нескольких различающихся форм того или иного вариабельного признака (так называемый полиморфизм ), что позволяет прово дить разделение популяции на ряд локальных популяций , , включающих в свой сост ав те особи , которые имеют одинаковые или “достаточно близкие” формы тех или иных качественных или /и количественных признаков. Так , в задаче оптимального дихотомического разбиения (1.11) для дифференциации особей по количественному признаку может быть выбрано , например , условие , что в локальную популяцию включаются только те особи, у которых значение веса разреза Q(Х 1 ,X 2 ) не превосходит некоторой заданной величины Q + : Q(Х 1 ,X 2 ) . Тогда другую локальную популяцию составят все те особи , которые не попали в , т.е . особи , для которых вес разреза удовлетворяет условию : Q(Х 1 ,X 2 ) . В том случае , когда для дифференциации особей используется качественный признак , например , генотип E(Х 1 ,X 2 ), в качестве мер ы “близости” особей и по этому признаку можно использовать Хэммингово расстояни е , которое определяется как число несовпадающих по своим значениям битов в n -битовых бинарных строках E и E : d[E , E ]= E E , (2.11) где - операция суммирования по mod.2 Тогда в локальную популяцию будем включать только те особи , у которых Хэммингово расстояние меньше заданного неотрицательного целого числа 0, а в локальную попу ляцию - те особи , для генотипов которых это условие не выполняется . При =0 в локальную популяцию будут включены только те особи , генотипы которых совпадают между собой. Будем считать , что во времени популяции P t состоят из дискретных , не перекрывающихся между собой поколений , - групп особей , одинаково о тдаленных в родственном отношении от общих предков , т.е . каждое последующее поколение P t+1 является совокупностью из особей , которые отбираются только из особей предыдущего t-го поколения . Будем отождествлять номер поколения (верхний индекс t в обозначениях особи и популяции P t ) с моментом времени t=0,1,...,Т , где Т - жизненный цикл популяции , определяющий период ее эволюции . В дальнейше м эволюцию популяции P t будем понимать в ограниченном смысле как чередование поколений , в процессе которого особи изменяют свои вариабельные признаки таким образом , чтобы каждая следующая популяция проявляла лучшую степень приспособленности к внешней среде , например , в смысле обеспечения наибольшего значения средней степени приспособленности по популяции P t : ср (t)= . (2.12) Совокупность из генотипов всех особей , составляющих популяцию P t , образует хромосомный набор, который полностью содержит в себе генетическую информацию о популяции P t в целом . Наличие изменчивости хромосомного набора от поколения к поколению является необходимым условием эволюции популяции P t на генетическом уровне . Для оценки разнообразия генотипов популяции P t введем в рассмотрение функцию диаллейного разнообразия по каждому биту хромосомного набора : D i =1-4 , (2.13) где i -число нулей в i-ом бите хромосомн ого набора популяции P t ; - численность популяции P t . Тогда побитовое разнообразие популяции P t определим как среднее значение диаллельных разнообразий по всем (n ) битам хромосомного набора : D Б (t) = . (2.14) При D Б (t) =1 имеем максимальное разнообразие генотипов в популяции P t ; при D Б (t) =0 все генотипы в хромосомном наборе совпадают между собой. Обобщением побитового разнообразия на общий случай э кстремальной задачи (1.3) является генетическое разнообразие популяции P t по всем n локусам : , (2.15) где (2.16) - функция аллельного разнообразия в i-ом локусе ; - частота аллельной формы e (k) в i-ом локусе ; i - число генотипов в хромосомном наборе популяции P t , в которых i-ый локус содержит аллельную форму ; - численность популяции P t ; m i - число форм аллелей в i-м локусе (1 m i ). Когда все генотипов имеют в i-м локус е одну и ту же аллельную форму D (i)=0; если аллельные формы в i-м локусе всех генотипов хромосомного набора отличаются друг от друга ( i =1), то D (i)=1. По хромосомному набору популяции P t можно также определить частоту генотипа P(E( )) как долю особей , имеющих одинаковую форму генотипа в рассматриваемой по пуляции P t . 3. ВЗАИМОДЕЙСТВИЕ ОСНОВНЫХ ФАКТОРОВ ЭВОЛЮЦИИ ПОПУЛЯЦИИ В ТЕЧЕНИЕ ЖИЗНЕННОГО ЦИКЛА 3.1 Размножение особей , поддерживающее наследственную преемственность “потомками” признаков “родителей” Будем считать , что популяция представляет собой репродукционную группу - совокупность из особей , любые две из которых могут размножаться , выступая в роли “родителей” ( - “мать” ; - “от ец” ). Здесь под размножением понимается свойство особей P t воспроизводить одного или нескольких себе подобных непосредственных “потомков ” (“детей” ) , 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. 3.2 Приобретение особями новых качественных признаков В результате размножения воспроизводятся “потомки” , обладающие свойст вом преемственности наследственных признаков (генов ) “родителей” . При этом генотипы “потомков” , как правило , содержат новые сочетания аллельных форм генов “родителей” , ведущие к новым количественным признакам “потомков” (фенотипу и степени приспособленнос т и ). Однако , генетическая информация , содержащаяся в хромосомном наборе “родителей” и “потомков” , не меняется , т.к . в результате размножения особей путем сигнамии и мейоза частоты аллелей остаются постоянными , а меняются только частоты генотипов . Источнико м генетической изменчивости особей являются мутации - изменения качественных признаков особей в результате появления новых аллельных форм в отдельных генах или целиком во всей хромосоме . Тем самым в каждом поколении мутации поставляют в хромосомный набор по пуляции множество различных генетических вариаций , присущих особям , которых в дальнейшем будем называть мутантами . Процесс изменения содержания генов в хромосоме особе й путем мутаций называется мутагенезом. По сути дела , этот фактор эволюции популяции является источником новой генетической информации , не содержащейся ранее в генах генотипов “родителей” и их “потомков”. Мутации являются случайными в том смысле , что не за висят ни от генетического кода особи , содержащегося в ее генотипе , ни от количественных значений фенотипа и степени приспособленности особи . Они происходят спонтанно с определенными вероятностями , заменяя в одном или нескольких локусах тех или иных генов а ллельные формы последних новыми значениями аллелей , которые принадлежат генофонду и отличаются от аллелей всех “родительских” генотипов в том же самом локусе (гене ). Мутации происходят независимо от того , приносят ли они особи вред или пользу . Они не напра влены на повышение или понижение степени приспособленности особи , а только производят структурные изменения в аллельных формах генов , меняя тем самым частоту аллелей по отдельным локусам в хромосомном наборе текущего поколения , что , в свою очередь , привод и т к изменению количественных признаков особи . В принципе , комбинация мутаций может привести к возникновению новых форм аллелей в некоторых генах генотипа мутанта , которые обеспечивают увеличение его степени приспособленности к внешней среде . Эволюция попу ляции в течение смены нескольких поколений в смысле изменения генетической наследственности представляет из себя процесс одновременного и постепенного изменения как частот , так и форм аллелей в различных локусах хромосомы . При этом аллели действуют на кол и чественные признаки не изолированно друг от друга . Так , влияние того или иного аллеля на степень приспособленности особи зависит от присутствия или отсутствия в его генотипе других аллелей . Набор аллелей каждого локуса взаимно приспособлен ( коадаптирован ) с набором аллелей других локусов . Поэтому изменение частот аллелей в одном локусе влечет за собой изменение частот аллелей и в других локусах. Наиболее простым видом мутаций является точечная мутация, связанная с изменением аллеля “родительского” гена в од ном из бит генной информации (0 заменяется на 1 или 1 заменяется на 0). Определим интенсивность процесса мутагенеза в t-м поколении как среднее число точечных мутаций M T (t), которые могут произойти в хромосомном наборе t- ой популяции P t : M т (t)= (n ) P m , (3.1) где - численность популяции P t ; n - длина хромосомы , равная числу битов в бинарной строке ; P m - вероятность точечной мутации, определяемая как число возможных однобитовых изменений на 100 бит генетической информации. Обычно вероятность точечной мутации в популяции очень мала (P m =0.01 или P m =0.001), что приводит к невысокому темпу возникновения мутаций . Например , при =10, n=12, =32 и P m =0.01 получаем , что в среднем в каждом поколении будет приходить 38 точечных мутаций. Подробно вопросы реализации процесса мутагенеза будут рассмотрены в разделе 6. 3.3 Базовая структура генетического алгоритма , моделирующего эволюционное развитие популяции Обобщая вышесказанное , цель эволюции первоначально заданной популяции в течение жизненного цикла T, можно сфо рмулировать следующим образом . Отношения между особями и внешней средой , приводящие к избирательной элиминации (“гибели” ) менее приспособленных и выживанию более приспособленных особей , должны быть построены таким образом , чтобы в течение смены поколений в хромосомном наборе популяции накапливались такие новые качественные признаки (гены и генотипы ), которые обеспечивают увеличение средней степени приспособленности особей по популяции в целом : (3.3) При этом генотипы особей , t=0,1,2, ...,T, заданные с помощью бинарных строк E( ), в процессе своего преобразования в результате факторов эв олюционного развития популяции по Дарвину в каждом поколении должны обладать следующими свойствами : · наследственности , которая закрепляет у “потомков” лучшие признаки , полученные от “родителей” в результате их размножения ; · изменчивости , которая служит основой образования новых признаков за счет изменения генетического состава популяции в результате мутаций ; · соревновательности , которая определяет направление генетических изменений в популяции в результате естественного отбора по степени приспособленн ости особей к условиям внешней среды . В дальнейшем под генетическим алгоритмом будем понимать алгоритмический подход к решению экстремальных задач однокритериального выбора , основанный на моделировании основных факторов эволюционного развития популяции. Б ольшую роль в развитии генетических алгоритмов сыграли I. Holland [5], D. Goldberg [6] и L. Davis [7], которые заложили и развили теоретические основы генетического подхода к решению задач оптимизации . Не останавливаясь на обзоре этих работ , приведем обоб щенную схему генетического алгоритма , структура которого является типичной для широкого круга публикаций по этому вопросу. Базовая структура “Генетического алгоритма” : I. Формирование начальной популяции P 0 из особей : A. Генерация хромосомного набора из бинарных строк E( ), удовлетворяющих требованиям , предъявляемым к символьной модели исходной экстремальной задачи . B. Преобразование бинарных строк E( ) в соответствующие им векторы управляемых переменных и вычисление степени приспособленности ( ) для каждой особи , обладающей генотипом E( ). C. Особи образуют начальную популяцию P t для поколения t=0. II. Воспроизводство “потомков” с наследственными признаками “родителей” : A. В ыбор конкретной “родительской” пары для участия в процессе размножения. B. Выбор схемы размножения. C. Построение по выбранной схеме из генотипов “родителей” E( ), генотипов их “потомков” , сохраняющих наследственные признаки “родителей” . D. Преобразование бинарных строк в соответствующие векторы управляемых переменных и вычисление степени приспособленности “потомков” , обладающих генотипами E( ). E. Вычисления повторяются с шага 2.1. до тех пор , пока не будет воспроизведено заданное число “потомков” . III. Мутагенез , приводящий к генетическим изменениям “родитель ских” признаков : A. Выбор типа мутации. B. Построение по генотипу E( ) одной из особей P t генотипа особи - ”мутанта” с п омощью конкретного типа мутации. C. Преобразование бинарной строки в соответствующий вектор управляемых переменных и вычисление степени приспособленности особи - ”мутанта” , обладающей генотипом E( ). D. Вычисления повторяются с шага 3.1. до тех пор , пока не будет создано заданное число “мутантов”. IV. Естественный отбор : A. Определение среди “родителей” , “потомков” и “мутантов” особей , образующих репродуктивную груп пу , которая примет участие в естественном отборе. B. Выбор схемы естественного отбора. C. Формирование по выбранной схеме хромосомного набора популяции следующего поколения из особей , принадлежащих репродукционной группе. V. Проверка условий окончания процесса эволюции популяции P. Если условия окончания процесса эволюции не выполнены , то происходит смена поколений и все вычисления для популяции следующего (t+1) - го пок оления P t+1 повторяются с шага 2. В качестве условий окончания процесса эволюции популяции может использоваться одно из следующих неравенств : t T (3.4) или D Б (t)=0. (3.5) Выполнение неравенства (3.4) означает , что эволюция популяции закончена в связи с тем , что она исчерпала свой жизненный цикл ; окончание эволюции популяции при равенстве побитового разнообразия текущей популяции P t нулю означает , что все генотипы в хромосомном наборе популяции P t совпадают между собой. В зак лючение данного раздела приведем отличия генетических алгоритмов от поисковых методов оптимизации [6]. 1. Генетические алгоритмы осуществляют прямое манипулирование бинарными строками E( ), с помощью которых закодированы в двоичном коде допустимые решения , а не самими внутренними параметрами , заданными действительными числами. 2. Генетические алгоритмы в каждом t-ом поколении оперируют одновременно со всей совокупностью из допустимых решений , образующих популяцию P t , с целью получения хромосомного набора популяции следующего поколения P t+1 . Таким образом генетические алгоритмы на каждой итерации , совпадающей с текущим поколением , по зволяют определять новых допустимых решений, в то время как классические методы поиска [8] на каждой итерации определяют единственное новое допустимое решение . Например , градиентный метод минимизации реализуется с помощью ре куррентного выражения : , k=0,1,2,... (3.6) где - начальное приближение ; - градиент минимизируемой функции ; - шаг вдоль градиента. 3. Генетические алгоритмы основаны на вероятностных схемах преобразования бинарных ст рок E( ), составляющих хромосомный набор популяции P t , которые моделируют биологические механизмы популяционной генетики [4]. 4. Генетические алгоритмы - это методы нуле вого порядка, стратегия поиска , в которых построена только на вычислении значений критерия оптимальности Q и не требует знания дополнительной информации о производных , константе Липшица и т.д ., что характерно для градиентных и квази-ньютоновских методов [ 8]. 5. Генетические алгоритмы являются робастными методами по отношению к виду минимизируемой функции, т.к . при их применении не требуется , чтобы критерий оптимальности был непрерывным , дифференцируемым , унимодальным и т.д . Они осуществляют поиск оптимальн ого решения по одной и той же стратегии как для унимодальных , так и для многоэкстремальных функций. 4. СХЕМЫ РАЗМНОЖЕНИЯ ОСОБЕЙ 4.1 Рекомбинация генов Пусть особи и с различающимися между собой генотипами E( ) и E( ) являются "родительской " парой , которая образована из особей популяции P t по одной из рассмотренных в разделе 4 систем скрещивания . Под рекомбинацией генов будем понимать схему размножения особей , которая моделирует акты сигнамии и мейоза , удовлетворяющие законам наследственности Менделя . По своей сути рекомбинация генов ведет к появлению новых сочетаний "родите льских " генов , так как аллель любого гена "родительской " гомологичной хромосомы , согласно первого закона Менделя , целиком передается "потомку " по наследству . При этом гомологичные хромосомы "родителей " сравниваются по содержанию каждого гена . Если аллели в i-ом локусе одинаковы у "отцовской " и "материнской " хромосом , то аллель e (i) сохраняется в i-ом гене "потомка ". В противном случае в i-ый локус гаметы "потомка " заносится с вероятностью (1/2) либо аллель , либо а ллель . Эта операция случайного расхождения "родительских " генов по гаметам "потомков ", согласно второго закона Менделя , проводится для всех "родительских " генов , для к оторых аллели не совпадают между собой . Рекомбинация генов позволяет воспроизвести два типа "потомков ": · копию одной из "родительских " гамет ("отца " или "матери " ); · гамету одного из "родителей ", в которой некоторые гены имеют аллелеформы другого "родителя ". На рис . 5.1. приведен пример воспроизводства двух гибридных гамет "по томков " ( ), образованных из "родительской " пары с помощью рекомбинации генов. " Отцовская " гамета "Материнская " гамета E( ): e (1) e (3) E( ): e (1) e (3) 1 2 3 4 1 2 3 4 Гибридные гаметы “потомков” и : e (1) e (3) 1 2 3 4 Гибридные гаме ты “потомков” и E( ): e (1) e (3) 1 2 3 4 Рис. 4 .1. Воспроизводство "потомства " путем рекомбинации генов (гены 1 и 3 являются гомозиготами , а гены 2 и 4 - гетерозиготами ). В некоторых случаях какие-то аллели могут оказывать боле е сильное влияние на соответствующий признак особи и в процессе рекомбинации генов им необходимо отдавать большее предпочтение при формировании генов в гаметах "потомков ". Будем называть рецессивным аллелем аллельную форму a , которая проявляется лишь в г омозиготе (aa), когда "родители " имеют одинаковые аллели в рассматриваемом локусе аллельного гена , а доминантным аллелем - аллельную форму A, которая проявляется не то лько в гомозиготе (AA), но и в гетерозиготах (Aa или aA). Взаимоотношение двух введенных аллелей a и A в конкретном локусе гомологичных хромосом зиготы обладает свойством доминантности (доминирования ) , которое заключается в том , что доминантный аллель A всегда передается "потомку " независимо от того , принадлежит ли он "материнской " или "отцовской " гамете (рис .5.2), т.е . доминантный аллель A оказывает более сильное влияние на соответствующий признак "потомка " по сравнению с рецессивным аллелем a. "Отцовск ая " гамета E( ): А а " Материнская " гамета E( ): а А 1 1 Гамета "потомка " : А А а )доминантный аллель A принадлежит "отцовской” гамете б )доминантный аллель A принадлежит " материнской“ гамете Рис .5.2. Доминирование доминантного аллеля A над рецессивным аллелем a. Для учета доминантности некоторых из аллельных форм e (k), , можно воспользоваться частотой аллели e (k), наход ящейся в i-м локусе хромосомного набора популяции P t : , , (4.1) где - численность популяции P t ; i - число генотипов в хромосомном наборе популяции P t , в которых i-ый локус содержит аллельную форму e (k); m i - число форм аллеле й в i-м локусе (1 m i ). Тогда , если P(e (k),i) > P(e (j),i), то аллель e (k) считается доминантным аллелем ; это приводит к тому , что при наличии в i-м аллельном гене двух аллелей e (k) и e (j),в i-ый локус гаметы "потомка " заносится доминантный аллель e (k) с вероятностью 1 вместо вероятности (1/2), принятой для рекомбинации генов без доминирования . В качестве иллюстрации приведем реализацию схемы размножения особей путем рекомбинации генов для задачи оптимального разбиения графа G(X,V,W) порядка n на два подграфа G 1 (X 1 ,V 1 ,W 1 ) и G 2 (X 2 ,V 2 ,W 2 ) порядка n 1 и n 2 , соответственно . Обозначим символами , и - аллельные формы i-го гена гамет "отца ", "матери " и "потомка ". Алгоритм рекомбинации генов I. I:= 1,2,...n ; I 1 :=I 2 :=0 ; n 1 (t):=n 2 (t):=0. II. Для всех i I формируются гомозиготные гены "потомка ": A. Если = =1, то :=1; I 1 :=I 1 i ; n 1 (t):=n 1 (t)+1 ; B. Если = =0, то :=0; I 2 :=I 2 i ; n 2 (t):=n 2 (t)+1 ; III. I: = I\ I 1 I 2 - множество гетерозиготных генов . IV. 4. Случайным образом с вероя тностью (1/ I ) выбирается j-ый гетерозиготный ген (j J). V. Случайным образом с вероятностью (1/2) в j-ый локус гаметы "потомка " заносится или ("1" или "0"); VI. Если =1, то n 1 (t): = n 1 (t)+1 иначе n 2 (t): =n 2 (t)+1. A. I: = I\ j . VII. 8. [n 1 (t)=n 1 или Vn 2 (t) = n 2 ]? да VIII. Если n 1 (t)=n 1 , то : = 0 для всех k I иначе :=1 для всех k I (гамета "п отомка " сформирована ). Для учета доминантности аллельных форм п .5 рассмотренного алгоритма должен быть заменен следующей процедурой : 5.1. Случайным образом с вероятностью ( j / ) в j-ый локус "потомка " заносится "1" и с вероятностью (1 - j / ) заносится "0" (Здесь j - число единиц в j-м локусе хромосомного н абора популяции P t численностью ). Введенная процедура позволяет определить доминантный аллель A с помощью частот аллелей хромосомного набора текущей популяции P t , т.к . каждый ген имеет всего две формы аллелей "1" или "0". Пример 4.1. Пусть для графа , приведенного на рис .1.1. задано два дихотомических разбиения ( ) и ( ) : = x 2 , x 4 , x 5 , x 7 , x 9 , = x 1 , x 3 , x 6 , x 8 , x 10 , x 11 , x 12 и = x 1 , x 2 , x 5 , x 8 , x 10 = x 3 , x 4 , x 6 , x 7 , x 9 , x 10 , x 12 . Будем считать , что ( ) соответствует особи , а разбиение ( ) - особи , которые образуют "родительскую " пару с генотипами , удовлетворяющими условию , что число "1" в каждом из них равно n 1 =5 В скобках указаны степени приспособленности особей , имеющих данный генотип. : "отцовская " гамета E( ): 0 1 0 1 1 0 1 0 1 0 0 0 (13) 1 2 3 4 5 6 7 8 9 10 11 12 "материнская " гамета E( ): 1 1 0 0 1 0 0 1 0 1 0 0 (19) 1 2 3 4 5 6 7 8 9 10 11 12 Для приведенных "родительских " гамет гомозиготные гены находятся во 2, 3, 5, 6, 11 и 12 локусах ; локусы , которые занимают гетерозиготные ге ны , помечены крестиками : x 1 0 x 1 0 x x x x 0 0 1 2 3 4 5 6 7 8 9 10 11 12 В результате рекомбинации генов может быть получена , например , следующая гамета "потомка ": 1 1 0 0 0 1 (18) 1 2 3 4 5 6 7 8 9 10 11 12 которой соответствует разбиение (X 1 , X 2 ): X 1 = x 1 , x 2 , x 4 , x 5 , x 10 , X 2 = x 3 , x 6 , x 7 , x 8 , x 9 , x 11 , x 12 . В генотипе "потомка " гены 2, 3, 5, 6, 11 и 12 (заштрихованные биты ) совпадают с гомозиготными генами "родителей ", сохраняя их аллели по наследству ; аллели генов "потомка " 1, 7, 9 и 10 получены от соответствующих генов "мат еринского " генотипа (эти биты помечены символом ); гены "потомки " 4 и 8 получены от соответствующих генов "отцовского " генотипа (эти биты помечены символом ). 5. Краткая теория 5.1 Математическая формулировка экстремальной задачи однокритериального выбора Многие прикладные проблемы , связанные с задачами выбора , управления и проекти рования , сводятся , как правило , к принятию решения на основе исследования математических моделей . Каждая математическая модель отображает взаимосвязь тех количественных свойств объекта , которые являются существенными для решаемой задачи. Предположим , что к онкретный объект (техническое устройство , физический или технологический процесс , экономическая система и т.д .) может быть охарактеризован конечной совокупностью существенных свойств , которые могут быть объективно измерены . Количественная оценка существен н ых свойств осуществляется с помощью величин , называемых параметрами . Можно выделить следующие типы параметров : · — внешние параметры , характеризующие внешнюю по отнош ению к объекту среду и оказывающие влияние на его функционирование ; · — внутренние параметры , характеризующие свойства отдельных элементов объекта. В определении конкр етных значений внутренних параметров , так же называемых управляемыми переменными , фактически состоит акт принятия решения. Объединенную совокупность внешних и внутренних параметров будем называть множеством входных параметров . Величины , характеризующие сво йства объекта в целом как системы , будем называть выходными параметрами (характеристиками ) , которые можно только измерять или вычислять , но непосредственно изменять нельзя . Обозначим их вектором . Управляемые переменные и характеристики определяют существенные свойства исследуемого объекта , а внешние параметры являются , как правило , константами и характеризуют внешнюю среду . При этом внутренние параметры играют роль независимых переменных , а выходные параметры являются зависящими от них величинами . Будем считать , что соотношения , выражающие эти зависимости , заданы в в иде “черного ящика” , который имеет n входов x i , и s выходов i , . В процессе принятия решения значения управляемых переменных могут варьироваться в некоторых пределах , определяемых системой неравенств : , ; , (1.1) где -нижнее и верхнее предельно-д опустимые значения , соответственно , для i-ой переменной и j-ой характеристики . Область управляемых переменных , в которой выполняется система ограничений (1.1), будем называть областью поиска D , а любой вектор , принадлежащий множеству D - допустимым решением. Для выбора из области поиска D одного или нескольких “лучших” допустимых решений часто приходится вводить критерий оптимальности Q - количественный показатель , поср едством которого осуществляется объективное измерение в некоторой числовой шкале Y какого-либо одного наиболее важного для задачи принятия решения выходного параметра i . Здесь под измерением по шкале Y понимается отображение Q, которое каждому решению ставит в соответствие числовую оценку таким образо м , чтобы отношения между числами сохраняли бинарные отношения предпочтения между решениями : 1) “предпочтительнее” тогда и только тогда , когда Q( )
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Если правительство недовольно своим народом, оно должно распустить его и выбрать себе новый.
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по медицине и здоровью "Программированное обучение и контроль по физиологии", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru