Вопрос 26: Алгоритмы роевого интеллекта.

Методы решения задач глобальной условной оптимизации

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

Методы решения задачи глобальной безусловной оптимизации деляться на:

• Детерминированные
• Стохастические
• Эвристические

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

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

Распространённые поведенческие методы решения задачи глобальной безусловной оптимизации:

• Метод поведения пчёл.
• Метод колонии Муравьёв
• Метод роя частиц
• Моделирование перемещения бактерий.

В методе оптимизации роем частиц (particle swarm optimization - PSO) агентами являются частицы в пространстве параметров задачи оптимизации. В каждый момент времени (на каждой итерации) частицы имеют в этом пространстве некоторое положение и вектор скорости. Для каждого положения частицы вычисляется соответствующее значение целевой функции, и на этой основе по определённым правилам частица меняет своё положение и скорость в пространстве поиска. В основу метода PSO положена социально-психологическая поведенческая модель толпы. Существует несколько разновидностей метода. В каноническом методе роя частиц (1995 г.) на каждой итерации при определении следующего положения частицы учитывается информация о наилучшей частице из числа «соседей» данной частицы, а также информация о данной частице на той итерации, когда этой частице соответствовало наилучшее значение целевой функции. Модификация канонической модели FIPS учитывает значения целевой функции, соответствующие всем частицам роя; в некоторых моделях частицы группируются в несколько роёв и т. д.

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

Динамика популяции общественных насекомых определяется взаимодействиями насекомых друг с другом, а также с окружающей средой. Эти взаимодействия осуществляются посредством различных химических и/или физических сигналов, например феромонов, выделяемых муравьями. Метод пчелиного роя (Bees Algorithm) является одним из новейших методов, относящихся к рассматриваемому направлению. Первые статьи, в которых был предложен данный метод, опубликованы в 2005 году. Метод представляет собой эвристический итеративный мультиагентный метод случайного поиска, основная идея которого состоит в моделировании поведения пчёл при поиске нектара. Среди недостатков метода пчелиного роя упоминания заслуживает большое число свободных параметров метода, от значений которых, с одной стороны, зачастую сильно зависит эффективность метода, а с другой - отсутствуют какие-либо содержательные основания для выбора этих значений.