Elágazás és korlátozás

Az elágazás és korlátozás (BB, B&B vagy BnB) algoritmustervezési paradigma diszkrét és kombinatorikus optimalizálási problémákhoz, valamint a matematikai optimalizáláshoz szolgálnak. Az elágazás és korlátozás algoritmus a jelölt megoldások szisztematikus felsorolását foglalja magában a térmodell keresés segítségével: a jelölt megoldások halmazát úgy gondolják, hogy egy gyökeres fát alkot, amelynek teljes része a gyökér. Az algoritmus e fa ágait vizsgálja, amelyek a megoldás halmazának részhalmazait képviselik. Az ág jelölt megoldásainak felsorolása előtt megvizsgáljuk az ágat az optimális megoldás felső és alsó becsült határaival szemben, és elvetjük, ha nem képes jobb megoldást eredményezni, mint az algoritmus által eddig megtalált legjobb megoldás.

Az algoritmus a keresési terület ágainak alsó és felső határainak hatékony becslésén múlik. Ha nem állnak rendelkezésre határok, az algoritmus aprólékos keresésre vált.

A módszert először Ailsa Land és Alison Doig tette közzé, miközben a British Petroleum^[1] ^[2] által 1960-ban támogatott londoni közgazdasági iskolában végzett kutatást diszkrét programozás témakörben, és ez lett a leggyakrabban használt eszköz az NP-nehéz feladat optimalizálási problémák megoldására. Az "ágak és összeköttetések" név először Little et al. az utazó értékesítő problémájával kezdődött.^[3]

Áttekintés

Az elágazás és korlátozás algoritmus célja, hogy olyan $x$ értéket keressen, amely maximalizálja vagy minimalizálja az objektív függvénynek nevezett $f (x)$ valós értékű függvény értékét néhány $S$ megengedhető vagy lehetséges megoldás között. Az $S$ halmazt keresési területnek vagy megvalósítható régiónak nevezzük. E szakasz többi része feltételezi, hogy az $f (x)$ érték minimalizálása a cél; ez a feltételezés a többség elvesztése nélkül valósul meg, mivel az $f (x)$ maximális értékét úgy találhatjuk meg, hogy megkeressük a $g (x) = - f (x)$ minimumot. A B & B algoritmus két alapelv szerint működik:

Rekurzív módon felosztja a keresési teret kisebb terekre, majd minimalizálja az $f (x)$ -et ezeken a kisebb tereken; ezt a felosztást elágazásnak nevezzük.
Az elágazás önmagában a lehetséges megoldások nyers erő számbavételét és mindegyikének tesztelését jelentené. A nyers erővel történő keresés teljesítményének javítása érdekében a B & B algoritmus minimálisan nyomon követi a korlátokat, amelyeket megpróbál megtalálni, és ezeket a korlátokat használja a keresési terület „ ritkításához ”, kiküszöbölve az olyan jelölt megoldásokat, amelyek bizonyítani tudják, hogy nem tartalmaznak optimális megoldást.

Ezeknek az alapelveknek a konkrét optimalizálási probléma konkrét algoritmussá történő alakításához valamilyen adatszerkezetre van szükség, amely rámutat a lehetséges megoldások halmazára. Az ilyen ábrázolást a probléma egyik esetének nevezzük. Jelölje meg a példány megoldáskészletét $S I$ -nél A példánynak három művelettel kell rendelkeznie:

Az (I) ág két vagy több példányt hoz létre, amelyek mindegyike az SI egy részhalmazát képviseli. (Általában az részhalmazok el vannak választva annak megakadályozására, hogy az algoritmus ugyanazt a jelöltet megoldást kétszer megvizsgálja, de ezt szeretnénk elkerülni. Az SI közötti optimális megoldást azonban az alkészletek legalább egyikében tartalmaznia kell.^[4])
Az ág (I) kiszámítja bármely jelölt megoldás értékének alsó határát az I által képviselt térben, azaz (I) ≤ f (x) az összes x-re SI-ben.
Az (I) megoldás határozza meg, hogy megfelelő-e az egyetlen jelölt megoldás. (Opcionálisan, ha nem, a művelet dönthet úgy, hogy valamely megvalósítható megoldást visszaad az SI közül^[4])

Ezeket a műveleteket használva a B&B algoritmus felülről lefelé történő rekurzív keresést hajt végre az ágművelet által létrehozott példányok fáján. Az $I$ példány meglátogatásakor ellenőrzi, hogy az $bound(I)$ nagyobb-e, mint valamely más példány alsó határa, amelyet már meglátogatott; Ha így van, $I$ is biztonságosan lehet dobni a keresési és a rekurzió leáll. Ezt a metszéslépést általában egy olyan globális változó fenntartásával valósítják meg, amely rögzíti a legkisebb alsó határt az eddig vizsgált esetek között.

Generikus változat

Az alábbiakban egy általános ág vázlatát és kötött algoritmust használjuk az önkényes $f$ függvény minimalizálására. Ahhoz, hogy ebből tényleges algoritmust kapjunk, szükség van egy $g$ határoló függvényre, amely kiszámítja az $f$ alsó határait a keresési fa csomópontjain, valamint egy probléma-specifikus elágazási szabályt. Mint ilyen, az itt bemutatott általános algoritmus magasabb rendű függvény.

Heurisztika segítségével keresse meg az $x h$ megoldást az optimalizálási problémára. Tárolja értékét, $B = f (x h)$ . (Ha nincs heurisztika, állítsa a $B$ -t végtelenre.) $B$ jelöli az eddig megtalált legjobb megoldást, és a jelölt megoldások felső határán fogja használni.
Inicializálja a sort, hogy egy részleges megoldást tartson a megadott probléma egyik változójával sem.
Hurok, amíg a sor üres:
1. Vegye ki az $N$ pontot a sorból.
2. Ha $N$ jelentése egy jelölt $x$ megoldást és $f (x) < B$ , akkor $x$ a legjobb megoldás eddig. Rögzítse és állítsa be a $B \leftarrow f (x)$ .
3. Egyébként, az ág N hogy készítsen új csomópontokat N_i-pontnak. Ezek mindegyikére:
  1. Ha $bound (N i) > B$ , ne tegyen semmit; mivel ezen a csomóponton az alsó határ nagyobb, mint a probléma felső határa, soha nem vezet az optimális megoldáshoz, és elvethető.
  2. Egyébként, tárolja az $N i$ -et a sorban.

Számos különböző sor-adatstruktúra használható. Ez a FIFO soron alapuló megvalósítás szélesség első keresést eredményez. A verem (LIFO sor) mélység első algoritmust eredményez. A legjobb az első ág és a kötött algoritmus olyan prioritási sor használatával érhető el, amely az alsó határon lévő csomópontokat rendezi. Példák a legelső keresési algoritmusokra, amelyek tartalmazzák ezt az előfeltételt, Dijkstra algoritmusa és A* keresés leszármazottjának. Az első mélységű változat akkor ajánlott, ha nincs megfelelő heurisztika a kezdeti megoldás előállításához, mert gyorsan teljes megoldásokat hoz létre, és ezáltal a felső határokat.^[5]

Pszeudokód

A fentiek C ++- szerű pszeudokód megvalósítása az alábbiakban:

// C++-like implementation of branch and bound, 
// assuming the objective function f is to be minimized
CombinatorialSolution branch_and_bound_solve(
  CombinatorialProblem problem, 
  ObjectiveFunction objective_function /*f*/,
  BoundingFunction lower_bound_function /*g*/) 
{
  // Step 1 above
  double problem_upper_bound = std::numeric_limits<double>::infinity; // = B
  CombinatorialSolution heuristic_solution = heuristic_solve(problem); // x_h
  problem_upper_bound = objective_function(heuristic_solution); // B = f(x_h)
  CombinatorialSolution current_optimum = heuristic_solution;
  // Step 2 above
  queue<CandidateSolutionTree> candidate_queue;
  // problem-specific queue initialization
  candidate_queue = populate_candidates(problem);
  while (!candidate_queue.empty()) { // Step 3 above
    // Step 3.1
    CandidateSolutionTree node = candidate_queue.pop();
    // "node" represents N above
    if (node.represents_single_candidate()) { // Step 3.2
      if (objective_function(node.candidate()) < problem_upper_bound) {
        current_optimum = node.candidate();
        problem_upper_bound = objective_function(current_optimum);
      }
      // else, node is a single candidate which is not optimum
    }
    else { // Step 3.3: node represents a branch of candidate solutions
      // "child_branch" represents N_i above
      for (auto&& child_branch : node.candidate_nodes) {
        if (lower_bound_function(child_branch) <= problem_upper_bound) {
          candidate_queue.enqueue(child_branch); // Step 3.3.2
        }
        // otherwise, g(N_i) > B so we prune the branch; step 3.3.1
      }
    }
  }
  return current_optimum;
}

Elágazás és korlátozás bemutatása lépésről-lépésre

A fenti pszeudokódokra a funkciókat heurisztikus megoldásnak és populate_candidates nevezett alprogramokként meg kell adni az alkalmazandó a problémát. Az $f$ (objective_function) és $g$ (lower_bound_function) függvényobjektumokként vannak írva, és megfelelhetnek a C++ programozási nyelvben szereplő lambda kifejezéseknek, függvénymutatóknak vagy funktoroknak, többek között a felhívható objektumok között.

Fejlesztések

Mikor $\mathbf {x}$ egy vektora $\mathbb {R} ^{n}$ -nek, az ág és a kötött algoritmusok kombinálhatók intervallumelemzéssel^[6] és a kivitelező technikákkal a globális minimum garantált körülhatárolása érdekében.^[7] ^[8]

Alkalmazások

Ezt a megközelítést számos NP-probléma esetén alkalmazzák

Egész számú programozás
Nemlineáris programozás
Utazó eladó probléma (TSP)^[3]^[9]
Másodlagos hozzárendelési probléma (QAP)
Maximális kielégítő probléma (MAX-SAT)
Legközelebbi szomszéd keresése^[10] (Keinosuke Fukunaga)
Flow üzlet ütemezése
A vágó készlet problémája
Hamis zaj analízis (FNA)
Számítógépes filogenetika
Állítsa be az inverziót
Paraméter becslés
0/1 hátizsák probléma
Funkcióválasztás a gépi tanulásban^[11]
Strukturált predikció a számítógépes látásban^[12]

Az elágazó és kötött is lehet a különféle heurisztikák alapja. Például lehet, hogy abba kell hagyni az elágazást, ha a felső és alsó határ közötti rés kisebb, mint egy meghatározott küszöb. Ezt akkor használják, amikor a megoldás "praktikus célokra elég jó", és jelentősen csökkentheti a szükséges számításokat. Ez a fajta megoldás különösen akkor alkalmazható, ha az alkalmazott költségfüggvény zajos vagy statisztikai becslések eredménye, és ezért nem ismert pontosan, hanem inkább csak arról van szó, hogy egy meghatározott valószínűséggel eső értéktartományon belül helyezkedik el.

Kapcsolat más algoritmusokkal

Nau et al. bemutatja az ág és a kötött általánosítását, amely szintén felveszi a mesterséges intelligencia A *, B * és alfa-béta keresési algoritmusait.^[13]

Jegyzetek

↑ A. H. Land and A. G. Doig. „An automatic method of solving discrete programming problems”, Econometrica, 497–520. oldal
↑ Staff News. www.lse.ac.uk. [2021. február 24-i dátummal az eredetiből archiválva]. (Hozzáférés: 2018. október 8.)
↑ ^a ^b Little (1963). „An algorithm for the traveling salesman problem”. Operations Research 11 (6), 972–989. o. DOI:10.1287/opre.11.6.972.
↑ ^a ^b Parallel Algorithm Design for Branch and Bound, Tutorials on Emerging Methodologies and Applications in Operations Research. Kluwer Academic Press (2004). Hozzáférés ideje: 2020. május 18. Archiválva 2017. augusztus 13-i dátummal a Wayback Machine-ben Archivált másolat. [2017. augusztus 13-i dátummal az eredetiből archiválva]. (Hozzáférés: 2020. május 18.)
↑ Mehlhorn, Kurt. Algorithms and Data Structures: The Basic Toolbox. Springer, 249. o. (2008)
↑ Moore, R. E.. Interval Analysis. Englewood Cliff, New Jersey: Prentice-Hall (1966). ISBN 0-13-476853-1
↑ Jaulin, L.. Applied Interval Analysis. Berlin: Springer (2001). ISBN 1-85233-219-0
↑ Hansen, E.R.. Global Optimization using Interval Analysis. New York: Marcel Dekker (1992)
↑ Conway, Richard Walter. Theory of Scheduling. Courier Dover Publications, 56–61. o. (2003)
↑ Fukunaga (1975). „A branch and bound algorithm for computing $k$ -nearest neighbors”. IEEE Transactions on Computers, 750–753. o. DOI:10.1109/t-c.1975.224297.
↑ Narendra (1977). „A branch and bound algorithm for feature subset selection”. IEEE Transactions on Computers C-26 (9), 917–922. o. DOI:10.1109/TC.1977.1674939.
↑ Nowozin (2011). „Structured Learning and Prediction in Computer Vision”. Foundations and Trends in Computer Graphics and Vision 6 (3–4), 185–365. o. DOI:10.1561/0600000033.
↑ Nau (1984). „General branch and bound, and its relation to A∗ and AO∗”. Artificial Intelligence 23 (1), 29–58. o. DOI:10.1016/0004-3702(84)90004-3.

Fordítás

Ez a szócikk részben vagy egészben a Branch and bound című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

LiPS - Ingyenes, könnyen használható GUI-program, lineáris, egész és célprogramozási problémák megoldására.
Cbc - (érme vagy elágazás és kivágás) egy nyílt forráskódú vegyes egész programozási megoldó, C ++-ban írva.

[land_doig-1] A. H. Land and A. G. Doig. „An automatic method of solving discrete programming problems”, Econometrica, 497–520. oldal

[2] Staff News. www.lse.ac.uk. [2021. február 24-i dátummal az eredetiből archiválva]. (Hozzáférés: 2018. október 8.)

[little-3] Little (1963). „An algorithm for the traveling salesman problem”. Operations Research 11 (6), 972–989. o. DOI:10.1287/opre.11.6.972.

[bader-4] Parallel Algorithm Design for Branch and Bound, Tutorials on Emerging Methodologies and Applications in Operations Research. Kluwer Academic Press (2004). Hozzáférés ideje: 2020. május 18. Archiválva 2017. augusztus 13-i dátummal a Wayback Machine-ben Archivált másolat. [2017. augusztus 13-i dátummal az eredetiből archiválva]. (Hozzáférés: 2020. május 18.)

[5] Mehlhorn, Kurt. Algorithms and Data Structures: The Basic Toolbox. Springer, 249. o. (2008)

[6] Moore, R. E.. Interval Analysis. Englewood Cliff, New Jersey: Prentice-Hall (1966). ISBN 0-13-476853-1

[7] Jaulin, L.. Applied Interval Analysis. Berlin: Springer (2001). ISBN 1-85233-219-0

[8] Hansen, E.R.. Global Optimization using Interval Analysis. New York: Marcel Dekker (1992)

[9] Conway, Richard Walter. Theory of Scheduling. Courier Dover Publications, 56–61. o. (2003)

[10] Fukunaga (1975). „A branch and bound algorithm for computing $k$ -nearest neighbors”. IEEE Transactions on Computers, 750–753. o. DOI:10.1109/t-c.1975.224297.

[11] Narendra (1977). „A branch and bound algorithm for feature subset selection”. IEEE Transactions on Computers C-26 (9), 917–922. o. DOI:10.1109/TC.1977.1674939.

[12] Nowozin (2011). „Structured Learning and Prediction in Computer Vision”. Foundations and Trends in Computer Graphics and Vision 6 (3–4), 185–365. o. DOI:10.1561/0600000033.

[13] Nau (1984). „General branch and bound, and its relation to A∗ and AO∗”. Artificial Intelligence 23 (1), 29–58. o. DOI:10.1016/0004-3702(84)90004-3.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]