Алгоритмы, обсуждаемые в предыдущих главах, работают систематически. Для достижения цели необходимо сохранить один или несколько ранее исследованных путей к решению, чтобы найти оптимальное решение.
Для многих проблем путь к цели не имеет значения. Например, в задаче 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 вычислительное время может быть экспоненциальным в зависимости от количества локальных максимумов.
Применение техники скалолазания
Техника Hill Climbing может быть использована для решения многих проблем, где текущее состояние позволяет выполнять точную функцию оценки, такую как Network-Flow, задача коммивояжера, задача 8 Queens, проектирование интегральной микросхемы и т. Д.
Скалолазание также используется в индуктивных методах обучения. Эта техника используется в робототехнике для координации действий нескольких роботов в команде. Есть много других проблем, где этот метод используется.
пример
Эта техника может быть применена для решения проблемы коммивояжера. Сначала определяется первоначальное решение, которое посещает все города ровно один раз. Следовательно, это начальное решение не является оптимальным в большинстве случаев. Даже это решение может быть очень плохим. Алгоритм Hill Climbing начинается с такого начального решения и вносит в него улучшения итеративным способом. В конце концов, гораздо более короткий путь может быть получен.