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

Question

У меня есть число с плавающей запятой x от [1, 500] который генерирует двоичный файл y из 1 с некоторой вероятностью p, И я пытаюсь найти x которые могут генерировать наиболее 1 или имеет самый высокий p, Я предполагаю, что есть только один максимум.

Есть ли алгоритм, который может быстро сходиться к x с самым высоким p удостоверившись, что он не прыгает слишком много после того, как он достигнут, например, в пределах 0,1% от оптимального x? В частности, было бы здорово, если бы он стабилизировался, когда около < 0,1% от оптимального x,

Я знаю, что мы можем сделать это с помощью имитации отжига, но я не думаю, что мне нужно жестко программировать температуру, потому что мне нужно использовать тот же алгоритм, когда x может быть из [1, 3000] или p Распределение отличается.

Answer 1

Эта статья предлагает интеллектуальный алгоритм восхождения на холм. Идея состоит в том, что вы берете n образцов в качестве отправных точек. Алгоритм выглядит следующим образом (для вашей задачи он упрощен в одно измерение):

1. принимать n выборочные точки в пространстве поиска. В статье он использует выборку линейного гиперкуба, поскольку размеры данных в статье предполагаются большими. В вашем случае, поскольку он одномерный, вы можете просто использовать случайный саженец как обычно.
2. Для каждой точки выборки соберите точки из ее "локальной окрестности" и найдите наилучшую квадратичную кривую. Найти нового максимального кандидата из квадратичной кривой. Если целевая функция нового максимального кандидата фактически выше, чем предыдущая, обновите точку выборки до нового максимального кандидата. Повторите этот шаг с меньшим размером "локальной окрестности" для каждой итерации.
3. Используйте лучшую точку из точек выборки
4. Перезагрузка: повторите шаги 2 и 3, а затем сравните максимумы. Если улучшения нет, остановитесь. Если есть улучшение, повторите еще раз.