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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Hill climbing»  -  новости  · газеты  · книги  · ученый  · JSTOR ( апрель 2017 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

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

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

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

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

Математическое описание [ править ]

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

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

Варианты [ править ]

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

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

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

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

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

Проблемы [ править ]

Локальные максимумы [ править ]

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

Хребты и переулки [ править ]

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

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

Плато [ править ]

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

Алгоритм псевдокода Discrete Space Hill Climbing - это currentNode: = startNode петля делать L: = СОСЕДИ (currentNode) nextEval: = -INF nextNode: = NULL для всех x в L делать,  если EVAL (x)> nextEval, то nextNode: = x nextEval: = EVAL (x) если nextEval ≤ EVAL (currentNode), то // Возвращаем текущий узел, так как лучших соседей не существует вернуть currentNode currentNode: = nextNode

алгоритм Continuous Space Hill Climbing - это currentPoint: = initialPoint // вектор нулевой величины является общим stepSize: = initialStepSizes // вектор всех единиц является общим ускорение: = someAcceleration // обычно используется значение, например 1,2 кандидат [0]: = −acceleration кандидат [1]: = −1 / ускорение кандидат [2]: = 1 / ускорение кандидат [3]: = ускорение bestScore: = EVAL (currentPoint) петля делать beforeScore: = bestScore для каждого элемента i в currentPoint выполните beforePoint: = currentPoint [i] bestStep: = 0 for j от 0 до 3 do // пробуем каждое из 4 возможных местоположений step: = 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

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

См. Также [ править ]

• Градиентный спуск
• Жадный алгоритм
• Tâtonnement
• Средний сдвиг
• Алгоритм поиска A *

Ссылки [ править ]

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

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

Внешние ссылки [ править ]

• Восхождение на холмы в Викиучебнике