|
|
|
scroollocker |
|
|||
.{--}. Профиль Группа: Участник Сообщений: 40 Регистрация: 17.9.2010 Репутация: нет Всего: нет |
Всем привет!
Есть задача написать программу, использующую метод Хука-дживса для минимизации функции. Алгоритм запрограммирован, но столкнулся с такой проблемой: По задаче у меня функция имеет 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 |
|
|||
Опытный Профиль Группа: Участник Сообщений: 586 Регистрация: 18.8.2011 Где: Красноярск Репутация: 4 Всего: 17 |
Очень странно описан алгоритм.
В Википедии алгоритм описан как двухшаговый. На первом шаге ищем локальный минимум фактически вариацией покоординатного спуска, описанной Вами. На втором шаге проводим попытку глобализации минимума. С новой точки снова запускаем первый шаг. Описание в Википедии достаточно подробное. Несколько существенных для реализации нюансов. 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, которая поставит в тупик любую градиентную минимизацию. Успехов. -------------------- Mirkes |
|||
|
||||
scroollocker |
|
|||
.{--}. Профиль Группа: Участник Сообщений: 40 Регистрация: 17.9.2010 Репутация: нет Всего: нет |
Mirkes,
Спасибо за развернутый ответ, как раз так и работает алгоритм. Тут вопрос в другом, почему если задать допустим шаги 1,1,1,1 то получим минимум, но переменные одни (рис 1), а если задать допустим шаги 0.5,2,2,1 минимум тот же, то переменные чуть чуть другие (рис 2)? Нигде про это не нашел... собственно сама задачка для наглядности: Это сообщение отредактировал(а) scroollocker - 9.7.2013, 16:18 |
|||
|
||||
Mirkes |
|
|||
Опытный Профиль Группа: Участник Сообщений: 586 Регистрация: 18.8.2011 Где: Красноярск Репутация: 4 Всего: 17 |
А ограничение на минимальный шаг какое? То есть при каком размере шага вы прекращает счет?
Вообще то на месте преподавателя я бы вас выдрал, за отсутствие представления о числе и записи числа. Начнем с того, что при начальных значениях точек функция равна 29053.0023566289 насколько хватает точности extended в Excel, а вовсе не 29053, как написано в задании. В конечной точке, предложенной в качестве правильного ответа значение функции равно 318.580821412608 Вы нашли две точки РЯДОМ с минимумом. В первой значение функции равно 318.57188775197, а во второй 318.571884767139 Различия идут в 6 знаке, после запятой, но они есть. Поскольку вы взялись использовать ЧИСЛЕННЫЕ методы, то крайне важно понимать, с какой ТОЧНОСТЬЮ вы считаете и тогда будет понятно, какие цифры значимы в ответе. Если вас интересует точность в три знака в значении функции, то используя предложенный преподом ответ, можно оценить вариацию каждого признака. Итак, значение функции ПОСЛЕ ОКРУГЛЕНИЯ до трех знаков после запятой должно быть 318.572 К сожалению приведенный "правильный" ответ не позволяет получить нужное значение функции при вариации одной (любой) переменной. Общее заключение: Оба полученных вами ответа правильны, если необходимо было найти минимум с точностью до 0.001. Еще раз подчеркну, что в отличии от математики, в численных методах минимум ищется с заданной точностью. Точность может быть задана на изменение переменных или на изменение значения функции. Если требование второе то вы нашли правильный ответ. PS Извините за некоторую резкозть, претензия скорее к преподавателю, не объяснившему базовых вещей. Это сообщение отредактировал(а) Mirkes - 9.7.2013, 17:55 -------------------- Mirkes |
|||
|
||||
scroollocker |
|
|||
.{--}. Профиль Группа: Участник Сообщений: 40 Регистрация: 17.9.2010 Репутация: нет Всего: нет |
Моя вина, не всю информацию раскрыл. =)
Точность стоит 0.000001. Как вы сказали, различия идут в 6 знаке после запятой, следовательно алгоритм работает правильно? т.е. с заданной точностью находит решение верное? |
|||
|
||||
Mirkes |
|
|||
Опытный Профиль Группа: Участник Сообщений: 586 Регистрация: 18.8.2011 Где: Красноярск Репутация: 4 Всего: 17 |
Если точность контролируется по изменению функции то видимо правильная.
Если это ограничение на длину шага, то понятия не имею, поскольку шаг у вас выводится только с 2-3 знаками (за исключением первой переменной. Должен сказать, что оба Ваших решения точнее, чем решение из методички -------------------- Mirkes |
|||
|
||||
scroollocker |
|
|||
.{--}. Профиль Группа: Участник Сообщений: 40 Регистрация: 17.9.2010 Репутация: нет Всего: нет |
Mirkes,
Спасибо вам за ответы =) Более понятен стал алгоритм и сам метод. Буду пробовать его сдать. |
|||
|
||||
jones123 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 1 Регистрация: 11.11.2019 Репутация: нет Всего: нет |
Модератор: Сообщение скрыто. |
|||
|
||||
Kuroki2223 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 10 Регистрация: 1.11.2020 Репутация: нет Всего: нет |
Понял алгоритм, спасибо, всё отлично
|
|||
|
||||
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |