Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,940

OPTIMIZATION PARTICLE SWARM BASED ON THE METHOD OF FRACTIONAL CALCULUS

Dutova I.G. 1 Mokhov V.A. 1 Kuznetsova A.V. 1 Esaulov V.A. 1
1 South-Russian State Technical University
Spend a research project in which was considered particle swarm optimization based on the method of fractional calculus. As part of the optimization of the classic swarm algorithm proposed fractional derivative. Applying the kind of optimization with dynamic changes in the parameters of the algorithm. This parameter is selected speed. In early studies, it was observed that the velocity of the particles can increase dramatically, which is typical of the particles are far from the best global and local positions. As a result, the particles go beyond the boundaries of search, that is dispersed. To avoid such situations, the speed limit is introduced. In this approach, a clear advantage ceases containment sharp increase in speed. Also important is the fact that in some cases the behavior of the swarm using algorithms related characteristic fractal dynamics, expressed in the self-similar configuration particle swarm finding the optimum for certain nonlinear functions. In view of this statement was searched, which will satisfy the above requirements. That statement is a derivative of non-integer order (fractional).
Swarm optimization
fractional calculus
fractional derivative
optimization

В последнее десятилетие роевая оптимизация (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 открывают новые перспективы в направлении разработке более эффективной оптимизации роя.

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

Рецензенты:

Привалов А. Н., д.т.н., профессор Тульского государственного педагогического университета им Л. Н. Толстого, г.Тула;

Петраков В. А., д.т.н., профессор, заведующий кафедрой «Системный анализ и управление» Южного государственного университета, г. Ростов-на-Дону.