|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Метод Хука-ДживсаОдин из наиболее известных методов прямого поиска предложен Хуком и Дживсом (R. Hooke, T. A. Jeeves) в 1961 г. Идея метода заключается в исследовании локальной топографии поверхности и попытке двигаться дальше, сохраняя то же направление, которое привело к самой низкой из найденных точек. Если это направление приводит к успеху, оно сохраняется, в противном случае на основании локального поиска выбирается новое направление и т. д. Алгоритм выглядит следующим образом: а) Выбрать начальную точку x0 и шаг по каждой переменной hi. Вычислить F0=F(x0). б) Исследовать локальное поведение F(x) в окрестности x0, а именно: – в качестве текущей точки x1 принять начальную точку x0. – для всех i от 1 до N повторить следующие действия: вычислить , где ei – вектор единичной длины, совпадающий по направлению с координатной осью xi. Иными словами, от текущей точки нужно сделать шаг длины hi по переменной xi при фиксированных значениях остальных переменных. если , перенести текущую точку в новое положение, т. е. , в противном случае сделать шаг по xi в обратном направлении: , и если этот шаг окажется успешным, передвинуть текущую точку. Если обе попытки перемещения по координате xi не привели к понижению значения функции, сохранить прежнее положение x1. в) Сравнить точку x1, достигнутую после исследующего поиска, с исходной точкой x0. Если x1=x0, т. е. ни в одном направлении не удалось добиться понижения функции, следует уменьшить величину шага () и вернуться к п. б) для повторения поиска. г) Если после исследующего поиска текущая точка сместилась (x1¹x0), попробовать продвинуться дальше в том же направлении, т. е. перейти в точку x2=x1+(x1-x0). Это называется «шаг по образцу». Значение функции в точке x2 не проверяется (оно может быть ниже или выше значения в x1). д) Выполнить исследующий поиск от точки x2 (так, как описано в п. б). В результате будет найдена точка x3. Сравнить значения функции в точках x1 и x3. е) Если F(x3)<F(x1), принять x3 за новую текущую точку (x0=x2, x1=x3) и сделать шаг по образцу, т. е. перейти к п. г). Если же F(x3)³F(x1), то точки x2 и x3 отвергаются, и продолжается исследующий поиск от точки x1 (x0=x1, перейти к п. б). Процесс заканчивается, когда шаги hi по всем переменным (постепенно уменьшающиеся благодаря периодическому выполнению п. в) станут меньше заданного предела точности. Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.) |