Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Ответы к вопросам к экзамену ММО.docx
Скачиваний:
12
Добавлен:
01.05.2025
Размер:
5 Мб
Скачать
☆
  1. Обзор алгоритмов оптимизации (Даша)

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

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

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

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

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

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

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

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

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

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

Метод пчелиного роя представляет собой эвристический итеративный мультиагентный метод случайного поиска, основная идея которого состоит в моделировании поведения пчёл при поиске нектара. Среди недостатков метода пчелиного роя упоминания заслуживает большое число свободных параметров метода, от значений которых, с одной стороны, зачастую сильно зависит эффективность метода, а с другой - отсутствуют какие-либо содержательные основания для выбора этих значений.