Введение

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

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

Для простоты в дальнейшем будем считать, что нам надо найти минимум целевой функции от нескольких аргументов дробного типа. Если у функции есть только один минимум (там, где производная функции обращается в ноль, а значение второй производной положительно), то для такого случая хорошо работают различные градиентные методы или алгоритм Нелдера-Мида, который не требует расчета производной функции. Если же у функции несколько экстремумов, то градиентные алгоритмы остановятся на ближайшем экстремуме, и не факт, что этот экстремум будет лучшим на всей области, где мы ищем решение. Или, другими словами, градиентные методы найдут локальный экстремум, а нам хотелось бы найти глобальный.

В качестве примера на следующем рисунке показана одномерная функция Растригина. Наша цель будет найти глобальный минимум, который расположен в точке с координатой x1 = 0.

1 Теоретические сведения

1.1 Описание алгоритма

Наблюдение за птицами вдохновило Крейга Рейнольдса (Craig Reynolds) на создание в 1986 году компьютерной модели, которую он назвал Boids. Для имитации поведения стаи птиц, Рейнольдс запрограммировал поведение каждой из них в отдельности, а также их взаимодействие. При этом он использовал три простых принципа. Во-первых, каждая птица в его модели стремилась избежать столкновений с другими птицами. Во-вторых, каждая птица двигалась в том же направлении, что и находящиеся неподалеку птицы. В-третьих, птицы стремились двигаться на одинаковом расстоянии друг от друга.

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

Как специалист в области компьютерной графики, Крейг Рейнольдс был в первую очередь заинтересован визуальной стороной результатов, созданной им имитации. Однако, в посвященной Boids статье он также отметил, что разработанная им поведенческая модель может быть расширена введением дополнительных факторов – таких, как поиск пищи или боязнь хищников [1].

Алгоритм роя частиц был предложен в 1995 году Джеймсом Кеннеди (Kennedy) и Расселом Еберхартом (Eberhart). Их статья (Kennedy, J.; Eberhart, R. (1995). "Particle Swarm Optimization". Proceedings of IEEE International Conference on Neural Networks IV, pp.1942-1948).

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

2 Описание алгоритмов

2.1 Функция Растригина

Эта функция сложная, и записывается она следующим образом:

3 Расчет характеристик

На рисунке 3.1 представлено главное окно программы.

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

Заключение

В первой статье, описывающей алгоритм роя частиц, Джеймс Кеннеди и Рассел Эберхарт высказывали идею использования алгоритм для имитации социального поведения – Кеннеди, как социального психолога, крайне привлекала эта идея [1]. Однако наибольшее распространение алгоритм получил в задачах оптимизации сложных многомерных нелинейных функций.

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

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

Скриншоты программы