Модели эволюции. Генетические алгоритмы

Вид материала

Реферат

Содержание 1.2. Модели предбиологической эволюции. Общие представления о моделях 2. Модели эволюции. 2.1. Модель квазивидов 2.1.2. Экспериментальные основы модели 2.1.3. Формальное описание модели – общая схема. 2.2. Модель случайно взаимодействующих элементов. 2.3. Модель "чисто нейтральной" эволюции 1. Имеется популяция черных и белых шаров, общее количество шаров в популяции равно 2.4. Схема гиперцикла. 2.5. Общая схема сайзеров I – полинуклеотидная матрица, Ei I кодирует протеины, фермент   репликации E1 обеспечивает   репликацию матрицы I Самовоспроизводящиеся автоматы Дж. фон Неймана A, предназначенный для изготовления произвольного автомата согласно информации, закодированной в ленте L B , копирующий ленту L 2.6. Гиперциклы или сайзеры? 2.7. NK-автоматы С. Кауффмана: сеть случайно связанных логических элементов K (порядка величины N K не достигнет величины порядка 2. При K  K  2; - если мы сравним число различных аттракторов NK

Подобный материал:

• Доклад «Моделирование эволюции. Генетические алгоритмы», 75.42kb.
• Доклад «Моделирование эволюции. Генетические алгоритмы», 108.9kb.
• Доклад на тему: "Модели эволюций и генетические алгоритмы", 155.74kb.
• Информатика, вычислительная техника и инженерное образование 2011, №1(3) эволюционное, 635.81kb.
• Л. И. Параллелизмы в молекулярной организации генома и проблемы эволюции. В кн.: Молекулярные, 251.18kb.
• Программа дисциплины «Нечеткая логика, генетические алгоритмы и экспертные системы, 228.23kb.
• Дисциплина: Инженерия знаний Доклад Генетические алгоритмы, 371.21kb.
• Курс, 1-й семестр лекции (51 час), экзамен практикум на ЭВМ (68 часов), зачет (с оценкой), 24.4kb.
• Фрагментные генетические алгоритмы, 140.16kb.
• Курсовая работа По дисциплине: «Моделирование систем» По теме: «Генетические алгоритмы, 324.78kb.

Министерство общего и профессионального образования РФ

Ульяновский государственный технический университет


Факультет «Информационные системы и технологии»

Кафедра «Информатика и вычислительная техника»

Дисциплина «Инженерия знаний»

реферат


«Модели эволюции. Генетические алгоритмы»


Выполнил студент группы ЭВМд-42

Шарафутдинов И.Г.

Проверил профессор Соснин П.И.

Ульяновск 2002

Содержание

Введение

Существуют два твердо установленных положения относительно живой природы: во-первых, в ней заключено богатейшее разнообразие животных, растений и микроорганизмов, а во-вторых, все живые организмы, по-видимому, хорошо приспособлены к тому, чтобы решать проблемы, встающие перед ними в той среде, в которой они обитают. Можно представить себе, что либо все признаки живых организмов постоянны и оставались таковыми с тех пор, как зародилась жизнь, либо эти признаки способны изменяться и их разнообразие и адаптивность прогрессивно развертывались с течением времени. Этот последний динамический процесс теперь называют эволюцией. Относительно механизмов эволюции высказывались различные предположения— от вмешательства богов до естественного отбора. Последняя точка зрения, впервые высказанная Дарвином, в настоящее время занимает господствующее положение, и цель этой книги состоит в том, чтобы суммировать ту сложную совокупность мыслей и фактов, которые оказались с ней связанными, особенно за последние сто лет. Однако для того чтобы сделать это должным образом, необходимо оценить исторические и философские предпосылки, на фоне которых Дарвин совершил переворот в науке, а поэтому в настоящей главе будет дан краткий исторический обзор и сделаны некоторые замечания философского характера.

Теории эволюции были основаны на трех главных принципах.

1. Считалось, что все организмы обладают врожденной способностью развиваться в сторону усложнения и совершенствования формы. Эразм Дарвин считал, что эта «способность совершенствоваться за счет своей собственной врожденной активности» дарована им богом; Ламарк же полагал, что «жизненная сила» проистекает из самой организации живых существ. Через организм протекают тонкие флюиды — тепловые и электрические,— не только поддерживающие, но и усиливающие его упорядоченность.
   
2. Все организмы имеют некую внутреннюю склонность (то, что Ламарк называл внутренним стремлением), которая заставляет их выполнять действия, достаточные для того чтобы удовлетворять требованиям (обеспечивать выживание), предъявляемым изменяющейся средой. Среда не вызывает изменений, она вызывает потребность в изменении, которую организм осознает и в соответствии с которой он действует. Эразм Дарвин выходил из положения, привлекая для объяснения этой внутренней склонности некое таинственное начало, а Ламарк — тонкие флюиды.
   
3. Признаки, приобретенные организмом в результате употребления того или иного органа в каких-то новых целях, передаются от одного поколения другому благодаря процессу, которому ни Дарвин, ни Ламарк не дали четкого определения. И напротив, признаки, утраченные вследствие неупотребления в одном поколении, не появляются в последующих поколениях.
   

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

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

1. Сфера и методы исследований эволюционной кибернетики. Модели возникновения молекулярно-генетических кибернетических систем.

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




 Рис. 1. Области исследований эволюционной кибернетики

Уже достаточно сложившаяся область – эволюционное моделирование (Рис.1), в котором можно выделить: 1) модели возникновения молекулярно-генетических информационных систем, 2) моделирование общих закономерностей эволюции, 3) эволюционные модели искусственной жизни, 4) прикладное эволюционное моделирование. Охарактеризуем кратко эти направления.

Интенсивные исследования по моделированию возникновения молекулярно-генетических информационных систем начались в 1960-70-х годах. Интерес к этим исследованиям связан с интригующими проблемами: как могла возникнуть жизнь на Земле? Каковы могли бы быть первые кибернетические схемы функционирования первобытных организмов? Обсуждение этих моделей мы начнем во второй части этой лекции.

Общие модели эволюции разрабатывались сравнительно давно. В 1910-1930-х годах классическими работами  Р. Фишера ( R.A.Fisher), Дж. Холдейна (J.B.S. Haldane), и С. Райта (S.Wright) были заложены основы популяционной генетики. Классическая теоретическая популяционная генетика была основана на синтетической теории эволюции, т.е. на синтезе Дарвиновской концепции естественного отбора и Меделевской дискретной генетики. Согласно синтетической теории эволюции, главный механизм прогрессивного развития - естественный отбор тех организмов, которые смогли получить выгодные мутации.

Теоретическая популяционная генетика характеризует популяцию как динамический процесс эволюции распределения частот генов.

Математическая популяционная генетика на базе синтетической теории эволюции интенсивно развивалась до 60-х годов, когда возникли определенные трудности, связанные с экспериментальными достижениями молекулярной генетики (оценки скорости эволюционной замены аминокислот в белках и полиморфизма белков). Чтобы проинтерпретировать экспериментальные результаты, М.Кимура предложил так называемую теорию нейтральной эволюции [1]. Основное предположение теории М.Кимуры: мутации на молекулярном уровне (замены нуклеотидов в ДНК и аминокислот в белках) преимущественно нейтральны, или слабо невыгодны. Используя математические методы популяционной генетики, М.Кимура вывел ряд следствий теории нейтральности, которые находятся в довольно хорошем согласии с экспериментальными данными. Образно говоря, теория нейтральности – это популяционная генетика на базе достижений молекулярной биологии.

Среди работ, посвященных моделированию общих кибернетических закономерностей биологической эволюции, отметим также цикл исследований С. Кауффмана, посвященный анализу автоматов, состоящих из множества случайно связанных логических элементов. Отдельный автомат можно рассматривать как модель молекулярно-генетической системы управления живой клетки, при этом каждый логический элемент интерпретируется как регулятор синтеза определенного фермента. Примечательно, что при исследовании автоматов Кауффмана применяются высокоэффективные математические методы статистической физики. Модели Кауффмана позволяют сделать ряд предсказаний относительно "программ" жизнедеятельности клеток. В частности, продемонстрировано, что для одновременного обеспечения устойчивости и гибкости программы число входов логических элементов должно быть ограничено определенным интервалом, а именно составлять величину примерно равную 2-3.

К работам по моделированию общих аспектов биологической эволюции можно отнести и исследования вопросов эволюции генетических текстов. В работах Д.С.Чернавского (Москва) исследовалась проблема возникновения в процессе эволюции новой биологически значимой информации, а также была сделана оценка вероятности случайного формирования в геноме участка ДНК, кодирующего новый функционально важный для организма белок. Д.С. Чернавский недавно написал новую книгу по динамике информационных систем, думаю, что в ближайшее время эта книга будет издана и в ней можно будет найти много интересного.

В конце 80-х годов сформировалось направление кибернетических исследований – искусственная жизнь (английское название Artificial Life или ALife). Многочисленные Интернет-ссылки на работы этого направления можно найти на Интернет-сайте междисциплинарного Института Санта Фе: ссылка скрыта. Основной мотивацией исследований искусственной жизни служит желание понять и промоделировать формальные принципы организации биологической жизни. Как сказал руководитель первой международной конференции по искусственной жизни К.Лангтон (C.Langton) “основное предположение Искусственной Жизни состоит в том, что “логическая форма” организма может быть отделена от материальной основы его конструкции”. “Организмы” в искусственной жизни – придуманные людьми объекты, живущие в мире компьютерных программ.

Приведем некоторые примеры характерных исследований Искусственной жизни:

• исследование динамики жизнеподобных структур в клеточных автоматах (К.Лангтон);
  
• эволюция двух конкурирующих популяций, одна из которых есть популяция программ, решающих определенную прикладную проблему (проблему сортировки), а вторая – популяция задач, эволюционирующих в направлении усложнения проблемы (Д.Хиллис (D.Hillis));
  
• эволюция и формирование “биоразнообразия” самовоспроизводящихся программ, живущих в виртуальных компьютерах (Т.Рей (T.Ray));
  
• анализ "биоразнообразия" самовоспроизводящихся программ на базе теории самоорганизованной критичности (К.Адами (C.Adami));
  
• компьютерная модель ПолиМир (PolyWorld), разработанная Л.Ягером (L.Yaeger),  в которой эволюция популяции искусственных организмов (агентов) происходит вполне естественным образом: агенты питаются растущей на лужайках травой, могут бороться друг с другом (в результате борьбы агент может погибнуть, тогда он превращается в пищу, которую может съесть победитель), могут скрещиваться, давая потомков - новых агентов; агенты имеют нейронную сеть, которая управляет поведением агентов.
  

В 60-х годах блестящий кибернетик и математик М.Л.Цетлин предложил и исследовал модели автоматов, способных адаптивно приспосабливаться к окружающей среде. Работы М.Л.Цетлина инициировали целое научное направление, получившее название “коллективное поведение автоматов”.

В 60-70-х годах под руководством талантливого кибернетика М.М.Бонгарда была построена весьма нетривиальная модель “Животное”, характеризующая адаптивное поведение искусственных организмов, живущих на разбитой на клетки плоскости и обладающих рядом конкурирующих между собой потребностей.

Эволюция кибернетических сущностей – одно из главных направлений исследований Искусственной жизни.

Согласованность и эффективность работы элементов биологических организмов наводит на мысль – можно ли использовать принципы биологической эволюции для оптимизации практически важных для человека систем?

В нескольких модификациях подобные идеи возникали у ряда авторов. В 1966 году Л.Фогель (L.J.Fogel), А.Оуенс (A.J.Owens), М.Уолш (M.J.Walsh) [3] предложили схему эволюции логических автоматов, решающих задачи прогноза. Исследования по прикладному эволюционному моделированию, идейно близкие к работам Л.Фогеля с сотрудниками, были разносторонне развиты в работах И.Л.Букатовой [4]. В 1975 г. вышла основополагающая книга Дж.Холланда (J.H.Holland) “Адаптация в естественных и искусственных системах” [5], в которой был предложен генетический алгоритм, исследованный в дальнейшем учениками и коллегами Дж.Холланда в Мичиганском университете. Примерно в это же время группа немецких ученых (И.Рехенберг (I.Rechenberg), Г.-П.Швефель (G.-P.Schwefel) и др.) начала разработку так называемой эволюционной стратегии. Эти работы заложили основы прикладного эволюционного моделирования или эволюционных алгоритмов.

В общем виде эволюционный алгоритм – это оптимизационный метод, базирующийся на эволюции популяции “особей”. Каждая особь характеризуется приспособленностью f(S) – многомерной функцией ее "генов" S = (S₁ , S₂ ,...,S_N). Задача оптимизации состоит в максимизации функции приспособленности f(S) . В процессе эволюции в результате отбора, рекомбинаций и мутаций геномов особей происходит поиск особей с высокими приспособленностями.

Основные эволюционные алгоритмы

1. генетический алгоритм, предназначенный для оптимизации функций дискретных переменных и акцентирующий внимание на рекомбинациях геномов;
   
2. эволюционное программирование, ориентированное на оптимизацию непрерывных функций без использования рекомбинаций;
   
3. эволюционная стратегия, ориентированная на оптимизацию непрерывных функций с использованием рекомбинаций;
   
4. генетическое программирование, использующее эволюционный метод для оптимизации компьютерных программ.
   

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

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

Изложенное выше демонстрирует один из методов исследований эволюционной кибернетики – метод математического и компьютерного моделирования.

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

Пример, иллюстрирующий разработку эволюционных концепций, – книга В.Ф.Турчина "Феномен науки. Кибернетический подход к эволюции”. В.Ф.Турчин рассматривает биологическую эволюцию с кибернетической точки зрения, а эволюцию научного познания - как продолжение биокибернетической эволюции. В книге последовательно проанализированы ступени биологической эволюции, а также этапы возникновения и развития математического знания. В качестве кибернетической основы исследования В.Ф.Турчин использует предложенную им "теорию метасистемных переходов".

Кратко и очень упрощенно суть теории метасистемных переходов сводится к следующему: переход от нижних уровней системной иерархии к верхним происходит путем метасистемных переходов. Каждый метасистемный переход можно рассматривать как объединение ряда подсистем S_i нижнего уровня и появление дополнительного механизма управления C объединенными подсистемами. В результате метасистемного перехода формируется система S' нового уровня (S' = C + _i S_i), которая может быть включена как подсистема в следующий метасистемный переход.

Схема метасистемного перехода представлена на Рис.2.



Рис. 2. Схема метасистемного перехода. S_i –  системы нижнего уровня, C –   управление объединенными подсистемами, S ' –  система нового уровня иерархии.

Примеры метасистемных переходов:

управление положением = движение
управление движением = раздражимость (простой рефлекс)
управление раздражимостью = (сложный) рефлекс
управление рефлексами = ассоциации (условный рефлекс)
управление ассоциациями = человеческое мышление
управление человеческим мышлением = культура

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

Как возникли первые кибернетические системы, самые простые молекулярно-генетические информационные системы в процессе происхождения жизни? В 60-80 годы подобные проблемы заинтриговали многих ученых. Целая плеяда Нобелевских лауреатов (Ф.Крик (F.H.C.Crick), М.Эйген (M.Eigen), Ф.Дайсон (F.J.Dyson), Ф.Андерсон (P.W.Anderson)) предприняла попытки представить и промоделировать сценарии возникновения предбиологических информационных систем.

Почему же возник такой интерес к проблеме возникновения молекулярно-генетических кибернетических   систем?

В 50-60-х годах в молекулярной биологии был сделан ряд потрясающих открытий:

1. расшифрована химическая структура ДНК (Уотсон и Крик, 1953) и стали известны основные принципы кодирования генетической информации;
   
2. стали известны основные принципы функционирования молекулярно-генетических самовоспроизводящихся систем живых клеток,
   
3. расшифрован генетический код.
   

Эти открытия совершили революцию в науках о жизни. Особенно впечатляет своей "продуманностью" схема функционирования молекулярно-генетических самовоспроизводящихся систем (Рис.3). 



Рис. 3. Схема самовоспроизводящейся молекулярно-генетической системы живой клетки.

На схеме представлена двойная цепь ДНК (постоянная память клетки), с которой (путем транскрипции) считываются матричные РНК (мРНК). По мРНК (путем трансляции) синтезируются белки (ферменты и структурные белки). В процессе трансляции участвуют транспортные РНК. Синтез белков происходит в рибосомах. Синтезируемые ферменты принимают участие в процессах репликации, транскрипции и трансляции.

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

Но каковы могли быть механизмы возникновения такой схемы в процессе происхождения жизни? Фактически попыткам осмыслить этот вопрос были посвящены исследования М.Эйгена и Ф.Крика с сотрудниками. Ф. Крик с сотр. тщательно исследовал возможные биомолекулярные механизмы происхождения генетического кода [9]. М.Эйген пошел по пути построения математических моделей, иллюстрирующих (но далеко не воспроизводящих) возможные процессы происхождения простейших самовоспроизводящихся молекулярно-генетических систем.