Программная модель поиска глобального минимума нелинейных "овражных" функций двух переменных (стр. 3 из 4)
1.2.3 Метод наискорейшего спуска
Поиск минимума функции R(x) выполняют по шагам начиная с начальной точки. На первом шаге вычисляют значение функции, градиент поля функции, путем вычисления частной производной по каждой переменной, модуль градиента, значения переменных в шаге и величину шага по каждой переменной.
В направлении градиента ищут минимум функции, поскольку направление одно, то используют один из методов оптимизации одномерной нелинейной функции. Например, сканирование с постоянным шагом по каждой переменной до локального минимума функции.
На втором и последующих шагах в точке локального минимума вновь вычисляют градиент поля, модуль градиента, значение переменных в шаге и величину шага. Вычисление заканчивают при значении модуля градиента меньше либо равного заданной погрешности.
2. Инструментальные программные средства
Перед началом работы над курсовым проектом передо мной встал вопрос: в какой системе программирования или с помощью какого приложения я буду писать программу по данной мне теме. Мой выбор остановился на приложении MicrosoftExcel. В настоящее время данный программный продукт можно найти практически на любом персональном компьютере, на котором установлена операционная система Windows 9x, 2000, NT 4.0, XP. MicrosoftExcel обладает требуемым для расчетов модели математическим аппаратом. Кроме того, в данный программный продукт встроен редактор VisualBasic, с помощью которого можно писать макросы.
Среда редактора VisualBasic.
VisualBasic предоставляет единую законченную среду редактирования, схожую со средой автономной версии VisualBasic 5.0. Каждая книга MicrosoftExcel имеет связанный с ней проект. Среда редактирования VisualBasic включает улучшенный редактор кода, иерархическое средство просмотра объектов, многооконный отладчик, окно отображения свойств и средство просмотра проектов для управления кодом и объектами проекта. Для облегчения создания синтаксически правильного кода среда редактирования VisualBasic имеет группу команд в меню Правка, включающую команды Список свойств/методов, Список констант и Параметры.
Использование объектов ActiveX в формах.
VisualBasic обеспечивает согласованные и расширяемые элементы управления и интерфейс диалоговых окон для всех программ MicrosoftOffice. Элементы ActiveX (ранее называвшиеся элементами управления OLE) могут быть внедрены непосредственно на листы, что позволяет пользователю создавать свои собственные формы.
События
Богатейшие возможности обработки событий предоставляют гибкие средства определения реакции на действия пользователя.
3. Блок-схема алгоритма моделирования
 |
Ввод данных осуществляется с помощью диалогового окно «Ввод данных» (см. рис. 7).
 |
Рисунок 7 Вид формы для ввода данных
Вывод промежуточных и выходных данных осуществляется в таблицу (см. табл. 1)
Таблица 1
Результаты решения
| X1 | X2 | dR/dX1 | dR/dX2 | |grad| | R(x) |
Минимальные требования предъявляемы к аппаратной части:
Процессор – 486 DX/2 80Mz
ОЗУ – 12Мб
Видеоадаптер – VGA640-480
Монитор
Клавиатура
Мышь
В качестве операционной среды на персональном компьютере должна быть установлена одна из версий Windows (9x, 2000, NT 4.0, XP, Me), а также программный пакет MicrosoftOffice (97, 2000) или, хотя бы, MicrosoftExcel.
Для того, чтобы начать работу с моделью нужно скопировать файл «Метод наискорейшего спуска» в папку «Мои документы» и с помощью программного приложения MicrosoftExcel открыть файл.
Задача. Найти минимум функции
R(x)=a*x1^3+b*x2^2-c*x1-d*x2, где a = 1, b = 2, c = 3, d = 4.
Начальные точки: х1 = -0,5; х2 = -1. Пробный шаг g = 0,01. Коэффициент пробного шага h = 0,1. Погрешность е = 0,01.
Решение. В начальных точках х1=-0,5, х2=-1 вычислим по методу градиента значение функции, градиент поля функции, значение переменных в шаге и величину шага. Полученные данные занесем в таблицу и поставим номер шага. Затем по формуле xi+1 = xi – h*(dR/dxi) найдем новые значения переменных х1 и х2 и вычислим значение функции. Последние операции будем повторять до тех пор, пока значение функции не начнет возрастать. Когда это случится, предыдущее значение функции будем считать локальным минимумом. Вычислим значения градиента поля, модуль градиента, занесем результаты в таблицу и укажем следующий номер шага.
Все вычисления закончим, когда значение модуля градиента будет меньше или равно значению погрешности. Результаты решения приведены в таблице 2.
Таблица 2
Результаты решения контрольной задачи
| Х1 | X2 | dR/dx1 | DR/dx1 | |R| | R(X) | №Шага |
| -0,5 | -1 | -2,2499 | -8 | 8,310358 | 7,375 | 1 |
| -0,27501 | -0,2 | 1,684231 | ||||
| -0,05002 | 0,6 | -1,53007 | ||||
| 0,17497 | 1,4 | -2,19955 | ||||
| 0,17497 | 1,4 | -2,90806 | 1,6 | 3,319155 | -2,19955 | 2 |
| 0,465776 | 1,24 | -3,18108 | ||||
| 0,756581 | 1,08 | -3,82387 | ||||
| 1,047387 | 0,92 | -3,98036 | ||||
| 1,047387 | 0,92 | 0,291158 | -0,32 | 0,432635 | -3,98036 | 3 |
| 1,018271 | 0,952 | -3,99438 | ||||
| 0,989155 | 0,984 | -3,99914 | ||||
| 0,989155 | 0,984 | -0,06462 | -0,064 | 0,090946 | -3,99914 | 4 |
| 0,995617 | 0,9904 | -3,99976 | ||||
| 1,002078 | 0,9968 | -3,99997 | ||||
| 1,002078 | 0,9968 | 0,012583 | -0,0128 | 0,017949 | -3,99997 | 5 |
| 1,00082 | 0,99808 | -3,99999 | ||||
| 0,999562 | 0,99936 | -4 | ||||
| 0,999562 | 0,99936 | -0,00253 | -0,00256 | 0,003599 | -4 | 6 |
Проанализировав результаты в таблице 2, мы видим, что если не учитывать промежуточные значения, минимум функции R(x) найден на 6-ом шаге. Если сравнить результаты, полученные при поиске минимума методом градиента и методом наискорейшего спуска, мы заметим, что метод наискорейшего спуска оправдывает свое название, т.к. минимум функции найден на 6-ом шаге, а метод градиента найдет этом минимум только на 15-ом. Отсюда вывод, метод наискорейшего спуска также эффективен, но работает гораздо быстрее.
Универсального метода (алгоритма), с помощью которого можно было бы успешно решать разнообразные задачи оптимизации, не существует. Поэтому для решения каждого конкретного класса задач используют (и, как правило, не один) «свой» численный метод. Следует помнить, что эффективность численного решения зависит от того, насколько полно и точно отражается в применяемом методе специфика данной задачи, ее «индивидуальные» особенности. Данную программную модель рекомендуется использовать для поиска глобального минимума нелинейных «овражных» функции двух переменных.
Конечно, на этом можно было бы и остановиться. Метод успешно работает, довольно быстро находит минимум функции, но этот поиск можно было бы еще ускорить. Следует разработать способ выбора овражного шага, т.е. величина шага должна меняться от этапа к этапу в зависимости от расположении локального минимума функции. Эффективность рассмотренного метода возросла бы еще больше, т.к. метод зависит от величин овражных шагов h1, h2. Но здесь есть свои трудности, если овражный шаг слишком велик, то можно довольно далеко отойти от линии «дна оврага»; если же этот шаг мал, то продвижение будет незначительным. Величину шага нужно подбирать эмпирически, учитывая известные свойства минимизируемой функции.
1. Юдин Д.Б., Юдин А.Д. «Число и мысль» М.: Знание, 2005. С.190
2. Немировский А.С., Юдин Д.Б. «Информационная сложность математического моделирования» Изв. АНСССР. Тех. Кибернетика. 2003 №1 С.88-117
3. Уайнд Д. «Методы поиска экстремума». М.: Наука, 2007. С.267
4. Гельфонд И.М., Цетлин М.Л. «О некоторых способах управления сложными системами». УМН, 2002. Т.27. С.3-26
5. Федоренко Р.П. «Об одном алгоритме решения задач математического программирования». Журнал вычислительная математика, 2006. Т.22 №6 С.1331-1343
6. Поляк Б.Т. «Введение в оптимизацию» М.: Наука, 2003. С.384
7. Ногин В.Д. «Основы теории оптимизации» М.: Знание, 2007. С99-122
8. Ларичев О.И., Горвиц Г.Г. «Методы поиска локальных экстремумов овражных функций» М.: Наука, 2003. С.5-12
Приложение
Код модуля
Option Explicit
Dim i, s, j, h1, h2
Sub Кнопка2_Щелкнуть()
Form1.Show 'Ввод исходных данных
End Sub
Sub Кнопка3_Щелкнуть()
j = 1
i = 2 'Номер шага(этапа)
Do'Цикл нахождения минимума функции
h1 = Range("aa3") 'Присвоение переменным
h2 = Range("aa4") 'h1,h2 значения шага
Do
Range("z1").Select'Сохранение предыдущего
s = ActiveCell'значения функции
'Вычисление новых начальных точек
Range("v1").Select
ActiveCell = Range("x1")
Range("v2").Select
ActiveCell = Range("x2")
Range("x1").Select
ActiveCell = ActiveCell - h1
Range("x2").Select
ActiveCell = ActiveCell - h2
'Вывод в таблицу новых начальных
'точек и значение функции в этих точках
Range("a3", "f23").Select
ActiveCell(j, "a") = Range("x1")
ActiveCell(j, "b") = Range("x2")
ActiveCell(j, "f") = Range("z1")
j = j + 1
'Cравнение нового значения функции с предыдущим