История появления эволюционных алгоритмов

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

Содержание

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

1 2 3 4 5 6 7 8 9

МОДЕЛИРОВАНИЕ ЭВОЛЮЦИИ

16.03.1999

ВЛАДИМИР РЕДЬКО

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

Владимир Редько - доктор физико-математических наук, автор более семидесяти научных публикаций. Область научных интересов - эволюционная биокибернетика. Разработал ряд математических моделей предбиологической эволюции. Ведет раздел "Математическое моделирование эволюции" в Principia Cybernetica Project.

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

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

Эволюционное моделирование

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

Уже достаточно сложившаяся область - эволюционное моделирование, в котором можно выделить:

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

2) моделирование общих закономерностей эволюции,

3) эволюционные модели искусственной жизни,

4) прикладное эволюционное моделирование.

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

Ф. Андерсон [P. W. Anderson]) предприняла попытки представить и промоделировать сценарии возникновения предбиологических информационных систем. Впечатляющие исследования провел М. Эйген. Он, в частности, предложил и проанализировал модель "квазивидов", описывающую достаточно простую эволюцию полинуклеотидных (информационных) последовательностей, и модель "гиперциклов", описывающую систему каталитически взаимодействующих ферментов и полинуклеотидов. Очень интересная модель - модель "сайзеров" (syser - от SYstem of SElf-Reproduction) - была предложена новосибирскими учеными В. А. Ратнером и В. В. Шаминым. Сайзер представляет собой самовоспроизводящуюся систему ферментов и кодирующих их полинуклеотидов. Проиллюстрируем это направление исследований на примере моделей квазивидов и сайзеров.

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

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

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

Среди работ, посвященных моделированию общих кибернетических закономерностей биологической эволюции, отметим интересный цикл исследований С. А. Кауффмана (S. A. Kauffman), посвященный анализу NK-автоматов, состоящих из множества случайно связанных логических элементов.

NK-автомат есть сеть из N булевых логических элементов (входы и выходы элементов принимают значения 0 либо 1),

N >>1. Выходы одних элементов поступают на входы других, эти связи случайны, но число входов K каждого элемента фиксировано. Сами логические элементы также выбираются случайно. Автомат функционирует в дискретном времени. Состояние автомата в каждый момент времени t определяется вектором X(t) - совокупностью выходных сигналов всех логических элементов. В процессе функционирования последовательность состояний сходится к аттрактору - предельному циклу. Последовательность состояний X(t) в этом аттракторе может рассматриваться как "программа" функционирования автомата.

Поведение автоматов существенно зависит от степени связности K.

При больших K (порядка величины N) "жизнь" автоматов стохастична: последовательные состояния аттракторов радикально отличаются друг друга, программы очень чувствительны (существенным образом изменяются) как по отношению к минимальным возмущениям (случайное изменение одного из компонентов выходного вектора X(t) в процессе работы автомата), так и по отношению к мутациям (изменение типа элемента или связи между элементами). Если степень связности K уменьшается, то такой стохастический тип поведения сохраняется до тех пор, пока K не достигнет величины порядка 2.

При K = 2 поведение автомата принципиально меняется. Влияние минимальных возмущений на программы мало. Мутации обычно вызывают только слабые изменения динамики функционирования автомата. Только отдельные редкие мутации приводят к радикальным, каскадным изменениям программ автоматов. Такое поведение характеризуют как жизнь на границе хаоса и порядка ("at the edge of chaos").

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

С. А. Кауффман аргументирует, что именно случай K = 2 есть адекватная модель молекулярно-генетических систем управления биологических клеточных организмов. Основные моменты этой аргументации состоят в следующем:

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

типичные схемы генной регуляции биологических клеток включают только небольшое число входов от других генов, что согласуется со значением K = 2;

если мы сравним число различных аттракторов NK-автомата при K = 2 (вычисленное для разных значений N ) с числом различных типов клеток (то есть с числом различных программ жизни клетки для фиксированного генома) биологических организмов разного эволюционного уровня, то получим близкие цифры.

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

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

Эволюционные модели искусственной жизни. В конце 80-х годов сформировалось очень интересное направление кибернетических исследований - искусственная жизнь (английское название Artificial Life, или ALife; tafe.edu/). Основной мотивацией исследований искусственной жизни служит желание понять и смоделировать формальные принципы организации биологической жизни. Как сказал руководитель первой международной конференции по искусственной жизни К. Лангтон (C. Langton), "основное предположение Искусственной Жизни состоит в том, что "логическая форма" организма может быть отделена от материальной основы его конструкции". "Организмы" в искусственной жизни - придуманные людьми объекты, живущие в мире компьютерных программ.

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

исследование динамики жизнеподобных структур в клеточных автоматах (К. Лангтон);

эволюция двух конкурирующих популяций, одна из которых есть популяция программ, решающих определенную прикладную проблему (проблему сортировки), а вторая - популяция задач, эволюционирующих в направлении усложнения проблемы (Д. Хиллис [D.Hillis]);

эволюция и формирование "биоразнообразия" самовоспроизводящихся программ, живущих в виртуальных компьютерах (Т. Рэй [T. Ray]).

Отметим, что хотя лозунг "Искусственная Жизнь" провозглашен в конце 80-х, в действительности идейно близкие модели разрабатывались в 50-70-е годы. Приведем два примера из истории отечественной науки.

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

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

Эволюция кибернетических сущностей - одно из главных направлений исследования искусственной жизни. Проиллюстрируем эволюционные модели искусственной жизни на примере компьютерной модели "ПолиМир" (PolyWorld; www.beanblossom.in.us/larryy/PolyWorld.phpl ), разработанной Л. Ягером (L. Yaeger) в 1992 году.

Опишем эту модель. Представим себе некое ограниченное пространство (скажем, большой стол), на котором могут жить искусственные организмы. По краям стол-мир ограничен барьерами так, чтобы организмы не падали со стола. На столе могут вырастать лужайки зеленой пищи. Организмы могут двигаться прямолинейно, поворачиваться, поглощать пищу. Они обладают цветовым зрением. Одни организмы могут вступать в борьбу с другими, при этом побежденные организмы умирают, и их каркас превращается в пищу. Организмы могут скрещиваться, давая потомство. Если организм вступает в борьбу, то он краснеет; если испытывает желание скреститься - синеет.

Организмы имеют нервную систему, состоящую из искусственных нейронов. Нейронная сеть организма управляет его поведением: регулирует скорость движения, повороты, воинственность и половую активность, обеспечивает фокусировку зрения на окружающих организм объектах. Поедая пищу (зеленые лужайки или каркасы мертвых особей), организмы пополняют запас энергии. Проявляя активность (движение, повороты, борьба, скрещивание), организмы расходуют энергию. Если ресурс организма опускается ниже определенного предела, организм умирает (и, естественно, превращается в пищу).

Параметры организма (размер, скорость движения, бойцовская сила, основной цвет и т. п.), а также структура нейронной сети определяются геномом организма. Потомки организмов наследуют гены родителей (часть генов от одного родителя, часть - от другого), при переходе от родителей к потомкам гены испытывают малые мутации.

Эволюция организмов в "ПолиМире" моделировалась компьютерной программой, содержащей 15000 строк на языке С++.

В процессе моделирования эволюции наблюдалось формирование определенных стратегий поведения животных.

Одну из стратегий можно условно назвать "тупая корова": организм движется прямолинейно с максимальной скоростью, поедает все встречающиеся лужайки пищи и скрещивается со всеми, кого встретит.

Вторая стратегия - "ленивый каннибал": организм крутится на месте, скрещиваясь или вступая в борьбу с каждым, кто приблизится (поедая каркас соперника в случае победы или погибая в случае поражения).

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

Интересно, что в модели "ПолиМир" не вводится понятие приспособленности организмов (или селективной ценности, как в модели квазивидов) - эволюция здесь происходит в результате достаточно естественной гибели и рождения организмов.

В целом "ПолиМир" и аналогичные модели обладают большим потенциалом для дальнейшего развития.

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

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

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

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

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

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

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

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

Отметим, что методы генетического программирования были разработаны сравнительно недавно (конец 80-х - начало 90-х годов) Дж. Козой (J. Koza).

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

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

Эволюционная нейрокибернетика

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

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

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

Модели эволюции нейронных сетей - это, фактически, оптимизация нейронных сетей с помощью эволюционных алгоритмов. Эти работы начались сравнительно недавно (конец 80-х годов) и сейчас интенсивно развиваются.

Если поставить цель - проанализировать эволюцию наиболее нетривиальных "интеллектуальных" биокибернетических свойств, - то можно предложить построение теории происхождения логики. Предметом такой теории могло бы быть исследование процесса развития "интеллектуальных изобретений" биологической эволюции (безусловных рефлексов, привыкания, условных рефлексов, цепей условных рефлексов и т. д. [1]), в результате которых возникла человеческая логика, обеспечивающая научное познание природы. Подходы к построению такой теории обсуждались в ряде работ автора [2, 3, 4].

Начать такие исследования можно было бы с моделирования процесса формирования новых знаний при адаптивном поведении животных.

Сформулируем общие требования к достаточно универсальной модели поведения, формализуя общие особенности функциональной системы по П. К. Анохину [5]. Для определенности будем считать, что рассматривается животное с развитой нервной системой, скажем, млекопитающее.

Модель поведения могла бы характеризовать следующие свойства системы управления поведением животного:

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

мотивацию - стремление к цели;

доминанту (по А. А. Ухтомскому), обеспечивающую мобилизацию ресурсов животного на достижение приоритетной цели, в том числе мобилизацию интеллектуальных ресурсов (концентрацию внимания);

распознавание ситуации;

"планирование" действий;

прогноз результата действия (с использованием "базы знаний", содержащейся в памяти животного);

выполнение самого целенаправленного действия;

оценку результата действия;

сопоставление прогноза и результата;

поиск нужного решения и корректировку базы знаний (в случае рассогласования прогноза и результата).

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

Отметим, что указанные исследования не ограничиваются чисто академическими интересами. Например, недавно появился термин "интеллектуальное предприятие". Замените всюду в приведенной двумя абзацами выше схеме слово "животное" на слово "предприятие", и вы получите вполне разумную общую схему управления предприятием и подход к созданию интеллектуальных предприятий будущего. Между прочим, даже такой прагматичный человек, как Б. Гейтс (B. Gates), инициирует разработки "нервной системы" предприятия.

Эволюционные концепции

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

Яркий пример, иллюстрирующий разработку эволюционных концепций, - книга В. Ф. Турчина "Феномен науки. Кибернетический подход к эволюции" [6]. Книга была написана в нашей стране в 1970 году, однако из-за политической деятельности ее автора впервые была издана только в США в 1977 году. В. Ф. Турчин рассматривает биологическую эволюцию с кибернетической точки зрения, а эволюцию научного познания - как продолжение биокибернетической эволюции. В книге последовательно проанализированы ступени биологической эволюции, а также этапы возникновения и развития математического знания. Книга написана исключительно четко, с хорошо обоснованной внутренней логикой.

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

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

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

управление положением = движение

управление движением = раздражимость (простой рефлекс)

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

управление рефлексами = ассоциации (условный рефлекс)

управление ассоциациями = человеческое мышление

управление человеческим мышлением = культура

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

На базе концепций, разработанных в "Феномене науки", развивается уникальный Интернет-проект "Principia Cybernetica Project" (ub.ac.be/), редактируемый В. Ф. Турчиным (Нью-Йорк), Ф. Хейлигхеном (F.Heylighen) (Брюссель), К. Джослиным (C. Joslin) (Лос-Аламос). В нем делается попытка осмыслить на основе эволюционной научной концепции вечные вопросы человечества: "Почему мир такой, какой он есть? Откуда мы (люди, человечество) произошли? Кто мы? Куда эволюционирует человечество?"

Blog

История появления эволюционных алгоритмов

Содержание

МОДЕЛИРОВАНИЕ ЭВОЛЮЦИИ