Алгоритм подъёма на холм: оптимизация и применение.

Введение

Алгоритм оптимизации – математический алгоритм.

В численном анализе, метод восхождения на холм (hill climbing) – это математическая техника оптимизации, относящаяся к семейству локального поиска. Это итеративный алгоритм, который начинается с произвольного решения задачи, а затем пытается найти лучшее решение, внося в него инкрементные изменения. Если изменение приводит к улучшению решения, то к новому решению применяется еще одно инкрементное изменение, и так далее, пока дальнейшие улучшения не станут возможными. Например, метод восхождения на холм можно применить к задаче коммивояжера. Легко найти начальное решение, которое посещает все города, но оно, вероятно, будет значительно хуже оптимального. Алгоритм начинается с такого решения и вносит в него небольшие улучшения, например, меняя порядок посещения двух городов. В конечном итоге, скорее всего, будет найден гораздо более короткий маршрут. Метод восхождения на холм находит оптимальные решения для выпуклых задач – для других задач он находит только локальные оптимумы (решения, которые нельзя улучшить, изменив любую соседнюю конфигурацию), которые не обязательно являются наилучшим возможным решением (глобальным оптимумом) из всех возможных решений (пространства поиска). Примеры алгоритмов, решающих выпуклые задачи методом восхождения на холм, включают симплекс-метод для линейного программирования и бинарный поиск. Чтобы попытаться избежать застревания в локальных оптимумах, можно использовать перезапуски (т.е. повторные локальные поиски) или более сложные схемы, основанные на итерациях (например, итерационный локальный поиск), на памяти (например, реактивный поиск оптимизации и поиск с запретами) или на менее ресурсоемких стохастических модификациях (например, имитация отжига). Относительная простота алгоритма делает его популярным первым выбором среди алгоритмов оптимизации. Он широко используется в искусственном интеллекте для достижения целевого состояния из начального узла. В связанных алгоритмах используются различные варианты выбора следующих и начальных узлов. Хотя более продвинутые алгоритмы, такие как имитация отжига или поиск с запретами, могут давать лучшие результаты, в некоторых ситуациях метод восхождения на холм работает не хуже. Метод восхождения на холм часто может дать лучший результат, чем другие алгоритмы, когда время, доступное для поиска, ограничено, например, в системах реального времени, при условии, что небольшое количество инкрементов обычно сходится к хорошему решению (оптимальному решению или его близкой аппроксимации). С другой стороны, сортировку пузырьком можно рассматривать как алгоритм восхождения на холм (каждая смена соседних элементов уменьшает количество неупорядоченных пар элементов), однако этот подход далек от эффективного даже для умеренных значений N, поскольку количество необходимых обменов растет квадратично. Метод восхождения на холм – это алгоритм любого времени: он может вернуть допустимое решение, даже если его прервут в любой момент до завершения.

In numerical analysis, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by making an incremental change to the solution. If the change produces a better solution, another incremental change is made to the new solution, and so on until no further improvements can be found. For example, hill climbing can be applied to the travelling salesman problem. It is easy to find an initial solution that visits all the cities but will likely be very poor compared to the optimal solution. The algorithm starts with such a solution and makes small improvements to it, such as switching the order in which two cities are visited. Eventually, a much shorter route is likely to be obtained. Hill climbing finds optimal solutions for convex problems – for other problems it will find only local optima (solutions that cannot be improved upon by any neighboring configurations), which are not necessarily the best possible solution (the global optimum) out of all possible solutions (the search space). Examples of algorithms that solve convex problems by hill climbing include the simplex algorithm for linear programming and binary search. To attempt to avoid getting stuck in local optima, one could use restarts (i. e. repeated local search), or more complex schemes based on iterations (like iterated local search), or on memory (like reactive search optimization and tabu search), or on memory less stochastic modifications (like simulated annealing). The relative simplicity of the algorithm makes it a popular first choice amongst optimizing algorithms. It is used widely in artificial intelligence, for reaching a goal state from a starting node. Different choices for next nodes and starting nodes are used in related algorithms. Although more advanced algorithms such as simulated annealing or tabu search may give better results, in some situations hill climbing works just as well. Hill climbing can often produce a better result than other algorithms when the amount of time available to perform a search is limited, such as with real time systems, so long as a small number of increments typically converges on a good solution (the optimal solution or a close approximation). At the other extreme, bubble sort can be viewed as a hill climbing algorithm (every adjacent element exchange decreases the number of disordered element pairs), yet this approach is far from efficient for even modest N, as the number of exchanges required grows quadratically. Hill climbing is an anytime algorithm: it can return a valid solution even if it's interrupted at any time before it ends.

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

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

Варианты

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

Местные максимумы

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

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

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