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

Министерство образования и науки РФ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Сибирский государственный индустриальный университет»

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

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

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

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

Выполнил:

ст. гр. ИС-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), xEⁿ

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

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

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

f(X) f(X^*).

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

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

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

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

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

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

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

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

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

1.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^*.

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

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

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

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

Шаг 2. Положить X^(k+1) = Y⁽ⁿ⁾. Если ||X^(k+1) — X^(k)||, то остановиться; в противном случае вычислить шаг а=||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.

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методом Хука—Дживса.

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

1.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)²

f (x)= (x₁+x₂)²+(x₂+4)²

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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,94 595,f (x)=3,891 891 892 на 12 итерации стали такими былих1=-19,3, х2=-2,94 054,f (x)=6,510 540 541.

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

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

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—зависимость итераций от точности и начального приближения

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

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

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

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

Заключение

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

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

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

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

Приложение 1

Var //описание глобальных переменных

x1,x2:double;

iteration:integer;

F:double;

functionRB1ExplSearch (x1,x2:double;check:integer):Double; //Функция для расчета метода квадратичной аппроксимации она же исследующий поиск

var

xopt:double;

f1,f2,f3:double;

a0,a1,a2:double;

tx1,tx2,tx3:double;

begin

ifcheck=1 then //для расчета первого х

begin

tx1:=x1;

tx2:=tx1+1;

tx3:=tx2+1;

f1:=sqr (tx1+x2)+sqr (x2−1);

f2:=sqr (tx2+x2)+sqr (x2−1);

f3:=sqr (tx3+x2)+sqr (x2−1);

a0:=f1;

a1:=(f2-f1)/(tx2-tx1);

a2:=1/(tx3-tx2)*((f3-f1)/(tx3-tx1)-(f2-f1)/(tx2-tx1));

xopt:=(tx2+tx1)/2-a½/a2;

end

else

ifcheck=2 then //для расчета второго х

begin

tx1:=x2;

tx2:=tx1+1;

tx3:=tx2+1;

f1:=sqr (tx1+x1)+sqr (tx1−1);

f2:=sqr (tx2+x1)+sqr (tx2−1);

f3:=sqr (tx3+x1)+sqr (tx3−1);

a0:=f1;

a1:=(f2-f1)/(tx2-tx1);

a2:=1/(tx3-tx2)*((f3-f1)/(tx3-tx1)-(f2-f1)/(tx2-tx1));

xopt:=(tx2+tx1)/2-a½/a2;

end;

result:=xopt;

end;

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

var

x1opt, x2opt: double;

sx1,sx2:double;

h1,h2:double;

dF:double;

tx1,tx2:double;

error:single; //погрешность

test:double;

n:integer;

begin

iteration:=0;

ListBox1.Items.Clear;

EXopt1.Text:='';

EXopt2.Text:='';

EIteration.Text:='';

try

n:=0;

x1:=StrToFloat (Ex1.text);

n:=1;

x2:=StrToFloat (Ex2.text);

n:=2;

error:=strtofloat (Eerror.Text);

ifRB1.Checkedthen //проверка на выбор функции и запуск метода Хука—Дживса

repeat

begin

sx1:=x1;

sx2:=x2;

x1opt:=RB1ExplSearch (x1,x2,1); //Передача значений в функцию квадратичной аппроксимации для первого х

x2opt:=RB1ExplSearch (x1opt, x2,2); // Передача значений в функцию квадратичной аппроксимации для второго х

ListBox1.Items.Add ('Исследующий поиск');

ListBox1.Items.Add ('x1 = '+FloatToStr (x1opt)+' x2 = '+FloatToStr (x2opt));

h1:=(x1opt-x1)*0.1;

h2:=(x2opt-x2)*0.1;

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

dF:=0;

whiledF

begin

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

tx1:=x1;

tx2:=x2;

x1:=x1+h1;

x2:=x2+h2;

ListBox1.Items.Add ('Поискпообразцу');

ListBox1.Items.Add ('x1 = '+FloatToStr (x1)+' x2 = '+FloatToStr (x2));

dF:=sqr (x1+x2)+sqr (x2−1);

end;

test:=sqrt (sqr (x1-sx1)+sqr (x2-sx2)); // расчет критерий для окончание поиска

x1:=tx1;

x2:=tx2;

iteration:=iteration+1; //подсчет количества итераций

end;

untiltest<=error //проверка критерий с заданной точность

else

begin

raiseException.Create ('Выбиритефункцию');

end;

ListBox1.Items.Add ('');

ListBox1.Items.Add ('Количество итераций '+inttostr (iteration));

EIteration.Text:=IntToStr (iteration); //вывод результатов итерации

EXopt1.Text:=FloatToStr (x1); //вывод результатов для х первого

EXopt2.Text:=FloatToStr (x2); //вывод результатов для ч второго

EFunc.Text:=FloatToStr (F); //вывод результатов для функции в точках х1 х2

Except //блок обработки ошибок

onEConvertError do

begin

if n=0 then

begin

Ex1.SetFocus;

ShowMessage ('х1 должен быть числом или вместо точки должна быть запятая');

end;

if n=1 then

begin

Ex2.SetFocus;

ShowMessage ('х2 должен быть числом или вместо точки должна быть запятая');

end;

if n=2 then

begin

Eerror.SetFocus;

ShowMessage ('Точность должна быть числом или вместо точки должна быть запятая');

end;

end;

end;

end;