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   gde je   iz skupa   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  .

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

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

Glavna ideja za BB algoritam je: ako je donja granica nekog cvora   veca od gornje granice nekog čvora  , onda   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   koji čuva minimum gornje granice koja je pronađena među trenutno proverenim. Bilo koj čvor čija je donja granica veća od od   može da se izbaci.

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

Kada je   vektor iz  , 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.