Модераторы: maxim1000
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Алгоритм оптимизации методом Хука-Дживса, Вопрос 
V
    Опции темы
scroollocker
  Дата 8.7.2013, 10:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


.{--}.



Профиль
Группа: Участник
Сообщений: 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]. Как правильно выбрать шаги для алгоритма Хука-Дживса, чтобы в результате находился правильный минимум?
PM MAIL WWW ICQ Jabber   Вверх
Mirkes
Дата 9.7.2013, 14:35 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 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
PM MAIL   Вверх
scroollocker
Дата 9.7.2013, 16:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


.{--}.



Профиль
Группа: Участник
Сообщений: 40
Регистрация: 17.9.2010

Репутация: нет
Всего: нет



Mirkes

Спасибо за развернутый ответ, как раз так и работает алгоритм. 

Тут вопрос в другом, почему если задать допустим шаги 1,1,1,1 то получим минимум, но переменные одни (рис 1), а если задать допустим шаги 0.5,2,2,1 минимум тот же, то переменные чуть чуть другие (рис 2)? Нигде про это не нашел... 

user posted image

собственно сама задачка для наглядности:
user posted image

Это сообщение отредактировал(а) scroollocker - 9.7.2013, 16:18
PM MAIL WWW ICQ Jabber   Вверх
Mirkes
Дата 9.7.2013, 17:53 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 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
PM MAIL   Вверх
scroollocker
Дата 9.7.2013, 18:27 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


.{--}.



Профиль
Группа: Участник
Сообщений: 40
Регистрация: 17.9.2010

Репутация: нет
Всего: нет



Моя вина, не всю информацию раскрыл. =) 

Точность стоит 0.000001. Как вы сказали, различия идут в 6 знаке после запятой, следовательно алгоритм работает правильно? т.е. с заданной точностью находит решение верное? 


PM MAIL WWW ICQ Jabber   Вверх
Mirkes
Дата 9.7.2013, 20:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 586
Регистрация: 18.8.2011
Где: Красноярск

Репутация: 4
Всего: 17



Если точность контролируется по изменению функции то видимо правильная.
Если это ограничение на длину шага, то понятия не имею, поскольку шаг у вас выводится только с 2-3 знаками (за исключением первой переменной.
Должен сказать, что оба Ваших решения точнее, чем решение из методички smile


--------------------
Mirkes
PM MAIL   Вверх
scroollocker
Дата 10.7.2013, 15:44 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


.{--}.



Профиль
Группа: Участник
Сообщений: 40
Регистрация: 17.9.2010

Репутация: нет
Всего: нет



Mirkes
Спасибо вам за ответы =) Более понятен стал алгоритм и сам метод. Буду пробовать его сдать.
PM MAIL WWW ICQ Jabber   Вверх
jones123
Дата 11.11.2019, 17:22 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 2
Регистрация: 11.11.2019

Репутация: нет
Всего: нет




Модератор: Сообщение скрыто.

PM MAIL   Вверх
Google
  Дата 8.12.2019, 13:28 (ссылка)  





  Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
2 Пользователей читают эту тему (2 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0779 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.