Separacija i evaluacija

Izvor: Wikipedia

Separacija i evaluacija (eng. 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[uredi - уреди]

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 (eng. 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' (eng. 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 (eng. 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[2] i ugovoračem technika da bi moglo da se obezbedi ograđivanje globalnog minimuma.[3][4]

Primene[uredi - уреди]

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[uredi - уреди]

  1. A. H. Land and A. G. Doig. "An automatic method of solving discrete programming problems", pp. 497–520.
  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[uredi - уреди]

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