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 nepotebnih 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.