Размещено на http://www.allbest.ru/

Содержание

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

2. Используемые методы оптимизации

2.1 Метод покоординатного спуска

2.1.1 Краткие теоретические сведения

2.1.2 Разработка программного обеспечения

2.2 Генетический алгоритм

2.2.1 Краткие теоретические сведения

2.2.2 Разработка программного обеспечения

2.3 Метод PSO

2.3.1 Краткие теоретические сведения

2.3.2 Разработка программного обеспечения

3. Сравнительный анализ работы алгоритмов

3.1 График зависимости времени выполнения программы от объема выборки

3.2 График зависимости количества итераций от объема выборки

Выводы

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

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

Для проведения минимизации была выбрана функция Сферы.

Первая минимизируемая функция - это фукнция

Ее глобальный (и единственный) минимум расположен в точке xi = 0, где i = 1, 2, ..., n. Значение функции в этой точке равно 0.

Ее трехмерный вид для n = 2 показан ниже:

Рис.1.1 Трехмерный вид функции Сфера для n=2

И пример такой же функции для n = 1.



Рис.1.2 Вид функции Сфера для n=1

2. Используемые методы оптимизации

2.1 Метод покоординатного спуска

2.1.1 Краткие теоретические сведения

Пусть нужно найти наименьшее значение целевой функции

u=f(M)=f(x?, x, . . . ,xn). Здесь через М обозначена точка n-мерного пространства с координатами x?, x, . . . ,xn: M=(x?, x . . . ,xn). Выберем какую-нибудь начальную точку М?=(x??, x?, . . . ,xn0) и рассмотрим функцию f при фиксированных значениях всех переменных, кроме первой: f(x?, x?,x?, . . . ,xn0). Тогда она превратится в функцию одной переменной x? . Изменяя эту переменную, будем двигаться от начальной точки x?=x?? в сторону убывания функции, пока не дойдем до ее минимума при x?=x??, после которого она начинает возрастать. Точку с координатами ( x??, x?,x?, . . . ,xn0) обозначим через М?, при этом f(M0) f(M?). алгоритм генетический программный

Фиксируем теперь переменные: x?=x??, x= x?, . . . ,xn=xn0 и рассмотрим функцию f как функцию одной переменной x: f(x??, x, x? . . . ,xn0). Изменяя x , будем опять двигаться от начального значения x2=x20 в сторону убывания функции, пока не дойдем до минимума при x2=x21 .Точку с координатами {x??, x?, x? . . . xn0} обозначим через М, при этом f(M1) f(M).

Проведем такую же минимизацию целевой функции по переменным x, x?, . . . ,xn. Дойдя до переменной xn, снова вернемся к x? и продолжим процесс. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М??М??М??. . . , которой соответствует монотонная последовательность значений функции f(M0) ?f (M?)?f(M)???Обрывая ее на некотором шаге k можно приближенно принять значение функции f(Mk) за ее наименьшее значение в рассматриваемой области.

Проведем такую же минимизацию целевой функции по переменным x, x, . . . ,xn. Дойдя до переменной xn, снова вернемся к x? и продолжим процесс. Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек М?,М?,М, . . . , которой соответствует монотонная последовательность значений функции

f(M0)--f(M1)--f(M) --...--Обрывая ее на некотором шаге k можно приближенно принять значение функции f(Mk) за ее наименьшее значение в рассматриваемой области. Отметим , что данный метод сводит задачу поиска наименьшего значения функции нескольких переменных к многократному решению одномерных задач оптимизации. Если целевая функция f(x?, x, ... ,xn) задана явной формулой и является дифференцируемой, то мы можем вычислить ее частные производные и использовать их для определения направления убывания функции по каждой переменной и поиска соответствующих одномерных минимумов. В противном случае, когда явной формулы для целевой функции нет, одномерные задачи следует решать с помощью одномерных методов

На рис.изображены линии уровня некоторой функции двух переменных u= f (х, у). Вдоль этих линий функция сохраняет постоянные значения, равные 1, 3, 5, 7, 9. Показана траектория поиска ее наименьшего значения, которое достигается в точке О, с помощью метода покоординатного спуска. При этом нужно ясно понимать, что рисунок служит только для иллюстрации метода.

Пусть требуется решить задачу (2):

f(x) min, х Rn. (2)

В двумерном пространстве R2. Решение задачи (2) методом покоординатного спуска, иначе называемого методом Гаусса - Зейделя, производят по следующей общей схеме.

Выбирают произвольно начальную точку х(0) из области определения функции f(х). Приближения х(k) определяются соотношениями

(3): x(k+1)=x(k)+t(k)S(k) (k=0,1,2, ...),

где вектор направления спуска s(k)- это единичный вектор, совпадающий с каким-либо координатным направлением (например, если S(k) параллелен х1, то S(k)= {1,0,0,...,0}, если он параллелен x2, то S(k)={0, 1, 0, . . . ,0} и т.д.) ; величина t(k) является решением задачи одномерной минимизации: f(x(k)+ts(k)) min, t R1, (k=0,1,2, ...), и может определяться, в частности, методом сканирования. Детальная реализация общей схемы в двумерном случае R2 дает траекторий приближения к точке х* методом покоординатного спуска, состоящую из звеньев ломаной, соединяющих точки х(k), x1(k) x(k+1) (k=0, 1, 2,) . При k=0, исходя из начальной точки х(0)=(x1(0),x2(0)), находят точку х(0)= (x1(0),x2(0)), минимума функции одной переменной f(x1,x2(0)); при этом f(x(0))f(x(0)).Затем находят точку минимума x(1) функции f (x1(0),x2) по второй координате. Далее делают следующий шаг вычислений при k=1. Полагают, что исходной точкой расчета является х(1). Фиксируя вторую координату точки х(1), находят точку минимума х(1)= (x1(1),x2(1)), функции f(x1,x2(1)) одной переменной x(1); при этом f(x(1))f(x(1))f(x(0)). Точку х(2) получают, минимизируя целевую функцию f(x1(1),x2), вновь по коорданате х2, фиксируя координату x1(1) ,точки x(1) , и т.д.

Условием прекращения вычислительной процедуры при достижении заданной точности может служить неравенство

2.1.2 Разработка программного обеспечения

#include <time.h>

#include <math.h>

#include <conio.h>

#include <iostream>

#include <fstream>

#define delta 0.000000000001

#define step 0.1

int i, j;

int menu_select(void);

void result (void);

double Sfera(double *a, int b);

double Proizv (double a);

int main()

{

char choice;

for(;;)

{

choice = menu_select();

switch(choice)

{

case 1: result();

break;

case 2: exit(0);

}

}

return 0;

}

int menu_select(void)

{

setlocale( LC_ALL,"Russian" );

int c;

std::cout<<"1. Вычислить функцию"<<std::endl;

std::cout<<"2. Выход\n"<<std::endl;

do

{

std::cout<<"Введите номер нужного пункта: "<<std::endl;

std::cin>> c;

}

while(c<0 || c>2);

return c;

}

void result(void)

{

setlocale( LC_ALL,"Russian" );

int iteration=0;

int n;

double A,B;

double del;

srand((unsigned)time(NULL));

std::cout<<"Введите число переменных n"<<std::endl;

std::cin>>n;

unsigned int start = clock();

double x[n];

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

{

x[i]= (double)(-10000+ rand()%10000);

}

B=Sfera(x,n);

do

{

A=B;

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

{

if (fabs(x[i])>delta)

{

x[i]-=step*Proizv(x[i]);

}

}

B=Sfera(x,n);

del=fabs(A-B);

iteration++;

}

while (del>delta);

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

{

std::cout<<"x"<<i+1<<"= "<<x[i]<<" "<<std::endl;

}

std::cout<<"Приблизительное значение минимума - "<<B<<std::endl;

std::cout<<"Количество итераций - "<<iteration<<std::endl;

unsigned int end = clock();

unsigned int search = end - start;

std::cout<<" Время выполнния расчетов: "<<double(search)/1000<<" сек"<<std::endl;

std::cout<<"Для продолжения нажмите Enter"<<std::endl;

getch();

system( "cls" );

return;

}

double Sfera(double *a,int b)

{

double c=0;

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

{

c+=pow(a[i],2);

}

return c;

}

double Proizv (double a)

{

return 2*a;

}

2.2 Генетический алгоритм

2.2.1 Краткие теоретические сведения

Основной (классический) генетический алгоритм (также называемый элементарным или простым генетическим алгоритмом) состоит из следующих шагов:

1) инициализация, или выбор исходной популяции хромосом;

оценка приспособленности хромосом в популяции;

проверка условия остановки алгоритма;

селекция хромосом;

применение генетических операторов;

формирование новой популяции;

выбор «наилучшей» хромосомы.

Блок-схема основного генетического алгоритма изображена на рис.2. Рассмотрим конкретные этапы этого алгоритма более подробно с использованием дополнительных подробностей, представленных на рис. 3.

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

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

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

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

Рис.2. Блок-схема генетического алгоритма

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

(2)

где, (3)

причем - значение функции приспособленности хромосомы , a - вероятность селекции хромосомы . Селекция хромосомы может быть представлена как результат поворота колеса рулетки, поскольку «выигравшая» (т.е. выбранная) хромосома относится к выпавшему сектору этого колеса. Очевидно, что чем больше сектор, тем больше вероятность «победы» соответствующей хромосомы. Поэтому вероятность выбора данной хромосомы оказывается пропорциональной значению ее функции приспособленности. Если всю окружность колеса рулетки представить в виде цифрового интервала [0, 100], то выбор хромосомы можно отождествить с выбором числа из интервала , где и обозначают соответственно начало и окончание фрагмента окружности, соответствующего этому сектору колеса; очевидно, что . В этом случае выбор с помощью колеса рулетки сводится к выбору числа из интервала [0, 100], которое соответствует конкретной точке на окружности колеса.

В результате процесса селекции создается родительская популяция, также называемая родительским пулом (mating pool) с численностью , равной численности текущей популяции.

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

2.2.2 Разработка программного обеспечения

#include <time.h>

#include <math.h>

#include <conio.h>

#include <iostream>

#include <fstream>

int i, j;

int n,m;

int menu_select(void);

void result (void);

double Sfera (double x);

double SUMSfera(double *a);

int main()

{

char choice;

for(;;)

{

choice = menu_select();

switch(choice)

{

case 1: result();

break;

case 2: exit(0);

}

}

return 0;

}

int menu_select(void)

{

setlocale( LC_ALL,"Russian" );

int c;

std::cout<<"1. Вычислить функцию"<<std::endl;

std::cout<<"2. Выход\n"<<std::endl;

do

{

std::cout<<"Введите номер нужного пункта: "<<std::endl;

std::cin>> c;

}

while(c<0 || c>2);

return c;

}

void result(void)

{

setlocale( LC_ALL,"Russian" );

std::cout<<"Введите число переменных n"<<std::endl;

std::cin>>n;

m=2*n;

std::cout<<n<<" "<<m<<std::endl;

int individ[m][n];

int buff[m][n];

int roz[m];

double cf[m];

double sect[m];

int nom[m];

int ver[m];

double delta=n*0.9999999;

double sumcellf;

int sumsum=0;

int rez=0;

int w=0;

double ul[2]={0,0};

unsigned int start = clock();

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

{

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

{

individ[i][j] = 0 + rand()%20;

}

}

do

{

if (ul[1]>5)

{

ul[1]=0;

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

{

individ[i][rand()%n]= rand()%20;

}

}

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

{

cf[i]=0.0;

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

{

cf[i]+=Sfera(individ[i][j]);

}

}

sumcellf=SUMSfera(cf);

double temp=0;

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

{

temp+=(cf[i]/sumcellf)*100;

sect[i]=temp;

}

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

{

roz[i]=rand()%101;

}

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

{

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

{

if(roz[i]<sect[j])

{

nom[i]=j;

break;

}

}

}

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

{

if(rand()%101<=10)

{

ver[i]=0;

sumsum++;

}

else

{

ver[i]=1;

}

}

for( i=1;i<m;i++)

{

for(j=i;j>0 && ver[j-1]>ver[j];j--)

{

std::swap(ver[j-1],ver[j]);

std::swap(nom[j-1],nom[j]);

}

}

if (sumsum%2!=0)

{

ver[sumsum+1]=0;

sumsum++;

}

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

{

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

{

buff[i][j] = individ[nom[i]][j];

}

}

if (sumsum>0)

{

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

{

buff[i][rand()%n]= rand()%20;

}

}

for (i = sumsum; i <m ; i+=2 )

{

int l=rand()%n;

for (int j=0; j<n; j++)

{

if (j<l)

{

std::swap(buff[i][j],buff[i+1][j]);

}

}

}

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

{

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

{

individ[i][j]=buff[i][j];

}

}

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

{

cf[i]=0.0;

for (int j=0;j<n;j++)

{

cf[i]+=Sfera(individ[i][j]);

}

}

sumcellf=0;

sumcellf=SUMSfera(cf);

double elit=0.0;

int fiks=0;

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

{

if (cf[i]>elit)

{

elit=cf[i];

fiks=i;

}

}

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

{

if (cf[i]<(sumcellf/m))

{

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

{

individ[i][j] = individ[fiks][j];

}

}

}

for (int i = 0; i <m ; i++ )

{

cf[i]=0.0;

for (int j=0;j<n;j++)

{

cf[i]+=Sfera(individ[i][j]);

}

}

for (int i = 0; i <m ; i++ )

{

if (cf[i]>=delta)

{

rez++;

}

}

if (ul[0]<=sumcellf)

{

ul[0]=sumcellf;

ul[1]=0;

}

else

{

ul[1]+=1;

}

w++;

sumcellf=0;

sumsum=0;

if (rez<(int)(m*0.9))

{

rez=0;

}

}

while (rez<(int)(m*0.9));

std::cout<<"Результат найден!"<<" Количество итераций "<<w<<"; Количество оптимальных особей "<<rez<<std::endl;

unsigned int end= clock(); // конечное время

unsigned int search = end - start; // искомое время

std::cout<<" Время выполнения расчетов: "<<double(search)/1000<<" сек"<<std::endl<<std::endl;

std::cout<<"Для продолжения нажмите Enter"<<std::endl;

getch();

system( "cls" );

return;

}

double Sfera (double x)

{

return 1/(1+(pow(x,2)));

}

double SUMSfera(double *a)

{

double c=0.0;

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

{

c+=a[i];

}

return c;

}

2.3 Метод PSO

2.3.1 Краткие теоретические сведения

Рассмотрим задачу глобальной безусловной минимизации целевой функций Ф(Х) в n-мерном арифметическом пространстве Rn:

min Ф{Х) = Ф(Х*)

ХRn

Множество частиц обозначим S = {Рi, i [1:N]}, где N -- число частиц в рое S (размер популяции). В момент времени t = 0, 1, 2 ... координаты частицы Pi определяются вектором Хi,t = (xi,t,1, xi,t,2, xi,t,n), а ее скорость -- вектором Vi,t= (vi,t,1, vi,t,2, vi,t,n). Начальные координаты и скорости частицы Pi равны Xi,0 = , Vi,0 = соответственно.

Итерации в каноническом методе PSO выполняются по следующей схеме:

; (7)

; (8)

Здесь U[a,b] представляет собой n-мерный вектор псевдослучайных чисел, равномерно распределенных в интервале [a, b]; -- символ покомпонентного умножения векторов; -- вектор координат частицы Pi с наилучшим значением целевой функции Ф(Х); за все время поиска; Xg,t -- вектор координат соседней с данной частицы с наилучшим за время поиска значением целевой функции Ф(Х); б,в,г -- свободные параметры алгоритма.

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

В процессе итераций вектор образует так называемый собственный путь (private guide) частицы Pi, а вектор Xg,t -- локальный путь (local guide) этой частицы.

Свободный параметр б определяет "инерционные" свойства частиц (при б < 1 движение частиц замедляется). Рекомендуемое значение параметра б равно 0,7298. В процессе оптимизации может быть эффективным постеленное уменьшение коэффициента а от 0,9 до 0,4, При этом большие значения параметра обеспечивают широкий обзор пространства поиска, а малые -- точную локализацию минимума целевой функции. Рекомендуемые значения свободных параметров в,г равны 1,49618.

Второй компонент в формуле (8) называется "когнитивным" компонентом (по социальной аналогии) и формализует тенденцию частицы вернуться в положение с минимальным значением целевой функции. Третий компонент в формуле (8) называется "социальным" компонентом. Компонент отражает влияние на данную частицу ее соседей.

2.3.2 Разработка программного обеспечения

#include <time.h>

#include <math.h>

#include <conio.h>

#include <iostream>

#define a 0.7298

#define b 1.49618

#define g 1.49618

int i, j;

int n,m;

int menu_select(void);

void result (void);

double Sfera (double x);

double sumSfera(double *x,int i);

int main()

{

char choice;

for(;;)

{

choice = menu_select();

switch(choice)

{

case 1: result();

break;

case 2: exit(0);

}

}

return 0;

}

int menu_select(void)

{

setlocale( LC_ALL,"Russian" );

int c;

std::cout<<"1. Вычислить функцию"<<std::endl;

std::cout<<"2. Выход\n"<<std::endl;

do

{

std::cout<<"Введите номер нужного пункта: "<<std::endl;

std::cin>> c;

}

while(c<0 || c>2);

return c;

}

void result(void)

{

setlocale( LC_ALL,"Russian" );

std::cout<<"Введите число переменных n"<<std::endl;

std::cin>>n;

m=2*n;

double speed[m][n], best[m][n], cel[m][n], b_cel[m], x[m][n];

double min=-500, max=500, U1, U2;

unsigned int start = clock();

srand((unsigned)time(NULL));

int iteration=0;

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

{

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

{

x[i][j]=min + (max - min)*rand()/RAND_MAX;

speed[i][j]=0;

best[i] [j]=1000;

}

b_cel[i]=1000;

}

do

{

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

{

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

{

cel[i][j]=Sfera (x[i][j]);

if (cel[i][j]<best[i][j])

best[i][j]=cel[i][j];

if (best[i][j]<b_cel[i])

{

b_cel[i]=best[i][j];

}

}

}

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

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

{

U1 = 1.*rand()/RAND_MAX;

U2 = 1.*rand()/RAND_MAX;

speed[i][j] = a*speed[i][j] + b*U1*(best[i][j] - x[i][j]) + g*U2*(b_cel[i] - x[i][j]);

x[i][j] = x[i][j] + speed[i][j];

}

iteration++;

}

while(iteration<1000);

std::cout<<"Программа осуществила 1000 итераций результат найден!"<<std::endl;

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

{

std::cout<<" Целевая функция для частицы "<<i+1<<"= "<<sumSfera(*cel,i)<<"\t";

std::cout<<std::endl;

}

unsigned int end = clock();

unsigned int search = end - start;

std::cout<<" Время выполнения расчетов: "<<double(search)/1000<<" сек"<<std::endl<<std::endl;

std::cout<<"Для продолжения нажмите Enter"<<std::endl;

getch();

system( "cls" );

return;

}

double Sfera (double x)

{

return (pow(x,2));

}

double sumSfera(double *x,int i)

{

double c;

for (int j=0; j<n; j++)

{

c+=x[i*n+j];

}

return c;

}

3. Сравнительный анализ работы алгоритмов

3.1 График зависимости времени выполнения программы от объема выборки

Исходя из представленного выше графика можно сделать следующие выводы:

Наиболее быстрым алгоритмом для решения поставленной задачи является метод покоординатного спуска,однако решение, найденное данным методом будет приблизительным - проблема «ямы» экстремума;

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

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

3.2 График зависимости количества итераций от объема выборки

Исходя из представленного выше графика можно сделать следующие выводы:

Объем выборки для покоординатного спуска почти не влияет на количество итераций;

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

Для метода роя частиц количество итераций фиксировано и не зависит от объема выборки.

Выводы

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

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

На основе проделанной работы можно сделать следующие выводы:

Если для пользователя важна скорость выполнения программы и он готов пожертвовать точностью вычислений - рекомендуется использовать метод покоординатного спуска.

Если же точность - основополагающее требование конечного пользователя - рекомендуется использовать метод PSO.

Генетический алгоритм в чистом виде использовать не рекомендуется ввиду большого объема времени, затрачиваемого для вычисления конечных значений.

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

1. Карпенко А.Б., Селиверстов Е.Ю. Глобальная оптимизация методом роя частиц. Обзор. // Информационные технологии, - 2010, №2,С 25-34.

2. Kennedy J., Eberhart R. Particle Swarm Optimization // Proceedings of IEEE International Conference on Neural Networks-IV (Perth, Australia, 1995). IEEE Service Center, Piscataway, NJ, pр. 1942-1948.

3. Еременко, Ю.И. Введение в искусственный интеллект / Ю.И. Еременко. - Старый Оскол: ООО «ТНТ»., 2008. - 392 с.

4. Андрейчиков, А.В. Интеллектуальные информационные системы [Текст]: учебник / А. В. Андрейчиков, О. Н. Андрейчикова. - М.: Финансы и статистика, 2004. - 424с.: ил.

Размещено на Allbest.ru

...