В настоящее время в науке и технике находят широкое применение алгоритмы, основанные на природных системах. К ним относятся генетические, эволюционные, алгоритмы роевого интеллекта и пр. В работе рассматриваются алгоритмы и методы роевого интеллекта.
Алгоритм роя частиц широко применяется, в числе прочих, в задачах машинного обучения (в частности, для обучения нейросетей и распознавания изображений), параметрической и структурной оптимизации (форм, размеров и топологий) в области проектирования, в областях биохимии и биомеханики. По эффективности он может соперничать с другими методами глобальной оптимизации, а низкая алгоритмическая сложность способствует простоте его реализации.
Наиболее перспективными направлениями дальнейших исследований в данном направлении следует считать теоретические исследования причин сходимости алгоритма роя частиц и связанных с этим вопросов из областей роевого интеллекта и теории хаоса, комбинирование различных модификаций алгоритма для решения сложных задач, рассмотрение алгоритма поя частиц как многоагентной вычислительной системы, а также исследование возможностей включения в него аналогов более сложных природных механизмов.
Объектом изучения данной курсовой работы являются роевые алгоритмы. Предмет изучения – роевые алгоритмы и методы, изучение и описание коллективного поведения децентрализованной самоорганизующейся системы.
Целью данной курсовой работы является написание пакета программ, осуществляющих использование и тестирование роевого алгоритма, и выбор целевой функции.
Исходя из цели, задачами являются:
- изучение роевых алгоритмов и методов;
- изучение и описание коллективного поведения децентрализованной самоорганизующейся системы;
- создание приложения, использующее роевой алгоритм для решения целевой функции.
При решении многих задач приходится иметь дело с оптимизацией функций (которую называют целевой функцией) в зависимости от многих параметров. В качестве такой функции, например, может быть количество пересечений дорожек на печатной плате в системе автоматизированного проектирования в зависимости от расположения элементов на плате, или количество ошибок, допущенных нейронной сетью при обучении в зависимости от ее весовых коэффициентов. Оптимизация используется при составлении расписаний, в различных математических задачах, например, задаче коммивояжера или задача об N ферзях и во многих других областях.
Оптимизация (от лат. optimum — наилучшее), процесс нахождения экстремума (глобального максимума или минимума) определённой функции или выбора наилучшего (оптимального) варианта из множества возможных.
Для простоты в дальнейшем будем считать, что нам надо найти минимум целевой функции от нескольких аргументов дробного типа. Если у функции есть только один минимум (там, где производная функции обращается в ноль, а значение второй производной положительно), то для такого случая хорошо работают различные градиентные методы или алгоритм Нелдера-Мида, который не требует расчета производной функции. Если же у функции несколько экстремумов, то градиентные алгоритмы остановятся на ближайшем экстремуме, и не факт, что этот экстремум будет лучшим на всей области, где мы ищем решение. Или, другими словами, градиентные методы найдут локальный экстремум, а нам хотелось бы найти глобальный.
В качестве примера на следующем рисунке показана одномерная функция Растригина. Наша цель будет найти глобальный минимум, который расположен в точке с координатой x1 = 0.
Наблюдение за птицами вдохновило Крейга Рейнольдса (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.1.
Чтобы понять алгоритм роя частиц, представьте себе n-мерное пространство (область поиска), в котором рыщут частицы (агенты алгоритма). В начале частицы разбросаны случайным образом по всей области поиска и каждая частица имеет случайный вектор скорости. В каждой точке, где побывала частица, рассчитывается значение целевой функции. При этом каждая частица запоминает, какое (и где) лучшее значение целевой функции она лично нашла, а также каждая частица знает где расположена точка, являющаяся лучшей среди всех точек, которые разведали частицы. На каждой итерации частицы корректируют свою скорость (модуль и направление), чтобы с одной стороны быть поближе к лучшей точке, которую частица нашла сама (авторы алгоритма назвали этот аспект поведения «ностальгией»), и, в то же время, приблизиться к точке, которая в данный момент является глобально лучшей. Через некоторое количество итераций частицы должны собраться вблизи наиболее хорошей точки, хотя возможно, что часть частиц останется где-то в относительно неплохом локальном экстремуме, но главное, чтобы хотя бы одна частица оказалась вблизи глобального экстремума.
На рисунке 3.1 представлено главное окно программы.
В первой статье, описывающей алгоритм роя частиц, Джеймс Кеннеди и Рассел Эберхарт высказывали идею использования алгоритм для имитации социального поведения – Кеннеди, как социального психолога, крайне привлекала эта идея [1]. Однако наибольшее распространение алгоритм получил в задачах оптимизации сложных многомерных нелинейных функций.
Алгоритм роя частиц широко применяется, в числе прочих, в задачах машинного обучения (в частности, для обучения нейросетей и распознавания изображений), параметрической и структурной оптимизации (форм, размеров и топологий) в области проектирования, в областях биохимии и биомеханики. По эффективности он может соперничать с другими методами глобальной оптимизации, а низкая алгоритмическая сложность способствует простоте его реализации.
Наиболее перспективными направлениями дальнейших исследований в данном направлении следует считать теоретические исследования причин сходимости алгоритма роя частиц и связанных с этим вопросом из областей роевого интеллекта и теории хаоса, комбинирование различных модификаций алгоритма для решения сложных задач, рассмотрение алгоритма роя частиц как многоагентной вычислительной системы, а также исследование возможностей включения в него аналогов более сложных природных механизмов.
В ходе работы над курсовым проектом была достигнута поставленная цель – разработан роевый алгоритм для решения целевой функции.
Решены следующие задачи:
- изучены роевые алгоритмы и методы;
- изучены и описаны коллективное поведения децентрализованной самоорганизующейся системы;
- создано приложение, использующее роевой алгоритм для решения целевой функции.
Анализ приведенных в работе методов эволюционного моделирования, роевого интеллекта, относящихся к методам искусственного интеллекта, а также выявленные недостатки данных методов предоставляют возможность дальнейших исследований в плане разработки новых методов, методик, алгоритмов для решения широкого класса научных и практических задач.
Развитие темы проекта в дальнейшем может заключаться в добавлении целевых функций, методов решения.
