Многомерная оптимизация методом Хука-Дживса

Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования "Сибирский государственный индустриальный университет"

Кафедра информационных технологий в металлургии.

Курсовая работа

по дисциплине: «Оптимизация в технике и технологиях»

Многомерная оптимизация методом Хука-Дживса

Выполнил:

ст. гр. ИС-10

Хлыстов Д.С.

Проверил:

к.т.н., доцент

Рыбенко И.А.

Новокузнецк2013

Оглавление

1.Теоретические основы метода оптимизации

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

1.2 Математические основы метода

1.2.1 Метод Хука-Дживса

1.2.2 Метод квадратичной аппроксимации

1.3 Разработка алгоритма численной реализации

1.3.1 Метод Хука-Дживса

1.3.2 Метод квадратичной аппроксимации

1.4 Составление и реализация контрольных примеров средствами Excel

1.5 Анализ результатов расчета

2.       Программная реализация системы на ЭВМ средствами Delphi

2.1 Описание структуры программы и ее компонентов

2.2 Результаты отладки программы на контрольных примерах

2.3 Составление инструкции по использованию программы

3. Исследование эффективности работы метода оптимизации на тестовых задачах

3.1 Выбор и описание тестовых задач

3.2 Исследование влияния параметров задачи (начальное приближение, точность, параметры алгоритма) на количество

расчетов целевой функции

3.3 Исследование работоспособности метода путем решения задач различной размерности и сложности

3.4 Обработка результатов исследований визуальными и формальными средствами Excel

Заключение

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

Приложение 1

1.Теоритические основ метода оптимизации.

 

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

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

 

f(x₁, x₂, x₃, …, x_n) = f(X), xÎEⁿ

компонентов вектора X^*, которые дают условие

 

f(X^*) = min(max)f(X).

Рассматривая локальный X₀ и глобальный X^* экстремумы функции можно отметить их особенности. Функция f(X) имеет локальный минимум в точке X₀, если существует окрестность, такая, что f(X) больше f(X₀) во всех точках этой окрестности. В случае глобального минимума в точке X^* для всех X справедливо неравенство

f(X) ³ f(X^*).

Для решения поставленной задачи я использовал алгоритмы безусловной оптимизации методами:

Для многомерной Хука-Дживса.

Для одномерной квадратичной аппроксимации.

 

1.2    Математические основы метода

 

.2.1 Метод Хука-Дживса.

Метод включает два этапа: “исследующий поиск” вокруг базисной точки и “поиск по образцу” в направлении, выбранном для минимизации. В исследующем поиске задается начальное приближение X⁽¹⁾ и приращения по координатам DX. Рассчитывается значение f(X⁽¹⁾) в базисной точке. Затем в циклическом порядке совершаются пробные шаги. Если приращение улучшает целевую функцию, то шаг считается “удачным”. По этой переменной значение изменяется на величину шага и дается приращение по другой переменной Иначе - “неудачным” и делается шаг в противоположном направлении. И если он тоже оказался “неудачным”, то значение этой переменной оставляют без изменения, и дается приращение по другой переменой и т.д. пока не будут изменены все независимые переменные. На этом завершается первый исследующий поиск, найдена точка X⁽²⁾. Поиск по образцу осуществляется вдоль направления, соединяющего X⁽²⁾ иX⁽¹⁾. Совершается один или несколько шагов до тех пор, пока шаги являются “удачными”.

Применяют две модификации метода прямого поиска:

·   в исследующем поиске используется одномерная минимизация вдоль координатных направлений;

·   исследующий поиск осуществляется на основе дискретных шагов по направлениям.

 

.2.2 Метод квадратичной аппроксимации.

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

 = (x₂ + x₁)/2 - (a₁/2a₂).

Предполагается, что заданы x₁, x₂, x₃, и известны значения функции в этих точках f₁, f₂, f₃, а аппроксимирующая функция

 

g(x) = a₀ + a₁(x - x₁) + a₂(x - x₁)(x - x₂)

совпадает с f(x) в трех указанных точках.

Коэффициенты полинома определяются уравнениями

 

a₀ = f₁; a₁ = (f₂ - f₁)/(x₂ - x₁); a₂ = 1/(x₃ - x₂)×[(f₃ - f₁)/(x₃ - x₁) - (f₂ - f₁)(x₂ - x₁)].

Для унимодальных функций оказывается приемлемой для оценки оптимума x^*.

 

.3 Разработка алгоритма численной реализации

 

.3.1 Метод Хука-Дживса

Начальный этап. Выбрать начальную точку X⁽¹⁾, и e> 0 - скаляр, используемый в критерии остановки. Пусть единичные координатные направления, α - коэффициент сжатия шага. Положить Y⁽¹⁾ = X⁽¹⁾, k = j = 1 и перейти к основному этапу.

Основной этап.Шаг 1. Любым методом одномерной оптимизации найти l_j^* - оптимальное решение задачи минимизации функции f(Y^(j) + l_j) при условии l Î eи положить Y^(j+1) = Y^(j) + l_j^*. Если j < n, то заменить j на j + 1 и вернуться к шагу 1. Если j=n, то перейти к шагу 2.

Шаг 2. Положить X^(k+1) = Y⁽ⁿ⁾. Если ||X^(k+1) - X^(k)|| < e, то остановиться; в противном случае вычислить шаг а=||X^(k+1) - X^(k)|| ·α, Y⁽¹⁾ = X^(k), заменить k на k + 1, положить j = 1 и перейти к шагу 3.

Шаг 3. Вычислить Y^(j+1) = Y^(j)+a и f(Y^(j) ), f(Y^(j+1) ). Если f(Y^(j+1) )<f(Y^(j) ), то j=j+1 и вернуться к шагу 3. Иначе положить X^(k)=Y^(j) ,j=1, Y⁽¹⁾ = X^(k), и вернуться к шагу 1.

 

.3.2 Метод квадратичной аппроксимации

Шаг 1. Задать x₁, x₂, x₃, и вычислить значения функции в этих точках f(х₁), f(х₂), f(х₃).

Шаг 2. Рассчитать a₀ = f(х₁); a₁ = (f(х₂) - f(х₁))/(x₂ - x₁); a₂ = 1/(x₃ - x₂)×[(f(х₃) - f(х₁))/(x₃ - x₁) - (f(х₂) - f(х₁))(x₂ - x₁)].

Шаг 2. Вычислить оптимальное решение:  = (x₂ + x₁)/2 - (a₁/2a₂).

 

1.4 Составление и реализация контрольных примеров средствами Excel

Рассмотрим функцию f(x)=(х1+х2)^2+(х2-1)^2 с точностью e=0,01 и начальными значениями х1=5, х2=6. Результаты расчетов приведены в таблице 1.

Таблица 1 - Расчет экстремума функции f(x)=(х1+х2)^2+(х2-1)^2методом Хука-Дживса.

№	x1	x2	f(x)	S1	S2	h1	h2
1	5	6	146	-11	-2,5	-1,1	-0,25
	-6	3,5	12,5
По образцу
№	x1	x2	f(x)	h1	h2	|x(k+1)-xk|	Критерий
1	5	6	146	-1,1	-0,25	11,2805142	Не достигнут
2	3,9	5,75	115,685
3	2,8	5,5	89,14
4	1,7	5,25	66,365
5	0,6	5	47,36
6	-0,5	4,75	32,125
7	-1,6	4,5	20,66
8	-2,7	4,25	12,965
9	-3,8	4	9,04
10	-4,9	3,75	8,885
11	-6	3,5	12,5
№	x1	x2	f(x)	S1	S2	h1	h2
1	-4,9	3,75	8,885	1,15	-1,375	0,115	-0,1375
	-3,75	2,375	3,78125
По образцу
№	x1	x2	f(x)	h1	h2	|x(k+1)-xk|	Критерий
1	-4,9	3,75	8,885	0,115	-0,1375	3,40578644	Не достигнут
2	-4,785	3,6125	8,199913
3	-4,67	3,475	7,55365
4	-4,555	3,3375	6,946213
5	-4,44	3,2	6,3776
6	-4,325	3,0625	5,847813
7	-4,21	2,925	5,35685
8	-4,095	2,7875	4,904713
9	-3,98	2,65	4,4914
10	-3,865	2,5125	4,116913
11	-3,75	2,375	3,78125
12	-3,635	2,2375	3,484413
13	-3,52	2,1	3,2264
14	-3,405	1,9625	3,007212
15	-3,29	1,825	2,82685
16	-3,175	1,6875	2,685312
17	-3,06	1,55	2,5826
18	-2,945	1,4125	2,518712
19	-2,83	1,275	2,49365
20	-2,715	1,1375	2,507412
№	x1	x2	f(x)	S1	S2	h1	h2
1	-2,83	1,275	2,49365	1,555	-0,1375	0,1555	-0,01375
	-1,275	1,1375	0,037812
По образцу
№	x1	x2	f(x)	h1	h2	|x(k+1)-xk|	Критерий
1	-2,83	1,275	2,49365	0,1555	-0,01375	1,87328081	Не достигнут
2	-2,6745	1,26125	2,065527
3	-2,519	1,2475	1,677968
4	-2,3635	1,23375	1,330974
5	-2,208	1,22	1,024544
6	-2,0525	1,20625	0,758678
7	-1,897	1,1925	0,533376
8	-1,7415	1,17875	0,348639
9	-1,586	1,165	0,204466
10	-1,4305	1,15125	0,100857
11	-1,275	1,1375	0,037812
12	-1,1195	1,12375	0,015332
13	-0,964	1,11	0,033416
№	x1	x2	f(x)	S1	S2	h1
1	-1,1195	1,12375	0,015332	-0,00425	-0,06187	-0,000425	-0,0061875
	-1,12375	1,061875	0,007657
По образцу
№	x1	x2	f(x)	h1	h2	|x(k+1)-xk|	Критерий
1	-1,1195	1,12375	0,015332	-0,00043	-0,00619	0,06822287	Не достигнут
2	-1,11993	1,117563	0,013827
3	-1,12035	1,111375	0,012485
4	-1,12078	1,105188	0,011307
5	-1,1212	1,099	0,010294
6	-1,12163	1,092813	0,009444
7	-1,12205	1,086625	0,008759
8	-1,12248	1,080438	0,008237
9	-1,1229	1,07425	0,00788
10	-1,12333	1,068063	0,007686
11	-1,12375	1,061875	0,007657
12	-1,12418	1,055688	0,007792
№	x1	x2	f(x)	S1	S2	h1	h2
1	-1,12375	1,061875	0,007657	0,061875	-0,03094	0,0061875	-0,00309375
	-1,06188	1,030938	0,001914
По образцу
№	x1	x2	f(x)	h1	h2	|x(k+1)-xk|	Критерий
1	-1,12375	1,061875	0,007657	0,006187	-0,00309	0,14527454	Не достигнут
2	-1,11756	1,058781	0,00691
3	-1,11138	1,055688	0,006202
4	-1,10519	1,052594	0,005532
5	-1,099	1,0495	0,0049
6	-1,09281	1,046406	0,004307
7	-1,08663	1,043313	0,003752
8	-1,08044	1,040219	0,003235
9	-1,07425	1,037125	0,002757
10	-1,06806	1,034031	0,002316
11	-1,06188	1,030938	0,001914
12	-1,05569	1,027844	0,001551
13	-1,0495	1,02475	0,001225
14	-1,04331	1,021656	0,000938
15	-1,03713	1,018563	0,000689
16	-1,03094	1,015469	0,000479
17	-1,02475	1,012375	0,000306
18	-1,01856	1,009281	0,000172
19	-1,01238	1,006188	7,66E-05
20	-1,00619	1,003094	1,91E-05
21	-1	1	9,77E-30
22	-0,99381	0,996906	1,91E-05
№	x1	x2	f(x)	S1	S2	h1	h2
1	-1	1	9,77E-30	-3E-15	0	-2,998E-16	0
	-1	1	3,94E-31
По образцу
№	x1	x2	f(x)	h1	h2	|x(k+1)-xk|	Критерий
1	-1	1	9,77E-30	-3E-16	0	3,2196E-15	Достигнут
2	-1	1	7,89E-30
3	-1	1	6,22E-30
4	-1	1	4,78E-30
5	-1	1	3,56E-30
6	-1	1	2,56E-30
7	-1	1	1,79E-30
8	-1	1	1,23E-30
9	-1	1	9,86E-31
10	-1	1	8,38E-31
11	-1	1	7,89E-31
12	-1	1	8,38E-31

Таким образом экстремум в точке [-1;1] найден за шесть итерации с точностью e =0,01.

 

.5 Анализ результатов расчета

При подсчете функции f(x)=(х1+х2)^2+(х2-1)^2с точностью e =0,01, был найден экстремум в точке [-1;1]за 6 итераций.

Достоинства метода:

Простая стратегия поиска, вычисление только значений функции, небольшой объём требуемой памяти.

Недостатки:

Алгоритм основан на циклическом движении по координатам. Это может привести к вырождению алгоритма в бесконечную последовательность исследующих поисков без поиска по образцу.

2.      Программная реализация системы на ЭВМ средствами Delphi

 

2.1    Описание структуры программы и ее компонентов

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

-    Поле для ввода начальных координат

-       Поле для ввода точности поиска

-       Выбор функции.

-       Поле для вывода всех шагов и итераций.

-       Поля для вывода экстремума в точках.

-       Вывод конечного числа итераций.

Программа реализованная в среде Delphiи имеет следующий вид (рис.1).

Рисунок 1 - интерфейс программы Хука-Дживса

Ознакомится с листингом программы на примере одной функции можно в приложении 1.

2.2    Результаты отладки программы на контрольных примерах

В программной реализации использовались функции различной сложности:

f(x) = (x₁+x₂)²+(x₂-1)²(x)= (x₁+x₂)²+(x₂+4)²(x)= (x₁-3x₂)²+(x₂+1)²(x)= (x₁-6x₂)²+(x₂+1)²(x)= (x₁-2x₂)²+(x₂-3)²(x)= (x₁+2x₂)²+(x₂-4)²

Мною была выбрана функция для отладки программы f(x) = (x₁+x₂)²+(x₂-1)², с начальным интервалом [5;6] и точность поиска равную e=0,01.

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

2.3    Составление инструкции по использованию программы

)        Запустить программу - после открытия программы перед вами появится окно интерфейса программы (Рис.2).

Рисунок 2- Интерфейс программы.

)        Вводим точность и начальныезначения интервала (Рис.3)

Рисунок 3-Поля для ввода точности и начального значения интервала.

оптимизация программа хук дживс

3)      Выбираем функцию и нажимаем кнопку «Рассчитать» (Рис.4).

Рисунок 4- Окно для выбора функций.

)        После нажатия кнопки «Рассчитать», в нижнихполях «Количество итераций», «Координаты х» и «Значение функции» будут выведены ответы (Рис.5).

Рисунок 5-Поля вывода.

)        После нажатия кнопки «Рассчитать», в правой области программы появятся подробные расчеты выбранной функции. (Рис.6).

Рисунок 6 - Подробные расчеты выбранной функции.

3.   Исследование эффективности работы метода оптимизации на тестовых задачах

 

.1 Выбор и описание тестовых задач

Для тестов выбралфункцию f(x)= (x₁-6x₂)²+(x₂+1)² с начальными координатами[-5; -3] и точность e=0,015

Сначала делаем исследующий поиск с помощью квадратичной аппроксимации f(x)= (x₁-6x₂)²+(x₂+1)² при х1=-5,х2=-3 и получаем х`1=-18. После для х1=-18 и х2=-3 и получаем х`2=-2,945. Вычисляем S1=-13и S2=0,054,а также h1=-1,2 и h2=0,0054.

Далее переходим к поиску по образцу. Первое действие подставляем в функцию f(x)= (x₁-6x₂)²+(x₂+1)² наши значения х1=-5,х2=-3 получая f(x)=173. Второе действие меняем х1=х1+h1 а х2=x2+h2 и снова считаем значение функции получая f(x)=140,11. Повторяем второе действие пока функция убывает , как только она начинает возрастать прекращаем поиск по образцу. Мне потребовалось 12 итераций на 11 итерации значения былих1=-18, х2=-2,94595,f(x)=3,891891892 на 12 итерации стали такими былих1=-19,3, х2=-2,94054,f(x)=6,510540541.

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

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

 

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

Проведя исследования заданных мной функций выяснилось:

1.   Что количество итераций будет зависть от начального приближения и если точки выбраны грамотно, итерация может быть всего несколько в противном случаи количество итераций возрастет.

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

 

3.3 Исследование работоспособности метода путем решения задач различной размерности и сложности.

Алгоритм Хука-Дживса показал себя как быстро работающий. Если e=<0,9 то количество итерация не возрастает, но если точность будет больше e>0,9 то количество итераций уменьшится.

При исследовании сложных функций было выявленочто не у всех функций можно найти точный экстремум.

 

3.4 Обработка результатов исследований визуальными и формальными средствами Excel

В качестве показателей будут выступать начальное приближение, точность и количество итераций.

Рассмотрим первую функциюf(x)= (x₁-6x₂)²+(x₂+1)²при х1=-5,х2=-3 получаем таблицу 2, а также график 1.

Таблица 2-зависимость итераций от точности и начального приближения

x1	x2	точность	итерации
-5	-3	0,1	3
-5	-3	0,01	3
-5	-3	0,001	3
-5	-3	0,0001	3
-5	-3	0,00001	3

График 1-зависимость итераций и начального приближения

Поменяем начальное приближение,но точность оставим прежней e=0.015, так как при изменении точности количество итераций в данной функции не меняется, и тогда получим таблицу 3 и график 2.

Таблица 2 - зависимость итерации от начального приближения

x2

итерации

45

8

31

44

8

9

-13

45

3

-7

6

3

3

14

3

График 2 - зависимость итерации от начального приближения

 

Заключение

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

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

1.   Р.Хук ,Т.А.Дживс “ Прямой поиск решения для числовых и статических проблем ”, 212-219 с., 1961.

2.       Алгоритмы и примеры решения задач одномерной оптимизации: Метод.указ./ Сост.: С.П Мочалов, И.А. Рыбенко.: СибГИУ.- Новокузнецк, 2004.- 18с., ил.

.        Мочалов С.П. Методы оптимизации металлургических процессов: Учебное пособие / КузПИ. -Кемерово, 1989.- 81с.

 

Приложение 1

         //описание глобальных переменных,x2:double;:integer;:double;ExplSearch(x1,x2:double;check:integer):Double; //Функция для расчета метода квадратичной аппроксимации она же исследующий поиск:double;,f2,f3:double;,a1,a2:double;,tx2,tx3:double;=1 then //для расчета первого х:=x1;:=tx1+1;:=tx2+1;:=sqr(tx1+x2)+sqr(x2-1);

f2:=sqr(tx2+x2)+sqr(x2-1);:=sqr(tx3+x2)+sqr(x2-1);

a0:=f1;:=(f2-f1)/(tx2-tx1);:=1/(tx3-tx2)*((f3-f1)/(tx3-tx1)-(f2-f1)/(tx2-tx1));:=(tx2+tx1)/2-a1/2/a2;=2 then //для расчета второго х:=x2;:=tx1+1;:=tx2+1;:=sqr(tx1+x1)+sqr(tx1-1);:=sqr(tx2+x1)+sqr(tx2-1);:=sqr(tx3+x1)+sqr(tx3-1);:=f1;:=(f2-f1)/(tx2-tx1);:=1/(tx3-tx2)*((f3-f1)/(tx3-tx1)-(f2-f1)/(tx2-tx1));:=(tx2+tx1)/2-a1/2/a2;;:=xopt;;

procedure TForm1.RezClick(Sender: TObject); //основная процедура

varopt,x2opt:double;,sx2:double;,h2:double;:double;,tx2:double;:single; //погрешность:double;:integer;:=0;

ListBox1.Items.Clear;.Text:='';

EXopt2.Text:='';.Text:='';:=0;:=StrToFloat(Ex1.text);:=1;:=StrToFloat(Ex2.text);:=2;:=strtofloat(Eerror.Text);

.Checkedthen //проверка на выбор функции и запуск метода Хука-Дживса:=x1;:=x2;opt:=RB1ExplSearch(x1,x2,1); //Передача значений в функцию квадратичной аппроксимации для первого хopt:=RB1ExplSearch(x1opt,x2,2); // Передача значений в функцию квадратичной аппроксимации для второго х.Items.Add('Исследующий поиск');.Items.Add('x1 = '+FloatToStr(x1opt)+' x2 = '+FloatToStr(x2opt));:=(x1opt-x1)*0.1;:=(x2opt-x2)*0.1;

F:=sqr(x1+x2)+sqr(x2-1);

dF:=0;<Fdo //запуск цикла поиска по образцу

F:=sqr(x1+x2)+sqr(x2-1);

tx1:=x1;:=x2;:=x1+h1;:=x2+h2;.Items.Add('Поискпообразцу');.Items.Add('x1 = '+FloatToStr(x1)+' x2 = '+FloatToStr(x2));:=sqr(x1+x2)+sqr(x2-1);;:=sqrt(sqr(x1-sx1)+sqr(x2-sx2)); // расчет критерий для окончание поиска:=tx1;:=tx2;:=iteration+1; //подсчет количества итераций;<=error //проверка критерий с заданной точность .Create('Выбиритефункцию');;

.Items.Add('');.Items.Add('Количество итераций '+inttostr(iteration));.Text:=IntToStr(iteration); //вывод результатов итерации.Text:=FloatToStr(x1); //вывод результатов для х первого.Text:=FloatToStr(x2); //вывод результатов для ч второго.Text:=FloatToStr(F); //вывод результатов для функции в точках х1 х2//блок обработки ошибокdon=0 then.SetFocus;('х1 должен быть числом или вместо точки должна быть запятая');;n=1 then.SetFocus;('х2 должен быть числом или вместо точки должна быть запятая');;n=2 then.SetFocus;('Точность должна быть числом или вместо точки должна быть запятая');;;;;