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

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

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

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

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

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

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

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

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

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

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