Лабораторная работа №1

Санкт-Петербургский Государственный

Электротехнический Университет «ЛЭТИ»

Кафедра САПР

Лабораторная работа №1

«Методы одномерного поиска унимодальных функций»

Вариант 1

Выполнили: Байда А.Ю.

Турченко П.Н.

Группа 2372

Преподаватель: Алешкевич П.А.

Санкт-Петербург

2004

Оглавление

Санкт-Петербургский Государственный 1

Задание. 3

Описание методов оптимизации. 3

Блок-схемы методов: 4

Спецификация программы: 6

Текст программы: 6

Результаты тестирования различных методов: 8

Выводы: 8

Ответы на контрольные вопросы: 8

Задание.

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

при выборе разных начальных точек и по числу итераций заданных методов оптимизации. Сделать выводы.

Описание методов оптимизации.

Метод Свенна:

С помощью этого метода получаем начальный интервал локализации минимума.

Начальный этап:

1) задать x⁰ – произвольная начальная точка.

2) выбрать шаг h равным 0.001 или 0.01*|x⁰|.

Основной этап:

Шаг 1:

Установить направление убывания целевой функции. Для этого надо взять x₂=x₁+h. Если f1<f2, то надо поменять направление движения(h=-h и взять x₂=x₁+h).

Шаг 2:

Вычислять f_k в точках x_k+1=x_k+h_k, где h_k=2h_k-1, k=2,3,…,n-1 до тех пор пока не придём в точку x_n такую что f_n>f_n-1.

Шаг 3:

Установить начальный интервал локализации минимума a₁=x_n-2 и b₁=x_n.

Метод Золотого Сечения 1:

Начальный этап:

1) Выбрать погрешность , начальный интервал [a₁, b₁].

2) Вычислить стартовые точки по формулам: ₁ = a₁ + 0.618L₁, ₁ = a₁ + 0.382L₁.

3) Принять k = 1.

Основной этап:

Шаг 1:

1)Сократит текущий интервал локализации рассмотрением двух ситуаций:

если f1<f2, то a_k+1=a_k,

b_k+1=_k,

_k+1=_k,

и найти _k+1=a_k+1+0.382L_k+1,

иначе f1>f2, то a_k+1=_k,

b_k+1=b_k,

_k+1=_k,

и найти _k+1=a_k+1+0.618L_k+1, где L_k+1=| b_k+1- a_k+1|

2) Положить k=k+1.

Шаг 2:

Проверить критерий окончания поиска:

если L=|a-b| <  -остановиться, точнее фиксируем аппроксимирующий минимум x*=(a+b)/2.

Блок-схемы методов:

Метод Свенна 1:

h=-h;

x2=x1+h;

Д

Н

x1=x2;

x2=x1+h;

h=2*h;

Д

Н

a=x2;

b=x1-h/2;

Метод Золотого сечения 1:

x=(a+b)/2;

Спецификация программы:

Каждый метод реализован в виде функции.

Переменные в программе:

a, b – текущий интервала локализации

h – размер шага

x – аппроксимирующий минимум

x1 – стартовая точка

l, m - точки деления интервала локализации в ЗС1

k – счетчики числа итераций.

Текст программы:

#include <iostream.h>

#include <math.h>

#include <conio.h>

long double a,b;

int k1,k;

double Sven (long double,long double,long double);

double ZS1 (long double,long double);

double fx(long double);

/**************************************************************************/

void main()

{

clrscr();

long double h=0.01,x2,x1;

x1=1;

x2=x1+h;

if ( fx(x2) > fx(x1))

h=-h;

h=Sven (x1,x2,h);

cout << " a " << a << endl;

cout << " b " << b << endl;

long double m,l,x;

m=a+0.618*(b-a);

l=a+0.382*(b-a);

x=ZS1 (m,l);

cout << endl <<" x " << x << endl;

cout << endl <<" k(Svenn) " << k1 << endl;

cout << endl <<" k(ZS1) " << k << endl;

getch();

}

/**************************************************************************/

double Sven(long double x1, long double x2, long double h)

{

long double x3,z;

x2=x1+h;

while (1)

{

h=2*h;

x3=x2+h;

if (fx(x3)>fx(x2))

break;

x1=x2;

x2=x3;

k1=k1+1;

}

a=x1;

b=x3;

if (a>b)

{

z=b;

b=a;

a=z;

}

return h;

}

/**************************************************************************/

double ZS1(long double m, long double l)

{

long double x;

while (1)

{

if (fx(l) < fx(m))

{

b=m;

m=l;

l=a+0.382*(b-a);

}

else

{

a=l;

l=m;

m=a+0.618*(b-a);

}

if (abs(b-a)<0.001)

break;

k=k+1;

}

x=(a+b)/2;

return x;

}

/**************************************************************************/

double fx(long double x)

{

long double s,f;

s=(2*pow(x,2)+3*pow(2.7,(-x)));

return s;

}

f(x)=x^4-14 x^3 +60 x^2 -70x	0.0001		0.00001		0.000001
X0=2	k	x*	k	x*	k	x*
Метод Свенна 1	7	[-0.56 ; 2]	7	[-0.56 ; 2]	7	[-0.56 ; 2]
Метод ЗС 1	15	0.780885	18	0.780884	21	0.780884

Результаты тестирования различных методов:

f(x)=x^4-14 x^3 +60 x^2 -70x	0.0001		0.000001
X0=23	k	x*	k	x*
Метод Свенна 1	7	[-6.44 ; 23]	7	[-6.44 ; 23]
Метод ЗС 1	17	0.78088	24	0.780884

Выводы:

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

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

Ответы на контрольные вопросы:

1. Унимодальная функция – это функция которая имеет единственный минимум и монотонна по обе стороны от него. При этом у неё не должно быть горизонтальных участков. Унимодальная функция является основной в теории поиска, так как она разработана для большинства методов поиска

.

2. Аналитическое условие экстремума, т. е. равенство производной функции в данной точке, является необходимым и достаточным условием минимума.

Задача на поиск максимума преобразовывается в задачу на поиск минимума противоположной функции, т. е. задача на поиск максимум функции (F(x)), а на поиск минимума (-F(x)).

3. Характерные особенности методов одномерного поиска:

• Линейный поиск, рассматриваются только унимодальные функции.

• Начальный интервал локализации минимума находится методом Свенна.

• Меньший интервал локализации получается путем рассмотрения значений функции в двух точках на ТИЛ, или в производной в одной точке, и выборе новых границ интервала.

9