Separacija i evaluacija — разлика између измена

Садржај обрисан Садржај додат

Инлајн

Верзија на датум 4. јун 2013. у 22:44

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 $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^[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

^ 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.
^ 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.
^ Hansen, E.R. (1992). Global Optimization using Interval Analysis. New York: Marcel Dekker.

[land_doig-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.

[1]

[2]

[3]

[4]

@@ Ред 1: / Ред 1: @@
+'''Separacija i evaluacija''' ({{jez-eng-lat|Branch and bound}}, BB, B&B) je opšti [[algoritam]] za pronalaženje optimalnog rešenja za različite zadatke [[Optimizacija (matematika)|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.
-{{Почетник|31|5|2013}}
-'''Branch and bound''' (BB ili 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.
+Ova metodu je prvi predstavio A.H. Land i A.G. Doig [[1960]] za [[diskretno programiranje]].<ref name=land_doig>{{cite article |author = A. H. Land and A. G. Doig | year = 1960 | title = An automatic method of solving discrete programming problems | journal = Econometrica | volume = 28 | issue = 3 | pages = 497–520 | doi=10.2307/1910129}}</ref>
 ==Generalni opis==
 Da bi se olakšao konkretan opis, pretpostavljamo da je cilj da se nađe minimalna vrednost za funkciju <math>f(x)</math> gde je <math>x</math> iz skupa <math>S</math> iz prihvatljivog ili mogućeg rešenja. Imajući na umu da može da se nađe maksimalna vredost <big>f(x)</big> tako što se nađe minimum iz <math>g(x)= -f(x)</math>.
-Branch-and-bound algoritam zahteva dva procesa. Prvi je proces deljenja koji, imajući skup kandidata <math>S</math>, vraća dva ili više slična skupa <math>S_1,S_2...</math> čija unija čini skup <math>S</math>. Imajući na umu da minimum fukcije <math>f(x)</math> iz skupa <math>S</math> je <math>\min\{v_1, v_2, \ldots\}</math>, gde je svako <math>V_i</math> minimum funkcije <math>f(x)</math> iz skupa <math>S_i</math>. Ovaj korak se zove '''branching(grananje)''', pošsto njegova rekurzivna primena definiste strukturu stablo ciji su čvorovi podskupovi <math>S</math>.
+Algoritam separacije i evaluacije zahteva dva procesa. Prvi je proces deljenja koji, imajući skup kandidata <math>S</math>, vraća dva ili više slična skupa <math>S_1,S_2...</math> čija unija čini skup <math>S</math>. Imajući na umu da minimum fukcije <math>f(x)</math> iz skupa <math>S</math> je <math>\min\{v_1, v_2, \ldots\}</math>, gde je svako <math>V_i</math> minimum funkcije <math>f(x)</math> iz skupa <math>S_i</math>. Ovaj korak se zove ''grananje'' ({{jez-eng-lat|branching}}), pošsto njegova rekurzivna primena definiste strukturu stablo ciji su čvorovi podskupovi <math>S</math>.
-Drugi proces je procedura koja izracunava gornju i donju granicu za minimalnu vrednost funkcije <math>f(x)</math> iz datog podskupa skupa <math>S</math>. Ovaj korak se zove '''bounding(spajanje)'''
+Drugi proces je procedura koja izracunava gornju i donju granicu za minimalnu vrednost funkcije <math>f(x)</math> iz datog podskupa skupa <math>S</math>. Ovaj korak se zove ''spajanje''' ({{jez-eng-lat|bounding}}).
-Glavna ideja za BB algoritam je: ako je donja granica nekog cvora <math>A</math>  veca od gornje granice nekog cvora <math>B</math>, onda <math>A</math> može bezbedno da se izbaci iz  pretrage. Ovaj korak se zove '''pruning(orezivanje)''', i obično se implementira tako sto se održava globalna varijabla <math>m</math> koji čuva minimum gornje granice koja je pronađena među trenutno proverenim. Bilo koj čvor čija je donja granica veća od od <math>m</math> može da se izbaci.
+Glavna ideja za BB algoritam je: ako je donja granica nekog cvora <math>A</math>  veca od gornje granice nekog čvora <math>B</math>, onda <math>A</math> može bezbedno da se izbaci iz  pretrage. Ovaj korak se zove ''orezivanje'' ({{jez-eng-lat|pruning}}), i obično se implementira tako sto se održava globalna varijabla <math>m</math> koji čuva minimum gornje granice koja je pronađena među trenutno proverenim. Bilo koj čvor čija je donja granica veća od od <math>m</math> može da se izbaci.
 Rekurzija se zaustavlja kada se trenutni kandidat iz skupa <math>S</math> smanji na jedan element ili kada se gornja granica iz skupa <math>S</math> poklopi sa donjom granicom. Bilo koji element iz skupa <math>S</math> će biti minimum te funkcije iz skupa <math>S</math>.
-Kada je <math>x</math> vektor iz <math>R^n</math>, branch-and-bound algoritam se spaja sa  intervalnom analziom i ugovoračem technika da bi moglo da se obezbedi ograđivanje globalnog minimuma.
+Kada je <math>x</math> vektor iz <math>R^n</math>, algoritam separacije i evaluacije se spaja sa [[Intervalna analiza|intervalnom analziom]]<ref>{{cite book|last1=Moore|first1=R. E.| title=Interval Analysis| year=1966|publisher=Prentice-Hall| location=Englewood Cliff, New Jersey|isbn=0-13-476853-1}}</ref> i ugovoračem technika da bi moglo da se obezbedi ograđivanje globalnog minimuma.<ref>{{cite book |last1=Jaulin |first1=L.|last2=Kieffer |first2=M.|last3=Didrit |first3=O.|last4=Walter|first4=E.| title=Applied Interval Analysis|year=2001|publisher=Springer|location=Berlin|isbn=1-85233-219-0}}</ref><ref>{{cite book|last=Hansen|first=E.R.| title=Global Optimization using Interval Analysis|year=1992| publisher=Marcel Dekker|location=New York}}</ref>
 ==Primene==
 Ovaj pristup se koristi za veliki broj NP-teških problema:
 * Celobrojno programiranje
 * Nelinearno programiranje
@@ Ред 32: / Ред 30: @@
 * 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 [[Heuristika (informatika)|heuristike]].
+Iz ovog raloga, tehnike separacije i evaluacije se često koriste u [[Algoritmi pretraživanja|algoritmu za pretragu]] [[Stablo igre|stabla igre]], najznačanije je u korišćenju [[alpha-beta orezivanje|alpha-beta orezivanja]].
+== Reference ==
+{{Reflist}}
+[[Категорија:Оптимизациони алгоритами и методи]]
-Branch-and-bound algoritam 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, branch-and-bound tehnkike se često koriste u "game tree" algoritmu za pretragu , najznačanije je u korišćenju alpha-beta orezivanja.