Коэволюция в методах вычислительного интеллекта

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

Коэволюция в методах вычислительного интеллекта

Л.А. Зинченко

МГТУ им. Н. Э. Баумана, Москва

С.Н. Сорокин

Институт инновационных систем и технологий, Москва

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

Введение

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

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

1. Модели эволюции

коэволюция алгоритм вычислительный интеллект

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

1. Методы, базирующиеся на моделировании принципов естественной эволюции.

2. Методы, имитирующие работу человеческого мозга как адаптивной системы.

3. Методы, базирующиеся на искусственной теории эволюции.

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

В настоящее время теория эволюции по Дарвину развивается в нескольких направлениях. В работах неодарвинистов, в частности в работе Докинз, 1993 ген рассматривается как основной механизм и действующая сила эволюции. Р. Докинз придерживается идеи постепенности эволюции (градуализма) и отрицания эволюционных скачков - сальтаций. Еще одним важнейшим механизмом с точки зрения неодарвинизма, позволяющим проводить отбор лучших решений, является селекция. По мнению Р. Докинза, наиболее приспособленные организмы отбираются как результат отсева случайных мутаций - природа являются слепым часовщиком, который посредством отбора создает удивительную и организованную сложность видов вокруг. Однако работы неодарвинистов на современном этапе не могут обосновать связь между изменениями в генотипе и вызванные этими изменениями изменения в фенотипе. Биология развития изучает влияние генов на развитие эмбриона. В основе работ по биологии развития лежат идеи Аристотеля о том, что в развивающемся организме все части заранее определены и в процессе развития все части просто увеличиваются в своих размерах. Большую роль в биологии развития играет мутация. При этом все мутации в генах подразделяются на доминантные, полудоминантные и рецессивные. Доминантные и полудоминантные мутации приводят к значительным изменениям в фенотипе, тогда как рецессивные мутации проявляются только в процессе скрещивания. С точки зрения биологии развития, в частности Л. Вольперта [Wolpert et al., 2002], эволюция позволяет объяснить, как работает мозг. При этом гены управляют развитием, контролируя время и место синтеза протеина. Таким образом, с точки зрения биологии развития связь между генотипом и фенотипом является более сложной по сравнению подходами, используемыми в эволюционных вычислениях. Синтетическая теория эволюции [Воронцов, 1980] в качестве основного движущего фактора рассматривает естественный отбор организмов, получивших мутации, которые позволяют наилучшим образом адаптироваться к окружающейся среде. Однако результаты экспериментальных исследований в молекулярной биологии привели к созданию теории нейтральности [Кимура, 1985]. Основная идея этой теории базируется на положении, что в эволюции важную роль играют случайные мутации.

Методы, базирующие на искусственной теории эволюции, отличаются большим разнообразием. Эти методы, не имеющие аналогов в живой природе, строятся на основе двух подходов. Первый подход базируется на видоизменении существующих в природе механизмов эволюции. В основе второго подхода лежит введение новых механизмов для создания новых искусственных видов. Примером первого подхода является оператор кроссинговера, широко используемый в алгоритмах эволюционных вычислений. Его отличительной чертой является то, что оператор кроссинговера применяется к любым проектным решениям, при этом не вводятся ограничения на отличительные свойства объектов, например, принадлежность к определенному полу, аналогично процессам, происходящим в естественных средах. Второй подход приводит к использованию механизмов эволюции, не имеющих аналогов в естественной среде. Примером подобного подхода является операторы многородительского скрещивания, использованные, например, в [Зинченко и др., 2003], которые базируются на применении генетических операторов к нескольким решениям для получения нового решения. В результате новое решение является результатом комбинации фрагментов нескольких исходных решений.

Методы, базирующиеся на моделировании работы человеческого мозга как адаптивной системы, позволяют дополнить теорию биологической эволюции символикой, эпигенетическом поведенческим уровнем и эпигенетическом культурным уровнем. В работе [Jablonka et al., 2005]утверждается, что эволюция - это нечто большее, чем гены и случай. Эволюционное развитие представляет собой результат воздействия многих факторов, включающих эпигенетические, культурные факторы, а также символику. Таким образом, эволюция идет одновременно на четырех уровнях: генетическом уровне; на эпигенетическом культурном уровне; на эпигенетическом поведенческом уровне; на символическом уровне. Взаимодействие этих четырех уровней определяет пригодность организма для дальнейшего выживания и размножения. Однако в настоящее время не разработаны математические модели, позволяющие описать весь комплекс взаимодействий между различными уровнями. Преодолеть эту проблему позволяет использование механизмов взаимодействия между различными особями и видами как один из возможных вариантов моделей эволюции.

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

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

К отличительным чертам коэволюционной модели следует отнести:

1. Популяции могут иметь разный размер.

2. Эволюция в разных популяциях может идти на основе различных алгоритмов.

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

Рис. 1. Пример структуры коэволюционной модели

В зависимости от представления требуемого решения модели коэволюции могут быть простые, композиционные и тестовые. В простых моделях коэволюции любое альтернативное решение в каждой популяции может быть требуемым решением. В композиционных моделях требуемое решение компонуется из фрагментов, найденных в различных популяциях. На Рис. 2 показан простейший пример композиционной модели коэволюции. Здесь P1 - часть решения, найденная в первой популяции; P2 - часть решения, найденная во второй популяции. В тестовых моделях элементы одной популяции являются альтернативными решениями, при этом элементы второй популяции являются тестами для найденных альтернативных решений.

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

Рис. 2. Пример композиционной модели коэволюции

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

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

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

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

(2.1)

Здесь N1(t),…, NM(t) - размер популяции; F1(t),…, FM(t) - функции пригодности для соответствующей популяции; M - число популяций, взаимодействующих в процессе коэволюции.

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

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

(2.2)

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

Для описания модели взаимодействия могут быть использованы линейные и нелинейные модели. Одной из наиболее общих нелинейных моделей является ряд Вольтера [Зинченко, 1999]. Однако практическое применение этой модели затруднено сложностью корректного задания ядра Вольтерра. В связи с этим в литературе предлагаются различные упрощенные линейные модели. В частности, в работах [Muhlenbein et al., 2002, Muhlenbein et al., 2006] были предложены различные линейные модели для применения в алгоритмах вычислительного интеллекта.

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

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

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

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

Необходимо отметить, что использование коэволюционной адаптации приводит к тому, что возрастает влияние некорректных решений. Если начальная популяция содержит только некорректные решения, то требуется выполнение нескольких итераций, иногда даже нескольких десятков итераций для того, чтобы избежать дальнейшего размножения некорректных проектных решений. В связи с этим очень важна правильная формулирование концепции решения. В коэволюционных алгоритмах применяются следующие концепции решения [De Jong, 2007].

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

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

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

Понятие множества Парето - оптимальных решений является базой четвертой концепции. В этом случае решение отбираются на основе критерия оптимальности по Парето. В работе [Zinchenko et al., 2008] было показано, что использование коэволюционной адаптации при решении задачи многокритериальной оптимизации позволяет уменьшить вычислительные затраты за счет обмена потенциально полезными решениями между популяциями.

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

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

Заключение

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

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

При использовании коэволюции в задачах оптимизации необходимо учитывать, что при изучении развития различных биологических объектов наблюдается не только эволюционное улучшение, но и эволюционная деградация объектов эволюции. В частности, в [Jones, 1993] отмечается не только положительная роль эволюции, но и ее отрицательная роль. В связи с этим необходимо корректное задание параметров эволюционного процесса.

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

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

1. Воронцов, 1980 Воронцов Н. Н. Синтетическая теория эволюции: ее источники, основные постулаты и нерешенные проблемы. // Журн. Всес. хим. о-ва им. Д. И. Менделеева. 1980. 25(№ 3).

2. Докинз, 1993 Докинз Р. Эгоистичный ген. - М.: «Мир», 1993.

3. Зинченко и др., 2003 Зинченко Л.А., Сорокин С.Н. Эволюционное проектирование элементов телекоммуникационных систем. - Таганрог: Изд-во ТРТУ, 2003.

4.Зинченко, 1999 Зинченко Л.А. Алгоритмы численно-аналитического моделирования и средства программной поддержки САПР электронных устройств. - Таганрог: Изд-во ТРТУ, 1999.

5. Кимура, 1985 Кимура М. Молекулярная эволюция: теория нейтральности. М.: Мир, 1985.

6. De Jong, 2007 De Jong E. Objective fitness correlation // Proc. of the conference Genetic and evolutionary computation GECCO 2007. 2007.

7. Jablonka et al., 2005 Jablonka E. , Lamb M.J. Evolution in Four Dimensions. - MIT Press, 2005.

8 Jones, 1993 Jones S. The Language of the Genes. - HarperCollins, 1993.

9. Muhlenbein et al., 2002 Muhlenbein H., Kureichik V.M., Mahnig Th., Zinchenko L. A. Evolutionary algorithms with hierarchy and dynamic coding in computer aided design // Evolutionary Methods for Design, Optimization and Control with Applications to Industrial Problems. - CIMNE, 2002.

10. Muhlenbein et al., 2006 Muhlenbein H., Hons R. The factorized distribution algorithm and the minimum relative entropy pronciple // Scalable Optimization via Probabilistic Modelingю- Springer, 2006.

11. Wolpert et al., 2002 Wolpert L., Beddington R., Jessell T. et al. Principles of Development. -OxfordUniversity Press, 2002.

Размещено на Allbest.ur