Алгоритм сходження на вершину

Алгоритм сходження на вершину максимізує (або мінімізує) цільову функцію ${\displaystyle f(\mathbf {x} )}$, де ${\displaystyle \mathbf {x} }$ це вектор безперервного і / або дискретного значення. На кожній ітерації алгоритм сходження на вершину буде регулювати один елемент в ${\displaystyle \mathbf {x} }$ і визначає, чи підвищує значення ${\displaystyle f(\mathbf {x} )}$. (Зауважимо, що це відрізняється від методів градієнтного спуску, які регулюють всі значення в ${\displaystyle f(\mathbf {x} )}$ на кожній ітерації відповідно до градієнту пагорба.) Сходження на вершину приймає будь-яку зміну, яка поліпшує ${\displaystyle f(\mathbf {x} )}$ і процес триває допоки не буде знайдено значення в якому неможливо поліплишити ${\displaystyle f(\mathbf {x} ).}$ Тоді ${\displaystyle \mathbf {x} }$ оголошують локальним оптимальним розв'яком.

У дискретних векторних просторах, кожне можливе значення для ${\displaystyle \mathbf {x} }$ можна собі уявити як вершину в графі.

Опукла поверхня.

У спрощеному алгоритмі сходження на вершину, обирають перший ближчий до розв'язку вузол, тоді як у найстрімкішому сходжені всі наступники порівнюються з обраним і тоді вибирається найближчий до розв'язку. Обидва варіанти можуть зазнати невдачі, якщо немає ближчого вузла, це може статись, якщо в області пошуку є локальні максимуми не розв'язки.

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

Discrete Space Hill Climbing Algorithm
   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;

Continuous Space Hill Climbing Algorithm
   currentPoint = initialPoint;    
   stepSize = initialStepSizes;   
   acceleration = someAcceleration; 
   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       
            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 not 0
            currentPoint[i] = currentPoint[i] + stepSize[i] * candidate[best];
            stepSize[i] = stepSize[i] * candidate[best]; 
      if (EVAL(currentPoint) - before) < epsilon 
         return currentPoint;

• Список алгоритмів

• Hill Climbing visualization Візуалізація алгоритму сходження на вершину для задачі «N-Queens puzzle», зроблена Yuval Baror.