| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Алгоритм оптимизации методом Хука-Дживса |
| Автор: scroollocker 8.7.2013, 10:55 |
| Всем привет! Есть задача написать программу, использующую метод Хука-дживса для минимизации функции. Алгоритм запрограммирован, но столкнулся с такой проблемой: По задаче у меня функция имеет 4 параметра (Xi, i = 1,...,4) и 4 значения шага (Di, i = 1,...,4). В ходе работы алгоритма, X прибавляется или уменьшается на свой шаг, до тех пор, пока значение функции уменьшается. Если уменьшение не происходит, делим шаг пополам. Программа находит минимум, но он каждый раз отличается. В зависимости от значений шага например для значений x = [ 1, 20, 12, 3] и шага D = [1,1,1,1] минимум равен 13.212 в точках x = [ 1.173, 53.411, 4.33, 20] если изменить шаг и сделать их D = [0.5,2,1,0.8], то минимум уже равен 13.611 в точках x = [ 1.173, 50.212, 3.18, 19.81]. Как правильно выбрать шаги для алгоритма Хука-Дживса, чтобы в результате находился правильный минимум? |
| Автор: Mirkes 9.7.2013, 14:35 |
| Очень странно описан алгоритм. Вhttp://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%A5%D1%83%D0%BA%D0%B0_%E2%80%94_%D0%94%D0%B6%D0%B8%D0%B2%D1%81%D0%B0 алгоритм описан как двухшаговый. На первом шаге ищем локальный минимум фактически вариацией покоординатного спуска, описанной Вами. На втором шаге проводим попытку глобализации минимума. С новой точки снова запускаем первый шаг. Описание в Википедии достаточно подробное. Несколько существенных для реализации нюансов. 0. Запоминаем начальную точку SX1 1. Поиск производится по одной координате. Пусть Вы знаете значение в точке Х1,Х2,Х3,Х4 и имеете шаги Н1,Н2,Н3,Н4. Тогда поиск состоит из последовательно повторяющихся четверок поисков: 1.1. Берем i=1 1.2. Значение функции в исходной точке F0 1.3. Вычисляем значения функции в точках Х1+Н1,Х2,Х3,Х4 (F+) и Х1-Н1,Х2,Х3,Х4 (F-) 1.4. Если минимальное значение функции F+ то производим замену Х1=Х1+Н1 1.5. Если минимальное значение функции F- то производим замену Х1=Х1-Н1 1.6. Если минимальное значение функции F0 то уменьшаем шаг Н1=Н1/2 (можно делить на 3 или на 1.1) 1.7. ТО же для i=2, 3, 4 1.8. Если ВСЕ шаги меньше заданного порога - завершение первой фазы, иначе переход к шагу 1.1 2. Запоминаем полученную точку как SX2 3. Попытка глобализации минимума - вычисляем точку SX3=SX1+k(SX2-SX1) 4. Для точки SX3 повторяем первый шаг Естественно с БОЛЬШИМИ начальными шагами. Ну и далее по Википедии или другому описанию Если при старте из одной и той же точки с близкими начальными шагами Вы каждый раз получаете другое решение, то либо Вы не тот алгоритм реализовали, либо у Вас предельно дрянная функция (что тоже случается) Насколько я понимаю, этот алгоритм вполне способен найти глобальный минимум функции типа (Sin(x1+x2+x3+x4)+x1+x2+x3+x4)^2, которая поставит в тупик любую градиентную минимизацию. Успехов. |
| Автор: scroollocker 9.7.2013, 16:07 |
| Mirkes, Спасибо за развернутый ответ, как раз так и работает алгоритм. Тут вопрос в другом, почему если задать допустим шаги 1,1,1,1 то получим минимум, но переменные одни (рис 1), а если задать допустим шаги 0.5,2,2,1 минимум тот же, то переменные чуть чуть другие (рис 2)? Нигде про это не нашел...  собственно сама задачка для наглядности:  |
| Автор: Mirkes 9.7.2013, 17:53 |
| А ограничение на минимальный шаг какое? То есть при каком размере шага вы прекращает счет? Вообще то на месте преподавателя я бы вас выдрал, за отсутствие представления о числе и записи числа. Начнем с того, что при начальных значениях точек функция равна 29053.0023566289 насколько хватает точности extended в Excel, а вовсе не 29053, как написано в задании. В конечной точке, предложенной в качестве правильного ответа значение функции равно 318.580821412608 Вы нашли две точки РЯДОМ с минимумом. В первой значение функции равно 318.57188775197, а во второй 318.571884767139 Различия идут в 6 знаке, после запятой, но они есть. Поскольку вы взялись использовать ЧИСЛЕННЫЕ методы, то крайне важно понимать, с какой ТОЧНОСТЬЮ вы считаете и тогда будет понятно, какие цифры значимы в ответе. Если вас интересует точность в три знака в значении функции, то используя предложенный преподом ответ, можно оценить вариацию каждого признака. Итак, значение функции ПОСЛЕ ОКРУГЛЕНИЯ до трех знаков после запятой должно быть 318.572 К сожалению приведенный "правильный" ответ не позволяет получить нужное значение функции при вариации одной (любой) переменной. Общее заключение: Оба полученных вами ответа правильны, если необходимо было найти минимум с точностью до 0.001. Еще раз подчеркну, что в отличии от математики, в численных методах минимум ищется с заданной точностью. Точность может быть задана на изменение переменных или на изменение значения функции. Если требование второе то вы нашли правильный ответ. PS Извините за некоторую резкозть, претензия скорее к преподавателю, не объяснившему базовых вещей. |
| Автор: scroollocker 9.7.2013, 18:27 |
| Моя вина, не всю информацию раскрыл. =) Точность стоит 0.000001. Как вы сказали, различия идут в 6 знаке после запятой, следовательно алгоритм работает правильно? т.е. с заданной точностью находит решение верное? |
| Автор: Mirkes 9.7.2013, 20:22 |
| Если точность контролируется по изменению функции то видимо правильная. Если это ограничение на длину шага, то понятия не имею, поскольку шаг у вас выводится только с 2-3 знаками (за исключением первой переменной. Должен сказать, что оба Ваших решения точнее, чем решение из методички  |
| Автор: scroollocker 10.7.2013, 15:44 |
| Mirkes, Спасибо вам за ответы =) Более понятен стал алгоритм и сам метод. Буду пробовать его сдать. |
| Автор: jones123 11.11.2019, 17:22 |
Модератор: Сообщение скрыто. |
| Автор: Kuroki2223 1.11.2020, 22:47 |
| Понял алгоритм, спасибо, всё отлично |