Эволюционное моделирование. Проблемы формы и содержания

Размещено на http://www.allbest.ru/

1

Эволюционное моделирование. Проблемы формы и содержания

В.Э. Карпов

Введение

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

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

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

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

История вопроса

Впервые, пожалуй, идея ЭМ была явно сформулирована еще в 60-х гг. Л.Фогелем в работе «Искусственный интеллект и эволюционное моделирование» ([Fogel, 1966] или в русском переводе [Фогель Л. и др., 1969]), которую можно было бы назвать классической, если б она не была, фактически, предана незаслуженному забвению. Причин тому можно выделить несколько.

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

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

Самое интересное, что параллельно, практически одновременно с работами Фогеля создавались разнообразные модели, которые могли бы стать основой для эволюции. Например, исследования М.Л.Цетлина по теории автоматов ([Цетлин, 1969]) должны бы дать эволюционному моделированию замечательную модель объекта эволюции. С другой стороны, интенсивно развивались и формализовывались модели эволюции как таковой ([Шмальгаузен, 1968]). Однако пересечения этих трех составляющих ЭМ - самой концепции создания сложных систем на основе эволюции простейших, модели эволюционирующей особи и формальной эволюционной теории - в тот момент, к сожалению, не произошло.

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

Ознаменовалось это прежде всего появлением такого явления, как генетические алгоритмы. Предложенные Холландом [Holland, 1975] генетические алгоритмы (ГА), как водится, изначально претендовали на революционный метод решения интеллектуальных поисковых задач. Приверженцы этого направления утверждают, что ГА основываются на теории эволюции Дарвина (а именно, на идее естественного отбора). О проблемах ГА мы поговорим позже. Пока же достаточно сказать, что сейчас ГА рассматриваются значительно более скромно - лишь как некий стохастический оптимизационный метод, иногда дающий неплохие результаты. Действительно, находить экстремумы с помощью ГА можно. Но не более.

В то же время предпринимались попытки возобновления исследований в области ЭМ. Речь идет прежде всего о работах И.Л.Букатовой ([Букатова, 1975]). Однако даже в одной из наиболее значительных работ ([Букатова и др., 1991]) факторы эволюции лишь декларируются. Фактически речь идет о повторении исследований Фогеля на несколько более высоком качественном уровне с улучшенной методологической (декларативно) проработкой. Даже основной объект эволюции остался на том же уровне, что и у основателей ЭМ.

Заканчивая предысторию вопроса, можно сделать еще пару замечаний. Не исключено, что само мышление человека (по крайне мере та часть, которая относится к понятию инсайта - озарения) является эволюционным процессом. Речь идет о переборе на подсознательном уровне вариантов решения задачи [Тихомиров, 1966]. Раз перебор - значит, необходим механизм эффективного решения этой комбинаторной задачи. А это и есть предмет ЭМ. Кроме того, принятый в ЭМ подход достаточно хорошо сходится и с представлениями биологов относительно того, что отличает живые организмы высокого уровня развития от примитивных. Например, Р.Фокс в [Фокс, 1992] пишет: «биологическое преимущество развитой нервной системы состоит в способности к предсказанию нелинейных событий на основе быстрого моделирования». Тот же Фокс приводит примеры того, как осуществляется это быстрое прогнозирование в системах двигательного контроля, а также в зрительной коре хордовых.

Современность

Говоря о современном состоянии вопроса, главное - не потонуть в огромном количестве терминов, общим для которых является добавка «эволюционное»: эволюционная кибернетика, эволюционная биокибернетика, эволюционные модели и прочие эволюционные, желательно, многоагентные системы. К эволюционному моделированию относят и т.н. модели искусственной жизни (эволюционные, конечно), и молекулярно-генетические системы (вплоть до модели ДНК Уотсона и Крика), т.е. все, в чем так или иначе может фигурировать эволюция, биология и т.п.

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

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

Методология ЭМ

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

Начнем с того, что эволюционное моделирование, как метод решения задач, можно представить в виде тройки

ЭМ = <М, О, З>

где М - модель эволюции, О - эволюционирующий объект, З - решаемая задача или критерии эволюции.

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

Модель эволюции

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

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

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

Приведем лишь некоторые «впечатляющие» тезисы противников теории естественного отбора.

Геном человека лишь наполовину сложнее генома дождевого червя, а геном древесной лягушки в сотни раз больше генома «царя природы».

Теория эволюции никак не объясняет миллионы лет застоя, чередующиеся с бурным образованием видов.

С помощью экспериментов можно подтвердить лишь внутривидовые изменения, но нельзя объяснить происхождение новых видов. Да и между видами нет, якобы, переходных форм.

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

Нет надежных теорий, объясняющих появление и наследование вариаций. Неясен механизм наследования жизненных изменений.

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

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

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

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

А подытожить вышеизложенное можно универсальным патетическим заявлением: до сих пор наука не может достаточно внятно объяснить не только происхождение человека, но и хотя бы приблизительные сроки его появления на Земле. Каждое очередное палеонтологическое открытие становится сенсационным и «заставляет пересмотреть взгляды на эту проблему».

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

Итак, будем считать, что в основе ЭМ, как метода решения задач, лежат не некоторые конъюнктурные и «субъективно-интуитивные» соображения, а достаточно объективная, хорошо описывающая наблюдаемые явления жизни на Земле аксиоматика.

Модель особи

Говоря о важности выбора модели эволюционирующего объекта, имеется в виду не что иное, как извечный вопрос формы. С одной стороны, исходя из принципа универсальности и глобальности самого метода ЭМ, декларируется, что субъектом эволюции может быть что угодно. Однако здесь все не так просто. «Неудачная» модель может погубить все дело. Так произошло, например, с генетическими алгоритмами. Дело даже не в том, что эволюция не может происходить без учета фенотипической деятельности организма. Этот, возможно, не совсем очевидный факт будет нами обсуждаться позже. На поверхности лежит другое соображение. Интерес представляет поиск априори неизвестного алгоритма решения некоторой задачи. Следовательно, структура особи должна нести в себе как минимум описание этого искомого алгоритма (либо его фрагмента, если речь идет о получении решения в виде популяции). При этом желательно, чтобы форма этого представления была бы как можно более естественной. Если же мы будем говорить теперь именно об эволюции алгоритмов, то останется лишь выбрать, исходя из практических соображений, удобную и/или естественную форму представления.

Достаточно очевидной представляется следующая цепочка:

… Алгоритм Машина Тьюринга Автомат …

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

Задачи или критерии эволюции

Под эволюцией в ЭМ будем понимать процесс образования особей, успешно решающих обусловленные средой задачи. На самом деле задача заключается в банальном выживании. То, насколько устойчива численность популяции, и определяет степень успеха эволюции. Постановка же задачи в ЭМ заключается прежде всего в формировании среды, к которой и должны приспосабливаться члены популяции. Естественно, что с практической точки зрения интерес представляют прежде всего популяции, состоящие из особей, решающих задачу приспособления/выживания «самостоятельно», вне их связи с другими членами популяции. Но, как будет видно в дальнейшем, иногда можно рассматривать эволюцию не особи, а популяции в целом (хотя, с точки зрения биологии, эволюция имеет интегральный, популяционный, видовой характер).

Итак, рассмотрим абсолютно абстрактную, не имеющую практически ничего общего с конъюнктурными (в хорошем смысле этого слова) представлениями об эволюции модель.

Реализация моделей

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

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

Опишем теперь этот процесс более формально. Начнем с описания простейшей модели популяции, в которой отсутствует непосредственное взаимодействие особей. Такая модель может быть названа «автоматным газом».

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

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

S(x1,x2,..,xn,y1,y2,...,yn),

где x1,x2,..,xn - входная последовательность, y1,y2,...,yn - выходная последовательность символов. Функция ошибки определяет величину штрафа, получаемого автоматом за неверный выходной сигнал (действие или предсказание). Когда величина накопленных особью штрафов превышает некоторое заданное значение, данная особь «умирает» (аналог естественного отбора). Автомат содержит стохастическую матрицу P, определяющую вероятности действий. Выходная реакция автомата yt определяется стохастическим вектором из P, соответствующим состоянию автомата и входному сигналу.

эволюция газ нейронная сеть

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

В результате эволюции популяции происходит процесс формирования особей, которые с минимальными ошибками классифицируют входные последовательности. До сих пор считалось, что фактически мы имеем дело с нерегрессивным поиском в пространстве структур (см., например, [Букатова и др., 1991]). Однако, как будет показано ниже, эволюция - это поиск не только и не столько в пространстве структур (пространстве генотипов), но поиск в комбинированном пространстве - пространстве гено-фенотипов.

Рассмотрим теперь среду, в которую погружены эволюционирующие особи. Назовем некий набор элементарных признаков (ЭП) ?i(Xi,Vi) составной средой C={?1,?2,..,?m}. ?i - это двойка: вектор признаков Xi=(x1i,x2i,..,xni) и значение характеристической функции (номер класса, если речь идет о решении задачи классификации) Vi , Vi=1,..,n. Понятие составной среды C отличается от составной среды, введенной Цетлиным [Цетлин, 1969]. Различие это заключается прежде всего в детерминированном характере компонентов составной среды. Функционирование распознающей системы состоит в периодическом случайном выборе очередного элементарного признака ?i из среды C и предъявления его множеству автоматов. Данный ЭП можно, в свою очередь, рассматривать как стационарную среду, в которую погружается автомат. Мы же, поскольку речь здесь идет о задаче индуктивного вывода, будем трактовать ЭП ?i как очередной пример. Индуктивный вывод будет делаться именно на основе множества примеров C. Итак, автомату A периодически предъявляются примеры среды C, правильность классификации которых служит мерой эффективности распознающего (классифицирующего) алгоритма (или автомата, что суть одно и то же). Будем говорить, что множество ЭП фиксированной и одинаковой размерности представляет собой составную среду (С-среду).

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

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

t

Рис.1. Фрагмент временной диаграммы процесса эволюции

Как видно из графика, в начале эволюции качество предсказаний далеко от оптимального. С течением времени в популяции появляются автоматы, более успешно решающие задачу - показатель качества достигает максимума. В дальнейшем эволюция может прекратиться. Это означает, что вымрут «неоптимальные» особи и останутся лишь те, кого не за что будет наказывать. В связи с этим более «устойчивым» показателем качества популяции является средний возраст особей. В «благополучной» популяции (как и в обществе) преобладают «долгожители». Впрочем, и об этом будет говориться ниже, отсутствие «естественной» смертности вовсе не является единственным вариантом процесса моделирования. Иногда можно и даже нужно иметь некий небольшой уровень смертности особей.

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

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

Факторы эволюции

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

Мутации

В ЭМ под мутацией понимается случайное изменение структуры дочерней особи. Например, добавление или удаление состояния, перехода и т.п. структурные изменения, если эволюционирующей особью является автомат. При этом считается, что изменения эти должны быть «малы» - появляться не часто, не быть кратными (комплексными) и т.д. Дело в том, что интенсивные мутации приводят к тому, что система «идет в разнос» - поиск (блуждание) в пространстве состояний приобретает хаотический характер, проскакиваются близлежащие локальные экстремумы и процесс часто завершается полным вымиранием популяции.

С точки зрения популяционной генетики ([Фогель Ф., 1990]) различают следующие типы мутаций:

геномные мутации (изменяется число хромосом);

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

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

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

Если говорить о количественных параметрах, то при проведении экспериментов частоты мутаций (по крайней мере - соотношение их вероятностей) определялись заимствованными из биологии оценками ([Фогель Ф., 1990]):

геномные мутации: 5.67*10-4...2.7*10-5;

хромосомные мутации: 5*10-5...1.15*10-3.

Иными словами, частота хромосомных мутаций больше геномных примерно в 10 раз.

Кроме того, существуют и т.н. кодонные мутации, суть которых заключается в замещении данного основания другим определенным основанием, в результате которого одна аминокислота заменяется на другую. Они достаточно редки. Их частота оценивается в 2.5*10-9. С некоторой натяжкой можно считать, что аналогом кодонных мутаций могут быть изменения таких параметров, как период размножения, использование режима наследования признаков родительской особи и т.п.

О роли фенотипа

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

Итак, пусть мы имеем процесс блуждания точки или множества точек в пространстве состояний. Задача этого блуждания заключается в нахождении некоторого экстремума (локального или глобального - не важно; хотя лучше, конечно, глобального). Блуждая, точки-особи делают пробные шаги - оставляют потомство, отстоящее, благодаря мутациям, на некоторое расстояние от родителя. Оценка качества особи, накопление штрафов и т.д. играют роль управляющего воздействия. Существует ли механизм, позволяющий, с одной стороны, избежать «застревания» точки в локальном экстремуме с одной стороны, и обеспечивающий достаточно «мелкий» шаг блуждания (чтобы не пропустить искомый глобальный экстремум) - с другой?

Иными словами, необходим «запас прочности», чтобы точка смогла бы доползти до соседнего экстремума. Состояние точки между экстремумами можно назвать промежуточным видом. Аналогия здесь абсолютно естественна. Вот лишь одна из классических иллюстраций - летающие рыбы. Сначала была просто рыба. С короткими плавниками. В конце концов появилась рыба летающая, с длинными плавниками. А где же промежуточная рыба, с плавниками, уже достаточно длинными, чтобы они мешали ей плавать, но еще короткими для того, чтобы летать? Очевидно, что такая «промежуточная» рыба нежизнеспособна, потомства оставить не может (не успеет, вымрет раньше) и так далее.

Та же картина наблюдается и тогда, когда мы рассматриваем эволюцию автоматов. Предположим, что имеется автомат со структурой A1. Требуемый автомат Ak может быть получен последовательным применением операторов мутаций M:

A1 A2 =M(A1) A3 =M(A2) … Ak =Mk(A1)

Если структуры автоматов A1 и Ak отвечают состояниям экстремумов, то «промежуточные виды» Ai могут иметь худшие показатели качества, т.е. быть нежизнеспособными.

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

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

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

Фенотипическое приспособление, основанное, скажем, на рассмотренных выше условно-рефлекторных принципах, вполне может обеспечить кратковременную жизнеспособность организма, несмотря на его «неудачную» наследственность.

Отказ от взаимно однозначного соответствия между поведением особи и ее генотипом является достаточно серьезным шагом. С одной стороны, мы получаем более гибкую схему, позволяющей одному и тому же генотипу по-разному проявлять себя в условиях изменяющейся среды. С другой - мы получаем тот самый «непрерывный ряд» вариантов и т.н. «малые», «локальные» мутации. Кроме того, все это хорошо согласуется с результатами из основной предметной области - биологии. Во-первых, существует такое явление, как фенокопия - воспроизведение генетически детерминированного признака под воздействием внешних факторов ([Фогель Ф., 1990], [Гольдшмидт, 1935]). Во-вторых, известно, что большинство мутаций безразлично для организма. Речь идет о пресловутой проблеме «молчащей» ДНК. На самом деле, общая интенсивность мутаций весьма высока. Если речь идет о человеке, то при размножении происходит в среднем 17.5 мутаций на 1 половую клетку и 35 мутаций на индивида (вероятность замещения одного основания/аминокислоты на другое). Введение фено-генотипического пространства и оценки особи именно с точки зрения ее поведения позволяет достаточно естественно интерпретировать эти вопросы. Действительно, результаты большинства мутаций «нивелируются» фенотипической составляющей. Кроме того, «молчащие» (в конкретных условиях среды) фрагменты ДНК могут отвечать за постепенное «депонирование», накапливание новых видовых признаков.

Наследование благоприобретенных признаков

Если вернуться к модели особи в виде автомата, то в соотношении, определяющем реакцию автомата y на входной сигнал x

Y=F(x,Q,P)

матрица переходов Q играет роль генотипа, а стохастическая матрица P реализует фенотипическое поведение.

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

Уже много лет одним из наиболее цитируемых авторов является К.Поппер, особенно его «Логика и рост научного знания». Отдадим и мы дань этой традиции.

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

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

В 1809 г. Ж.Б.Ламарк предположил, что все живые организмы целесообразно приспосабливаются к условиям среды. Согласно Ламарку, эволюция, т.е. проявление форм, более сложных и современных, - это проявление «закона градации», стремление живых существ усложнять свою структуру, целесообразные изменения организмов, направленные на приспособление к внешним условиям.

Раз возникнув, приспособительные изменения далее, по мнению Ламарка, способы передаваться по наследству (это и есть концепция «наследования благоприобретенных признаков»). Изменения эти, как утверждал Ламарк, вызываются прямым влиянием внешней среды, упражнением органов и наследованием приобретенных при жизни признаков.

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

Их оппоненты, вейсманисты, говорили о невозможности непосредственной передачи по наследству «благоприобретенных» признаков.

Итак, согласно теории Дарвина наследственная изменчивость случайна и не зависит от среды. По Ламарку же среда оказывает прямое влияние на наследуемые признаки.

Как водится, со временем оба эти подхода начали сливаться в нечто единое. Так, одна из современных теорий ([Животовский, 2001]) предлагает комбинированный механизм эволюции на основе дарвиновского отбора передаваемых по наследству приобретенных признаков. Согласно этой теории эволюции по Ламарку-Дарвину можно выделить три основные группы приобретенных признаков, которые могут передаваться от родителей к потомкам:

признаки культуры и поведения, воспринятые через обучение;

эпигенетические признаки, возникшие в клеточных структурах;

внедрение соматических мутаций в ДНК клеток полового пути.

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

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

Уже отмечалось, что один и тот же генотип может давать разные фенотипы в различных условиях окружающей среды. В результате удачной модификации фенотипа популяция может оставаться в сложившихся условиях среды до тех пор, пока не произойдет генетического закрепления этого фенотипа (данное проявление «генетического ламаркизма» [Горбань и др., 1988] называется эффектом Болдуина). Так что так ли уж был неправ Т.Д.Лысенко с его наследованием благоприобретенных признаков?

Эффект Болдуина - вещь занятная сама по себе. Обычно ее принято понимать в попперовской интерпретации, суть которой сводится к следующему.

Каждый организм постоянно принимает участие в решении проблем методом проб и ошибок. Если пробы оказываются успешными, то тем самым увеличивается вероятность выживания мутантов, «имитирующих» достигнутое решение и создается тенденция для закрепления этого решения в наследственности (“эффект Болдуина” [Baldwin, 1902]) путем включения его в пространственную структуру или форму нового организма.

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

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

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

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

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

Во-первых, была обнаружена четкая корреляция между CF-фактором и общим показателем качества популяции. Кроме того, доля особей с признаком CF меняется скачкообразно. Это видно из графиков на Рис.2.

Рис.2. Роль CF-фактора. Quality - показатель качества, sQu - средний показатель качества, sTP/CF - доля особей с CF-фактором в общей численности популяции.

Это - «внешний эффект». Однако были обнаружены и не столь тривиальные зависимости. Оказалось, что роль CF-фактора существенно зависит от условий существования, которые можно условно разбить на 3 типа: благоприятные, когда решение находится быстро, сложные, когда для этого требуется значительное время, и неблагоприятные, когда приемлемое решение в классе конечных автоматов отсутствует либо оно может быть найдено за очень большое время.

Оказывается, что в благополучных средах наличие CF-фактора особого влияния на скорость эволюции не оказывает. CF-фактор начинает играть важную роль в сложных условиях: у индивидуума нет времени на длительное обучение. Ему нужен опыт родителей сразу. А в неблагоприятных средах, особенно в тех, в которых происходит резкое изменение условий существования, CF-фактор становится, напротив, крайне вредным. Это связано с тем, что в неблагоприятных условиях должна происходить очень быстрая смена поколений, а опыт старших поколений оказывается неприменимым, тормозящим прогресс. Когда же преодолевается некоторое критическое значение «жесткости» среды, CF-фактор вновь начинает играть положительную, стабилизирующую роль. Эти соображения подтверждаются также экспериментами, в которых использовались большие мутационные частоты. Чем выше частота мутаций, тем меньшее значение имеет CF-фактор.

Эволюция вида и эволюция особи

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

Дело в том, что при этом в ряде экспериментов популяция автоматов начинала вырождаться в совокупность примитивных по своей структуре особей, весьма неэффективно осуществляющих предсказания. Однако в целом популяция вела себя достаточно устойчиво за счет возросшего коэффициента размножения. Этакая совокупность короткоживущих, но крайне интенсивно размножающихся «идиотов». Этот момент представляется, вообще говоря, достаточно важным для того, чтобы остановиться на нем более подробно. Во-первых, подобное решение (высокая скорость размножения при неоптимальной, крайне упрощенной структуре особи) - это тоже оптимальное приспособление. Амеба приспособлена не хуже человека. Развитие простейших - такой же биологический прогресс, но только с точки зрения процветания вида [Горбань, 1988]. Во-вторых, возможно, в этом усматривается некий общий эволюционный принцип: при использовании в качестве наследуемой и мутируемой единицы периода размножения популяция имеет тенденцию не к морфологическому, а к биологическому прогрессу. В биологии тому есть немало примеров.

Как бы то ни было, нас интересует, конечно, именно морфологический прогресс, связанный с совершенствованием организма.

В качестве иллюстрации на Рис.3 приведены фрагменты графиков обобщенных показателей эволюции. При этом параметр «период размножения» (фаза клеточного деления) является мутируемым. Обратите внимание на то, что усредненный показатель качества sQu популяции близок к 1, средний возраст sAge - мал, а средний период размножения sTp в конце концов так же установился на очень небольшом уровне. Как видно, вариабельность фазы клеточного деления приводит, во-первых, к уменьшению периода размножения и, во-вторых, к упрощению структуры особей, что влечет за собой ухудшение показателя качества отдельной особи, но не популяции в целом.



Рис.3. Эволюция вида

Синтезогенез

К.М. Завадским [Завадский, 1970] было введено понятие синтезогенеза - одного из путей эволюции, при котором происходит объединение простых организмов в более сложный. Примером синтезогенеза в природе являются переход от одноклеточных водорослей к многоклеточным, сообщество пчел в улье, муравьев в муравейнике и т.п. Однако это не просто скопление однородных подсистем. Совокупность элементов лишь тогда образует единую систему, когда эти элементы обладают потенциальным свойством образовывать статические или динамические структуры, необходимые для «выживания» элементов и всей их совокупности, т.е. обладают свойством устанавливать взаимодействие друг с другом для достижения локальных или глобальных целей.

Одним из примеров организации синтезогенетических систем является моделирование поведения автоматов на тороидальной поверхности [Варшавский, Поспелов, 1984]. По поверхности тора, разбитой на клетки, перемещаются автоматы с одним действием. При попадании в одну клетку нескольких особей происходит объединение их структур. Тем самым усложняется структура «организма» и, соответственно, изменяется манера его поведения. Следует отметить, что здесь мы имеем не реализацию мажоритарной логики напрямую - в составном объекте четко выражены составляющие его «одноклеточные». Поведение составного автомата строится на основе переключения между поведенческими актами образующих его элементарных автоматов.

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

В основе теории коллективного поведения лежит гипотеза простоты, высказанная М.Л.Цетлиным [Цетлин, 1969]. Суть ее сводится к тому, что любое достаточно сложное поведение слагается из совокупности простых поведенческих актов. Их совместная реализация и простейшее взаимодействие приводят в результате к весьма сложным поведенческим процессам. Отсюда возникла идея о том, что совместное функционирование простых «маленьких зверушек» в сложной среде способно обеспечить устойчивое существование всего коллектива, который можно рассматривать как некий «сверхорганизм».

Выше неоднократно подчеркивалось, что особый интерес представляет морфологический прогресс, приводящий к созданию сложной структуры особи. Однако можно предположить, что функционально-логически между муравейником и, скажем, каким-нибудь «большим животным» различие не так уж велико. Здесь вновь возникает проблема формы-содержания, т.к. речь идет о логической модели с одной стороны и «физической», «пространственной» локализации частей организма - с другой. Совокупность отдельных «узкоспециализированных» особей эквивалентна единому сложному организму, состоящему из множества функциональных частей. Именно в этом смысле колония насекомых эквивалентна (функционально, с точки зрения умения решать задачи) единому, морфологически сложному организму.

Здесь мы подходим к самому проблемному моменту ЭМ - образованию сложных синтезогенетических структур. Схематично процесс функционирования, скажем, автоматного газа можно представить так:

Рис.4. Схема функционирования автоматного газа

Естественно было бы предположить схему, при которой выходные сигналы некоторой части особей были входными для других, т.е. чтобы особи реагировали на действия друг друга, образуя сложные системы рецепторов, формируя понятия внешней и внутренней среды и т.п. Действительно, могла бы получиться красивая картинка (рис.5.):

Рис.5. Коннекционистская модель

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

Только здесь возникает проблема: как оценивать весь этот конгломерат, какие составные части системы наказывать/поощрять, и, главное, за что. Вряд ли здесь подойдет могучий аппарат обучения нейронных сетей в явном виде (см., например, [Горбань, 1990]), ведь наша задача заключается в максимальной естественности как оценки функционирования, так и процедуры наказания/поощрения.

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

«Родственные» направления

Для полноты наших представлений интересно посмотреть, как обстоят дела в аналогичных, родственных направлениях исследований.

Нейронные сети и генетические алгоритмы - это в некотором смысле «близкие» к эволюционному моделированию направления. Близость эта заключается прежде всего в том, что все они, так или иначе, претендуют на глубокие аналогии с биологическими механизмами, используют зачастую одну и ту же терминологию и относятся к бионической ветви ИИ. Более того, иногда все они объединяются в одно направление, называемое «искусственной жизнью» (на самом деле определение «искусственной жизни» выглядит формально несколько иначе, однако сути дела это не меняет). На самом же деле и генетические алгоритмы, и элементы «искусственной жизни», построенные на основе нейроподобных элементов, являются лишь частным случаем (причем, весьма неудачным) эволюционного моделирования. Для начала остановимся вкратце на «искусственной жизни», перейдя затем к более подробному анализу генетических алгоритмов.

Искусственная жизнь и нейронные сети

Отличительной особенностью работ из области т.н. «искусственной жизни» (ИЖ) является активное использование био-, психо-, зоо- и прочих поражающих воображение терминов и аналогий. При этом объект исследования называется животным или, что более благозвучно, аниматом. Несмотря на кажущиеся разнообразия, типичная модель ИЖ выглядит примерно так. Имеется множество аниматов, представленных, скажем, однослойными нейронными сетями. Они «живут» на одномерной (реже - двумерной) поверхности. Часть их рецепторов воспринимает состояние окружающей среды, другая отвечает за определение внутреннего состояния анимата. Сеть, как водится, изначально не обучена. Далее запускается процесс, называемый эволюцией, аниматы, в соответствии с имеющимися весами своей нейронной сети совершают действия - перемещаются, убегают, питаются, размножаются и т.п. Существенным моментом является определение совокупности весов связей мотиваций поведения. А далее делаются разнообразные наблюдения, выводы и проч. Самое интересное заключается в том, что подобные модели могут восприниматься всерьез. Дело даже не в том, что были работы тех же Цетлина и Варшавского, Поспелова и Завадского. Дело даже не в спекулятивной терминологии. Пусть их. Но нельзя же говорить о поведении без памяти, нельзя отрывать генотип от фенотипа, мешать в кучу мутации и параметрическую оптимизацию, вовсе не учитывать обучение. И усложнение моделей аниматов, введение памяти, реализация той же мотивации на ситуационном уровне вряд ли здесь помогут. Дело здесь в отсутствии единой эволюционной методологии, которую нельзя заменить никакими благозвучными терминами.

Генетические алгоритмы

Начнем с формального определения. Генетические алгоритмы (ГА), предложенные Холландом [Holland, 1975] более четверти века назад - это стохастический, эвристический оптимизационный метод, находящий субоптимальное решение за относительно короткое время. Если бы дело ограничивалось только этим, то не стоило бы заниматься сопоставлением ГА с эволюционным моделированием. Однако ГА многими исследователями по-прежнему рассматривается как некое магистральное направление исследований в области искусственного интеллекта, продолжая интриговать окружающих своей терминологией и подводимым под ГА методологическим базисом. Дело в том, что в основе ГА, по мнению их приверженцев, лежит дарвиновская теория эволюции - теория естественного отбора.

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

ГА работают с совокупностью «особей» - популяцией, каждая из которых представляет (описывает) возможное решение некоторой задачи. Качество каждой особи оценивается по тому, насколько «близка» она к искомому оптимальному решению. Это - некая мера «приспособленности» особи. Обычно тут же приводятся аналогии с природой, говоря, что это эквивалентно оценке эффективности организма.

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

При этом действует механизм «естественного отбора», суть которого заключается в следующем. Дело в том, что в ГА выбор родительской пары происходит случайным образом. Но для наиболее приспособленной особи вероятность попадания в кандидаты на размножения больше, чем у менее приспособленной. Так как наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда это объявляют реализацией явления «конкуренции за ресурсы».

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

Итак, фундамент ГА составляют только 2 механизма эволюции - естественный отбор и наследственная изменчивость (или т.н. генетическое наследование). Такой фактор эволюции, как борьба за существование, о котором говорилось выше, явным образом в ГА не фигурирует.

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

...