Поиск восхождением к вершине

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

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

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

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

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

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

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

• Градиентный спуск
• Жадный алгоритм
• Невидимая рука
• Сдвиг среднего

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