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

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

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

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

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

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

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);

}

int main ()

{double V[n] [m];

double lower_limit=1, upper_limit=300;

double best_pos[n] [m];

double cel[n] [m]; // массив генотипа

double best_cel=1000; // лучшее глобальное значение

double x;

double R1, R2;

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;

V[i] [j]=0;

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

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];

x=X[i] [j];

printf («%fn», 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];

}

}

return 0;

}

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

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

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

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

1) операцию присваивания ab;

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

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

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

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

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

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

for i1 to N

тело

next 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= 528 800 809 элементарных операций.

Заключение

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

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

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

1. Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. — М.: МГАПИ, 2003. — 80 с.

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

3. Global Optimization Algorithms — Theory and Application.

4. http://ru.wikipedia.org