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

Реферат

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

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

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

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 227 kb, скачать бесплатно
Обойти Антиплагиат
Повысьте уникальность файла до 80-100% здесь.
Промокод referatbank - cкидка 20%!
Заказать
Узнать стоимость написания уникального реферата

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

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Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
Если производство молока упало на 0,5%, а производство молочной продукции увеличилось на 26%, то что мы едим?
Anekdot.ru

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

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

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


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