В численном анализе восхождение на холм — это метод математической оптимизации , принадлежащий к семейству локального поиска . Это итерационный алгоритм , который начинается с произвольного решения проблемы, а затем пытается найти лучшее решение, внося в него дополнительные изменения. Если изменение приводит к лучшему решению, в новое решение вносится еще одно постепенное изменение и так далее, пока не будет обнаружено никаких дальнейших улучшений.
Например, восхождение на холм можно применить к задаче коммивояжера . Легко найти первоначальное решение, которое охватит все города, но, скорее всего, будет очень плохим по сравнению с оптимальным решением. Алгоритм начинается с такого решения и вносит в него небольшие улучшения, например, меняет порядок посещения двух городов. В конечном итоге, вероятно, будет получен гораздо более короткий маршрут.
Восхождение на холм находит оптимальные решения для выпуклых задач – для других задач оно находит только локальные оптимумы (решения, которые не могут быть улучшены никакими соседними конфигурациями), которые не обязательно являются лучшим возможным решением (глобальным оптимумом ) из всех возможных решений ( пространство поиска ). Примеры алгоритмов, решающих выпуклые задачи путем восхождения на холм, включают симплексный алгоритм линейного программирования и двоичного поиска . [1] : 253 Чтобы попытаться избежать застревания в локальных оптимумах, можно использовать перезапуски (т. е. повторный локальный поиск) или более сложные схемы, основанные на итерациях (например, итерированный локальный поиск ) или на памяти (например, оптимизация реактивного поиска и табу). поиск ) или стохастических модификаций без памяти (например, имитация отжига ).
Относительная простота алгоритма делает его популярным выбором среди алгоритмов оптимизации. Он широко используется в искусственном интеллекте для достижения целевого состояния из начального узла. В связанных алгоритмах используются разные варианты выбора следующих и начальных узлов. Хотя более продвинутые алгоритмы, такие как имитация отжига или табу-поиск, могут дать лучшие результаты, в некоторых ситуациях восхождение на холм работает так же хорошо. Восхождение на холм часто может дать лучший результат, чем другие алгоритмы, когда количество времени, доступное для выполнения поиска, ограничено, например, в системах реального времени, при условии, что небольшое количество приращений обычно сходится к хорошему решению (оптимальное решение). или близкое приближение). С другой стороны, пузырьковую сортировку можно рассматривать как алгоритм восхождения на холм (каждая замена соседних элементов уменьшает количество пар неупорядоченных элементов), однако этот подход далеко не эффективен даже для скромного N, поскольку количество требуемых обменов растет квадратично.
Восхождение на холм — это алгоритм, работающий в любое время : он может вернуть допустимое решение, даже если он был прерван в любой момент до его завершения.
Восхождение на холм пытается максимизировать (или минимизировать) целевую функцию , где – вектор непрерывных и/или дискретных значений. На каждой итерации восхождение на холм будет корректировать один элемент и определять, улучшит ли это изменение значение . (Обратите внимание, что это отличается от методов градиентного спуска , которые корректируют все значения на каждой итерации в соответствии с уклоном холма.) При подъеме на холм любое улучшение принимается , и процесс продолжается до тех пор, пока не будет обнаружено никаких изменений. повысить ценность . Тогда говорят, что это «локально оптимальное».
В дискретных векторных пространствах каждое возможное значение можно визуализировать как вершину графа . Восхождение на холм будет следовать по графику от вершины к вершине, всегда локально увеличивая (или уменьшая) значение , пока не будет достигнут локальный максимум (или локальный минимум ) .
При простом восхождении на холм выбирается первый ближайший узел, тогда как при подъеме на холм с самым крутым подъемом сравниваются все преемники и выбирается наиболее близкий к решению. Обе формы терпят неудачу, если нет более близкого узла, что может произойти, если в пространстве поиска есть локальные максимумы, которые не являются решениями. Подъем на гору с самым крутым подъемом аналогичен поиску по принципу «сначала лучший» , который пробует все возможные продолжения текущего пути, а не только одно.
Стохастическое восхождение на холм не проверяет всех соседей, прежде чем решить, как двигаться. Скорее, он выбирает соседа случайным образом и решает (в зависимости от степени улучшения этого соседа), переходить ли к этому соседу или исследовать другого.
Координатный спуск выполняет поиск линии по одному координатному направлению в текущей точке на каждой итерации. Некоторые версии спуска по координатам случайным образом выбирают другое направление координат на каждой итерации.
Восхождение на гору со случайным перезапуском — это метаалгоритм, построенный на основе алгоритма восхождения на гору. Это также известно как восхождение на холм с дробовиком . Он итеративно выполняет восхождение на холм, каждый раз со случайным начальным условием . Лучшее сохраняется: если новый забег по восхождению дает результат лучше , чем сохраненное, оно заменяет сохраненное состояние.
Подъем на гору с произвольным перезапуском во многих случаях оказывается удивительно эффективным алгоритмом. Оказывается, зачастую лучше потратить время ЦП на изучение пространства, чем на тщательную оптимизацию исходных условий. [ оригинальное исследование? ]
Восхождение на холм не обязательно приведет к достижению глобального максимума, но вместо этого может привести к достижению локального максимума . Эта проблема не возникает, если эвристика выпуклая. Однако, поскольку многие функции не являются выпуклыми, восхождение на холм часто может не достичь глобального максимума. Другие алгоритмы локального поиска пытаются преодолеть эту проблему, например, стохастический подъем на холм , случайные блуждания и имитация отжига .
Гребни представляют собой сложную проблему для альпинистов, которые оптимизируются в непрерывных пространствах. Поскольку альпинисты корректируют только один элемент вектора за раз, каждый шаг будет двигаться в направлении оси. Если целевая функция создает узкий гребень, который поднимается в направлении, не совмещенном с осью (или, если цель состоит в том, чтобы свести к минимуму узкий переулок, который спускается в направлении, не совмещенном с осью), тогда альпинист может подняться только по гребень (или спуститься по переулку) зигзагами. Если склоны хребта (или переулка) очень крутые, то альпинист может быть вынужден делать очень маленькие шаги по мере зигзагообразного движения к лучшему положению. Таким образом, подъем на гребень (или спуск по переулку) может занять неоправданно много времени.
Напротив, методы градиентного спуска могут двигаться в любом направлении, в котором гребень или переулок могут подниматься или опускаться. Следовательно, градиентный спуск или метод сопряженных градиентов обычно предпочтительнее подъема в гору, когда целевая функция дифференцируема. Однако у альпинистов есть то преимущество, что они не требуют, чтобы целевая функция была дифференцируемой, поэтому альпинисты могут быть предпочтительнее, когда целевая функция сложна.
Другая проблема, которая иногда возникает при восхождении на холм, — это плато. Плато встречается, когда пространство поиска плоское или достаточно плоское, чтобы значение, возвращаемое целевой функцией, неотличимо от значения, возвращаемого для соседних регионов, из-за точности, используемой машиной для представления его значения. В таких случаях альпинист может оказаться не в состоянии определить, в каком направлении ему следует двигаться, и может отклониться в направлении, которое никогда не приведет к улучшению.
Алгоритм псевдокода Discrete Space Hill Climbing текущийузел:= начальныйузел цикл делать L := СОСЕДИ(текущийУзел) следующийEval := −INF следующийУзел := НУЛЬ для всех x в L сделайте , если EVAL(x) > nextEval, тогда следующийУзел := х следующийEval := EVAL(x) если nextEval ≤ EVAL(currentNode), то // Возвращаем текущий узел, поскольку лучших соседей не существует вернуть текущийузел текущийУзел := СледующийУзел
Алгоритм непрерывного космического восхождения на холм currentPoint := InitialPoint // вектор нулевой величины является общим StepSize := InitialStepSizes // вектор, состоящий из всех единиц, является общим ускорение := someAcceleration // обычно встречается значение, например 1,2. кандидат[0] := −ускорение кандидат[1] := −1 / ускорение кандидат[2] := 1 / ускорение кандидат[3] := ускорение bestScore := EVAL(currentPoint) цикл делать beforeScore := bestScore для каждого элемента я в currentPoint делаю beforePoint:= currentPoint[i] лучшийстеп:= 0 для j от 0 до 3 do // пробуем каждое из 4 возможных мест шаг := StepSize[i] × кандидат[j] currentPoint[i] := beforePoint + шаг оценка:= EVAL(currentPoint) если результат > bestScore , то bestScore := оценка bestStep := шаг если bestStep равен 0 , то currentPoint[i] := beforePoint StepSize[i] := StepSize[i] / ускорение еще currentPoint[i] := beforePoint + bestStep StepSize[i] := bestStep // ускорение если (bestScore − beforeScore) <epsilon, то вернуть currentPoint
Контрастный генетический алгоритм ; случайная оптимизация .
Восхождение на холм в Wikibooks
