Автор работы: Пользователь скрыл имя, 28 Декабря 2011 в 22:11, статья
В этой статье мы попытаемся обосновать необходимость возврата к пониманию сути ЭМ в изначальном его смысле, что должно привести к появлению предпосылок для создания целостной, единой методологии и принципов построения эволюционных интеллектуальных систем.
Эволюционное
моделирование. Проблемы
формы и содержания
Новости искусственного интеллекта №5, 2003
Сложно сказать точно, когда впервые возникла простая идея, заключающаяся в том, что вместо моделирования сложного объекта в уже готовом виде следует заниматься моделированием эволюции некоторого простого объекта. Действительно, запустить эволюционный процесс и ждать, когда с течением времени появится требуемый ответ – это достаточно естественный и привлекательный путь решения сложно формализуемых задач.
История
развития этого направления, называемого
эволюционным моделированием, весьма
характерна и показательна. Не успев
оформиться в некоторую строгую
и формальную теорию, эволюционное
моделирование (ЭМ) на некоторое время
уходит с арены активно
Да и само понимание методологии ЭМ претерпело такие метаморфозы, что была утеряна изначальная цель этого направления. Дело не в формальных определениях и терминологии. Дело в том, что сложившееся понимание ЭМ перестало быть конструктивным.
В этой статье мы попытаемся обосновать необходимость возврата к пониманию сути ЭМ в изначальном его смысле, что должно привести к появлению предпосылок для создания целостной, единой методологии и принципов построения эволюционных интеллектуальных систем.
Впервые, пожалуй, идея ЭМ была явно сформулирована еще в 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,...,y
где x1,x2,..,xn - входная последовательность, y1,y2,...,yn - выходная последовательность символов. Функция ошибки определяет величину штрафа, получаемого автоматом за неверный выходной сигнал (действие или предсказание). Когда величина накопленных особью штрафов превышает некоторое заданное значение, данная особь «умирает» (аналог естественного отбора). Автомат содержит стохастическую матрицу P, определяющую вероятности действий. Выходная реакция автомата yt определяется стохастическим вектором из P, соответствующим состоянию автомата и входному сигналу.
Особи периодически размножаются. Полученная в результате партеногенетического размножения особь наследует свойства (т.е. структуру) своего родителя. Однако при копировании структуры происходят локальные мутации, что обуславливает такой необходимый фактор эволюции, как наследственная изменчивость. Под локальными мутациями понимается множество элементарных структурных изменений: изменение количества состояний автомата, изменение связей между состояниями и т.п. В свою очередь, роль борьбы за существование играет конкуренция коэффициентов размножения автоматов в условиях ограниченного размера популяции.
В результате эволюции популяции происходит процесс формирования особей, которые с минимальными ошибками классифицируют входные последовательности. До сих пор считалось, что фактически мы имеем дело с нерегрессивным поиском в пространстве структур (см., например, [Букатова и др., 1991]). Однако, как будет показано ниже, эволюция – это поиск не только и не столько в пространстве структур (пространстве генотипов), но поиск в комбинированном пространстве – пространстве гено-фенотипов.
Рассмотрим теперь среду, в которую погружены эволюционирующие особи. Назовем некий набор элементарных признаков (ЭП) ji(Xi,Vi) составной средой C={j1,j2,..,jm}. ji - это двойка: вектор признаков Xi=(x1i,x2i,..,xni) и значение характеристической функции (номер класса, если речь идет о решении задачи классификации) Vi , Vi=1,..,n. Понятие составной среды C отличается от составной среды, введенной Цетлиным [Цетлин, 1969]. Различие это заключается прежде всего в детерминированном характере компонентов составной среды. Функционирование распознающей системы состоит в периодическом случайном выборе очередного элементарного признака ji из среды C и предъявления его множеству автоматов. Данный ЭП можно, в свою очередь, рассматривать как стационарную среду, в которую погружается автомат. Мы же, поскольку речь здесь идет о задаче индуктивного вывода, будем трактовать ЭП ji как очередной пример. Индуктивный вывод будет делаться именно на основе множества примеров C. Итак, автомату A периодически предъявляются примеры среды C, правильность классификации которых служит мерой эффективности распознающего (классифицирующего) алгоритма (или автомата, что суть одно и то же). Будем говорить, что множество ЭП фиксированной и одинаковой размерности представляет собой составную среду (С-среду).
И, наконец, введем понятие t-момента времени - значения локального времени, под которым будем понимать порядковый номер текущего символа анализируемой среды. В отличие от абсолютного значения времени моделирования, t-момент времени характеризует именно текущий вектор признаков, т.е. текущую стационарную среду. Особенностью решающих автоматов является отсутствие выделенных конечных (терминальных) состояний. Любое состояние, вообще говоря, может считаться конечным и становится им по достижении конца входной последовательности. В силу отсутствия выделенных терминальных состояний, каждый переход генерирует выходной символ - значение решающей (или классифицирующей) функции в данный 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] было введено понятие синтезогенеза - одного из путей эволюции, при котором происходит объединение простых организмов в более сложный. Примером синтезогенеза в природе являются переход от одноклеточных водорослей к многоклеточным, сообщество пчел в улье, муравьев в муравейнике и т.п. Однако это не просто скопление однородных подсистем. Совокупность элементов лишь тогда образует единую систему, когда эти элементы обладают потенциальным свойством образовывать статические или динамические структуры, необходимые для «выживания» элементов и всей их совокупности, т.е. обладают свойством устанавливать взаимодействие друг с другом для достижения локальных или глобальных целей.
Одним
из примеров организации
С точки зрения эволюционного моделирования наиболее приемлемой формой синтезогенеза могла бы быть популяция из взаимодействующих особей, образующих сложные, возможно, иерархические структуры наподобие сообщества муравьев. Речь здесь идет об изучении моделей коллективного поведения и взаимодействия популяций однородных особей.
В основе теории коллективного поведения лежит гипотеза простоты, высказанная М.Л.Цетлиным [Цетлин, 1969]. Суть ее сводится к тому, что любое достаточно сложное поведение слагается из совокупности простых поведенческих актов. Их совместная реализация и простейшее взаимодействие приводят в результате к весьма сложным поведенческим процессам. Отсюда возникла идея о том, что совместное функционирование простых «маленьких зверушек» в сложной среде способно обеспечить устойчивое существование всего коллектива, который можно рассматривать как некий «сверхорганизм».
Выше неоднократно подчеркивалось, что особый интерес представляет морфологический прогресс, приводящий к созданию сложной структуры особи. Однако можно предположить, что функционально-логически между муравейником и, скажем, каким-нибудь «большим животным» различие не так уж велико. Здесь вновь возникает проблема формы-содержания, т.к. речь идет о логической модели с одной стороны и «физической», «пространственной» локализации частей организма – с другой. Совокупность отдельных «узкоспециализированных» особей эквивалентна единому сложному организму, состоящему из множества функциональных частей. Именно в этом смысле колония насекомых эквивалентна (функционально, с точки зрения умения решать задачи) единому, морфологически сложному организму.
Здесь мы подходим к самому проблемному моменту ЭМ – образованию сложных синтезогенетических структур. Схематично процесс функционирования, скажем, автоматного газа можно представить так:
Рис.4. Схема
функционирования автоматного газа
Естественно было бы предположить схему, при которой выходные сигналы некоторой части особей были входными для других, т.е. чтобы особи реагировали на действия друг друга, образуя сложные системы рецепторов, формируя понятия внешней и внутренней среды и т.п. Действительно, могла бы получиться красивая картинка (рис.5.):
Рис.5. Коннекционистская
модель
Здесь и иерархия могла бы организоваться, если надо, и глубина памяти системы увеличивается. И вообще все это становится очень похожим на многослойную нейронную сеть. Это – типичная коннекционистская модель, в которой «связи решают все».
Только
здесь возникает проблема: как
оценивать весь этот конгломерат, какие
составные части системы
До сих пор предполагалось наличие некоторого внешнего «арбитра», оценивающего работу каждой особи по отдельности, независимо от остальных. На самом деле, этот внешний арбитр – некоторая противоестественность, дань удобству и эффективности. В действительности же явное задание арбитра является серьезнейшим препятствием для синтезогенетического пути развития ЭМ. Вопрос поэтому заключается в поиске преобразования исходной задачи в такую подходящую среду, в которой все шло бы максимально «естественным» путем, а роль арбитра, его оценочной функции сводилась бы непосредственно к задаче выживания популяции.
Для полноты наших представлений интересно посмотреть, как обстоят дела в аналогичных, родственных направлениях исследований.
Нейронные сети и генетические алгоритмы – это в некотором смысле «близкие» к эволюционному моделированию направления. Близость эта заключается прежде всего в том, что все они, так или иначе, претендуют на глубокие аналогии с биологическими механизмами, используют зачастую одну и ту же терминологию и относятся к бионической ветви ИИ. Более того, иногда все они объединяются в одно направление, называемое «искусственной жизнью» (на самом деле определение «искусственной жизни» выглядит формально несколько иначе, однако сути дела это не меняет). На самом же деле и генетические алгоритмы, и элементы «искусственной жизни», построенные на основе нейроподобных элементов, являются лишь частным случаем (причем, весьма неудачным) эволюционного моделирования. Для начала остановимся вкратце на «искусственной жизни», перейдя затем к более подробному анализу генетических алгоритмов.
Отличительной особенностью работ из области т.н. «искусственной жизни» (ИЖ) является активное использование био-, психо-, зоо- и прочих поражающих воображение терминов и аналогий. При этом объект исследования называется животным или, что более благозвучно, аниматом. Несмотря на кажущиеся разнообразия, типичная модель ИЖ выглядит примерно так. Имеется множество аниматов, представленных, скажем, однослойными нейронными сетями. Они «живут» на одномерной (реже – двумерной) поверхности. Часть их рецепторов воспринимает состояние окружающей среды, другая отвечает за определение внутреннего состояния анимата. Сеть, как водится, изначально не обучена. Далее запускается процесс, называемый эволюцией, аниматы, в соответствии с имеющимися весами своей нейронной сети совершают действия – перемещаются, убегают, питаются, размножаются и т.п. Существенным моментом является определение совокупности весов связей мотиваций поведения. А далее делаются разнообразные наблюдения, выводы и проч. Самое интересное заключается в том, что подобные модели могут восприниматься всерьез. Дело даже не в том, что были работы тех же Цетлина и Варшавского, Поспелова и Завадского. Дело даже не в спекулятивной терминологии. Пусть их. Но нельзя же говорить о поведении без памяти, нельзя отрывать генотип от фенотипа, мешать в кучу мутации и параметрическую оптимизацию, вовсе не учитывать обучение. И усложнение моделей аниматов, введение памяти, реализация той же мотивации на ситуационном уровне вряд ли здесь помогут. Дело здесь в отсутствии единой эволюционной методологии, которую нельзя заменить никакими благозвучными терминами.
Начнем с формального определения. Генетические алгоритмы (ГА), предложенные Холландом [Holland, 1975] более четверти века назад – это стохастический, эвристический оптимизационный метод, находящий субоптимальное решение за относительно короткое время. Если бы дело ограничивалось только этим, то не стоило бы заниматься сопоставлением ГА с эволюционным моделированием. Однако ГА многими исследователями по-прежнему рассматривается как некое магистральное направление исследований в области искусственного интеллекта, продолжая интриговать окружающих своей терминологией и подводимым под ГА методологическим базисом. Дело в том, что в основе ГА, по мнению их приверженцев, лежит дарвиновская теория эволюции - теория естественного отбора.
Попробуем разобраться в этом механизме. Он достаточно прост и, на первый взгляд, естественен.
ГА работают с совокупностью «особей» - популяцией, каждая из которых представляет (описывает) возможное решение некоторой задачи. Качество каждой особи оценивается по тому, насколько «близка» она к искомому оптимальному решению. Это – некая мера «приспособленности» особи. Обычно тут же приводятся аналогии с природой, говоря, что это эквивалентно оценке эффективности организма.
Особи, естественно, размножаются. Причем в качестве механизма размножения используется «перекрестное скрещивание» (кросинговер или кросовер, от англ. crossover). В результате такого размножения появляются новые особи, наследующие некоторые свойства своих родителей. Вдобавок при размножении могут происходить мутации - спонтанные изменения в генах.
При этом действует механизм «естественного отбора», суть которого заключается в следующем. Дело в том, что в ГА выбор родительской пары происходит случайным образом. Но для наиболее приспособленной особи вероятность попадания в кандидаты на размножения больше, чем у менее приспособленной. Так как наименее приспособленные особи с меньшей вероятностью смогут воспроизвести потомков, те свойства, которыми они обладали, будут постепенно исчезать из популяции в процессе эволюции. Иногда это объявляют реализацией явления «конкуренции за ресурсы».
Итак, из поколения в поколение, «хорошие» характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В конечном итоге популяция будет сходиться к приблизительно оптимальному решению задачи.
Итак, фундамент ГА составляют только 2 механизма эволюции – естественный отбор и наследственная изменчивость (или т.н. генетическое наследование). Такой фактор эволюции, как борьба за существование, о котором говорилось выше, явным образом в ГА не фигурирует.
Основным тезисом ГА является линейность эволюции, т.е. монотонное улучшение качества потомков: у лучшего родителя остаются лучшие потомки. Это обстоятельство, гарантирующее нерегрессивный поиск, как будет видно далее, заставляет вовсе усомниться в том, имеют ли вообще ГА отношение к моделированию эволюции как таковой.
Проблема формы и содержания. Основной проблемой ГА является, на наш взгляд, принципиальное несоответствие формы содержанию. Обоснование формы представления решения в виде битовой строки заключается в произнесении слов, что, мол, такая кодировка соответствует разбиению пространства параметров на гиперкубы, которым соответствуют уникальные комбинации битов в строке – хромосоме. А бинарные строки в таком случае - это номера таких гиперкубов и т.п.
Такой подход чреват множеством проблем. В ГА при таком раскладе отсутствует, например, понятие «небольшой» мутации. В свое время автору встретилось решение задачи оптимального размещения инвестиций, использующее «непрерывные хромосомы», позволяющие представлять значения произвольных числовых параметров. Битовая строка-хромосома представляла собою двоичный образ действительного числа. Со всеми вытекающими последствиями.
В этом смысле характерными представляются различные попытки улучшения ГА с точки зрения кодировки (или формы представления решений). Например, используется не обычная двоичная кодировка, а рефлексивный код Грея, обладающий свойством непрерывности бинарной комбинации: изменение кодируемого числа на единицу соответствует изменению кодовой комбинации только в одном разряде.
Не случайно от ГА отпочковалось дочернее направление, называемое генетическим программированием (ГП). В ГП объектом эволюции является уже не битовая строка, а дерево. Решение задачи сводится к нахождению соответствующего дерева подходящей структуры. При этом основные механизмы ГА остаются неизменными. Разве что кроссинговер заменяется несколько более сложной процедурой обмена фрагментами деревьев. Воистину, осталось сделать еще несколько шагов в направлении универсализации формы представления решения, и мы придем к автомату в эволюционном моделировании.
Фенотип. Роль фенотипа в ГА сводится исключительно к возможности оценки качества особи. В ГА фенотип особи определяется как точка, принадлежащая гиперкубу пространства поиска соответствующего генотипа. А отсюда следует взаимно однозначное соответствие между генотипом и фенотипом особи. Причем этот факт нисколько не смущает «генетических алгоритмистов», напротив, о нем говорится как о неотъемлемом, центральном свойстве ГА.
Размножение и элиминация. В ГА используются множество методов выбора родительской пары. Здесь и простейший случайный выбор («панмиксия») пары, и селективный выбор, при котором «родителями» могут стать только те особи, значение приспособленности которых не меньше среднего значения приспособленности по популяции, и элитный отбор, основанный на построении новой популяции только из лучших особей репродукционной группы, т.е. сохранение жизни лучшим индивидуумам текущего поколения, и метод рулетки и элитный турнирный отбор.
После выбора родительских пар и размножения старая популяция частично или полностью уничтожается, и мы переходим к рассмотрению следующего поколения.
Итак, суть всех методов сводится к тому, что члены популяции с более высокой приспособленностью будут с большей вероятностью оставлять потомство. Все это подается под маркой «принципа естественного отбора».
Очевидно, что реализация подобного рода механизмов является слишком искусственным, грубым вмешательством как в процесс размножения, так и в процесс элиминации особей, которые должны быть предоставлены «самим себе». И дело не в «некрасивости» подобного решения. Проблема в том, что это – краеугольный камень концепции ГА, ибо именно на этом основывается то, что потомки более приспособленных родителей будут, скорее всего, одними из наиболее приспособленных в своем поколении. А отсюда следует вывод о том, что эволюция в ГА – это процесс, в ходе которого приспособленность особей постепенно (монотонно) повышается.
Беда в том, что при таком подходе выпадают важнейшие факторы эволюции как таковой.
Во-первых, категорически нельзя считать процесс эволюции «линейным». Монотонное улучшение качества потомков в природе наблюдается далеко не всегда. Напротив, виды появляются и исчезают, эволюция одних видов заходит в тупики, тогда как другие достигают своего расцвета. Вся штука в том, что пространство решений, в котором происходит эволюция, вряд ли является метрическим и уж тем более линейным, чтобы можно было вообще всерьез говорить о сходимости и монотонности такого «градиентно-подобного» метода, как ГА.
Во-вторых, механизм размножения/элиминации в ГА отрицает возможность существования такого явления, как промежуточные виды. Промежуточный вид – это некая временная, «худшая» по сравнению с предыдущим форма, необходимая только для того, чтобы успеть дать потомство, «лучшее» по сравнению с предыдущими (своего рода временный пьедестал). У промежуточного вида должен быть шанс оставить потомство.
Роль мутаций в ГА. Главная роль в процессе «видообразования» в ГА принадлежит кроссинговеру. Мутации носят лишь вспомогательный, дополнительный характер. Однако совершенно очевидно, что в природе перекрестное «перемешивание» 60 тыс. генов, суммарная длина которых составляет более 90 млн. нуклеотидов, вряд ли позволит без случайных мутаций получить столь разнообразные даже внутривидовые отличия, какие имеются, скажем, в человеческой популяции.
Именно мутации являются причиной появления новых биологических видов, а кроссинговер определяет лишь дополнительную изменчивость внутри вида (например, генетические различия между людьми).
Но самое главное, что происходит ничем не обоснованный перенос «ДНК–подобного» механизма, механизма полового размножения с «высших» организмов на предельно примитивные формы – строки хромосом в ГА или деревья в генетическом программировании. Впрочем, пусть о достоинствах и недостатках партеногенеза и полового размножения спорят биологи.
Итак, в ГА накопилось слишком много искусственных допущений и механизмов – с одной стороны, и выпало из рассмотрения множество важнейших биологических, эволюционных факторов – с другой. Нельзя выбрасывать борьбу за существование или смешивать ее с естественным отбором; недопустимо говорить о механизме явного формирования новых поколений, тем более что в природе, к которой постоянно аппелируют приверженцы ГА, его нет; теряют смысл такие факторы, как период размножения и тем более – эффекты, связанные с фазой клеточного деления; отсутствие обучения, игнорирование роли фенотипа как такового, сведение его к генотипической составляющей; CF-фактор и многое, многое другое. Все это приводит к тому, что ГА не могут претендовать ни на что иное, нежели на некий оптимизационный поисковый метод, т.е. на то, что понималось изначально.
К настоящему времени разработано великое множество моделей и методов, которые можно отнести (или авторы которых относят) к области, называемой эволюционным моделированием. Однако далеко не всегда эти модели реализуют именно процесс эволюции в явном, невыхолощенном виде. Три фактора могут обусловить успех исследований в области ЭМ, переживающей сегодня сложный, критический момент. Во-первых, необходимо четко понимать цель и суть этого направления. Понимать именно так, как было заявлено изначально, не привнося в угоду коньюнктурным, сиюминутным, обусловленным сложностью решаемых задач соображениям некий новый смысл, иное понимание. Во-вторых, необходимо придерживаться четкой методологии моделирования, в основе которой должны быть именно эволюционные принципы, ибо в противном случае мы получим не моделирование эволюции, а нечто иное. В-третьих, необходимо избегать различного рода искусственных, неестественных приемов и методов. А отсюда следует важность удачного выбора объекта эволюции, позволяющем легко, просто и, главное, естественным образом вводить эволюционные факторы.
Рассмотренная
выше модель особи в виде модифицированного
конечного автомата вряд ли может
считаться наиболее эффективной
и/или бесспорно
Подытожив, можно сказать: не следует плодить сущностей сверх необходимого. Лучший эволюционный процесс – это тот, что идет естественно, сам собою. В этом – залог успеха эволюционного моделирования.
Информация о работе Эволюционное моделирование. Проблемы формы и содержания