ИМРС 4.4 Имитация отжига

[@ikitsar459]

Если F(x^*) - F(x)>=0, то вычисляем вероятность Здесь надо оставить строгое неравенство, так как если разность равна 0, то вероятность будет равняется 1 и нам придётся лишнее вычисление делать. Нужно знак равно перенести в первое сравнение F(x^*) - F(x)0 И ещё один момент. Нигде не услышал, как выбирается следующая точка. Если она выбирается случайным образом из всего множества решений, то зачем боятся застревания в локальном минимуме? В любой момент из него вылезти можно. Тогда алгоритм выглядит так: выбираем случайную точку и если она ниже текущей, то переходим на неё, если выше, то просто пробуем выбрать другую точку. Или есть какие то правила по выбору следующей точки?

[@ivanborisov8583]

Спасибо за наблюдение! Если разница F(x^*) - F(x) = 0, то вероятность действительно равна единице P = exp(-0/T) = 1, но если перенести знак равенства в первое условие, то при F(x^*) - F(x) = 0 вероятность тоже будет равна единице P=1, результат не изменится. "Лишнее вычисление" делает программа, быстродействие которой заметно не изменится, если знак равенства будет в первом условии. В целом можно и так и так в данном базовом исполнении алгоритма. Строгое условие принято указывать для решения, которое гарантировано дает лучшее значение функции, например меньшее при задаче минимизации функции; при равенстве значений функции у нас может быть и другое условие, например P=0, т.к. может быть в таком х нет большого смысла. Функция вероятности для F(x^*) - F(x)>=0 может быть модернизирована весовыми коэффициентами, дополнительными эвристиками и прч., так что при F(x^*) - F(x)=0, вероятность будет отлична от единицы. Следующее значение х выбирается случайным образом. Вы предложили альтернативный алгоритм поиска, но скажите, пожалуйста, а каково условие остановки работы алгоритма? До каких пор мы будем рассматривать решения? Пока не пересмотрим их все? Если так, то боюсь алгоритм будет не из самых быстрых. Или ограничение по количеству сравнений, как в алгоритмах прямого поиска? Вообще, то что вы предложили называется жадным алгоритмом и его тоже можно использовать, все зависит от задачи. Суть в компромиссе между исследованием пространства решений и использованием найденных значений. Полный перебор невозможен (см. задача коммивояжера), поэтому надо как-то "умно" исследовать пространство. Жадный алгоритм больше про использование быстро найденного решения, имитация отжига про взвешенный подход к исследованию и использованию.

[@ikitsar459]

@@ivanborisov8583 ну так если следующее значение выбирается случайным образом, то невозможно застрять в локальном минимуме, мы в любой момент можем перейти в любую более удачную точку. Вы об этом говорите 4:40 "мы никогда не вылезем..." А что не даст вам вылезти из локального минимума, если "Следующее значение х выбирается случайным образом." ? Допустим, вы попали в локальный минимум, случайно выбираете следующую точку и оказываетесь в глобальном минимуме и смело переходите туда И если "Следующее значение х выбирается случайным образом.", то нет смысла ни в в фиксировании текущей точки, ни в расчёте вероятности перехода. Просто случайно перебираем варианты заданное количество итераций и на выходе берём лучший вариант. В вашем варианте мы в точности также перебираем случайные варианты, но на выходе, возможно, берём не самый лучший вариант из найденных, плюс делаем кучу вычислений, которые ни как не влияют на то, какую точку мы выберем в следующий раз. Поиск будет такой же случайный, как и в случайном переборе

[@ivanborisov8583]

Все зависит от политики для х. Например, в локальный минимум мы попадем если используем градиентный спуск, т.к. там х выбирается не случайным образом, а в направлении минимизации значений градиента x_{n+1}=x_{n}+scale*df/dx Если х выбирается случайно, то локальные минимумы не страшны. Поэтому градиентные методы используются для выпуклых целевых функций, а для функций с локальными и глобальными минимумами и максимумами используются алгоритмы глобальной оптимизации. Алгоритм имитации отжига исследует пространство решений. Допустим начальная точка выбрана случайно х0=random, то последующая точка может быть сгенерирована, например, следующим образом x*=x_i+random*scale, где х* точка кандидат, x_i - предыдущее значение, random - какое то случайное число или какая-то эвристика, scale - какой-то весовой коэффициент, который может быть как константой, так и функцией. Алгоритм имитации отжига похож на градиентный спуск, но из-за random в х* может выбираться из локальных минимумов. Жадный алгоритм нацелен на максимизацию сиюмоментного вознаграждения, жадный алгоритм слепой. Можно запускать итерационно, допустим с учетом ранее рассмотренных значений и тоже найти решение.

[@ikitsar459]

@@ivanborisov8583 "..последующая точка может быть сгенерирована, например, следующим образом x*=x_i+random*scale.." Ну вот. Теперь следующая точка выбирается не случайно, а из какой то окрестности :( Странно всё это. Поискал в интернете, расстояние от текущей точки до следующей ограниченно и оно может уменьшаться пропорционально уменьшению температуры. В этом случае поиск перестаёт быть случайным перебором

[@ivanborisov8583]

@@ikitsar459 выбор точки зависит от случайной величины “random”, поэтому подход вероятностный. Стратегия выбора точки должна настраиваться разработчиком. То что я описал выше- один из способов реализации