Сепарација и евалуација

Separacija i evaluacija (engl. Branch and bound, ББ, Б&Б) је општи алгоритам за проналажење оптималног решења за различите задатке оптимизације, поготово у дискретној и комбинаторичкој оптимизацији. Бранцх анд боунд алгоритам се састоји из систематичног набрајања свих могућих решења, где се велики подскупови непотребних кандидата масовно одбацују, коришћењем процењене горње и доње границе колицине која је оптимизована.

Ова методу је први представио А.Х. Ланд и А.Г. Доиг 1960. за дискретно програмирање.

Генерални опис

Да би се олакшао конкретан опис, претпостављамо да је циљ да се нађе минимална вредност за функцију $f(x)$ где је $x$ из скупа $S$ из прихватљивог или могућег решења. Имајући на уму да може да се нађе максимална вредост ф(x) тако што се нађе минимум из $g(x)=-f(x)$.

Алгоритам сепарације и евалуације захтева два процеса. Први је процес дељења који, имајући скуп кандидата $S$, враћа два или више слична скупа $S_{1},S_{2}...$ чија унија чини скуп $S$. Имајући на уму да минимум фукције $f(x)$ из скупа $S$ је $\min\{v_{1},v_{2},\ldots \}$, где је свако $V_{i}$ минимум функције $f(x)$ из скупа $S_{i}$. Овај корак се зове гранање (енгл. branching), пошсто његова рекурзивна примена дефинисте структуру стабло цији су чворови подскупови $S$.

Други процес је процедура која израцунава горњу и доњу границу за минималну вредност функције $f(x)$ из датог подскупа скупа $S$. Овај корак се зове спајање' (енгл. bounding).

Главна идеја за ББ алгоритам је: ако је доња граница неког цвора $A$ веца од горње границе неког чвора $B$, онда $A$ може безбедно да се избаци из претраге. Овај корак се зове орезивање (енгл. pruning), и обично се имплементира тако сто се одржава глобална варијабла $m$ који чува минимум горње границе која је пронађена међу тренутно провереним. Било кој чвор чија је доња граница већа од од $m$ може да се избаци.

Рекурзија се зауставља када се тренутни кандидат из скупа $S$ смањи на један елемент или када се горња граница из скупа $S$ поклопи са доњом границом. Било који елемент из скупа $S$ ће бити минимум те функције из скупа $S$.

Када је $x$ вектор из $R^{n}$, алгоритам сепарације и евалуације се спаја са интервалном аналзиом и уговорачем тецхника да би могло да се обезбеди ограђивање глобалног минимума.

Примене

Овај приступ се користи за велики број НП-тешких проблема:

• Целобројно програмирање
• Нелинеарно програмирање
• Проблем путујућег продавца (ТСП)
• Проблем квадратне доделе
• Максимално задовољавајући проблем (МАX-САТ)
• Претрега за најближим суседом (ННС)
• Проблем сечења залихе
• Анализа лажне буке (ФНА)
• Рачунарска филогенија
• Инверзија скупова
• Процене параметара

Алгоритам сепарације и евалуације може такође да буде база за разне хеуристике. Нпр, један ће можда хтети да престане да се грана када се распон између горње и доње границе мањи од одређеног прага. Ово се користи када је решење "довољно добро за практичне употребе" и може знатно да се смањи број потребних рачунања. Овај тип решења је посебно прихватљив када је цена искоришћене функције велика или када је резлтат статичких процена и онда не зна се прецизно, али се само зна да се налази у распону вредности са специфичним могућностима. Пример његовре приемене је у биологији када се врси кладистична анализа да би се прорацунао еволуциони однос између организама, где су сетови података обично непрактично велики без хеуристике.

Из овог ралога, технике сепарације и евалуације се често користе у алгоритму за претрагу стабла игре, најзначаније је у коришћењу алпха-бета орезивања.

Литература

• Хансен, Е.Р. (1992). Глобал Оптимизатион усинг Интервал Аналyсис. Неw Yорк: Марцел Деккер. 
• Мооре, Р. Е. (1966). Интервал Аналyсис. Енглеwоод Цлифф, Неw Јерсеy: Прентице-Халл. ISBN 0-13-476853-1. 
• Јаулин, L.; Киеффер, M.; Дидрит, О.; Wалтер, Е. (2001). Апплиед Интервал Аналyсис. Берлин: Спрингер. ISBN 1-85233-219-0.