В последнее десятилетие роевая оптимизация (PSO) нашла применение во множестве областей, таких как социальное моделирование, компьютерная графика, моделирование и анимация природных стада и стаи, распознавание образов, квантование изображения и вычислительная биология.
Оптимизация роя частиц вызвала значительный интерес со стороны компьютерного сообщества. Исследователи постоянно предлагают различные способы улучшения производительности базового метода, которые можно разделить на две группы: комбинационные и метаоптимизационные. Метаоптимизация связана с процессами настройки или управления свободными параметрами роевого алгоритма [1]. Комбинационные методы подразумевают различные способы объединения PSOc другими методами или алгоритмами с целью компенсации недостатков первого за счёт достоинств вторых.
Цель
Целью работы является метаоптимизационная модификация алгоритма роя частиц на основе использования механизмов дробного исчисления с целью улучшения качества его сходимости.
Материалы и методы исследования
Дробное исчисление (Fractional Calculus) является естественным продолжением классической математики. С начала теории дифференциального и интегрального исчисления, несколько математиков исследовали расчет нецелых производных и интегралов. Тем не менее применение дробного исчисления (FC) было малоизвестно до недавнего времени, но последние научные достижения мотивировали повышенный интерес в этой области.
В качестве оптимизационной составляющей классического роевого алгоритма авторы предлагают использовать дробные производные.
Классический алгоритм роя частиц имеет вид:
Существует некая целевая функция f: ℝn → ℝ , которую следует минимизировать. S – число частиц в рое, каждой частице сопоставлена координата 
∈ ℝn в данном пространстве решений и 
∈ ℝn – скорость.
Пусть 
– лучшее из известных положений частицы i, а 
– наилучшее известное состояние роя в целом. Последовательность шагов алгоритма в общем виде выглядит следующим образом:
Для каждой частицы i = 1, …, S:
-
Генерируется начальное положение частицы с помощью случайного вектора.
-
рисвоить лучшему известному положению частицы его начальное значение: ← .
-
Если (f() < f()), то обновить наилучшее известное состояние роя: ← .
-
Значение скорости частицы:
.
Пока не выполнен критерий остановки (например, достижение заданного числа итераций или необходимого значения целевой функции), повторять:
-
Для каждой частицы i = 1, …, S сделать:
-
Обновить скорость частицы: ←
+ 
( -)
.
где – скорость частицы,
– коэффициент инерции,
когнитивная компонента, которая определяет характеристики частицы относительно ее предыстории,
– социальная компонента, которая характеризует частицу относительно своих соседей,
– лучшее из известных положений частицы i ,
– наилучшее известное состояние роя в целом.
-
Обновить положение частицы переносом на вектор скорости: ← +. Этот шаг выполняется вне зависимости от улучшения значения целевой функции.
-
Если (f() < f()), то:
-
Обновить лучшее известное положение частицы: ← .
-
Если (f() < f()), то обновить лучшее известное состояние роя в целом: ← .
Теперь содержит лучшее из найденных решений.
Результаты исследования и их обсуждение
Существует различные способы улучшения классического алгоритма роя частиц:
1. Создание оптимизационного метода, который состоит из соединения нескольких алгоритмов роя частиц.
2. Разовая настройка характеристик движения частиц, посредством которого можно влиять на вероятность преждевременной сходимости.
3. Оптимизация с динамическим изменением параметров алгоритма.
Ограничение скорости – один из методов повышения эффективности PSO. Для данного метода используется уравнение изменения скорости. Это уравнение содержит три слагаемых, которые регулируют величину и направление изменения скорости частицы. В начальных исследованиях было замечено, что скорость частиц может резко увеличиваться, что является характерным для частиц далеких от лучших глобальных и локальных позиций. В итоге частицы выходят за интересующую границу поиска, то есть расходятся. Во избежание таких ситуаций вводится ограничение скорости.
– максимально допустимая скорость в i – й компоненте. Скорость частицы можно регулировать следующим образом:
Данный подход имеет преимущество в том, что сдерживает резкое увеличение скорости [2]. Ограничение скорости влияет не только на шаг изменения, но и на направление движения частицы.
В данной модификации PSO можно отметить такой важный момент:
При удерживании скорости в определенном диапазоне не ограничивается позиция частицы и из этого следует, что изменяется только скорость.
Выбор
определяет скорость сближения частиц. При 
скорость частицы увеличивается и рой «расходится». Частицам трудно менять направление своего движения для возвращения к наиболее лучшей области поиска решения. При <1 частицы будут замедляться, пока их скорость не станет равной нулю. Из этого выходит, что большие значения предназначены для исследования пространства поиска, а малые для локализации решения. Следует учитывать, что очень малые значения не дают рою исследовать пространство поиска. Чем меньше, тем больше влияние когнитивной и социальной компоненты. Как и остальные параметры, оптимальное значение проблемно-ориентировано (индивидуально для каждой задачи) [5].
Обратим внимание на скорость частицы, которая выражена формулой:
← + ( -) (2)
Если рассматривать , как мгновенную скорость неравномерно движущегося тела (в данный момент времени, в данной точке траектории), можно записать:
(3)
Перепишем формулу для скорости частицы в алгоритме при значении = 1:
(4)
Перенесем 
в левую часть, получаем:
Левую часть можно интерпретировать как разностную аппроксимацию первой производной, т.е.
, где T=1 (6)
Подставим (6) в выражение (5):
(7)
Ввиду нелинейности функции 
допускать самоорганизацию, которая обеспечивает достижение общих целей роя на основе низкоуровневого взаимодействия. Из этого можно сделать вывод, о том, что формулам (4) и (5) присуще свойство нелокальности.
Нелокальность – это понятие, которое можно определить как наличие полной информации о всей системе и её элементах в каждой отдельной точке системы, либо как саму возможность того, что любая точка системы может иметь в себе полную информацию о всей системе.
В правой части (6) член, содержащий , можно интерпретировать как память частицы о ее предыдущем состоянии.
Построение схемы, учитывающей информацию о предыдущих значениях координат частиц 
и скоростей 
может способствовать повышению качества оптимизации целевой функции и улучшению сходимости алгоритма роя частиц.
Однако наличие производной 
в (7) в полной мере не позволяет построить нелокальную модель изменения 
, так как не учитывает возможные значения в более ранние моменты, чем t. Выходом из этого состояния является поиск дифференциального оператора, позволяющего учесть приведенное выше обстоятельство.
Отметим также, что в ряде случаев поведению роя при использовании родственных алгоритмов может быть характерна фрактальная динамика [4], выражающаяся в самоподобной конфигурации роя частиц при выполнении поиска оптимума для некоторых нелинейных функций. Ввиду этого искомый оператор должен допускать возможность своего применения в отношении фрактальных объектов.
Вышеперечисленным требованиям удовлетворяет производная нецелого порядка.
Производная нецелого порядка (или производная дробного порядка) является обобщением математического понятия производной.
Производная дробного порядка – это нелокальная характеристика функции:она зависит не только от поведения функции в окрестности рассматриваемой точки x, но и от принимаемых ею значений на всем интервале (
). Изменение плотности потока частиц зависит не только от её значений в окрестности рассматриваемой точки, но и от её значений в удаленных точках пространства. Понятие дробной производной можно интерпретировать в терминах случайных процессов следующим образом. Случайный процесс, скорость изменения плотности которого зависит от значений плотности в предшествующие моменты времени, называется эредитарным. Такие процессы удобно описывать уравнениями, содержащими дробную производную по времени. Порядок производной по времени определяется величиной α.
Для функции
, заданной на отрезке [], каждое из выражений
(8)
(9)
называется дробной производной порядка 
, 0<
соответственно левосторонней и правосторонней. Дробные производные в приведенном виде называют производными Римана – Лиувилля [3].
Альтернативный подход, основанный на определении производной дробного порядка в терминах предельного перехода, основан на ее определении через формулу Грюнвальда –Летникова:
Для численных расчетов можно использовать конечную аппроксимацию (10):
Запишем формулу (7), учитывая выражение (8)-(11):
(12)
Формула (12) позволяет наблюдать учет предыдущих значений 
и так далее.
Аппроксимируя (12) с порядком r=4 и повышая порядок r, получим:
Оценим качество сходимости алгоритма с учетом аппроксимаций (13),(14) и вклад в него параметра . Результат тестирования изображен на рисунке 1. Для тестирования алгоритма была выбрана функция Розенброка:
+
(15)
Тестовая функция рассматривается в диапазоне 
и имеет глобальный минимум равный 0 в точке (1,1).
Рис. 1. График функции +
Рис. 2. График зависимости лучшего результата от номера итерации с учетом параметра 
Заключение
FC (дробное исчисление) – хорошо развитый математический инструмент, который позволяет понять, как локальные и глобальные скоростные характеристики влияют на поведение PSO. Понятия FC открывают новые перспективы в направлении разработке более эффективной оптимизации роя.
Предложенный способ метаоптимизации, основанный на дробном исчислении, дает возможность для нахождения оптимального значения скорости движения частиц и позволяет сделать предположение о возможности его расхождения для настройки значения свободных параметров из других известных роевых алгоритмов.
Рецензенты:
Привалов А. Н., д.т.н., профессор Тульского государственного педагогического университета им Л. Н. Толстого, г.Тула;
Петраков В. А., д.т.н., профессор, заведующий кафедрой «Системный анализ и управление» Южного государственного университета, г. Ростов-на-Дону.