Санкт-Петербургскийгосударственный инженерно-экономический университет Филиал в городе ЧереповцеКафедра «Общепрофессиональныеи специальные дисциплины»
Реферат
По дисциплине«Информационные технологии в экономике»
Тема «Интеллектуальныеинформационные технологии и системы: генетические алгоритмы»
Студентки 3 курса
группы 4ЭУП-05
Валигура Т.В.
Череповец, 2007
Содержание
1. Генетические алгоритмы
2. Простой генетический алгоритм
3. Разновидности генетических алгоритмов
1. Генетическиеалгоритмы
В основе генетическихалгоритмов лежат генетика и хромосомная теория эволюции организмов. Хромосомы –это нитевидные структуры, находящиеся в клеточном ядре, которые являютсяносителями наследственности. Каждая хромосома уникальна морфологически игенетически и не может быть заменена другой либо восстановлена при утере (припотере хромосомы клетка, как правило, погибает). Каждый биологический вид имеетопределённое, постоянное количество хромосом. Каждая клетка содержит удвоенныйнабор морфологически и генетически сходных хромосом. Например, в клеткахчеловека содержится 23 пары хромосом, в клетках комара – 3.
На процесс наследованияпризнаков существенно влияет поведение хромосом при делении клеток. Существуетмитозное и мейозное деление клеток. Митозное деление обеспечивает распределениеисходных хромосом и будут между двумя образующимися дочерними клетками, которыебудут иметь равноценные наборы хромосом и будут очень похожи друг на друга. Приэтом происходит редупликация исходных хромосом, вследствие чего к моментуделения клетки каждая хромосома состоит из двух копий исходной материнскойхромосомы – сестринских хроматид.
Во время мейозапроисходит два последовательных деления: редукционное и эквационное. Мейозприводит к образованию клеток, у которых число хромосом вдвое меньше посравнению с исходной клеткой.
В фазе редукции хроматидыобмениваются генами, т.е. участками дезоксирибонуклеиновой кислоты (ДНК). Послеэтого клетка разделяется на две новые, причём каждая из них содержит удвоенныйнабор хромосом, структуры которых отличаются от исходных. Механизм обменагенами называется кроссинговером.
В результате эквационногоделения из двух получившихся клеток образуются четыре клетки, каждая из которыхсодержит одиночный набор хромосом.
Таким образом, митозобеспечивает возобновление клеток, а мейоз отвечает за передачу наследственнойинформации и способствует генетическому разнообразию организмов данного вида.
Классическая генетикаобосновала наследственность и изменчивость благодаря созданию фундаментальнойтеории гена, основные положения которой формулируются следующим образом:
· Все признакиорганизма определяются наборами генов;
· Гены — этоэлементарные единицы наследственной информации, которые находятся в хромосомах;
· Гены могутизменяться – мутировать;
· Мутации отдельныхгенов приводят к изменению отдельных элементарных признаков организма, илифенов.
Ген определяется какструктурная единица наследственной информации, далее неделимая в функциональномотношении. Он представляет собой участок молекулы ДНК, на котором сохраняетсяпостоянный порядок следования пар нуклеотидов. Комплекс генов, содержащихся внаборе хромосом одного организма, образует геном. Роль молекул ДНК, обладающихуникальной способностью к самовоспроизведению, заключается в хранении ипередаче генетической информации последующим поколениям.
В задачах поискаоптимальных решений каждое решение из множества возможных можно представитьнабором информации, который может быть изменён путём введения в него элементовдругого решения. Другими словами, возможные решения соответствуют хромосомам,состоящим из генов, причём в ходе оптимизации происходит обмен генами междухромосомами (рекомбинация). При построении генетических алгоритмов важен выборпринципа генетической рекомбинации. Существует несколько типовперераспределения наследственных факторов:
1. рекомбинацияхромосомных и нехромосомных генов;
2. рекомбинация целевыхнегомологических хромосом;
3. рекомбинация участковхромосом, представленных непрерывными молекулами ДНК.
Для построениягенетических алгоритмов наибольший интерес представляет третий типрекомбинации, который используется для накопления в конечном решении лучшихфункциональных признаков, какие имелись в наборе исходных решений. Существуетнесколько типов рекомбинации участков хромосом: кроссинговер, сайт, иллегальнаярекомбинация.
Кроссинговерсоответствует регулярной рекомбинации, при которой происходит обменопределёнными участками между гомологичными хромосомами. Он приводит кпоявлению нового сочетания сцепленных генов.
Сайт – это видрекомбинации, при которой на коротких специализированных участках хромосомпроисходит обмен генофоров (генных носителей), часто различных по объёму исоставу генетической информации.
Иллегальная рекомбинациядопускает негомологичные обмены, к которым относятся транслокации, инверсии ислучаи неравного кроссинговера. Такие способы могут оказаться полезными пригенерации новых решений.
В генетических алгоритмахнаибольшее распространение получила операция кроссинговера, заключающаяся вразрыве гомологических хроматид с последующим соединением их в новом сочетании.
Основная целькроссинговера заключается в создании из имеющегося генетического материалажелаемой комбинации признаков в одном решении.
Помимо кроссинговера длярешения различных прикладных задач полезными являются такие генетическиеоперации, как мутация, инверсия, транслокация, селекция (инбридинг игибридизация), генная инженерия.
Под мутацией понимаетсягенетическое изменение, приводящее к качественно новому проявлению основныхсвойств генетического материала: дискретности, непрерывности или линейности.Свойство дискретности позволяет выделить в исходном генетическом материалеотдельные фрагменты, контролирующие те или иные функции. Непрерывностьозначает, что определённые комбинации генов совместно контролируют некоторуюфункцию. Линейность проявляется в определённой последовательности генов впределах группы сцепления.
Процессы мутации ведут кполучению более разнообразного генетического материала. В связи с этимприменение операции мутации в генетических алгоритмах направлено на получениерешений, которые не могут быть улучшены качественно посредством кроссинговера.
Инверсия, транцлокация,транспозиция, делеция и дупликация относятся к разновидностям хромосомноймутации. При инверсии участок хромосомы поворачивается на 1800. транслокацией называют перенос части одной хромосомыв другую. При перемещении небольших участков генетического материала в пределаходной хромосомы используют термин транспозиция. Делеция – это выпадениеотдельных участков хромосом, дупликация – повторение участка генетическогоматериала. Кроме перечисленных, существуют другие разновидности хромосомныхмутаций.
Селекция представляетсобой форму искусственного отбора, который может быть массовым илииндивидуальным. Установлено, что массовый отбор по фенотипу (совокупности всехвнешних и внутренних признаков) менее эффективен, чем индивидуальный, когдапопуляцию делят на отдельные линии, а для размножения выбирают носителейжелаемых свойств. Применение процедуры селекции в генетических алгоритмахоптимизации способствует ускорению процесса синтеза искомого решения.
Генная инженерияпредставляет собой совокупность методов для получения рекомбинантной ДНК иоперации над нею. Рекомбинантная ДНК получается путём объединения фрагментовДНК различных организмов. Использование подходов генной инженерии позволяет вряде задач значительно быстрее находить желаемое решение.
Механизм эволюции основанна трёх повторяющихся процессах: отборе, амплификации (процесс производствапотомков) и мутации. Он используется в качестве механизма случайнонаправленного комбинаторного перебора при решении задач оптимизации ислабоструктурированных проблем принятия решений.
Генетический алгоритм –это поисковый алгоритм, основанный на природных механизмах селекции и генетики.Эти алгоритмы обеспечивают выживание сильнейших решений из множествасгенерированных, формируя и изменяя процесс поиска на основе моделированияэволюции исходной популяции решений. Генетические алгоритмы сконструированытаким образом, что при генерации каждой новой популяции используются фрагментыисходных решений, к которым добавляются новые элементы, обеспечивающиеулучшение решений относительно сформулированного критерия отбора. Другимисловами, генетические алгоритмы используют информацию, накопленную в процессеэволюции.
В генетических алгоритмахиспользуются специфические термины, взятые из генетики, которые трактуютсяследующим образом.Генетика Генетические алгоритмы хромосома Решение, стринг, строка, последовательность, родитель, потомок популяции Набор решений (хромосом) локус Местоположение гена в хромосоме поколение Цикл работы генетического алгоритма, в процессе которого сгенерировано множество решений. аллель Значение элемента, характеристики фенотип Структура эпистасис Множество параметров, альтернативные решения Скрещивание, рекомбинация, кроссинговер Оператор рекомбинации мутация Оператор модификации
При разработкегенетических алгоритмов преследуется две главные цели:
· Абстрактное иформальное объяснение процессов адаптации в естественных системах;
· Проектированиеискусственных программных систем, воспроизводящих механизмы функционированияестественных систем.
Основные отличия ГА отдругих алгоритмов оптимизации:
· Используютсяне параметры, а закодированная множества параметров;
· Поискосуществляется не из единственной точки, а из популяции точек;
· В процессепоиска используются значения целевой функции, а не её приращения;
· Применяютсявероятные, а не детерминированные правила поиска и генерации решений;
· Выполняетсяодновременный анализ различных областей пространства решений, в связи с чемвозможно нахождение новых областей с лучшими значениями целевой функции за счётобъединения квазиоптимальных решений из разных популяций.
2.Простой генетический алгоритм
Согласно репродуктивномуплану Холланда генетические схемы поиска оптимальных решений включают следующиеэтапы процесса эволюции:
1. конструируется начальная популяция.Вводится начальная точка отсчёта поколений t = 0. вычисляются приспособленность хромосом популяции(целевая функция) и средняя приспособленность всей популяции.
2. устанавливается значение t = t+1. выбираются два родителя (хромосомы) для кроссинговера.Выбор осуществляется случайным образом пропорционально жизнеспособностихромосом, которая характеризуется значениями целевой функции.
3. формируется генотип потомка. Дляэтого с заданной вероятностью над генотипами выбранных хромосом производитсяоперация кроссинговера. Случайным образом выбирается один из потомков А(t), который сохраняется как член новойпопуляции. Далее к потомку А(t)последовательно с заданными вероятностями применяются операторы инверсии имутации. Полученный в результате генотип потомка сохраняется как А(t).
4. обновление текущей популяции путёмзамены случайно выбранной хромосомы на А(t)/
5. определение приспособленности А (t) и пересчёт среднейприспособленности популяции.
6. если t=t, где t – заданное число шагов, то переход кэтапу 7, в противном случае – переход к этапу 2.
7. конец работы.
Основная идея эволюции,заложенная в различные конструкции генетических алгоритмов, проявляется вспособности «лучших» хромосом оказывать большее влияние на составновой популяции за счёт длительного выживания и более многочисленного потомства.
Простой генетическийалгоритм включает операцию случайной генерации начальной популяции хромосом иряд операторов, обеспечивающих генерацию новых популяций на основе начальной.Этими операторами являются репродукция, кроссинговер и мутация.
Репродукцией называетсяпроцесс копирования хромосом с учётом значений целевой функции, т.е. хромосомыс «лучшими» значениями целевой функции имеют большую вероятностьпопадания в следующую популяцию. Этот процесс является аналогией митозногоделения клеток выбор клеток (хромосом) для репродукции проводится всоответствии принципом «выживания сильнейшего». Простейшим способомпредставления операции репродукции в алгоритмической форме является колесорулетки, в котором каждая хромосома имеет поле, пропорциональное значениюцелевой функции.
3.Разновидности генетических алгоритмов
Генетический алгоритмДевиса (25) включает следующие шаги:
1. инициализацияпопуляции хромосом.
2. оценка каждойхромосомы в популяции.
3. создание новыххромосом посредством изменения и скрещивания текущих хромосом (применениеоператоров мутации и кроссинговера).
4. устранениехромосом из популяции для замены их новыми.
5. оценка новыххромосом и включение их в популяцию.
6. проверка условияисчерпания ресурса времени, отведённого на поиск оптимального решения (есливремя исчерпано, то работа алгоритма завершается и производится возврат кнаилучшей хромосоме, в противном случае – переход к шагу 3).
Холланд (14,26) предложилдля генетического алгоритма оператор инверсии, который реализуется по схеме:
1. стринг(хромосома) В=(b1,b2,…..,b1) выбирается случайным образом изтекущей популяции.
2. из множества Y= (0,1,2,…., L +1) случайным образом выбираются два числа у1 и у2и определяются значения х1=min(у1, у2).
3. из хромосомы Вформируется новая хромосома путём инверсии (обратного порядка) сегмента,лежащего справа от позиции х2 в хромосоме В. После примененияоператора инверсии строка В примет вид В = (b1, ….,bx1,bx2=1, bx2-2, …,bx1+1, bx2,…, bL).
Например, для строкиВ=(1,2,3,4,5,6) при выборе у1=6 и у2=2 и соответственно х1=2,х2=6 результатом инверсии будет В= (1,2,3,4,5,6).
Операции кроссинговера имутации, используемые в простом ГА, изменяют структуру хромосом, в том числеразрушают удачные фрагменты найденных решений, что уменьшает вероятностьнахождения глобального оптимума. Для устранения этого недостатка в генетическихалгоритмах используют схемы (схематы или шаблоны), представляющие собойфрагменты решений или хромосом, которые желательно сохранить в процессеэволюции. При использовании схем в генетическом алгоритме вводится новыйалфавит (0,1,), где интерпретируется как «имеет значение 1 или 0».Например:
Схема(*0000)соответствует двум стрингам (10000 и 00000);
Схема (*111*)соответствует четырём строкам (01110, 11110, 01111, 11111);
Схема (0*1**) можетсоответствовать восьми пятизначным стрингам.
В общем случая хромосомадлиной L максимально может иметь 3L(шаблонов), но только 2L различных альтернативных стрингов.Это следует из факта, что схеме (**) в общем случае могут соответствовать 32=9стрингов, а именно (**, *1, *0,1*, 0*, 00, 01, 10 11), и только 22=4альтернативные строки (00, 01, 10, 11), т.е. одной и той же строке можетсоответствовать несколько схем.
Если в результате работыгенетического алгоритма удалось найти схемы типа (11***) и (**111), то,применив к ним, оператор кроссинговера, можно получить хромосому (11111),обладающую наилучшим значением целевой функции.
Схемы небольшой длиныназываются строительными блоками. Размер строительных блоков заметно влияет накачество и скорость нахождения результата. Вид строительного блока выбирается сучётом специфики решаемой задачи, а их разрыв в генетических алгоритмахдопускается только в исключительных случаях, определяемых пользователем.Например, в схеме (****1) строительным блоком является элемент1, а в схеме(10***) – составной элемент10.
При использованиибольшого числа строительных блоков генетические алгоритмы, основанные наслучайной генерации популяций и хромосом, переходят в разряд беспорядочных.
Стационарные генетическиеалгоритмы отличаются от поколенческих тем, что у первых размер популяцииявляется заданным постоянным параметром, который определяется пользователем, ау вторых размер популяции в последующих генерациях может увеличиваться илиуменьшаться.
Процедура удаления лишниххромосом в стационарных и поколенческих генетических алгоритмах основана наэвристических правилах, примерами которых являются следующие
· случайноеравновероятное удаление хромосо;
· удалениехромосом, имеющих худшие значения целевой функции;
· удаление хромосомна основе обратного значения целевой функции;
· удаление хромосомна основе турнирной стратегии.
Следует иметь в виду, чтоиспользование в генетических алгоритмах тех или иных эвристик удаления хромосомможет повлечь за собой негативные последствия. Например, удаление худшиххромосом приводит к повреждённый утрате разнообразия и, как следствие, кпопаданию целевой функции в локальный оптимум, а при наличии большого числахромосом с плохими значениями целевой функции утрачивается направленностьпоиска, и он превращается в «слепой» поиск.