 |
Теоретическая оценка трудоемкости алгоритма оптимизации
|
|
|
|
Введение
Ещё со времён Ламарка развитие живого мира рассматривается как процесс постоянного совершенствования (приспособления) особей под влиянием среды. Моделируя отбор лучших планов, как процесс эволюции в популяции особей, можно получить решение задачи оптимизации, задав начальные условия эволюционного процесса, населив виртуальную вселенную существами - носителями информации и указав цель эволюционного процесса.
Копируя действия природы, человек создает всё более и более совершенные алгоритмы оптимизации. Для их создание чаще всего служат примеры из природы, например: генетический код или поведение птиц, моделирование миграций рыб или охлождение металла и т.д.
В настоящее время на производстве и в бизнесе широко используются алгоритмы оптимизации, так как они дают возможность сэкономить не только денежные средства, но и время, которого постоянно не хватает.
На производстве, благодаря оптимизации, решается множество проблем связанных с такими вещами как простой станка, переполнение склада или же перенаправление запчастей на другие станки при поломке.
Для данной работы был выбран метод оптимизации «рой частиц». Алгоритм метода благодаря своей простоте и скорости считается очень перспективным для задач планирования.
Постановка задачи
Математическая модель
Метод «рой частиц» - наиболее простой метод эволюционного программирования, появившийся в середине 90-х годов, основанный на идеи о возможности решения задач оптимизации с помощью моделирования поведения групп животных. В основу метода положен тот факт, что при формировании стаи птицы стремятся к некоторому центру «притяжения», постепенно замедляя скорость полёта.
|
|
|
Когда стая ищет еду, её представители будут проверять прилегающую область и двигаться вокруг стаи независимо друг от друга. Каждый представитель имеет степень свободы или хаотичности в движении, которая даёт ему возможность найти скопление пищи. Так, рано или поздно, один из них найдет, что-то съедобное, и, будучи частью стаи, сообщит остальным. Остальные также могут тогда приблизиться к источнику пищи, и уже каждый представитель, благодаря степени свободы и хаотичности своего движения может найти новое скопление пищи.
В реализации данного алгоритма многомерное пространство поиска населяется роем частиц (элементарных решений). Координаты частицы в пространстве однозначно определяют решение задачи оптимизации. Помимо координат каждая из частиц описывается скоростью перемещения и ускорением. В процессе перемещения частицы осуществляют «прочёсывание» пространства решений и тем самым находят текущий оптимум, к которому на следующем шаге устремляются остальные частицы. Каждая частица запоминает своё лучшее положение, данные о котором передаются соседним частицам, которые стремятся к этому значению.
Для введения случайной составляющей в процесс поиска могут быть включены «сумасшедшие» частицы, закон движения которых отличается от закона движения остальных.
Реализация алгоритма
Схема работы алгоритма
Схема работы алгоритма выглядит следующим образом:
1. Создаётся исходная «случайная» популяция частиц.
2. Для каждой частицы рассчитывается целевая функция.
. Лучшая частица с точки зрения целевой функции объявляется «центром притяжения».
. Векторы скоростей всех частиц устремляются к этому «центру», при этом чем дальше частица находится от него, тем большим ускорением она обладает.
. Осуществляется расчёт новых координат частиц в пространстве решений.
|
|
|
. Шаги 2-5 повторяются заданное число раз или пока не выполнится условие остановки.
. Последний «центр тяжести» объявляется найденным оптимальным решением.
Код программы
#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;
}
Блок схема алгоритма
Теоретическая оценка трудоемкости алгоритма оптимизации
Для теоретической оценки трудоемкости алгоритма необходимо определить количество элементарных операций, которые необходимо выполнить для решения задачи с помощью данного алгоритма.
Под элементарными операциями, будем понимать операции, которые могут быть представлены в виде элементарных конструкций данного языка (но не обязательно в виде одной машинной команды), а именно за одну элементарную операцию будем считать следующие:
) операцию присваивания ab;
) операцию индексации массива a[i];
) арифметические операции *,/,-,+;
) операции сравнения a < b;
) логические операции or, and, not.
Вызов функции будем считать за одну элементарную операцию +1 за каждое переданное значение и +1 за возвращенное.
Цикл for не является элементарной операцией, т.к. может быть представлен в виде;
for i1 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 элементарных операций.
Заключение
программа алгоритм моделирование
В последнее время стало появляться очень много новых алгоритмов, которые основанны на подражании природе, но не каждый алгоритм может похвастаться такой простатой реализации и оригинальностью идеи. Благодаря случайности распределения частиц и их хаотичности в движении пояляется очень большая вероятность найти оптимальное решение за несколько итераций, избегая при этом локальные оптимумы.
Дальнейшее развитие подобных алгоритмов является ключём к новым технологиям оптимизации и развития в целом.
|
|
|
