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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Алгоритм пошуку зі сходженням до вершини (англ. Hill climbing) являє собою звичайний цикл, в якому постійно відбувається переміщення в напрямку зростання деякого значення, тобто підйом. Робота цього алгоритму закінчується після досягнення «піку», в якому жоден з сусідніх станів не має більш високого значення. В даному алгоритмі не передбачено супровід дерева пошуку, тому в структурі даних поточного вузла необхідно реєструвати тільки стан і відповідне йому значення цільової функції.

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

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

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

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

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

Математичний опис[ред.ред. код]

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

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

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

Варіанти[ред.ред. код]

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

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

Проблеми[ред.ред. код]

Локальні максимуми[ред.ред. код]

Поверхня з двома локальними максимумами.

Локальний максимум являє собою пік, вищий в порівнянні з кожним з його сусідніх станів, але нижчий, ніж глобальний максимум. Алгоритми зі сходженням до вершини, які досягають околиць локального максимуму, забезпечують просування вгору, до цього піку, але після цього заходять в глухий кут, з якого більше нікуди рухатися. Така проблема схематично показана на малюнку. Більш конкретний приклад полягає в тому, що стан, показаний на малюнку, фактично являє собою локальний максимум (тобто локальний мінімум для оцінки вартості h).

Хребти[ред.ред. код]

Приклад хребта зображений на малюнку. При наявності хребтів виникають послідовності локальних максимумів, завдання проходження яких для жадібних алгоритмів є дуже важкою.

Хребет.

Плато[ред.ред. код]

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

Псевдокод[ред.ред. код]

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.