Стохастическое восхождение на гору против алгоритмов восхождения первого выбора
В чем разница между стохастическим восхождением на холм и алгоритмами первого выбора?
2 ответа
Алгоритм поиска по восхождению на холм является одним из семейства локальных поисков, которые перемещаются на основе лучших состояний своих соседей. Stochastic Hill Climbing выбирает случайное лучшее состояние из всех лучших состояний соседей, в то время как первый выбор Hill Climbing выбирает первое лучшее состояние из случайно сгенерированных соседей.
First-Choice Hill Climbing станет хорошей стратегией, если в нынешнем штате много соседей.
Общее восхождение на холм - это алгоритм локального поиска, который выбирает лучшее из соседей, то есть выбирает соседа с самым крутым путем и лучшим значением целевой функции. Но из-за этого он может не достичь глобального максимума и застрять на локальном максимуме. Принимая во внимание, что в случае стохастического восхождения на холм он случайным образом выбирает соседа с движением в гору, и вероятность выбора может меняться с крутизной подъема. В случае первого выбора подъема на холм он случайным образом генерирует следующее движение и выполняет поиск пока не будет найдено состояние, которое лучше, чем все состояния.
Я цитирую " Искусственный интеллект: современный подход" (3-е изд.) (2010) Рассела, Норвиг
Стохастическое восхождение на холм выбирает случайным образом из числа движений в гору; вероятность выбора может варьироваться в зависимости от крутизны движения в гору. Это обычно сходится медленнее, чем крутое восхождение, но в некоторых государственных ландшафтах оно находит лучшие решения. Скалолазание первого выбора реализует стохастическое восхождение на холмы путем генерации преемников случайным образом, пока не будет сгенерировано одно, которое лучше текущего состояния. Это хорошая стратегия, когда у государства много (например, тысяч) преемников.
Таким образом, альпинизм первого выбора - это особая разновидность стохастического альпинизма.