Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




Суть этого метода состоит в следующем. Задаются некоторой начальной точкой х[0]. Изменяя компоненты вектора х[0], обследуют окрестность данной точки, в результате чего находят направление, в котором происходит уменьшение минимизируемой функции f(x). В выбранном направлении осуществляют спуск до тех пор, пока значение функции уменьшается. После того как в данном направлении не удается найти точку с меньшим значением функции, уменьшают величину шага спуска. Если последовательные дробления шага не приводят к уменьшению функции, от выбранного направления спуска отказываются и осуществляют новое обследование окрестности и т. д.

Алгоритм метода прямого поиска состоит в следующем.

1. Задаются значениями координат хi[0] , i = 1, ..., п , начальной точки х[0], вектором изменения координат х в процессе обследования окрестности, наименьшим допустимым значением е компонентов  х.

2. Полагают, что х[0] является базисной точкой хб, и вычисляют значение f(xб).

3. Циклически изменяют каждую координату хбi, i = 1, ..., п , базисной точки хб на величину ?хi, i = 1, ..., п , т. е. хi[k] = хб +  х; хi[k] = хбi - ?хi. При этом вычисляют значения f(x[k]) и сравнивают их со значением f(xб). Если f(x[k]) < f(xб), то соответствующая координата хi, i = 1, ..., п , приобретает новое значение, вычисленное по одному из приведенных выражений. В противном случае значение этой координаты остается неизменным. Если после изменения последней п-й координаты f(x[k]) < f(xб), то переходят к п, 4. В противном случае - к п. 7.

4. Полагают, что х[k] является новой базисной точкой хб , и вычисляют значение f(xб).

5. Осуществляют спуск из точки х[k] > хi[k+1] = 2хi[k] - xб , i = 1, ..., n , где xб - координаты предыдущей базисной точки. Вычисляют значение f(x[k+1]).

6. Как и в п. 3, циклически изменяют каждую координату точки х[k+1], осуществляя сравнение соответствующих значений функции f(х) со значением f (х[k+1]), полученным в п. 5. После изменения последней координаты сравнивают соответствующее значение функции f(x[k]) со значением f(xб), полученным в п. 4. Если f(x[k]) < f(xб), то переходят к п. 4, в противном случае - к п. 3. При этом в качестве базисной используют последнюю из полученных базисных точек.

7. Сравнивают значения  х и е. Если  х < е, то вычисления прекращаются. В противном случае уменьшают значения  х и переходят к п. 3.

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

Недостаток метода прямого поиска состоит в том, что в случае сильно вытянутых, изогнутых или обладающих острыми углами линий уровня целевой функции он может оказаться неспособным обеспечить продвижение к точке минимума. Действительно, в случаях, изображенных на рис. 1.5, а и б, каким бы малым ни брать шаг в направлении х1 или x2 из точки х’ нельзя получить уменьшения значения целевой функции.

Рис. 1.5. Прямой поиск: невозможность продвижения к минимуму:

а – С1 > C2 > C3; б - С1 > C2


Поделиться:

Дата добавления: 2015-07-26; просмотров: 58; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты