Содержание

Введение

1 Решение задач оптимизации

1.1 Общие сведения об алгоритмах оптимизации функций

1.2 Сложные многомерные функции

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

1.2.2 Функция Швефеля

2 Роевые алгоритмы оптимизации

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

2.2 Модификации роевого алгоритма

3 Разработка программы поиска экстремума функции на базе алгоритма роя частиц

3.1 Работа с программой

3.2 Реализация алгоритма поиска минимума функции

3.3 Тестирование и анализ работы программы

Заключение

Список использованный источников

Приложение A Листинг программы

Выдержка из работы

Введение

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

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

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

Объектом изучения данной курсовой работы являются роевые алгоритмы. Предмет изучения – роевые алгоритмы и методы, изучение и описание коллективного поведения децентрализованной самоорганизующейся системы.

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

Исходя из цели, задачами являются:

- изучение роевых алгоритмов и методов;

- изучение и описание коллективного поведения децентрализованной самоорганизующейся системы;

- создание приложения, использующее роевой алгоритм для решения целевой функции.

1 Решение задач оптимизации

1.1 Общие сведения об алгоритмах оптимизации функций

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

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

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

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

2 Роевые алгоритмы оптимизации

2.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.1.

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

3 Разработка программы поиска экстремума функции на базе алгоритма роя частиц

3.1 Работа с программой

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

Заключение

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

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

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

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

Решены следующие задачи:

- изучены роевые алгоритмы и методы;

- изучены и описаны коллективное поведения децентрализованной самоорганизующейся системы;

- создано приложение, использующее роевой алгоритм для решения целевой функции.

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

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

Список литературы

1 Flocks, Herds, and Schools: A Distributed Behavioral Model. - Computer Graphics, 1987 г.

2 J. Kennedy. Particle swarm optimization / J. Kennedy. - In Proceedings of IEEE International Conference on Neural Networks, 1995 г.

3 R. C. Eberhart. A new optimizer using particle swarm theory / R. C. Eberhart. - Proceedings of the Sixth International Symposium on Micro Machine and Human Science, 1995 г.

4 F. Heppner. A stochastic nonlinear model for coordinated bird flocks / F. Heppner. - The Ubiquity of Chaos, 1990 г.

5 Y. Shi. A modified particle swarm optimizer / Y. Shi. - The 1998 IEEE International Conference on Evolutionary Computation Proceedings, 1998 г.

6 Y. Shi. Empirical study of particle swarm optimization / Y. Shi. - Proceedings of the 1999 IEEE Congress on Evolutionary Computation, 1999 г.

7 M. Clerc. The particle swarm – explosion, stability, and convergence in a multidimensional complex space / M. Clerc. - IEEE Transactions on Evolutionary Computation, 2002 г.

8 R. Mendes. The fully informed particle swarm: Simpler, maybe better / R. Mendes. - IEEE Transactions on Evolutionary Computation, 2004 г.