ИЗВЕСТИЯ РАИ. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2007, № 5, с. 114-126
^ ИСКУССТВЕННЫЙ
ИНТЕЛЛЕКТ
УДК 628.321.3
АНАЛИЗ И ОБЗОР МОДЕЛЕЙ ЭВОЛЮЦИИ*
© 2007 г. В. В. Курейчик, В. М. Курейчик, П. В. Сороколетов
Таганрог, Технологический ин-т Южного Федерального ун-та Поступила в редакцию 20.02.07 г.
Рассматривается анализ и обзор основных моделей эволюции. Приведены структурные схемы моделей эволюции, на их основе построены архитектуры поиска решений задач искусственного интеллекта. Это позволяет разрабатывать алгоритмы принятия решений с локальными оптимумами за полиномиальное время. Сложность алгоритмов имеет в среднем квадратичный порядок.
Введение. В настоящее время предпринимаются попытки применить биологические аналоги при разработке и создании интеллектуальных искусственных систем. При этом важнейшей проблемой является согласование концепций биологии, информационных технологий и искусственного интеллекта [1-14].
При построении общей стратегии создания интеллектуальных искусственных систем (ИС) перед учеными все время возникают вопросы, связанные с развитием природы. Какие пути эволюции выбирает природа? Почему природа экономна? Почему она идет оптимальным путем? Каким образом природе удается найти наиболее устойчивые формы? Как происходит самоорганизация? Какие механизмы лежат в основе алгоритмов построения порядка из хаоса? Как природа научилась ускорять эволюцию? И многие другие. Д. Дидро говорил: "Похоже, природе доставляет удовольствие варьировать один и тот же механизм бесконечным числом различных способов" [2, 4, 9, 14]. Моделирование развития и совершенствования природы позволяет найти новые пути построения интеллектуальных ИС. Основным направлением здесь может выступить эволюционное моделирование [11, 14, 15].
Под эволюцией понимаются медленные, постепенные, количественные и качественные изменения объекта. При этом каждое новое состояние объекта должно иметь по сравнению с предыдущим более высокий уровень развития и организации [13]. Эволюция приводит к формированию адаптаций (приспособлений) организмов к условиям их существования, изменению генетического состава от популяции видов, а также отмиранию неприспособленных видов [16, 17]. В настоящее время считается, что эволюция осуществляется под воздействием четырех основных признаков: наследственности, изменчивости, естественного и искусственного отборов [8, 1315, 18]. Суть метода эволюции состоит в реализа-
* Работа выполнена при финансовой поддержке РФФИ (гранты < 05-08-18115; 06-01-00272).
ции целенаправленного процесса "размножения-исчезновения", при котором размножению соответствует появление новых объектов, а исчезновению - удаление объектов из процесса в соответствии с определенным критерием естественного отбора (или селекции) [13]. В статье проведен анализ и обзор основных моделей эволюции. На их основе построены архитектуры процедур поиска решений для задач искусственного интеллекта [3]. При этом возможно создавать комбинированные, гибридные алгоритмы, в которых осуществляется параллельная обработка информации. Такие алгоритмы позволяют получать наборы альтернативных решений с локальными оптимумами за полиномиальное время. Сложность алгоритмов имеет в среднем квадратичный порядок.
1. Модели и архитектуры эволюции. Модель эволюции Ч. Дарвина - это условная структура, реализующая процесс, посредством которого особи некоторой популяции, имеющие более высокое функциональное значение, получают большую возможность для воспроизведения потомков, чем "слабые" особи. Такой механизм часто называют методом "выживания сильнейших" [13, 16]. Движущими силами эволюции по Ч. Дарвину выступают: неопределенная изменчивость, т.е. наследственно обусловленное разнообразие организмов каждой популяции; борьба за существование, в ходе которой устраняются от размножения менее приспособленные организмы; естественный отбор - выживание более приспособленных особей, в результате которого накапливаются и суммируются полезные наследственные изменения и возникают новые адаптации [5].
Существует спектр путей развития, по которым может пойти эволюция Ч. Дарвина. Возможный путь развития здесь определяет случайность. Эволюция по Ч. Дарвину состоит из ряда положений. В природе все подвержено неопределенной наследственной изменчивости, производится потомство, отличающееся по многим признакам; все
организмы в природе размножаются в геометрической прогрессии, по численности всех организмов в среднем остается более или менее постоянной, она колеблется около средней величины; основой отбора является метод "выживания сильнейших" [13]. На рис. 1 приведена условная упрощенная схема модели эволюции Ч. Дарвина.
На основе данной схемы представим примерный алгоритм (А1) решения оптимизационной задачи.
1. Популяция. Пусть заданы популяция альтернативных решений исходной задачи и дискретное время эволюции Т, определяющее количество генераций алгоритма.
2. Наследственность. После реализации каждой генерации алгоритма появляется новое поколение (потомство) альтернативных решений.
3. Изменчивость. В новой популяции (поколении) остаются отличающиеся друг от друга альтернативные решения.
4. Отбор. По заданным правилам отбираются элитные решения с лучшим значением целевой функции. Это соответствует принципу Ч. Дарвина "выживают сильнейшие".
5. Эволюционная смена форм. Лучшие решения "выживают" в результате реализации схемы эволюции Дарвина и постепенно, поколение за поколением становятся преобладающими (доминирующими) в данной популяции.
Модель эволюции Ж. Ламарка [14, 15, 19]. Она основана на предположении, что характеристики, приобретенные особью (организмом) в течение жизни, наследуются его потомками. Эти изменения, как утверждал Ж. Ламарк, вызываются прямым влиянием внешней среды, упражнением органов и наследованием приобретенных при жизни признаков. Он объясняет одну из особенностей эволюции органического мира приспособляемостью. Прогрессивная эволюция, появление форм, более сложных и совершенных, объясняется "законом градаций" - стремлением живых существ усложнять свою структуру. Согласно Ж. Ламар-ку, виды эволюционируют, приспособляясь и усложняясь, потому что у них существуют свойства - приспосабливаться и усложняться [14, 15]. На рис. 2 приведена условная упрощенная схема модели эволюции Ж. Ламарка.
На основе данной схемы запишем примерный алгоритм (А2) решения оптимизационной задачи.
1, 2. Популяция + Наследственность. Как видно из схемы, первые два пункта аналогичны алгоритму А1.
3. Внешняя среда. Происходит воздействие внешних факторов в виде указаний от экспертной системы и лица, принимающего решение (ЛПР).
Рис. 1. Условная упрощенная схема модели эволюции
Ч. Дарвина.
4. Приспособляемость. В условиях изменившихся параметров поиска создается новая популяция, ориентированная на сигналы внешней среды.
5, 6. Отбор + Эволюционная смена форм. Эти этапы аналогичны алгоритму А1.
Согласно Ж. Ламарку [5], предполагается, что живые организмы способны сами находить верное решение, как себя улучшить, и, более того, сами же способны свое решение осуществлять. Направленная изменчивость здесь не причина, а всегда результат эволюционного процесса. Данная модель не получила применения в биологии. Авторы считают, что она полезна при решении технических задач, когда популяция имеет сходимость в область локального оптимума [14, 15, 19].
Модель эволюции Г. де Фриза [5, 14, 15, 18]. В ее основе лежит моделирование социальных и географических катастроф, приводящих к резкому изменению видов и популяций. На рис. 3 приведена условная упрощенная схема модели эволюции Г. де Фриза. Идею этого алгоритма для реше-
Рис. 2. Условная упрощенная схема модели эволюции Ж. Ламарка.
Рис. 3. Условная упрощенная схема модели эволюции де Фриза.
ния оптимизационных задач можно представить следующим образом. Пусть существует популяция альтернативных решений исходной задачи и задано дискретное время эволюции Т, определяющее количество генераций алгоритма. В ходе эволюции данной популяции происходит постепенная смена поколений. Причем изменения генотипа популяции носят регулярный постепенный характер. Под воздействием внешней среды на некотором шаге эволюции данная популяция случайным образом подвергается катастрофическому воздействию, которое приводит к значительному сокращению (или уничтожению) популяции и вызывает кардинальное изменение генотипа. Вследствие этого "выживает" лишь незначительное количество альтернативных решений из рассматриваемой популяции. Эти пережившие катастрофу решения составят впоследствии новую популяцию с новыми качествами, которая заменит старую, и процесс эволюции будет продолжаться. Эволюция, таким образом, представляет собой последовательность скачков в развитии популяции без предварительного накопления количественных изменений в эволюционных процессах. Такой механизм эволюции иногда называют эволюцией катастроф. Он проявляется один раз ориентировочно в несколько тысяч поколений. Основная идея его состоит во внесении глобальных изменений в генофонд на момент катастрофы [18].
Модель прерывистого равновесия Гулда-Элдри-
джа [18]. В начале 70-х годов Н. Элдридж и С. Гулд предложили новую модель эволюции - прерывистого равновесия, когда эволюция происходит редкими и быстрыми толчками. Следует отметить, что эти идеи высказывали еще Ч. Дарвин, Г. де Фриз и др. Эта модель является развитием и модификацией модели Г. де Фриза. Здесь отмечается различие причин, от которых зависят темпы
Рис. 4. Структура макроэволюции.
микро- и макроэволюции. На рис. 4 и 5 приведены условные структуры микро- и макроэволюции согласно модели Гулда-Элдриджа, ориентированные на моделирование технических задач принятия решений.
Процессы микро- и макроэволюции описывает модель эволюции Шмальгаузена [5]. Эволюционирующую популяцию и внутривидовую дифференциацию популяций Шмальгаузен представил как трехмерную решетку. В ней каждая плоскость - это эволюция особи, прошедшей естественный отбор, а вершины (узлы) ячейки - ре-
Рис. 5. Структура микроэволюции.
зультат их скрещивания. Модель также демонстрирует
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.