восхождение на холм

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

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

Восхождение на холм находит оптимальные решения для выпуклых задач – для других задач оно находит только локальные оптимумы (решения, которые не могут быть улучшены никакими соседними конфигурациями), которые не обязательно являются лучшим возможным решением ( глобальным оптимумом ) из всех возможных решений ( пространство поиска ). Примеры алгоритмов, решающих выпуклые задачи путем восхождения на холм, включают симплексный алгоритм линейного программирования и двоичного поиска . ^{[ 1 ]}^: 253 Чтобы попытаться избежать застревания в локальных оптимумах, можно использовать перезапуски (т. е. повторный локальный поиск) или более сложные схемы, основанные на итерациях (например, итерированный локальный поиск ), или на памяти (например, оптимизация реактивного поиска и поиск с запретами ), или на стохастические модификации без памяти (например, имитация отжига ).

Относительная простота алгоритма делает его популярным выбором среди алгоритмов оптимизации. Он широко используется в искусственном интеллекте для достижения целевого состояния из начального узла. В связанных алгоритмах используются разные варианты выбора следующих и начальных узлов. Хотя более продвинутые алгоритмы, такие как имитация отжига или табу-поиск, могут дать лучшие результаты, в некоторых ситуациях восхождение на холм работает так же хорошо. Восхождение на холм часто может дать лучший результат, чем другие алгоритмы, когда количество времени, доступное для выполнения поиска, ограничено, например, в системах реального времени, при условии, что небольшое количество приращений обычно сходится к хорошему решению (оптимальное решение). или близкое приближение). С другой стороны, пузырьковую сортировку можно рассматривать как алгоритм восхождения на холм (каждая замена соседних элементов уменьшает количество пар неупорядоченных элементов), однако этот подход далеко не эффективен даже для скромного N, поскольку количество требуемых обменов растет квадратично.

Восхождение на холм — это алгоритм, работающий в любое время : он может вернуть допустимое решение, даже если он был прерван в любой момент до его завершения.

Математическое описание

Восхождение на холм пытается максимизировать (или минимизировать) целевую функцию . $f(\mathbf {x} )$ , где $\mathbf {x}$ представляет собой вектор непрерывных и/или дискретных значений. На каждой итерации восхождение на холм будет корректировать один элемент в $\mathbf {x}$ и определить, улучшит ли это изменение ценность $f(\mathbf {x} )$ . (Обратите внимание, что это отличается от методов градиентного спуска , которые корректируют все значения в $\mathbf {x}$ на каждой итерации в соответствии с уклоном холма.) При подъеме на холм любое изменение, улучшающее $f(\mathbf {x} )$ принимается, и процесс продолжается до тех пор, пока не будет найдено никаких изменений, которые могли бы улучшить ценность $f(\mathbf {x} )$ . Затем $\mathbf {x}$ называется «локально оптимальным».

В дискретных векторных пространствах каждое возможное значение $\mathbf {x}$ можно представить вершину графа . как Восхождение на холм будет следовать графику от вершины к вершине, всегда локально увеличивая (или уменьшая) значение $f(\mathbf {x} )$ , до достижения локального максимума (или локального минимума ) $x_{m}$ достигается.

Варианты

При простом восхождении на холм выбирается первый ближайший узел, тогда как при подъеме на холм с самым крутым подъемом сравниваются все преемники и выбирается наиболее близкий к решению. Обе формы терпят неудачу, если нет более близкого узла, что может произойти, если в пространстве поиска есть локальные максимумы, которые не являются решениями. Подъем на гору с самым крутым подъемом аналогичен поиску по принципу «сначала лучший» , который пробует все возможные продолжения текущего пути, а не только одно. ^{[ 2 ]}

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

Координатный спуск выполняет поиск линии по одному координатному направлению в текущей точке на каждой итерации. Некоторые версии спуска по координатам случайным образом выбирают другое направление координат на каждой итерации.

Восхождение на гору со случайным перезапуском — это метаалгоритм, построенный на основе алгоритма восхождения на гору. Это также известно как восхождение на холм с дробовиком . Он итеративно выполняет восхождение на холм, каждый раз со случайным начальным условием. $x_{0}$ . Лучшее $x_{m}$ сохраняется: если новый забег по холму дает лучший результат $x_{m}$ чем сохраненное состояние, оно заменяет сохраненное состояние.

Подъем на гору с произвольным перезапуском во многих случаях оказывается удивительно эффективным алгоритмом. Оказывается, зачастую лучше потратить время ЦП на изучение пространства, чем на тщательную оптимизацию исходных условий. ^{[ оригинальное исследование? ]}

Проблемы

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

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

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

Хребты и переулки

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

Напротив, методы градиентного спуска могут двигаться в любом направлении, в котором гребень или переулок могут подниматься или опускаться. Следовательно, градиентный спуск или метод сопряженных градиентов обычно предпочтительнее подъема в гору, когда целевая функция дифференцируема. Однако у альпинистов есть то преимущество, что они не требуют, чтобы целевая функция была дифференцируемой, поэтому альпинисты могут быть предпочтительнее, когда целевая функция сложна.

Плато

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

Pseudocode
algorithm Discrete Space Hill Climbing is
    currentNode := startNode
    loop do
        L := NEIGHBORS(currentNode)
        nextEval := −INF
        nextNode := NULL
        for all x in L do
            if EVAL(x) > nextEval then
                nextNode := x
                nextEval := EVAL(x)
        if nextEval ≤ EVAL(currentNode) then
            // Return current node since no better neighbors exist
            return currentNode
        currentNode := nextNode

algorithm Continuous Space Hill Climbing is
    currentPoint := initialPoint    // the zero-magnitude vector is common
    stepSize := initialStepSizes    // a vector of all 1's is common
    acceleration := someAcceleration // a value such as 1.2 is common
    candidate[0] := −acceleration
    candidate[1] := −1 / acceleration
    candidate[2] := 1 / acceleration
    candidate[3] := acceleration
    bestScore := EVAL(currentPoint)
    loop do
        beforeScore := bestScore
        for each element i in currentPoint do
            beforePoint := currentPoint[i]
            bestStep := 0
            for j from 0 to 3 do      // try each of 4 candidate locations
                step := stepSize[i] × candidate[j]
                currentPoint[i] := beforePoint + step
                score := EVAL(currentPoint)
                if score > bestScore then
                    bestScore := score
                    bestStep := step
            if bestStep is 0 then
                currentPoint[i] := beforePoint
                stepSize[i] := stepSize[i] / acceleration
            else
                currentPoint[i] := beforePoint + bestStep
                stepSize[i] := bestStep // acceleration
        if (bestScore − beforeScore) < epsilon then
            return currentPoint

Контрастный генетический алгоритм ; случайная оптимизация .

См. также

Ссылки

Рассел, Стюарт Дж .; Норвиг, Питер (2003), Искусственный интеллект: современный подход (2-е изд.), Аппер-Сэдд-Ривер, Нью-Джерси: Прентис-Холл, стр. 111–114, ISBN 0-13-790395-2

^ Скиена, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science+Business Media . ISBN 978-1-849-96720-4 .
^ Эта статья основана на материалах, взятых из Hill+climbing в Бесплатном онлайн-словаре вычислительной техники до 1 ноября 2008 г. и включенных в соответствии с условиями «повторного лицензирования» GFDL версии 1.3 или более поздней.

Дальнейшее чтение

Ласри, Джордж (2018). Методология криптоанализа классических шифров с метаэвристикой поиска (PDF) . Издательство Кассельского университета . ISBN 978-3-7376-0459-8 .

Внешние ссылки

Восхождение на холм в Wikibooks

[1] Скиена, Стивен (2010). Руководство по разработке алгоритмов (2-е изд.). Springer Science+Business Media . ISBN 978-1-849-96720-4 .

[2] Эта статья основана на материалах, взятых из Hill+climbing в Бесплатном онлайн-словаре вычислительной техники до 1 ноября 2008 г. и включенных в соответствии с условиями «повторного лицензирования» GFDL версии 1.3 или более поздней.

[ 1 ]

[ 2 ]