DAA - алгоритм восхождения на холм

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

Для многих проблем путь к цели не имеет значения. Например, в задаче N-Queens нам не нужно заботиться об окончательной конфигурации ферзей, а также о том, в каком порядке они добавляются.

Скалолазание

Hill Climbing - это метод решения определенных задач оптимизации. В этом методе мы начинаем с неоптимального решения, которое многократно улучшается, пока какое-то условие не будет максимальным.

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

Следовательно, технику восхождения можно рассматривать как следующие этапы:

  • Построение неоптимального решения с учетом ограничений задачи
  • Пошаговое улучшение решения
  • Улучшение решения до тех пор, пока улучшение не станет невозможным

Техника Hill Climbing в основном используется для решения сложных вычислительных задач. Он смотрит только на текущее состояние и состояние в ближайшем будущем. Следовательно, этот метод эффективен с точки зрения памяти, поскольку он не поддерживает дерево поиска.

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

Итеративное улучшение

В итеративном методе улучшения оптимальное решение достигается за счет продвижения к оптимальному решению на каждой итерации. Однако при этом методе могут встречаться локальные максимумы. В этой ситуации нет ближайшего состояния для лучшего решения.

Избежать этой проблемы можно разными способами. Один из таких методов - имитационный отжиг.

Произвольный перезапуск

Это еще один метод решения проблемы локальных оптимумов. Эта техника позволяет проводить серию поисков. Каждый раз он запускается из случайно сгенерированного начального состояния. Следовательно, можно получить оптимальное или почти оптимальное решение, сравнивая решения выполненных поисков.

Проблемы техники восхождения на холмы

Локальные максимумы

Если эвристика не является выпуклой, Hill Climbing может сходиться к локальным максимумам, а не к глобальным максимумам.

Гряды и аллеи

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

Плато

Плато встречается, когда пространство поиска является плоским или достаточно плоским, чтобы значение, возвращаемое целевой функцией, было неотличимо от значения, возвращаемого для соседних регионов, из-за точности, используемой машиной для представления его значения.

Сложность техники восхождения на холм

Этот метод не имеет проблем, связанных с пространством, поскольку он учитывает только текущее состояние. Ранее исследованные пути не сохраняются.

Для большинства проблем в технике Hill Climbing со случайным перезапуском оптимальное решение может быть достигнуто за полиномиальное время. Однако для задач NP-Complete время вычислений может быть экспоненциальным в зависимости от количества локальных максимумов.

Применение техники восхождения на холм

Технику восхождения на холм можно использовать для решения многих проблем, где текущее состояние позволяет выполнять точную функцию оценки, таких как Network-Flow, задача коммивояжера, задача 8-Queens, проектирование интегральных схем и т. Д.

Скалолазание также используется в индуктивных методах обучения. Этот метод используется в робототехнике для координации между несколькими роботами в команде. Есть много других проблем, где используется этот метод.

пример

Эту технику можно применить для решения задачи коммивояжера. Сначала определяется исходное решение, которое посещает все города ровно один раз. Следовательно, это начальное решение в большинстве случаев не является оптимальным. Даже это решение может быть очень плохим. Алгоритм Hill Climbing начинается с такого начального решения и итеративно вносит в него улучшения. В конце концов, вероятно, будет получен гораздо более короткий маршрут.