Separacija i evaluacija

Separacija i evaluacija (engl. Branch and bound, BB, B&B) je opšti algoritam za pronalaženje optimalnog rešenja za različite zadatke optimizacije, pogotovo u diskretnoj i kombinatoričkoj optimizaciji. Branch and bound algoritam se sastoji iz sistematičnog nabrajanja svih mogućih rešenja, gde se veliki podskupovi nepotrebnih kandidata masovno odbacuju, korišćenjem procenjene gornje i donje granice kolicine koja je optimizovana.

Ova metodu je prvi predstavio A.H. Land i A.G. Doig 1960. za diskretno programiranje.

Generalni opis

Da bi se olakšao konkretan opis, pretpostavljamo da je cilj da se nađe minimalna vrednost za funkciju $f(x)$ gde je $x$ iz skupa $S$ iz prihvatljivog ili mogućeg rešenja. Imajući na umu da može da se nađe maksimalna vredost f(x) tako što se nađe minimum iz $g(x)=-f(x)$.

Algoritam separacije i evaluacije zahteva dva procesa. Prvi je proces deljenja koji, imajući skup kandidata $S$, vraća dva ili više slična skupa $S_{1},S_{2}...$ čija unija čini skup $S$. Imajući na umu da minimum fukcije $f(x)$ iz skupa $S$ je $\min\{v_{1},v_{2},\ldots \}$, gde je svako $V_{i}$ minimum funkcije $f(x)$ iz skupa $S_{i}$. Ovaj korak se zove grananje (engl. branching), pošsto njegova rekurzivna primena definiste strukturu stablo ciji su čvorovi podskupovi $S$.

Drugi proces je procedura koja izracunava gornju i donju granicu za minimalnu vrednost funkcije $f(x)$ iz datog podskupa skupa $S$. Ovaj korak se zove spajanje' (engl. bounding).

Glavna ideja za BB algoritam je: ako je donja granica nekog cvora $A$ veca od gornje granice nekog čvora $B$, onda $A$ može bezbedno da se izbaci iz pretrage. Ovaj korak se zove orezivanje (engl. pruning), i obično se implementira tako sto se održava globalna varijabla $m$ koji čuva minimum gornje granice koja je pronađena među trenutno proverenim. Bilo koj čvor čija je donja granica veća od od $m$ može da se izbaci.

Rekurzija se zaustavlja kada se trenutni kandidat iz skupa $S$ smanji na jedan element ili kada se gornja granica iz skupa $S$ poklopi sa donjom granicom. Bilo koji element iz skupa $S$ će biti minimum te funkcije iz skupa $S$.

Kada je $x$ vektor iz $R^{n}$, algoritam separacije i evaluacije se spaja sa intervalnom analziom i ugovoračem technika da bi moglo da se obezbedi ograđivanje globalnog minimuma.

Primene

Ovaj pristup se koristi za veliki broj NP-teških problema:

• Celobrojno programiranje
• Nelinearno programiranje
• Problem putujućeg prodavca (TSP)
• Problem kvadratne dodele
• Maksimalno zadovoljavajući problem (MAX-SAT)
• Pretrega za najbližim susedom (NNS)
• Problem sečenja zalihe
• Analiza lažne buke (FNA)
• Računarska filogenija
• Inverzija skupova
• Procene parametara

Algoritam separacije i evaluacije može takođe da bude baza za razne heuristike. Npr, jedan će možda hteti da prestane da se grana kada se raspon između gornje i donje granice manji od određenog praga. Ovo se koristi kada je rešenje "dovoljno dobro za praktične upotrebe" i može znatno da se smanji broj potrebnih računanja. Ovaj tip rešenja je posebno prihvatljiv kada je cena iskorišćene funkcije velika ili kada je rezltat statičkih procena i onda ne zna se precizno, ali se samo zna da se nalazi u rasponu vrednosti sa specifičnim mogućnostima. Primer njegovre priemene je u biologiji kada se vrsi kladistična analiza da bi se proracunao evolucioni odnos između organizama, gde su setovi podataka obično nepraktično veliki bez heuristike.

Iz ovog raloga, tehnike separacije i evaluacije se često koriste u algoritmu za pretragu stabla igre, najznačanije je u korišćenju alpha-beta orezivanja.

Literatura

• Hansen, E.R. (1992). Global Optimization using Interval Analysis. New York: Marcel Dekker. 
• Moore, R. E. (1966). Interval Analysis. Englewood Cliff, New Jersey: Prentice-Hall. ISBN 0-13-476853-1. 
• Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E. (2001). Applied Interval Analysis. Berlin: Springer. ISBN 1-85233-219-0.