АНАЛИЗ ЭФФЕКТИВНОСТИ НЕКОТОРЫХ МОДИФИКАЦИЙ КЛАССИЧЕСКОГО МЕТОДА РОЯ ЧАСТИЦ

П.Г. Ткаченко

Введение

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

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

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

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

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

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

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

Рассмотрим некоторые из них.

Метод полностью информированного роя (FIPS)

В FIPS [1, 2] сделана попытка учитывать при поиске оптимума не только информацию, предоставляемую лучшим соседом, но использовать прошлый опыт всех соседей. В методе FIPS степень влияния каждого k-го соседа при обновлении j-й компоненты скорости i-й частицы задается с применением весовых коэффициентов:

. (1)

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

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

, (2)

. (3)

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

Избежать возможных трудностей также позволяет разновидность метода полностью информированного роя с рангами (ranked FIPS) [3].

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

Метод роя частиц, основанный на отношении «значение-расстояние» (FDR PSO)

Данный метод предложен в работе [4] и отличается от канонического PSO добавлением еще одного слагаемого в формулу обновления частиц роя. В FDR PSO для каждой j-й частицы рассчитываются значения

(4)

и определяется какая из них по отношению к i-й имеет наименьшую величину критерия «значение-расстояние»:

для всех соответствует. (5)

После этого скорости частиц обновляются по правилу:

, (6)

где – наилучшее решение, найденное k_i-м соседом i-й частицы, с минимальным значением, вычисляемым по формуле (4).

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

Величина FDR с точностью до знака представляет собой приближенное значение градиента в точке i, что в ряде случаев позволяет улучшить локальный поиск в ее окрестности. В тоже время, введение нового параметра с₃ требует дополнительного времени на «настройку» алгоритма.

Метод роя частиц с дополнением графа соседних частиц (DS PSO)

Алгоритм DS PSO предложен в работах [5, 6]. Идея метода состоит в том, чтобы на ранних этапах поиска во избежание преждевременной сходимости к одному из локальных оптимумов использовать меньшее количество связей в рое. На заключительных же этапах количество соседей нужно увеличить, что может повысить скорость сходимости к глобальному оптимуму.

В методе DS PSO на первых итерациях оптимизации используется сильно разреженный граф соседства частиц. Через фиксированное количество итераций в этот граф по некоторому правилу добавляется новое ребро.

Таким образом, на ранних стадиях поиска в DS PSO реализуется стратегия глобального исследования (обзор), а на заключительных – производится уточнение полученного решения (поиск).

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

(7)

итераций. Для перехода от топологии «кольцо» к полносвязной топологии нужно соответственно генерировать новую связь через

(8)

итераций. Также возможен вариант установки связи L_ij случайным образом: добавлением в i-ю строку j-го столбца матрицы инцидентности значения «1».

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

Основной сложностью метода DS PSO является неопределенность в выборе параметра I, так как неизвестно, сколько ориентировочно нужно итераций для окончания процесса оптимизации.

Адаптивный PSO (APSO)

В алгоритме оптимизации роем частиц есть ряд параметров (величины коэффициентов w, c₁, c₂; размер роя s, тип используемой топологии связей), оптимальные значения которых для разных решаемых задач могут быть разными. Вектор значений свободных параметров алгоритма называется его стратегией. Стратегия алгоритма оптимизации в значительной степени определяет его эффективность. Поэтому возникает задача поиска оптимальной стратегии этого алгоритма, которая называется задачей метаоптимизации. Ее решают численными методами, которые можно разделить на две группы – методы управления параметрами и методы настройки параметров [7].

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

В методах управления параметрами задача метаоптимизации решается в процессе решения исходной задачи оптимизации.

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

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

Вариант адаптации величины коэффициента w, предложенный в методе PSO-IIWSS [8] основывается на следующей идее: если значение целевой функции у одной из частиц лучше, чем у другой, то вероятность того, что глобальный оптимум находится в ее окрестности выше. И наоборот, если частица находится в неперспективной области пространства, то имеет смысл покинуть ее как можно быстрее. Описанного результата можно добиться, регулируя величину инерционного коэффициента w каждой частицы. Его уменьшение приводит к более быстрому уменьшению скорости частицы, что может быть полезно для локального поиска. Более высокие значения параметра w приводят к более медленному уменьшению скорости и возможности посещать более отдаленные участки пространства поиска. Для этой цели, текущее значение инерционного коэффициента i-й частицы роя проще всего определять по формуле:

, (9)

где – верхняя и нижняя допустимые границы изменения инерционного коэффициента; – соответственно лучшее и худшее положения частиц в рое в текущий момент времени.

Таким образом, каждая частица обладает своим значением инерционного коэффициента w_i, и его величина меняется в зависимости от текущей позиции частицы и общего состояния роя.

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

, (10)

где w₀ = rand(0.5,1); dist_i – текущее евклидово расстояние от i-й частицы до глобального решения роя, определяемое как

, (11)

а – наибольшее расстояние от частиц до глобального решения, найденного роем на текущей итерации алгоритма, то есть:

. (12)

Благодаря предложенной коррекции инерционного коэффициента, при значительном удалении частицы от глобального решения роя g притяжение к нему усиливается, так как в этом случае параметр w уменьшается, скорость частицы уменьшается и, как следствие, она перестает отдаляться от этого решения. Чтобы избежать преждевременной сходимости, нужно быть уверенным, что частицы обладают достаточной мобильностью на последних этапах оптимизации. Для достижения этой цели уравнения обновления положений частиц модифицируется в соответствии с зависимостью:

, (13)

где – случайное число с равномерным законом распределения на интервале [-0,25; 0,25]. Для когнитивного и социального параметров в [9] рекомендуется использовать значения с₁ = с₂ = 2.

Верификация алгоритмов оптимизации роем частиц

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

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

• сферическая:

; (14)

• эллиптическая:

; (15)

• функция Швефела 1.2:

; (16)

• функция Розенброка:

; (17)

• функция Растригина:

. (18)

Графическое представление данных функций при условии d=2 продемонстрировано на рисунках 1-5.

Рисунок 1 – Графическое представление сферической функции

Рисунок 2 – Графическое представление эллиптической функции

Рисунок 3 – Графическое представление функции Швефела 1.2

Рисунок 4 – Графическое представление функции Розенброка

Рисунок 5 – Графическое представление функции Растригина

Результаты сравнения различных модификаций PSO

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

Результаты расчета сведены в таблицу 1.

Таблица 1 – Результаты расчета

f	Ranked FIPS	FDR PSO	DS PSO	PSO-IIWSS	IA-PSO
f1	38,8	36,6	0	113,2	0
f2	6·105	8·105	0	1,5·106	0
f3	183,4	183,3	1·10-13	171,6	0
f4	3,5·103	7·103	3,8	1,2·104	32,1
f5	118,3	206,8	116,9	146,7	83,2

Заключение

На основании полученных выше данных можно сделать вывод, что наилучшие поисковые качества имеют алгоритмы DS PSO и IA-PSO.