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.[1]

Generalni opis

Da bi se olakšao konkretan opis, pretpostavljamo da je cilj da se nađe minimalna vrednost za funkciju f ( x ) {\displaystyle f(x)} gde je x {\displaystyle x} iz skupa S {\displaystyle 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 ) {\displaystyle g(x)=-f(x)} .

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

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

Glavna ideja za BB algoritam je: ako je donja granica nekog cvora A {\displaystyle A} veca od gornje granice nekog čvora B {\displaystyle B} , onda A {\displaystyle 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 {\displaystyle 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 {\displaystyle m} može da se izbaci.

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

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

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.

Reference

  1. ^ A. H. Land and A. G. Doig (1960). „An automatic method of solving discrete programming problems”. Econometrica. 28 (3). стр. 497—520. doi:10.2307/1910129. 
  2. ^ Moore, R. E. (1966). Interval Analysis. Englewood Cliff, New Jersey: Prentice-Hall. ISBN 0-13-476853-1. 
  3. ^ Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E. (2001). Applied Interval Analysis. Berlin: Springer. ISBN 1-85233-219-0. 
  4. ^ Hansen, E.R. (1992). Global Optimization using Interval Analysis. New York: Marcel Dekker. 

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.