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

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

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

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

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

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

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

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

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

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

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

(2.1).

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

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

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

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

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