ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОУВПО «Самарский государственный
архитектурно-строительный университет»
Факультет информационных систем и технологий
Кафедра прикладной математики и вычислительной техники
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
К КУРСОВОЙ РАБОТЕ
по дисциплине
МЕТОДОЛОГИЯ
НАУЧНЫХ ИССЛЕДОВАНИЙ
на тему
«Исследование методов безусловной оптимизации нулевого
порядка»
8 СЕМЕСТР 4
КУРС
Научный руководитель: фио
|
Проверили: |
Выполнил: студент ГИП фио |
|
1. фио
оценка подпись дата |
подпись дата |
|
2. фио оценка подпись дата |
|
|
|
|
|
|
|
Общая оценка _______________
Методический руководитель оценка дата
Содержание:
1. Проблема и актуальность её решения
2. Состояние проблемы и сравнительный анализ
источников
3. Постановка задачи исследования, используемые
методы
Метод спирального координатного спуска
Метод деформированного многогранника (метод
Нелдера-Мида)
4.
Программная реализация методов.
5. Исследование и сравнительный анализ методов
1. Проблема и актуальность её решения
Проблема поиска
оптимального решения с каждым годом становится все популярней не только среди
ученых, но и предпринимателей. Успешность решения подавляющего большинства
экономических задач зависит от наилучшего, наивыгоднейшего
способа использования ресурсов. В процессе экономической деятельности
приходится распределять такие важные ресурсы, как деньги, товары, сырье,
оборудование, рабочую силу и др. И от того, как будут распределяться эти, как
правило, ограниченные ресурсы, зависит конечный результат деятельности,
бизнеса. Значительные вклады ресурсов в увеличение качества и эффективность
производства говорят о необходимости поиска способа их экономия.
Об актуальности решения
проблемы можно судить по огромному числу работ выполненных для решения
специфических задач, например ([1]).
2. Состояние проблемы и сравнительный анализ источников
В настоящее время
новейшие достижения математики и современной вычислительной техники находят все
более широкое применение как в экономических исследованиях и планировании, так
и в других задачах. Этому способствует развитие таких разделов математики как
математическое программирование, теория игр, теория массового обслуживания, а
также бурное развитие быстродействующей электронно-вычислительной техники. Уже
накоплен большой опыт постановки и решения экономических и тактических задач с
помощью математических методов. Экономика и производство развивается быстро
там, где широко используются математические методы.
Исследование и сопоставление
различных методов представлены в источниках ([1]),
([2]), ([3]).
3. Постановка задачи исследования, используемые методы
Среди огромного числа задач, которые решаются
математическими методами, есть направление задач, требующих огромное число
расчетов, не только человека, но и компьютера – методы оптимизации. Эти методы
характеризуются различной эффективностью, а так же порядком, т.е.
необходимостью вычисления производных, что существенно затрудняет
алгоритмическое вычисление. Наибольшей популярностью, при решении задач такого
рода на компьютере, пользуются методы нулевого порядка, не требующие вычисления
производных. Но эффективность некоторых методов является невысокой, поэтому
передо мной встала задача исследования таких методов на непрерывной
многопараметрической задаче оптимизации:
С целью сравнить наиболее
слабые, по общепринятому мнению, методы с наиболее эффективными:
- метод координатного спуска;
- метод спирального координатного спуска;
- метод деформированного многогранника (метод Нелдера-Мида);
Метод координатного спуска
Метод координатного
спуска заключается в поочерёдном поиске минимума по координате х1, затем х2 и т.д. После
нахождения точки минимума по координате х1
переходим к нахождению минимума по координате х2 и т.д. Поиск
ведётся с одинаковым шагом, который уменьшается после нахождения всех значений 
, 
, 
для уточнения решения.
Геометрический образ решения задачи в трёхмерном пространстве напоминает спуск
на дно чаши.
В общем случае, чтобы
найти точку x* локального минимума функции F(x(k)), составляют последовательность точек (приближений к
решению) {x(k)}сходящуюся к точке x*.
Шаг выбирается таким
образом, что
xn+1(k)=xn(k) + h (1)
при
F (xn+1(k))<F (xn(k)) (2)
и
xn+1(k)=xn(k) – h (3)
при
F (xn+1(k))>F (xn(k)) (4)
Вычисления прекращают,
когда достигается заданная точность
(5)
Метод спирального координатного спуска
Отличается от
рассмотренного выше лишь тем, что шаг H меняется каждый раз при переходе от
поиска минимума по одной переменной к поиску минимума по другой переменной. В
трехмерном пространстве это напоминает спуск во впадину по спирали. Обычно этот
метод дает некоторое сокращение времени поиска.
Метод деформированного многогранника (метод Нелдера-Мида)
Данный метод([4]) состоит
в том, что для минимизации функции п
переменных f(х) в n-мерном
пространстве строится многогранник, содержащий (п +
1) вершину. Очевидно, что каждая вершина соответствует некоторому вектору х.
Вычисляются значения целевой функции f(х) в каждой из вершин многогранника, определяются максимальное из этих значений и соответствующая ему вершина х[h]. Через эту вершину и центр
тяжести остальных вершин проводится проецирующая прямая, на которой находится
точка х[q] с меньшим
значением целевой функции, чем в вершине х[h] (Рис. 2.5). Затем исключается вершина х[h]. Из оставшихся вершин и
точки x[q] строится новый
многогранник, с которым повторяется описанная процедура. В процессе выполнения
данных операций многогранник изменяет свои размеры, что и обусловило название
метода.
Рис. 1.
Геометрическая интерпретация метода
деформируемого
многогранника
Введем следующие
обозначения:
x[i, k] =(x1[i, k],
…, xj[i, k], …, xn[i,
k])T
где i
= 1, ..., п + 1; k = 0, 1, ..., - i-я вершина многогранника на k-м этапе
поиска; х[h, k] — вершина, в которой значение целевой функции
максимально, т. е. f(х[h, k] = max{f(x[1, k]),
…, f(x[n+1, k])}; х[l,
k] - вершина, в которой значение целевой функции
минимально, т. е. f(х[l, k]) =min
{f(x[1, k]),
…, f(x [n+1, k])}; х [п+2,
k]- центр тяжести всех вершин, за исключением х[h, k].
Координаты центра тяжести вычисляются по формуле
Алгоритм метода
деформируемого многогранника состоит в следующем.
1. Осуществляют
проецирование точки х[h, k] через центр тяжести:
x[n+3, k]
=x[n+2, k] + a(x[n+2, k] - x[h, k]) ,
где а > 0 - некоторая константа. Обычно а = 1.
2. Выполняют операцию
растяжения вектора х[n+3, k]
- х[n+2, k]:
x[n+4, k]
=x[n+2, k] + g(x[n+3, k] - x[n+2, k]),
где g
> 1 - коэффициент растяжения. Наиболее удовлетворительные результаты
получают при 2,8 <= g <= 3.
Если f(x[n+4, k]) < f(х[l, k]), то х[h
, k] заменяют на x[n+4, k] и продолжают вычисления с п. 1
при k = k + 1. В противном
случае х[h, k] заменяют на х[n+3, k] и переходят к п. 1 при k = k + 1.
3. Если f(x[n+3, k])
> f(х[i, k]) для всех i, не равных h, то сжимают вектор x[h, k] - x[n+2,
k]:
x[n+5, k] =x[n+2, k] + b
(х[h, k]
– x[n+2, k] ), где b > 0 - коэффициент
сжатия. Наиболее хорошие результаты получают при 0,4 <= b
<= 0,6.
Затем точку х[h, k]
заменяют на х[n+5, k] и
переходят к п. 1 при k = k+ 1.
4. Если f(x[n+3, k])>
f(x[h,
k]), то все векторы х[i, k] - х[l, k] . i=
1,..., п + 1, уменьшают в
два раза:
x[i, k] = x[l, k] + 0,5(x[i,
k] - x[l, k]) .
Затем переходят к п. 1
при k= k + 1.
В диалоговой системе
оптимизации выход из подпрограммы, реализующей метод деформируемого
многогранника, осуществляется при предельном сжатии многогранника, т. е. при
выполнении условия
,
где e
= (е1 ,..., еn) - заданный
вектор.
С помощью операции
растяжения и сжатия размеры и форма деформируемого многогранника адаптируются к
топографии целевой функции. В результате многогранник вытягивается вдоль
длинных наклонных поверхностей, изменяет направление в изогнутых впадинах,
сжимается в окрестности минимума, что определяет эффективность рассмотренного
метода.
4. Программная реализация методов
Описанные методы были
реализованы([5]) на языке Visual C++ 2005 с использованием графического
интерфейса MFC. В программе существует возможность выбора 3- функции, которые и
предполагается использовать для проведения анализа и исследования методов:
1. Функция Розенброка
f(x, y) = 100(y
- x2)2 + (1 - x)2,
F*=F (1, 1)=0
2. Тестовая функция De
Jong 2
, F*=F(1.00,1.00) = 100
3. Тестовая функция Griewank
, F*=F(0.00, 0.00)=1.0
Интерфейс программы представлен
на рисунке 2. Перед началом работы необходимо выбрать функцию, после чего
задается начальное значение точки, из положения которой осуществляется поиск
минимума функции. Для методов спирального и координатного спуска во внимание
принимается пользовательские параметры погрешности расчета и начального шага,
тогда как для метода Нелдера-Мида необходим
дополнительный параметр – максимальное число итераций.
Рис. 2.
Графический интерфейс программы
Результаты вычисления выводятся в
соответствующее окно «результаты расчета»
5. Исследование и сравнительный анализ методов
Для исследования методов
воспользуемся функцией Розенброка. Функция определена
3-ех мерном пространстве. Точность расчетов E=0.0001, начальный шаг H=0,5. Результаты тестирования методов
представлены в таблице 1.
|
|
|
Методы |
||
|
|
Начальное значение |
Спирального координатного спуска |
Координатного спуска |
Деформируемого многогранника (Нелдера-Мида) |
|
x0 |
0 |
0,933856 |
0,226183 |
0,999725 |
|
x1 |
0 |
0,69536 |
0,051136 |
0,999452 |
|
F* |
- |
0,027604 |
0,598793 |
0,000001 |
|
N |
|
118 |
967 |
73 |
|
x0 |
2 |
2,833184 |
0,226183 |
0,999725 |
|
x1 |
0 |
8,026949 |
0,051136 |
0,999452 |
|
F* |
- |
3,360564 |
0,598793 |
0,000001 |
|
N |
|
147 |
967 |
73 |
|
x0 |
3 |
3,833184 |
0,226183 |
1,000156 |
|
x1 |
-3 |
14,69326 |
0,051136 |
1,000302 |
|
F* |
- |
8,026932 |
0,598793 |
0 |
|
N |
|
191 |
967 |
108 |
Таблица 1.
Исследование методов безусловной оптимизации
на тестовой
функции Розенброка
Из одного взгляда на таблицу
видно что, результаты расчета по методам спирального и координатного спуска
требуют большего числа итераций. Хотя этот недостаток может компенсировать их
более простой алгоритма расчета, но полученные значения, оставляют желать
лучшего.
Уже при незначительном отдалении от искомого значения, методы спирального и координатного спуска получают абсолютно противоричивые результаты, тогда как метод Нелдера-Мида, обладает лишь незначительной погрешностью.
Заключение
Поиск методов позволяющих
наиболее быстро и с наименьшими потерями времени и труда решать типовые задачи
поиска минимума (максимума) является актуальной проблемой, особенно с известным
фактом применения этих задач в коммерческих расчетах, для получения большей
прибыли.
В результате проведенного
тестирования, на примере трех методов безусловной оптимизации, было доказано,
что высокая сложность алгоритма, может компенсироваться за счет времени
расчета, меньшего числа итерации и
значительно большей точности.
Развитие современного общества характеризуется повышением технического уровня, усложнением организационной структуры производства, углублением общественного разделения труда, предъявлением высоких требований к методам планирования производственной деятельности. В этих условиях только научный подход к экономике предприятий позволит обеспечить высокие темпы развития промышленности. Методы научного подхода требуется так же и для решение тактических и стратегических задач.
Список источников:
1.
Руденко
С.И. Исследование методов оптимизации в задачах планирования производства //
Северокавказский государственный технический университет URL: science.ncstu.ru/conf/past/2006/student/informatika/18.pdf (2008. 29 апр.)
2.
Медынский
М.М., Антоний Е.В. Численные методы нелинейной
оптимизации: алгоритмы и программы. Учебное
пособие – Москва: МАИ, 2003.- 192 с./ Результаты тестирования C.-179
3.
Исаев
Сергей. Генетические алгоритмы в задачах оптимизации // URL:http://www.masters.donntu.edu.ua/2005/kita/shestopalov/library/gaoptim.htm
(2008. 29 апр.)
4.
Консультационный
центр MATLAB компании
Softline // Численные методы безусловной оптимизации нулевого
порядка URL: http://www.tspu.tula.ru/ivt/old_site/lcopy/Matlab_RU/optimiz/book_2/2_1.asp.htm ()
5.
William T. Vetterling,
William H. Press, Saul A. Teukolsky, Brian P.
Flannery Numerical Recipes Example Book (C++) 1988-1992 Cambridge University
Press/ Downhilp.-408