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

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

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


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


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


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


реферат


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


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

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

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


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

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

Содержание 2

Введение 3

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

1.2. Модели предбиологической эволюции. Общие представления о моделях 15

2. Модели эволюции. 17

2.1. Модель квазивидов 17

2.1.1. Модель квазивидов – простейшая модель эволюции информационных последовательностей. 17

2.1.2. Экспериментальные основы модели: 18

2.1.3. Формальное описание модели – общая схема. 19

2.2. Модель случайно взаимодействующих элементов. 21

2.3. Модель "чисто нейтральной" эволюции 25

2.4. Схема гиперцикла. 27

2.5. Общая схема сайзеров 29

2.6. Гиперциклы или сайзеры? 32

2.7. NK-автоматы С. Кауффмана: сеть случайно связанных логических элементов 33

Список литературы. 38


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

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

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

Все организмы имеют некую внутреннюю склонность (то, что Ламарк называл внутренним стремлением), которая заставляет их выполнять действия, достаточные для того чтобы удовлетворять требованиям (обеспечивать выживание), предъявляемым изменяющейся средой. Среда не вызывает изменений, она вызывает потребность в изменении, которую организм осознает и в соответствии с которой он действует. Эразм Дарвин выходил из положения, привлекая для объяснения этой внутренней склонности некое таинственное начало, а Ламарк — тонкие флюиды.

Признаки, приобретенные организмом в результате употребления того или иного органа в каких-то новых целях, передаются от одного поколения другому благодаря процессу, которому ни Дарвин, ни Ламарк не дали четкого определения. И напротив, признаки, утраченные вследствие неупотребления в одном поколении, не появляются в последующих поколениях.


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

Поэтому неудивительно, что ученые, занимающиеся компьютерными исследованиями, обратились к теории эволюции в поисках вдохновения. Возможность того, что вычислительная система, наделенная простыми механизмами изменчивости и отбора, могла бы функционировать по аналогии с законами эволюции в природных системах, была очень привлекательна. Эта надежда стала причиной появления ряда вычислительных систем, построенных на принципах естественного отбора.
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). Многочисленные Интернет-ссылки на работы этого направления можно найти на Интернет-сайте междисциплинарного Института Санта Фе: http://alife.santafe.edu/. Основной мотивацией исследований искусственной жизни служит желание понять и промоделировать формальные принципы организации биологической жизни. Как сказал руководитель первой международной конференции по искусственной жизни К.Лангтон (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 = (S1 , S2 ,...,SN). Задача оптимизации состоит в максимизации функции приспособленности f(S) . В процессе эволюции в результате отбора, рекомбинаций и мутаций геномов особей происходит поиск особей с высокими приспособленностями.

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

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

эволюционное программирование, ориентированное на оптимизацию непрерывных функций без использования рекомбинаций;

эволюционная стратегия, ориентированная на оптимизацию непрерывных функций с использованием рекомбинаций;

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

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

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

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

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

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

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

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



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

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

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

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

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

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

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

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

стали известны основные принципы функционирования молекулярно-генетических самовоспроизводящихся систем живых клеток,

расшифрован генетический код.

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



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

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

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

Но каковы могли быть механизмы возникновения такой схемы в процессе происхождения жизни? Фактически попыткам осмыслить этот вопрос были посвящены исследования М.Эйгена и Ф.Крика с сотрудниками. Ф. Крик с сотр. тщательно исследовал возможные биомолекулярные механизмы происхождения генетического кода [9]. М.Эйген пошел по пути построения математических моделей, иллюстрирующих (но далеко не воспроизводящих) возможные процессы происхождения простейших самовоспроизводящихся молекулярно-генетических систем.
^ 1.2. Модели предбиологической эволюции. Общие представления о моделях
И на этом пути М.Эйген провел впечатляющие исследования. Он, в частности, предложил и проанализировал модель "квазивидов", описывающую достаточно простую эволюцию полинуклеотидных (информационных) последовательностей, и модель "гиперциклов", описывающую систему каталитически взаимодействующих ферментов и полинуклеотидов. Очень интересная модель – модель "сайзеров" (syser от System of self-reproduction), была предложена новосибирскими учеными В.А. Ратнером и В.В.Шаминым.

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

Характерная эволюция распределения последовательностей схематически показана на Рис.4. Для простоты предполагается, что последовательности бинарны, т.е. “геном” каждой “особи” представляет собой последовательность нулей и единиц. Длина последовательностей равна N (N >>1). Есть одна оптимальная последовательность, обладающая максимальной селективной ценностью. Селективные ценности остальных последовательностей тем меньше, чем больше расстояние по Хеммингу  (число несовпадающих символов) между рассматриваемой и оптимальной последовательностями. Исходное распределение (t = 0) случайно. В результате эволюции формируется квазивид: популяция, в которой наряду с оптимальной последовательностью есть множество сходных с ней мутантов.



Модель сайзеров (Рис.5) [12,13] описывает самовоспроизводящуюся систему макромолекул, в которую входят: полинуклеотидная матрица I, фермент репликации E1 и фермент трансляции E2 . Полинуклеотидная матрица хранит информацию, кодирующую синтезируемые в сайзере ферменты, фермент репликации E1 обеспечивает копирование полинуклеотидной матрицы, а фермент трансляции E2 – синтез ферментов в соответствии с закодированной в матрице информацией. Возможны также другие ферменты E3 , E4 , ..., En , выполняющие какие-либо еще полезные для сайзера функции. По общей структуре модель сайзеров сходна со схемой самовоспроизводящихся автоматов, исследованных на заре развития вычислительной техники Дж. фон Нейманом (J.von Neumann) [14].


^ 2. Модели эволюции. 2.1. Модель квазивидов 2.1.1. Модель квазивидов – простейшая модель эволюции информационных последовательностей.
В 70-х годах лауреат Нобелевской премии из ФРГ Манфред Эйген предпринял впечатляющую попытку построения моделей возникновения в ранней биосфере Земли молекулярно-генетических систем обработки информации [1,2]. Одна из наиболее известных моделей – модель "квазивидов", описывающая достаточно простую эволюцию полинуклеотидных (информационных) последовательностей.

В модели квазивидов рассматривается эволюция информационных последовательностей или векторов S = (S1 , S2 , ... , SN), компоненты которых принимают небольшое число   дискретных значений (для полинуклеотидных последовательностей  = 4). Предполагается, что такие последовательности способны к саморепликации (или к репликации с помощью простейших ферментных систем). Рассматривается популяция последовательностей S1 , S2 , ... , Sn и анализируется Дарвиновская эволюция этой популяции, в процессе которой отбирается квазивид: распределение сходных последовательностей, обладающих достаточно большой скоростью репликации.
^ 2.1.2. Экспериментальные основы модели:
1. Синтез малых полинуклеотидов. В экспериментах Л.Оргела было показано, что небольшие цепочки РНК (порядка 10 нуклетидов) способны к самореплицированию. В присутствии ионов цинка (действующего как катализатор) длина воспроизводимых цепочек достигает 40   нуклетидов.

2. Эволюция цепочек РНК в присутствии Q- репликазы. Вирус Q содержит РНК-участок длиной 220 нуклеотидов (спутниковая РНК), который реплицируется ферментом Q - репликазой с высокой эффективностью. М. Сумпер из лаборатории М. Эйгена активно исследовал процесс эволюции РНК в присутствии Q- репликазы. Были исследованы количественные характеристики этого процесса.

Вход: шаблон РНК (спутниковая РНК) + Q- репликаза + богатые энергией мономеры (АТФ, УТФ, ГТФ, ЦТФ).
Выход: растущая популяция РНК, идентичных шаблону.

3. Синтез РНК de novo. Однажды М. Сумпер сообщил, что если в раствор не вносится шаблон, то синтез РНК также возможен, но он идет значительно дольше и менее стабильно. В результате появляются цепочки РНК, сходные со спутниковой РНК. К.Биебрихер и Р. Луа (сотрудники М.Эйгена) показали, что синтез РНК de novo происходит путем постепенного удлинения РНК-цепочек.

Вход: Q- репликаза + богатые энергией мономеры (АТФ, УТФ, ГТФ, ЦТФ).
Выход: растущая популяция РНК, сходных с шаблоном.

Вывод. Эксперименты показывают, что есть процессы, которые можно интерпретировать (хотя с некоторыми натяжками) как Дарвиновскую эволюцию полинуклеотидных последовательностей.
^ 2.1.3. Формальное описание модели – общая схема.
Приведем формальное описание модели квазивидов.
Квазивид - модель эволюции информационных последовательностей [1,2,4]. Эволюционирующая популяция есть множество {Sk}, состоящее из n последовательностей Sk , k = 1,..., n. Каждая последовательность представляет собой цепочку из N символов, Ski, i = 1,..., N. Символы выбираются из алфавита, содержащего  различных букв. Например, мы можем рассматривать алфавит с двумя буквами ( = 2, Ski = 1, -1 или  Ski == Г, Ц) или алфавит с четырьмя буквами ( = 4, Ski  = Г, Ц, A, У). Предполагается, что длина последовательностей N и численность популяции n велики: N, n > > 1.

Последовательности представляют собой геномы модельных "организмов", организмы характеризуются определенными неотрицательными приспособленностями  f(S) (селективными ценностями в терминологии М. Эйгена). В простейшем случае предполагается, что имеется оптимальная последовательность (the master sequence) Sm , имеющая максимальную приспособленность. Приспособленность произвольной особи S определяется расстоянием по Хеммингу  (S, Sm) между S и Sm (числом несовпадающих компонент в этих векторах), причем f(S) экспоненциально уменьшается с ростом  (S, Sm).

Эволюционный процесс состоит из последовательности поколений. Новое поколение  {Sk (t+1)}получается из старого {Sk(t)} путем отбора и мутаций последовательностей Sk (t) ; здесь t  – номер поколения.

Шаг 0. Формирование начальной популяции {Sk (0)}. Для каждого k = 1, ..., n, и для каждого  i = 1 , ..., N , выбираем случайно символ Ski, полагая его равным произвольному символу данного алфавита.

Шаг 1. Отбор

Подшаг 1.1.   Расчет приспособленностей. Для каждого k = 1, ..., n, вычисляем величину f(Sk).

Подшаг 1.2. Формирование новой популяции {Sk (t+1)}. Отбор  n особей в новую популяцию {Sk(t+1)} с вероятностями, пропорциональными f(Sk).

Шаг 2. Мутации особей в новой популяции. Для каждого k = 1, ..., n, для каждого   i = 1, ..., N, заменяем Ski(t+1) на  произвольный символ алфавита с вероятностью P . Параметр P характеризует интенсивность мутаций.

Организация последовательности поколений. Повторяем шаги 1, 2 для t = 0, 1, 2, ...

Схему отбора проиллюстрируем следующим образом. Представим, что у нас есть рулетка. Для каждого поколения отмечаем на рулетке n секторов, долю k-го сектора (отнесенную ко всей площади круга) полагаем равной qk =  fk [ l fl ]-1 (Рис. 1). Здесь мы обозначили: fk =  f(Sk) . Далее n раз крутим рулетку, каждый раз определяем номер сектора, на котором останавливается стрелка, и соответствующую этому номеру особь выбираем в популяцию следующего поколения. Таким образом в следующее поколение будут отобраны  n особей. При этом для каждого вращения рулетки вероятность k-й особи попасть в следующее поколение пропорциональна ее приспособленности fk .



Рис.1. Схема отбора, при которой особи выбираются в популяцию нового поколения с вероятностями qk , пропорциональными их приспособленностям  fk . Показан пример, для которого n = 4,  f1 = 2,  f2 = 4,  f3 = 1,  f4 = 1.
^ 2.2. Модель случайно взаимодействующих элементов.
Была рассмотрена Дарвиновская эволюция информационных последовательностей – модель квазивидов. Был рассмотрен простейший случай Хемминговой меры близости между последовательностями. А именно, анализировалась эволюция популяции последовательностей S1 , S2 , ... , Sn в предположении, что имеется одна наилучшая особь Sm , а приспособленность f(S) произвольной особи S определяется расстоянием по Хеммингу  (S, Sm) между S и Sm (числом несовпадающих компонент в этих векторах), причем  f(S) экспоненциально уменьшается с ростом (S, Sm):

  f(Sk) = exp[-  (Sk, Sm)],                                                              (1)

где - параметр, характеризующий интенсивность отбора.

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

Существенный недостаток модели с Хемминговой мерой близости – предположение о существовании единственного максимума приспособленности f(S). В настоящей лекции мы устраним этот недостаток и построим модель для многоэкстремальной функции приспособленности f(S) , используя хорошо известную модель спиновых стекол Шеррингтона-Киркпатрика (1975г.), и покажем, что основные особенности "спин-стекольной" модели эволюции во многом аналогичны таковым в модели с Хемминговой мерой близости. Основное отличие состоит в том, что квазивид формируется в окрестности не глобального минимума приспособленности, а в окрестности одного из локальных максимумов приспособленности.

Рассмотрим эволюцию популяции, в которой "геномы" S модельных особей представляют собой информационные последовательности N символов S = S1 , S2 ,..., SN . Символы принимают значения 1 или  -1: Si = 1, -1 .   Популяция есть набор {Sk}, состоящий из n  последовательностей, k = 1,..., n. Приспособленности модельных "организмов" Sk определяем как:

f(Sk) = exp[- E(Sk)] ,                                                                             (9)

где E(Sk)   – энергия спинового стекла, задаваемая формулами (2), (3),  – параметр интенсивности отбора.

Определение (9) подразумевает, что модельный "геном"  Sk состоит из последовательности элементов Ski,  i = 1 , ..., N ,  которые случайно попарно взаимодействуют в  соответствии с матрицей взаимодействия Jij . Максимальной приспособленностью (соответственно, минимальной энергией  E(S)) будут обладать те "организмы",  имеющие такую комбинацию элементов Si , которая обеспечивает максимальную  кооперативность взаимодействий между спинами Si  для данной матрицы Jij .

Как и для Хемминговой меры близости предполагаем, что эволюционный процесс состоит из последовательности поколений. Новое поколение  {Sk (t+1)}получается из старого Sk(t) путем отбора и мутаций последовательностей Sk (t).

Формально эволюционный процесс может быть описан следующим псевдокодом:




Шаг 0. Формирование начальной популяции {Sk (0)}. Для каждого k = 1, ..., n, и для каждого  i = 1 , ..., N , выбираем случайно символ Ski, полагая его равным 1 или -1.




Шаг 1. Отбор







Подшаг 1.1.   Расчет приспособленностей. Для каждого k = 1, ..., n, вычисляем величину f(Sk) в соответствии с формулами (2), (3), (9).




Подшаг 1.2. Формирование популяции следующего поколения{Sk (t+1)}. Отбор   n особей в новую популяцию{Sk (t+1)} с вероятностями, пропорциональными f(Sk).







Шаг 2. Мутации. Для каждого k = 1, ..., n, для каждого   i = 1, ..., N, с вероятностью Pm переворачиваем спин Ski(t+1): Ski --> - Ski. Параметр Pm характеризует интенсивность мутаций.




Шаг 3. Организация последовательности поколений. Повторяем шаги 1, 2 для t = 0, 1, 2, ...


Отметим, что здесь параметр Pm отличается от параметра P (вероятность выбора символа для мутационной  замены), введенного в предыдущей лекции: Pm = 0,5P.

Описанная модель "спин-стекольной" эволюции анализировалась путем компьютерного моделирования и приближенных оценок [6]. Особенности эволюционного процесса иллюстрируются Рис. 1. Здесь n(E) – число таких последовательностей S , что  E(S) = E  в рассматриваемой популяции,  t   – номер поколения.



Рис. 1. Распределение последовательностей по энергиям  n(E) для разных поколений t ; t3 > t2 > t1 ;  E0 и EL – глобальный и локальный минимумы энергии, соответственно; глобальный минимум энергии E0 приближенно составляет: E0 = - 0,8 N. Схематично, согласно компьютерному моделированию  [6].

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

Наряду с эволюционным процессом мы можем рассматривать последовательный поиск минимумов энергии спинового стекла. А именно, задаем систему из  N спинов, случайно выбираем спин Si , переворачиваем его (Si --> - Si) и смотрим: уменьшилась энергия или увеличилась, при уменьшении энергии принимаем новое значение спина, при увеличении – возвращаемся к старому. Такой последовательный процесс также сходится к какому-либо локальному минимуму EL . Моделирование показывает, что в среднем эволюционный процесс сходится к более глубокому локальному минимуму энергии EL, чем последовательный поиск. Это обусловлено тем, что при эволюционном поиске одновременно просматриваются несколько "долин" в энергетическом ландшафте E(S) и увеличиваются шансы попасть в более глубокую долину и соответственно достичь более глубокого минимума энергии. 

Итак, на основе понятия спиновых стекол можно построить модель эволюции для "организмов", геномы которых состоят из множества случайно взаимодействующих между собой элементов. Эволюция может рассматриваться как процесс поиска такой комбинации элементов, которая обеспечивает наиболее эффективную кооперацию элементов генома.
^ 2.3. Модель "чисто нейтральной" эволюции
Нейтральный отбор играет важную роль в эволюции популяций конечной численности n. Для того чтобы продемонстрировать особенности нейтрального отбора явно, рассмотрим "чисто нейтральную" эволюционную игру, которую определим следующим образом:

^ 1. Имеется популяция черных и белых шаров, общее количество шаров в популяции равно n.

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

Мы говорим, что популяция находится в l -состоянии, если число черных и белых шаров для рассматриваемого поколения равны  l и n - l, соответственно. Будем характеризовать эволюцию вероятностями переходов Plm . Plm   есть вероятность перехода из  l -состояния в  m -состояние в течение одного поколения. Используя простой комбинаторный расчет, можно определить значения Plm :



Матрица Plm  задает случайный Марковский процесс, который может рассматриваться как пример простого стохастического эволюционного процесса [12]. Используя общие методы анализа та