"Рой частиц" как наиболее простой метод эволюционного программирования, основанный на идеи о возможности решения задач оптимизации с помощью моделирования поведения групп животных. Схема работы алгоритма, составление кода программы и блок-схемы.
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Введение
Ещё со времён Ламарка развитие живого мира рассматривается как процесс постоянного совершенствования (приспособления) особей под влиянием среды. Моделируя отбор лучших планов, как процесс эволюции в популяции особей, можно получить решение задачи оптимизации, задав начальные условия эволюционного процесса, населив виртуальную вселенную существами - носителями информации и указав цель эволюционного процесса.
Копируя действия природы, человек создает всё более и более совершенные алгоритмы оптимизации. Для их создание чаще всего служат примеры из природы, например: генетический код или поведение птиц, моделирование миграций рыб или охлождение металла и т.д.
В настоящее время на производстве и в бизнесе широко используются алгоритмы оптимизации, так как они дают возможность сэкономить не только денежные средства, но и время, которого постоянно не хватает.
На производстве, благодаря оптимизации, решается множество проблем связанных с такими вещами как простой станка, переполнение склада или же перенаправление запчастей на другие станки при поломке.
Для данной работы был выбран метод оптимизации «рой частиц». Алгоритм метода благодаря своей простоте и скорости считается очень перспективным для задач планирования.
1 . Постановка задачи
1.1 Математическая модель
Метод «рой частиц» - наиболее простой метод эволюционного программирования, появившийся в середине 90-х годов, основанный на идеи о возможности решения задач оптимизации с помощью моделирования поведения групп животных. В основу метода положен тот факт, что при формировании стаи птицы стремятся к некоторому центру «притяжения», постепенно замедляя скорость полёта.
Когда стая ищет еду, её представители будут проверять прилегающую область и двигаться вокруг стаи независимо друг от друга. Каждый представитель имеет степень свободы или хаотичности в движении, которая даёт ему возможность найти скопление пищи. Так, рано или поздно, один из них найдет, что-то съедобное, и, будучи частью стаи, сообщит остальным. Остальные также могут тогда приблизиться к источнику пищи, и уже каждый представитель, благодаря степени свободы и хаотичности своего движения может найти новое скопление пищи.
В реализации данного алгоритма многомерное пространство поиска населяется роем частиц (элементарных решений). Координаты частицы в пространстве однозначно определяют решение задачи оптимизации. Помимо координат каждая из частиц описывается скоростью перемещения и ускорением. В процессе перемещения частицы осуществляют «прочёсывание» пространства решений и тем самым находят текущий оптимум, к которому на следующем шаге устремляются остальные частицы. Каждая частица запоминает своё лучшее положение, данные о котором передаются соседним частицам, которые стремятся к этому значению.
Для введения случайной составляющей в процесс поиска могут быть включены «сумасшедшие» частицы, закон движения которых отличается от закона движения остальных.
2 . Реализация алгоритма
2.1Схема работы алгоритма
Схема работы алгоритма выглядит следующим образом:
1. Создаётся исходная «случайная» популяция частиц.
2. Для каждой частицы рассчитывается целевая функция.
3. Лучшая частица с точки зрения целевой функции объявляется «центром притяжения».
4. Векторы скоростей всех частиц устремляются к этому «центру», при этом чем дальше частица находится от него, тем большим ускорением она обладает.
5. Осуществляется расчёт новых координат частиц в пространстве решений.
6. Шаги 2-5 повторяются заданное число раз или пока не выполнится условие остановки.
7. Последний «центр тяжести» объявляется найденным оптимальным решением.
2. 2 Код программы
#include
#include
#include
#include
const int n=200;
const int m=200;
int i, j, k, t=200;
double F (double x)
return pow (pow(x, 3) - 125,2);
{double V[n] [m];
double lower_limit=1, upper_limit=300;
double best_pos[n] [m];
double cel[n] [m]; // массив генотипа
double best_cel=1000; // лучшее глобальное значение
const double C1=0.7, C2=1.2, w=0.93;
double **X=new double*[n];
for (i=0; i X[i]=new double[m]; srand (time(NULL)); // инициализация положения и скоростей частиц for (i=0; i for (j=0; j X[i] [j]=lower_limit + (upper_limit - lower_limit)*rand()/RAND_MAX; // Инициалиция генотипом частиц самым худшем best_pos[i] [j]=1000; for (k=0; k // заполнение массива генотипов for (i=0; i for (j=0; j // определение текущего генотипа cel[i] [j]=F (X[i] [j]); // сохранение значения лучшего генотипа для каждой частицы if (cel[i] [j] best_pos[i] [j]=cel[i] [j]; if (best_pos[i] [j] best_cel=best_pos[i] [j]; printf («%f\n», x); // Обновление скоростей частиц и их позиций for (i=0; i for (j=0; j R1 = 1.*rand()/RAND_MAX; R2 = 1.*rand()/RAND_MAX; V[i] [j] = w*V[i] [j] + C1*R1*(best_cel - X[i] [j]) + C2*R2*(best_pos[i] [j] - X[i] [j]); X[i] [j] = X[i] [j] + V[i] [j]; 2.3 Блок схема алгоритма
Размещено на http://www.allbest.ru/ Размещено на http://www.allbest.ru/ 3
.
Теоретическая оценка трудоемкости алгоритма оптимизации
Для теоретической оценки трудоемкости алгоритма необходимо определить количество элементарных операций, которые необходимо выполнить для решения задачи с помощью данного алгоритма. Под элементарными операциями, будем понимать операции, которые могут быть представлены в виде элементарных конструкций данного языка (но не обязательно в виде одной машинной команды), а именно за одну элементарную операцию будем считать следующие: 1) операцию присваивания ab; 2) операцию индексации массива a[i]; 3) арифметические операции *,/,-,+; 4) операции сравнения a < b; 5) логические операции or, and, not. Цикл for не является элементарной операцией, т.к. может быть представлен в виде; Таким образом конструкция цикла требует 2*N элементарных операций: F
«цикл»
= 2*
N
+
N
*
f
«тело цикла».
Таким образом, для нашей программы получим: F=9+ // константы 2*200+200*(2*200+(8+6)*200)+ // инициализация положения и скоростей 2*200+200*(2*200+200*(2*200+200*(6+20))+ // заполнение массива генотипа и лучших значений 2*200+200*(2*200+200*(4+4+10+2+16)) // обновление скоростей и позиций В результате теоретического вычисления трудоемкость данной программы составила F= 528800809 элементарных операций. Заключение
программа алгоритм моделирование В последнее время стало появляться очень много новых алгоритмов, которые основанны на подражании природе, но не каждый алгоритм может похвастаться такой простатой реализации и оригинальностью идеи. Благодаря случайности распределения частиц и их хаотичности в движении пояляется очень большая вероятность найти оптимальное решение за несколько итераций, избегая при этом локальные оптимумы. Дальнейшее развитие подобных алгоритмов является ключём к новым технологиям оптимизации и развития в целом. Список использованных источников
1. Ульянов М.В., Шептунов М.В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. - М.: МГАПИ, 2003. - 80 с. 2. Конспект лекций по дисциплине «Математическая логика и теория алгоритмов». 3. Global Optimization Algorithms - Theory and Application. 4. http://ru.wikipedia.org Размещено на Allbest.ru Особенности задач линейного программирования. Симплексный метод решения задач линейного программирования. Обоснование выбора языка, инструментария программирования, перечень идентификаторов и блок-схема алгоритма. Логическая схема работы программы. дипломная работа , добавлен 13.08.2011 Рзработка библиотеки, которая позволит моделировать динамику частиц в трехмерной графики. Выбор средств и методов разработки. Варианты моделирования систем частиц. Моделирование на вершинном шейдере. Диаграммы класса Particle System и PSBehavior. курсовая работа , добавлен 07.02.2016 Основные аналитические соотношения. Блок схемы и алгоритм решения задачи. Проверка работоспособности алгоритма вручную. Таблица идентификации переменных. Формы входной и выходной печати. Разработка и отладка программы. Инструкция для работы с программой. курсовая работа , добавлен 13.02.2012 Понятие линейного программирования и оптимизации. Основы работы в системе MathCAD. Интерфейс пользователя, входной язык и тип данных. Этапы компьютерного математического моделирования. Пример решения оптимизационной задачи средствами программы MathCAD. курсовая работа , добавлен 16.10.2011 Создание программы в среде программирования MatLab для решения задачи одномерной оптимизации (нахождение минимума и максимума заданных функций) методом золотого сечения, построение блок-схемы алгоритма и графическое изображение исследованных функций. реферат , добавлен 14.06.2010 Система программирования Delphi, ее характеристика. Основные требования к обучающей программе. Составление блок-схемы алгоритма программы "Математика. 1 класс". Виды задач для решения в обучающей программе. Описание работы системы, инструкция к ней. курсовая работа , добавлен 17.06.2015 Оптимизация решения задачи с помощью алгоритма отжига. Анализ теории оптимизации как целевой функции. Метод градиентного спуска. Переменные и описание алгоритма отжига. Представление задачи коммивояжера через граф. Сведение задачи к переменным и решение. курсовая работа , добавлен 21.05.2015 Построение математической модели движения заряженных частиц, реализация на алгоритмическом языке с помощью ЭВМ. Описание предметной области. Имитация взаимодействия двух разноименно заряженных частиц. Результаты работы программы, руководство пользователя. курсовая работа , добавлен 26.02.2015 Преобразование матрицы системы линейных алгебраических уравнений (СЛАУ) с помощью алгоритма Гаусса. Решение задачи методом простой итерации. Создание блок-схемы и текста программы для решения СЛАУ, реализованной на языке программирования Turbo Pascal. курсовая работа , добавлен 15.06.2013 Паскаль как язык профессионального программирования, который назван в честь французского математика и философа Блеза Паскаля, история его разработки и функциональные особенности. Задача с использованием двумерного массива, составление блок-схемы решения. На последнем факте следует остановиться подробнее, поскольку он играет одну из ключевых ролей в рассматриваемом методе оптимизации. Причины такого «альтруизма» птиц (и других животных, действующих сходным образом) являлись предметом исследования многих социобиологов. Одним из наиболее популярных объяснений этого феномена является то, что преимущества от такого поведения каждой особи стаи больше, чем такие очевидные недостатки, как необходимость борьбы за найденную пищу с другими особями. Источники пищи обычно расположены случайным образом, поэтому в одиночестве птица вполне может погибнуть, не найдя ни один в течение долгого времени. Однако если все птицы будут «играть по правилам», делясь с сородичами информацией о находках, то шансы каждой из них на выживание резко повышаются. Таким образом, будучи неэффективной для отдельной особи, такая стратегия является залогом эффективности стаи и вида в целом. Результаты первых же симуляций удивили самого создателя: несмотря на простоту лежащих в основе программы алгоритмов, стая на экране выглядела крайне правдоподобно. Птицы сбивались в группы, уходили от столкновений и даже хаотично метались точь-в-точь как настоящие. Разработанный ими алгоритм довольно прост и может быть реализован буквально в нескольких десятках строчек кода на любом высокоуровневом языке программирования. Он моделирует многоагентную систему, где агенты-частицы двигаются к оптимальным решениям, обмениваясь при этом информацией с соседями. Текущее состояние частицы характеризуется координатами в пространстве решений (то есть, собственно, связанным с ними решением), а также вектором скорости перемещения. Оба этих параметра выбираются случайным образом на этапе инициализации. Кроме того, каждая частица хранит координаты лучшего из найденных ей решений, а также лучшее из пройденных всеми частицами решений – этим имитируется мгновенный обмен информацией между птицами. На каждой итерации алгоритма направление и длина вектора скорости каждой из частиц изменяются в соответствие со сведениями о найденных оптимумах: Где – вектор скорости частицы ( – его i-ая компонента), , – постоянные ускорения, – лучшая найденная частицей точка, – лучшая точка из пройденных всеми частицами системы, – текущее положение частицы, а функция возвращает случайное число от 0 до 1 включительно. После вычисления направления вектора , частица перемещается в точку . В случае необходимости, обновляются значения лучших точек для каждой частицы и для всех частиц в целом. После этого цикл повторяется. Где – лучший результат среди частицы и ее соседей. Соседними считаются либо частицы, отличающихся от данной индексом не более чем на некоторое заданное значение, либо частицы, расстояние до которых не превышает заданного порога. Данный алгоритм более тщательно исследует пространство поиска, однако является более медленным, чем оригинальный. При этом, чем меньшее число соседей учитывается при формировании вектора скорости, тем ниже скорость сходимости алгоритма но тем эффективней он избегает субоптимальных решений. Коэффициент , названный ими коэффициентом инерции, определяет упомянутый баланс между широтой исследования и вниманием к найденным субоптимальным решениям. В случае, когда , скорости частиц увеличиваются, они разлетаются в стороны и исследуют пространство более тщательно. В противном случае, скорости частиц со временем уменьшаются, и скорость сходимости в таком случае зависит от выбора параметров и . Значение коэффициента инерции может как убывать, так и расти. При его убывании, частицы сначала исследуют область поиска экстенсивно, находя множество субоптимальных решений, и со временем все более концентрируются на исследовании их окрестностей. Возрастание инерции способствует сходимости алгоритма на поздних стадиях работы. Клер и Кеннеди изменили способ вычисления векторов скоростей частиц, введя в него дополнительный множитель: Где , а коэффициент сжатия равен: Такой подход гарантирует сходимость алгоритма без необходимости явно контролировать скорость частиц. Исходя из этого, они решили сделать все частицы «полностью информированными», то есть получающими информацию от всех соседних частиц. Для этого они изменили в каноническом алгоритме закон изменения скорости: Где – множество соседей частицы, – лучшая из пройденных k-ым соседом точек. – весовая функция, которая может отражать любую характеристику k-ой частицы, которая считается важной: значение целевой функции в точке, в которой она находится, дистанцию от нее до данной частицы и так далее. Алгоритм роя частиц широко применяется, в числе прочих, в задачах машинного обучения (в частности, для обучения нейросетей и распознавания изображений), параметрической и структурной оптимизации (форм, размеров и топологий) в области проектирования, в областях биохимии и биомеханики. По эффективности он может соперничать с другими методами глобальной оптимизации, а низкая алгоритмическая сложность способствует простоте его реализации. Наиболее перспективными направлениями дальнейших исследований в данном направлении следует считать теоретические исследования причин сходимости алгоритма роя частиц и связанных с этим вопросов из областей роевого интеллекта и теории хаоса, комбинирование различных модификаций алгоритма для решения сложных задач, рассмотрение алгоритма роя частиц как многоагентной вычислительной системы, а также исследование возможностей включения в него аналогов более сложных природных механизмов. Пусть f
: ℝ
n
→ ℝ
- целевая функция, которую требуется минимизировать, S
- количество частиц в рое, каждой из которых сопоставлена координата x
i ∈ ℝ
n
в пространстве решений и скорость v
i ∈ ℝ
n
. Пусть также p
i - лучшее из известных положений частицы i
, а g
- наилучшее известное состояние роя в целом. Тогда общий вид метода роя частиц таков. Параметры ω, φ p , и φ g выбираются вычислителем и определяют поведение и эффективность метода в целом. Эти параметры составляют предмет многих исследований (см. ниже)
. Выбор оптимальных параметров метода роя частиц - тема значительного количества исследовательских работ, см., например, работы Ши и Эберхарта , Карлисла и Дозера , ван ден Берга , Клерка и Кеннеди , Трелеа , Браттона и Блеквэлла , а также Эверса . Простой и эффективный путь подбора параметров метода предложен Педерсеном и другими авторами. Они же провели численные эксперименты с различными оптимизациоными проблемами и параметрами. Техника выбора этих параметров называется мета-оптимизацией, так как другой оптимизационный алгоритм используется для «настройки» параметров МРЧ. Входные параметры МРЧ с наилучшей производительностью оказались противоречащими основным принципам, описанным в литературе, и часто дают удовлетворительные результаты оптимизации для простых случаев МРЧ. Реализацию их можно найти в открытой библиотеке SwarmOps. Постоянно предлагаются новые варианты алгоритма роя частиц для улучшения производительности метода. Существует несколько тенденций в этих исследованиях, одна из которых предлагает создать гибридный оптимизационный метод, использующий МРЧ в комбинации с иными алгоритмами, см. например . Другая тенденция предлагает каким-либо образом ускорить работу метода, например, отходом назад или переменой порядка движения частиц (об этом см. ). Также есть попытки адаптировать поведенческие параметры МРЧ в процессе оптимизации .Подобные документы
Стая птиц представляет собой прекрасный пример коллективного поведения животных. Летая большими группами, они почти никогда не сталкиваются в воздухе. Стая двигается плавно и скоординировано, словно ей кто-то управляет. А любой, кто вешал в своем дворе кормушку, знает, что спустя несколько часов его найдут все птицы в округе.
Дело тут отнюдь не в вожаке, отдающем приказы – в стаях многих видов птиц его просто нет. Как и колония муравьев или пчел, стая представляет собой роевой интеллект. Птицы в ней действуют согласно определенным – довольно простым – правилам. Кружа в небе, каждая из птиц следит за своими сородичами и координирует свое движение согласно их положению. А найдя источник пищи, она оповестит их об этом.Boids
Наблюдение за птицами вдохновило Крейга Рейнольдса (Craig Reynolds) на создание в 1986 году компьютерной модели, которую он назвал Boids. Для имитации поведения стаи птиц, Рейнольдс запрограммировал поведение каждой из них в отдельности, а также их взаимодействие. При этом он использовал три простых принципа. Во-первых, каждая птица в его модели стремилась избежать столкновений с другими птицами. Во-вторых, каждая птица двигалась в том же направлении, что и находящиеся неподалеку птицы. В-третьих, птицы стремились двигаться на одинаковом расстоянии друг от друга.
Как специалист в области компьютерной графики, Крейг Рейнольдс был в первую очередь заинтересован визуальной стороной результатов созданной им имитации. Однако, в посвященной Boids статье он также отметил, что разработанная им поведенческая модель может быть расширена введением дополнительных факторов – таких, как поиск пищи или боязнь хищников .Классический алгоритм роя частиц
В 1995 году Джеймс Кеннеди (James Kennedy) и Рассел Эберхарт (Russel Eberhart) предложили метод для оптимизации непрерывных нелинейных функций, названный ими алгоритмом роя частиц . Вдохновением для них послужила имитационная модель Рейнольдса, а также работа Хеппнера (Heppner) и Гренадера (Grenader) на схожую тему . Кеннеди и Эберхарт отметили, что обе модели основаны на управлении дистанциями между птицами – а, следовательно, синхронность стаи является в них функцией от усилий, которые птицы прилагают для сохранения оптимальной дистанции.Модификации классического алгоритма
Алгоритм роя частиц появился относительно недавно, однако различными исследователями уже был предложен целый ряд его модификаций, и новые работы на эту тему не перестают публиковаться. Можно выделить несколько путей улучшения классического алгоритма, реализованных в большинстве из них. Это соединение алгоритма с другими алгоритмами оптимизации, уменьшение вероятности преждевременной сходимости путем изменения характеристик движения частиц, а также динамическое изменение параметров алгоритма во время оптимизации. Ниже рассмотрены наиболее примечательные из модификаций.LBEST
Позже в том же 1995 году была опубликована статья Кеннеди и Эберхарта, в которой они назвали оригинальный алгоритм “GBEST”, поскольку он использует глобальное лучшее решение (global best) для формирования векторов скоростей, а также предложили его модификацию, названную ими “LBEST”. При обновлении направления и скорости движения частицы в LBEST используют информацию о решениях соседних с ними частиц:Inertia Weighted PSO
В 1998 году Юхи Ши (Yuhui Shi) и Рассел Эберхарт предложили модификацию, на первый взгляд совсем незначительно отличающуюся от классического алгоритма . В своей статье Ши и Эберхарт заметили, что одной из главных проблем при решении задач оптимизации является баланс между тщательностью исследованием пространства поиска и скоростью сходимости алгоритма. В зависимости от задачи и характеристик поискового пространства в ней, этот баланс должен быть различным.
С учетом этого, Ши и Эберхарт предложили изменить правило обновления векторов скоростей частиц:Time-Varying Inertia Weighted PSO
В своей работе 1998 года, Ши и Эберхарт отметили, что инерция не обязательно должна быть положительной константой: она может изменяться во время работы алгоритма по линейному и даже нелинейному закону . В статье 1999 года и более поздних работах они наиболее часто использовали линейный закон убывания, как достаточно эффективный и вместе с тем простой . Тем не менее, разрабатывались и успешно применялись и другие законы изменения инерции.Canonical PSO
В 2002 году Марис Клер (Maurice Clerc) и Джеймс Кеннеди предложили свою модификацию алгоритма роя частиц, которая стала настолько популярной, что теперь ее принято называть каноническим алгоритмом роя частиц . Он позволяет избавиться от необходимости «угадывать» подходящие значения регулируемых параметров алгоритма, контролируя сходимость частиц.Fully Informed Particle Swarm
В своей работе 2004 года Руи Мендес (Rui Mendes), Джеймс Кеннеди и Жозе Невес (José Neves) заметили, что принятое в каноническом алгоритм роя частиц допущение о том, что на каждую из частиц влияет только наиболее успешная, не соответствует лежащим в его основе природным механизмам и, возможно, ведет к снижению эффективности алгоритма . Они предположили, что из-за чрезмерного внимания алгоритма к единственному решению может быть потеряна важная информация о структуре пространства поиска.Заключение
В первой статье, описывающей алгоритм роя частиц, Джеймс Кеннеди и Рассел Эберхарт высказывали идею использования алгоритм для имитации социального поведения – Кеннеди, как социального психолога, крайне привлекала эта идея . Однако наибольшее распространение алгоритм получил в задачах оптимизации сложных многомерных нелинейных функций.Литература
Craig Reynolds, “Flocks, Herds, and Schools: A Distributed Behavioral Model” // Computer Graphics, 21(4), стр. 25–34, 1987 г.
J. Kennedy, R. C. Eberhart, “Particle swarm optimization” // In Proceedings of IEEE International Conference on Neural Networks, стр. 1942–1948, 1995 г.
R. C. Eberhart, J. Kennedy, “A new optimizer using particle swarm theory” // Proceedings of the Sixth International Symposium on Micro Machine and Human Science MHS’95, стр. 39–43, 1995 г.
F. Heppner, U. Grenander, “A stochastic nonlinear model for coordinated bird flocks” // The Ubiquity of Chaos, стр. 233–238, 1990 г.
Y. Shi, R. Eberhart, “A modified particle swarm optimizer” // The 1998 IEEE International Conference on Evolutionary Computation Proceedings, стр. 69–73, 1998 г.
Y. Shi, R. Eberhart, “Empirical study of particle swarm optimization” // Proceedings of the 1999 IEEE Congress on Evolutionary Computation, стр. 1945–1950, 1999 г.
M. Clerc, J. Kennedy, “The particle swarm – explosion, stability, and convergence in a multidimensional complex space” // IEEE Transactions on Evolutionary Computation, №6 (1), стр. 58–73, 2002 г.
R. Mendes, J. Kennedy, J. Neves, “The fully informed particle swarm: Simpler, maybe better” // IEEE Transactions on Evolutionary Computation, №8 (3), стр. 204–210, 2004 г.
Алгоритм
Подбор параметров
Варианты алгоритма
См. также
Примечания
Ссылки
Методы оптимизации
Одномерные