Подъем на холм

редактировать

Алгоритм оптимизации

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

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

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

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

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

Содержание

1 Математическое описание
2 Варианты
3 Проблемы
- 3.1 Локальные максимумы
- 3.2 Гряды и переулки
- 3.3 Плато
4 Псевдокод
5 См. Также
6 Ссылки
7 Внешние ссылки

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

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

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

Поверхность только с одним максимумом. Альпинисты хорошо подходят для оптимизации на таких поверхностях и сходятся к глобальному максимуму.

Варианты

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

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

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

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

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

Проблемы

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

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

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

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

Гряды и переулки

Гребень

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

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

Плато

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

Псевдокод

алгоритм Дискретное восхождение на космический холм равно currentNode: = startNode loop do L: = NEIGHBORS (currentNode) nextEval: = −INF nextNode : = NULL для все x в L doifEVAL (x)>nextEval затем nextNode: = x nextEval: = EVAL (x) если nextEval ≤ EVAL (currentNode) then // Возвращаем текущий узел, поскольку не существует лучших соседей return currentNode currentNode: = nextNode

алгоритм Непрерывное восхождение на холм в космосе is currentPoint: = initialPoint // вектор нулевой величины является обычным stepSize: = initialStepSizes // вектор всех единиц является общим ускорением: = someAcceleration // такое значение, как 1,2, является общим кандидатом [0]: = −acceleration scheme [ 1]: = -1 / кандидат ускорения [2]: = 0 кандидат [3]. = 1 / кандидат ускорения [4]: = ускорение цикл выполнить перед: = EVAL (currentPoint) для каждый элемент i в currentPoint do best: = −1 bestScore: = −INF для j от 0 до 4 do // пробуем каждое из 5 возможных местоположений currentPoint [i]: = currentPoint [i] + stepSize [i] × кандидата [j] temp: = EVAL (currentPoint) currentPoint [i]: = currentPoint [ i] - stepSize [i] × кандидат [j] если temp>bestScore, то bestScore: = temp best: = j если кандидат [лучший] равен 0 затем stepSize [i]: = stepSize [i] / ускорение else currentPoint [i]: = currentPoint [i] + stepSize [i] × кандидат [лучший] stepSize [i] : = stepSize [i] × кандидат [лучший] // ускорить if (EVAL (currentPoint) - before) < epsilon, затемreturn currentPoint

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

См. Также

Ссылки

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

Эта статья основана на материалах, взятых из Free On-line Dictionary of Computing до 1 ноября 2008 г. и включенных в раздел «перелицензирование "условия GFDL версии 1.3 или новее.

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

Альпинизм в Викиучебниках