lecture8

Евристичні методи пошуку розв’язку

Hill climbing methods

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

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

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

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

DB послаблює проблему за допомогою поняття квазілокального мінімума

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

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

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

Алгоритм

Початкова програма

breed [nodes node]

globals[colors]

links-own[weight]

to setup
  clear-all
  reset-ticks
  ask patches [set pcolor white]
  set colors [red blue green]

  create-nodes num-nodes [
    set shape "circle"
    setxy random-pxcor random-pycor
    ;set color black ;
    set color one-of colors
  ]

  repeat num-edges [
    ask one-of nodes [
      create-link-with one-of other nodes
    ]
  ]
  ask links [
  set weight 1
  set label-color black
  set label weight
  ]
end

to go
  tick
  ask nodes [
  ;change-color
  ]
end

to layout

  layout-spring nodes links 0.2 5 2

end

Імплементація алгоритму

to-report get-value [alist key]
  foreach alist [
    [i] -> if(first i = key) [report item 1 i
    ]
  ]
  report "ERROR. No such key"
end

to-report get-all-values [alist]
  report map [[i] -> item 1 i] alist
end

to-report get-all-keys [alist]
  report map [[i] -> first i] alist

end

to-report get-all-keys-for-value [alist value]

  report get-all-keys (filter [[i] -> (item 1 i) = value] alist )
end

to-report conflict-links [the-color]
  report my-links with [(end1 != myself and [color] of end1 = the-color) or
  (end2 != myself and [color] of end2 = the-color)]
end

to-report cost-of-color [the-color]
  report sum ([weight] of conflict-links the-color)
end


;; node methods
to change-color
  let gain-color best-gain-color
  let my-gain (first gain-color)
  let max-neighbors-gain max get-all-keys ([best-gain-color] of link-neighbors)
  if (my-gain >= max-neighbors-gain) [
    ask (conflict-links color)[
    set weight weight + 1
    set label weight
    ]
  set color ( item 1 gain-color)
  ]
end

to-report best-gain-color
  let color-costs map [[i] -> (list i cost-of-color i)] colors
  let min-cost min get-all-values color-costs
  let best-colors get-all-keys-for-value color-costs min-cost
  let current-cost (get-value color-costs color)
  let gain (current-cost - min-cost)
  report (list gain (one-of best-colors))
end

Резюме

Мінуси

• DB не є повним. Тобто може не знайти розв’язок навіть коли він існує.
• DB не може визначити, що розв’язку не існує.
• Алгоритм нерівномірно навантажує вузли.

Плюси

• в середньому працює краще за ABT (і інші)