НАУКА и ОБРАЗОВАНИЕ

МГТУ им. Н.Э. Баумана,
105005, Москва, 2-я Бауманская ул., д.5.

Введение

Оптимизация с использованием роя частиц (Particle Swarm Optimization, PSO) – это метод поиска, который базируется на понятии популяции и моделирует поведение птиц в стае и косяков рыб. Первоначальной целью использования концепции роя частиц была графическая имитация красивого и непредсказуемого движения птиц или рыб в стае с целью обнаружения базовых принципов, благодаря которым птицы летают (рыбы плавают) синхронно и умеют менять направление движения с перегруппировкой в оптимальные формации. С тех пор концепция развилась в простой и перспективный оптимизационный метод.

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

            Существует несколько разновидностей метода. В каноническом методе роя частиц, предложенном в 1995 году в работе Kennedy, Eberhart [3], на каждой итерации при определении следующего положения частицы учитывается информация о наилучшей частице из числа «соседей» данной частицы, а также информация о данной частице на той итерации, когда этой частице соответствовало наилучшее значение целевой функции.

1. Описание метода

            Будем рассматривать задачу глобальной безусловной минимизации целевой функции  в -мерном арифметическом пространстве :

.                                                          (1)

            Множество частиц обозначим , где  - количество частиц в рое (размер популяции). В момент времени  координаты частицы  определяются вектором , а ее скорость - вектором . Начальные координаты и скорости частицы  равны , , соответственно.

            Итерации в каноническом методе PSO выполняются по следующей схеме:

;                                                               (2)

.                      (3)

            Здесь  представляет собой -мерный вектор псевдослучайных чисел, равномерно распределенных в интервале ;  - символ покомпонентного умножения векторов;  - вектор координат частицы  с наилучшим (в смысле (1)) значением целевой функции  за все время поиска;  - вектор координат соседней с данной частицы с наилучшим за время поиска значением целевой функции ;  - свободные параметры алгоритма.

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

            В процессе итераций вектор  образует т.н. собственный путь (private guide) частицы , а вектор  - локальный путь (local guide) этой частицы.

            Свободный параметр  определяет «инерционные» свойства частиц (при  движение частиц, очевидно, замедляется). Рекомендуемое значение параметра  равно 0.7298 [2]. В процессе оптимизации может быть эффективным постепенное уменьшение коэффициента  от 0.9 до 0.4. При этом большие значения параметра обеспечивают широкий обзор пространства поиска, а малые – точную локализацию минимума целевой функции. Рекомендуемые значения свободных параметров  равны 1.49618 [2].

            Второй компонент в формуле (3) называется  «когнитивным» компонентом (по социальной аналогии) и формализует тенденцию частицы вернуться в положение с минимальным значением целевой функции. Третий компонент в формуле (3) называется «социальным» компонентом. Компонент отражает влияние на данную частицу ее соседей.

            Вместо формулы (3) часто используют ее вариант

.                                                       (4)

Коэффициент  в этом случае называется ограничивающим фактором (restriction factor),

,

.

Рекомендуемые значения параметров  в этом случае равны 2.05, а их оптимальные значения определяются классом целевой функции  [3].

2. Топологии соседства частиц

Эффективность метода PSO в значительной мере зависит от топологии соседства частиц (population topology, neighbourhood topology, swarm topology, sociometry). Топология соседства определяется неориентированным  графом, вершины которого соответствуют частицам роя, а ребра связывают непосредственных соседей.

            В вычислительной практике чаще всего используются следующие топологии соседства частиц [4]:

·               клика (gbest-топология - глобально оптимальная топология);

·               кольцо (lbest-топология - локально оптимальная топология);

·               двумерный тор (топология фон Неймана);

·               кластерная топология.

            В данной работе рассмотрены две топологии: «кольцо» и «двумерный тор» (фон Неймана).

В топологии «кольцо» соседями каждой из частиц  являются 2 частицы. Например, в графе, приведенном на Рис. 1, соседями частицы  являются частицы , . Диаметр соответствующего графа равен [5] .

Рис. 1. Топологии соседства частиц «кольцо»:

            В топологии «двумерный тор» соседями каждой из частиц ,  являются 4 частицы. Например, в графе, приведенном на Рис. 2, соседями частицы  являются частицы . Если граф типа «двумерный тор» построен на основе  решетки, то диаметр этого графа равен , где  - символ ближайшего целого меньшего; [5].

Рис. 2. Топологии соседства частиц «двумерный тор»:

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

3. Тестовые функции

Рассмотрим основные функции, на которых проводилось тестирование данного метода оптимизации для топологий «кольцо» и фон Неймана. На рисунках 3а, 4а, 5а и 6а изображены линии уровня и траектория частицы в процессе минимизации функций, изображенных на рисунках 3б, 4б, 5б и 6б, соответственно. При построении графиков данных функций использовалась программная система Matlab 6.5.

Функция эллиптического параболоида имеет вид (Рис. 3)

                       .                                                          (5)

Функция Розенброка (Rosenbrock) имеет вид (Рис. 4)

.                                             (6)

Функция Химмельблау (Himmelblau) имеет вид (Рис. 5)

            .                                               (7)

Функция Растригина (Rastrigin) имеет вид (Рис.6)

                             .                                                (8)

4. Исследование эффективности метода

Ниже рассмотрены результаты исследования эффективности PSO-метода топологий «кольцо» и «двумерный тор» для выбранных тестовых функций. Приведены таблицы вычисленных значений оптимизируемой функции для указанных топологий, построены графики сходимости функции в процессе итераций, а также гистограммы достигнутых значений минимизируемой функции. В конце раздела проведен сравнительный анализ эффективности топологий. Начальные позиции частиц генерируются случайным образом в области [-100, 100]^DIM, где DIM – размерность пространства.

Таблица 1. Параметры исследования.

4.1. Результаты исследования эффективности PSO-метода для функции эллиптического параболоида представлены в таблицах 2, 3 и на рис. 7 – 9.

Таблица 2. Топология «кольцо» (150 итераций, n=7)

*) Здесь и далее имеются в виду математическое ожидание и дисперсия достигнутых значений минимизируемой функции .

Рис. 7. Гистограмма значений достигнутых минимумов целевой функции для топологии «кольцо»: Δ=0.02

Здесь и далее Δ – величина шага гистограммы.

Таблица 3. Топология фон Неймана (150 итераций, размерность 7)

Рис. 8. Гистограмма значений достигнутых минимумов целевой функции для топологии фон Неймана: Δ=0.08

Для эллиптического параболоида более эффективной оказалась топология фон Неймана - Σ=0.07 (для топологии «кольцо» - Σ=0.49). Разброс значений минимизируемой функции является незначительным в топологии фон Неймана и существенным в топологии «кольцо».

4.2. Результаты исследования эффективности PSO-метода для функции Розенброка представлены в таблицах 4, 5 и на рис. 10-12.

Таблица 4. Топология «кольцо» (200 итераций, размерность 4)

Рис. 10. Гистограмма значений достигнутых минимумов целевой функции для топологии «кольцо»: Δ=1.13

Таблица 5. Топология фон Неймана (200 итераций, размерность 4)

Рис. 11. Гистограмма значений достигнутых минимумов целевой функции для топологии фон Неймана: Δ=2.22

Для функции Розенброка более эффективной оказалась топология «кольцо» - Σ=3.74  (для топологии фон Неймана - Σ=9.14). Имеет место значительный разброс достигнутых  значений минимизируемой функции. Основной вклад в величину Σ  вносят значения дисперсий (D=2.41 - для топологии «кольца», D=7.56 - для топологии фон Неймана).

4.3. Результаты исследования эффективности для функции Химмельблау представлены в таблицах 6, 7 и на рис. 13-15.

Таблица 6. Топология «кольцо» (100 итераций, размерность 2)

Рис. 13. Гистограмма значений достигнутых минимумов целевой функции для топологии «кольцо»: Δ=0.002

Таблица 7. Топология фон Неймана (100 итераций, размерность 2)

Рис. 14. Гистограмма значений достигнутых минимумов целевой функции для топологии фон Неймана: Δ=0.003

  Рис. 15. Сходимость итераций для топологий: 1 - «кольцо», 2 - фон Неймана

 (80 итераций)

Для функции Химмельблау более эффективной оказалась топология «кольцо» - Σ=0.001 (для топологии фон Неймана - Σ=0.002). Разброс достигнутых значений минимизируемой функции незначителен (см. Рис. 13, 14).

4.4. Результаты исследования эффективности для функции Растригина представлены в таблицах 8, 9 и на рис. 16-18.

Таблица 8. Топология «кольцо» (200 итераций, размерность 4)

Рис. 16. Гистограмма значений достигнутых минимумов целевой функции для топологии «кольцо»: Δ=0.40

Таблица 9. Топология фон Неймана (200 итераций, размерность 4)

Рис. 17. Гистограмма значений достигнутых минимумов целевой функции для топологии фон Неймана: Δ=0.37

Для функции Растригина более эффективной оказалась топология фон Неймана - Σ=1.76 (для топологии «кольцо» - Σ=2.39). В данном случае разброс значений минимизируемой функции незначителен (см. Рис. 16, 17).

5. Заключение

Сравнение оптимизационных свойств метода PSO проводилось по сумме математического ожидания и дисперсии достигнутого значения минимума заданной функции. Для эллиптического параболоида (n=7) и функции Химмельблау (n=2) обе топологии обеспечивают очень хорошую сходимость (достигнутое значение минимума ~10^-3) и малый разброс  достигнутых значений минимизируемой функции (см. Рис. 7, 8, 13, 14). Стоит подчеркнуть, что для функции Химмельблау оптимизация проводилось при размерности пространства DIM = 2.

            Для канонического метода PSO функции Розенброка и Растригина слишком сложны, и для обеих топологий при заданных начальных условиях имеет место плохая сходимость (достигнутое значение минимума ~10³). Поэтому для данных функций была принята размерность пространства DIM = 4 и число итераций было увеличено до 200.

Для функции Розенброка более эффективной оказалась топология «кольцо» - Σ=3.74 (для топологии фон Неймана - Σ=9.14). Хотя математическое ожидание достигнутого значения минимума функции при использовании топологии фон Неймана не сильно отличается от аналогичного математического ожидания при использовании топологии «кольца». Видно, что разброс достигнутых значений при минимизации функции Розенброка очень велик (D=2.41 - для топологии «кольцо», D=7.56 - для топологии фон Неймана). Скорость сходимости выше при использовании топологии фон Неймана (Рис. 12). Наконец, для функции Растригина более эффективной оказалась топология фон Неймана - Σ=1.76 (для топологии «кольцо» - Σ=2.39).

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

1. Субботин С.А., Олейник Ан.А., Олейник Ал.А. (2006) PSO-метод. //«Интеллектуальные мультиагентные методы (Swarm Intelligence)» – Ч.3 – С.55-70.

2. Карпенко А.П., Селиверстов Е.Ю. (2008) «Обзор методов роя частиц (PSO) для задачи глобальной оптимизации» // Наука и образование: электронное научно-техническое издание, www.technomag.edu.ru, март, 2009.

3. J. Kennedy, R. Eberhart (1995) Particle swarm optimization. // Proceedings of IEEE International conference on Neural Networks. – 1995, pp. 1942 - 1948.

 4. R. Mendes, Member, IEEE, J. Kennedy and J. Neves. The Fully Informed Particle Swarm: Simpler, Maybe Better. // IEEE Transactions of Evolutionary Computation, vol. 1, no. 1, January 2025.

5. Marco Doringo et al. (2008) Particle swarm optimization. // Scholarpedia, 3(11):1486.