ru %D0%9F%D0%BE%D0%B8%D1%81%D0%BA %D0%B2%D0%BE%D1%81%D1%85%D0%BE%D0%B6%D0%B4%D0%B5%D0%BD%D0%B8%D0%B5%D0%BC %D0%BA %D0%B2%D0%B5%D1%80%D1%88%D0%B8%D0%BD%D0%B5

Поиск восхождением к вершине (далее в статье просто восхождение) — это техника математической оптимизации, принадлежащая семейству алгоритмов локального поиска. Алгоритм является методом итерации, который начинается с произвольного решения задачи, а затем пытается найти лучшее решение путём пошагового^[англ.] изменения одного из элементов решения. Если решение даёт лучшее решение, делается приращение для получения нового решения и оно делается, пока не достигнем момента, в котором улучшение найти не удаётся.

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

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

Относительная простота алгоритма делает алгоритм популярным среди оптимизационных алгоритмов. Он широко используется в теории искусственного интеллекта для достижения целевого состояния из начальной точки. Метод выбора следующей точки и начальной точки может меняться, давая ряд связанных алгоритмов. Хотя более продвинутые алгоритмы, такие как алгоритм имитации отжига или поиск с запретами могут давать результаты лучше, в некоторых ситуациях восхождение работает с тем же успехом. Восхождение часто даёт лучший результат по сравнению с другими алгоритмами, когда ограничено время на осуществление поиска, что важно в системах реального времени, при условии, что малое число шагов сходится к хорошему решению (к оптимальному, либо близкому к нему). Другой экстремальный случай, сортировка пузырьком, может рассматриваться как алгоритм восхождения (каждая перестановка соседних элементов уменьшает число неупорядоченных пар), и такой подход далёк от оптимального даже при малых 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}$ .

Варианты

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

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

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

Случайное возобновление восхождения — это метаалгоритм, построенный на основе алгоритма восхождения. Он известен также как Shotgun Hill climbing (Пулемётное восхождение). Алгоритм итеративно осуществляет восхождение, каждый раз выбирая случайное начальное $x_{0}$ . Лучшее значение $x_{m}$ сохраняется и, если новая попытка восхождения даёт лучший $x_{m}$ по сравнению с запомненным, он заменяет запомненное состояние.

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

Задачи

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

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

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

Хребты и ущелья

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

Методы же градиентного спуска могут двигаться в направлении, в котором поднимается хребет или спускается ущелье. Следовательно, градиентный спуск или метод сопряжённых градиентов будет более предпочтительным, если целевая функция дифференцируема. Восхождение, однако, имеет преимущество отсутствия требования к дифференцируемости, так что восхождение может оказаться более предпочтительным, когда целевая функция сложная.

Плато

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

Псевдокод

Алгоритм восхождения в дискретном пространстве
   currentNode = startNode;
   loop do
      L = NEIGHBORS(currentNode);
      nextEval = -INF;
      nextNode = NULL;
      for all x in L 
         if (EVAL(x) > nextEval)
              nextNode = x;
              nextEval = EVAL(x);
      if nextEval <= EVAL(currentNode)
         //Возвращаем текущий узел, поскольку лучшего узла нет
         return currentNode;
      currentNode = nextNode;

Алгоритм восхождения в непрерывном пространстве
   currentPoint = initialPoint;    // обычно используется вектор нулевой длины
   stepSize = initialStepSizes;    // обычно используется вектор из единиц
   acceleration = someAcceleration; // обычно используется значение 1.2
   candidate[0] = -acceleration;
   candidate[1] = -1 / acceleration;
   candidate[2] = 0;
   candidate[3] = 1 / acceleration;
   candidate[4] = acceleration;
   loop do
      before = EVAL(currentPoint);
      for each element i in currentPoint do
         best = -1;
         bestScore = -INF;
         for j from 0 to 4         // пытаемся перебрать каждый из 5 кандидатов
            currentPoint[i] = currentPoint[i] + stepSize[i] * candidate[j];
            temp = EVAL(currentPoint);
            currentPoint[i] = currentPoint[i] - stepSize[i] * candidate[j];
            if(temp > bestScore)
                 bestScore = temp;
                 best = j;
         if candidate[best] is 0
            stepSize[i] = stepSize[i] / acceleration;
         else
            currentPoint[i] = currentPoint[i] + stepSize[i] * candidate[best];
            stepSize[i] = stepSize[i] * candidate[best]; // accelerate
      if (EVAL(currentPoint) - before) < epsilon 
         return currentPoint;

См. также

Примечания

↑ Skiena, 2010, с. 253.

Литература

Stuart J. Russell, Peter Norvig. Artifical Intelligence: A Modern Approach. — Upper Saddle River, New Jercey: Prentice Hall, 2003. — С. 111–114.
Steven Skiena. The Algorithm Design Manual. — 2nd. — Springer Science+Business Media, 2010. — ISBN 1-849-96720-2.

Статья базируется на материале, взятом из статьи Free On-line Dictionary of Computing (FOLDOC), имеющей лицензию GFDL (версия 1.3).

Ссылки

[_bf6bdd8deacde25d-1] Skiena, 2010, с. 253.

[1]