Оптимизация роем частиц (Particle swarm optimization)

Введение

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

Копируя действия природы, человек создает всё более и более совершенные алгоритмы оптимизации. Для их создание чаще всего служат примеры из природы, например: генетический код или поведение птиц, моделирование миграций рыб или охлождение металла и т.д.

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

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

Для данной работы был выбран метод оптимизации «рой частиц». Алгоритм метода благодаря своей простоте и скорости считается очень перспективным для задач планирования.

1. Постановка задачи

.1 Математическая модель

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

Когда стая ищет еду, её представители будут проверять прилегающую область и двигаться вокруг стаи независимо друг от друга. Каждый представитель имеет степень свободы или хаотичности в движении, которая даёт ему возможность найти скопление пищи. Так, рано или поздно, один из них найдет, что-то съедобное, и, будучи частью стаи, сообщит остальным. Остальные также могут тогда приблизиться к источнику пищи, и уже каждый представитель, благодаря степени свободы и хаотичности своего движения может найти новое скопление пищи.

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

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

2. Реализация алгоритма

.1Схема работы алгоритма

Схема работы алгоритма выглядит следующим образом:

1.Создаётся исходная «случайная» популяция частиц.

2.Для каждой частицы рассчитывается целевая функция.

.Лучшая частица с точки зрения целевой функции объявляется «центром притяжения».

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

.Осуществляется расчёт новых координат частиц в пространстве решений.

.Шаги 2-5 повторяются заданное число раз или пока не выполнится условие остановки.

.Последний «центр тяжести» объявляется найденным оптимальным решением.

2.2 Код программы

#include<time.h>

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

int n=200;int m=200;i, j, k, t=200;

double F (double x)

{pow (pow(x, 3) - 125,2);

}main()

{double V[n] [m];lower_limit=1, upper_limit=300;best_pos[n] [m];cel[n] [m]; // массив генотипаbest_cel=1000; // лучшее глобальное значениеx;R1, R2;double C1=0.7, C2=1.2, w=0.93;

**X=new double*[n];(i=0; i<n; i++)[i]=new double[m];

srand (time(NULL));

// инициализация положения и скоростей частиц

for (i=0; i<n; i++)(j=0; j<m; j++)

{[i] [j]=lower_limit + (upper_limit - lower_limit)*rand()/RAND_MAX;

V[i] [j]=0;

// Инициалиция генотипом частиц самым худшем

best_pos[i] [j]=1000;

}(k=0; k<t; k++)

{

// заполнение массива генотипов

for (i=0; i<n; i++)

for (j=0; j<m; j++)

{

// определение текущего генотипа[i] [j]=F (X[i] [j]);

// сохранение значения лучшего генотипа для каждой частицы

if (cel[i] [j]<best_pos[i] [j])_pos[i] [j]=cel[i] [j];(best_pos[i] [j]<best_cel)

{_cel=best_pos[i] [j];=X[i] [j];(«%f\n», x);

}

}

// Обновление скоростей частиц и их позиций

for (i=0; i<n; i++)(j=0; j<m; j++)

{= 1.*rand()/RAND_MAX;= 1.*rand()/RAND_MAX;[i] [j] = w*V[i] [j] + C1*R1*(best_cel - X[i] [j]) + C2*R2*(best_pos[i] [j] - X[i] [j]);[i] [j] = X[i] [j] + V[i] [j];

}

}0;

}

2.3 Блок схема алгоритма

3. Теоретическая оценка трудоемкости алгоритма оптимизации

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

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

) операцию присваиванияa¬b;

) операцию индексации массиваa[i];

) арифметические операции *,/,-,+;

) операции сравнения a < b;

) логические операции or, and, not.

Вызов функции будем считать за одну элементарную операцию +1 за каждое переданное значение и +1 за возвращенное.

Цикл for не является элементарной операцией, т.к. может быть представлен в виде;

for i¬1 to N

телоi;

Таким образом конструкция цикла требует 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 с.

. Конспект лекций по дисциплине «Математическая логика и теория алгоритмов».

3. Global Optimization Algorithms - Theory and Application.

4. http://ru.wikipedia.org

Больше работ по теме: