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

 

 

Министерство науки и образования РФ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

“Сибирский государственный индустриальный университет”

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

Пояснительная записка к курсовой работе

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

Тема: «Разработка компьютерной системы для решения задач многомерной безусловной оптимизации методом Хука-Дживса с дискретным шагом»

 

 

 

Выполнил: ст.гр. ИСТ-11

Игумнов А.М.

Проверил: к.т.н., доцент

Рыбенко И.А.

 

 

 

г. Новокузнецк 2014

Содержание

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

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

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

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

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

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

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

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

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

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

3.2 Исследование влияния  параметров задачи на количество  расчетов целевой функции……………............…………………………………………...12

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

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

Заключение……………………………………………………………………… 19

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

Приложение 1. ………….……………….……………….……………….……...21

 

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

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

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

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

 

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

Для решения поставленной задачи расчеты будут проходить через два этапа. Первый этап: "исследующий поиск" вокруг базисной точки.  В нем задается начальное приближение X(1) и приращения по координатам DX. Рассчитывается значение f(X(1)) в базисной точке. Затем в циклическом порядке совершаются пробные шаги. Если приращение улучшает целевую функцию, то шаг считается “удачным”. По этой переменной значение изменяется на величину шага и дается приращение по другой переменной Иначе – “неудачным” и делается шаг в противоположном направлении. И если он тоже оказался “неудачным”, то значение этой переменной оставляют без изменения, и дается приращение по другой переменой и т.д. пока не будут изменены все независимые переменные. Второй этап: "поиск по образцу" в направлении, выбранном для минимизации. Он осуществляется вдоль направления, соединяющего X(2) и X(1). Совершается один или несколько шагов до тех пор, пока шаги являются “удачными”.

 

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

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

Основной этап. Шаг 1. Положить = + .

Если > - то j = j+1, иначе k=k+1 и перейти к шагу 2

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

 

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

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

Программа реализована в среде разработки Delphi 7.

На рисунке 1 показана программа, которая состоит из следующих частей:

Рисунок 1 - структура программы

 

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

- блок для  ввода начальных значений(компонент  Edit) - пользователь должен задать 3 начальных значения: х1, х2 и точность, необходимые для расчетов всех последующих итераций,

- кнопка "Выполнить  расчет"(компонент Button) - после ввода начальных данных и выбора функции пользователь должен нажать эту кнопку для получения результатов,

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

В программе используются функции RB1ExplSearch, RB2ExplSearch и RB3ExplSearch для расчетов операции исследующего поиска и  " procedure TForm1.btn1Click(Sender: TObject) " - процедура описания действия кнопки "Выполнить расчет" при нажатии на нее.

 

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

В качестве примера используем формулу (x1-x2)2 + (x2+2,9)2 . Зададим начальные значения х1 = 3 и х2 = 4 и точность равную 0,015. На рисунке 2 видно, что программа выполнила все требуемые операции и вывела результат в соответствующие поля. При этом не было обнаружено никаких ошибок или проблем со скоростью выполнения задачи.

Рисунок 2 - результат работы программы

 

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

После запуска программы появится окно, изображенное на рисунке 3.

Рисунок 3 -  Стартовый вид программы после запуска

 

Далее нужно выбрать одну из трех функций, для которой требуется выполнить оптимизацию. Результат выбора показан на рисунке 4.

Рисунок 4 - Выбор функции

 

После этого нужно задать начальные значения х1, х2 и точность, к примеру так, как показано на рисунке 5.

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

Рисунок 5 - Ввод начальных значений

 

После того как все предыдущие шаги сделаны, нужно нажать на кнопку "Выполнить расчет". Результаты запишутся ниже, а в специальном окне справа будут прописаны все расчеты всех операций. Результат работы программы показан на рисунке 6, на котором видны расчеты минимума х1, минимума х2, значение функции и количество операций.

Рисунок 6 - Результаты расчетов после нажатия кнопки

 

 

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

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

В качестве тестовой задачи выберем функцию (x1-x2)2 + (x2+3)2 и зададим начальные координаты -2 и -3 с точностью 0,05.

Сначала выполняется исследующий поиск функции f(x)=(x1-x2)2 + (x2+3)2  при х1=-2,х2=-3 и получаем соответствующие результаты х1 и х2. В программе вычисляются S1 и S2, а также h1и h2.

Далее происходит к поиску по образцу. Вначале подставляются в функцию f(x)=(x1-x2)2 + (x2+3)2 наши значения х1, х2, получая f(x). Второе действие: х1=х1+h1 и х2=x2+h2 и снова считается значение функции получая другое значение f(x). Повторяем второе действие пока функция убывает , как только она начинает возрастать прекращаем поиск по образцу. Теперь идет проверка критерия точности. Он больше чем заданная точность - значит идет переход ко второй итерации исследующего поиска. И так выполняем исследующий поиск и поиск по образцу пока критерий точности не станет меньше заданной точности. Потребовалось 5 итераций для вычисления результатов: х1 стал равен -2,9744, х2 = -2,9808 и f(x) приблизительно 0,00041. Результат  показан на рисунке 7.

Рисунок 7 - Результаты теста программы

 

3.2 Исследование влияния параметров  задачи на количество расчетов целевой функции

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

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

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

Рисунок 8 - Влияние изменения точности на результат

 

К примеру, при точности 0,2 для решения задачи оптимизации программе потребовалось всего 2 итерации, как показано на рисунке 8,  однако результат получился менее точным.

 

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

Можно усложнить программу, взяв для примера более сложную функцию: (x1+x2-0,1)2 + (x2-1)2 , оставив те же значения. Результат показан на рисунке 9

Рисунок 9 - Первое усложнение задачи для решения

 

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

Рисунок 10 - Второе усложнение задачи

 

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

Результаты исследований с помощью Excel приведены ниже с графиками соответствующих функций с варьированием различных значений.

В качестве примера можно рассмотреть функцию (x1-x2)2 + (x2+2,9)2.

Далее, на рисунке 11, приведены значение функции по достижению минимума.

 

функция:	(x1-x2)^2+(x2+2,9)^2		начальное х1	начальное х2	точность
			3	4	0,3
			x1	x2	f(x)
			-3,0416	-3,0784	0,033181
			-3,0512	-3,0768	0,031914
			-3,0608	-3,0752	0,030902
			-3,0704	-3,0736	0,030147
			-3,08	-3,072	0,029648
			-3,0896	-3,0704	0,029405
			-3,0992	-3,0688	0,029418

 

 

Рисунок 11 - Изменение значения функции

Далее рассмотрено, как задаваемая точность влияет на количество итераций, необходимых для решения задачи. Результаты показаны на рисунке 12.

точность	количество итераций
0,007	6
0,015	5
0,019	4
0,07	4
0,15	3
0,18	2

 

 

Рисунок 12 - Влияние изменения точности

На рисунке 13 изображены графики изменения количества итераций и значений рассматриваемой функции в зависимости от задаваемого начального интервала.

точность=	0,015
начальный интервал	f(x)	кол-во итераций
[-2,-3]	1,6	5
[-1,-2]	0,005	4
[0,1]	0,0012	6
[4,2]	0,00044	6
[5,6]	3,91808	6
[7,3]	0,00368	5

 

 

Рисунок 13 - Влияние начального интервала на функцию

 

Заключение

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

 

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

1. Алгоритмы и примеры решения задач одномерной оптимизации: Метод.указ./ Сост.: С.П Мочалов, И.А. Рыбенко.: СибГИУ.- Новокузнецк, 2004.- 18с., ил.
2. Мочалов С.П. Методы оптимизации металлургических процессов: Учебное пособие / КузПИ. –Кемерово, 1989.- 81с.
3. Р.Хук ,Т.А.Дживс “ Прямой поиск решения для числовых и статических проблем ”, 212-219 с., 1961.