Větvené a vázané - Branch and bound

Větev a vazba ( BB , B & B nebo BnB ) je paradigma návrhu algoritmu pro diskrétní a kombinatorické optimalizační problémy i pro matematickou optimalizaci . Algoritmus větvení a vázání se skládá ze systematického výčtu kandidátních řešení pomocí hledání stavového prostoru : množina kandidátských řešení je považována za vytvoření kořenového stromu s úplnou sadou v kořenovém adresáři. Algoritmus zkoumá větve tohoto stromu, které představují podmnožiny sady řešení. Před vyjmenováním kandidátních řešení větve se větev zkontroluje proti horní a dolní odhadované hranici optimálního řešení a zahodí se, pokud nemůže přinést lepší řešení, než je dosud nejlepší algoritmus nalezený algoritmem.

Algoritmus závisí na účinném odhadu dolní a horní hranice oblastí / větví vyhledávaného prostoru. Pokud nejsou k dispozici žádné hranice, algoritmus degeneruje na vyčerpávající hledání.

Metodu poprvé navrhli Ailsa Land a Alison Doig při provádění výzkumu na London School of Economics sponzorovaného British Petroleum v roce 1960 pro diskrétní programování a stala se nejčastěji používaným nástrojem pro řešení problémů s NP-hard optimalizací. Název „větev a svázaný“ se poprvé objevil v práci Little et al. o problému obchodního cestujícího .

Přehled

Cílem algoritmu větve a vazby je najít mezi některými množinami S přípustných nebo kandidátských řešení hodnotu x, která maximalizuje nebo minimalizuje hodnotu funkce f ( x ) se skutečnou hodnotou , která se nazývá objektivní funkce . Sada S se nazývá vyhledávací prostor nebo proveditelná oblast . Zbytek této části předpokládá, že je požadována minimalizace f ( x ) ; tento předpoklad přichází bez ztráty obecnosti , protože maximální hodnotu f ( x ) lze najít nalezením minima g ( x ) = - f ( x ) . Algoritmus typu B&B funguje podle dvou principů:

  • Rekurzivně rozděluje vyhledávací prostor na menší prostory a poté minimalizuje f ( x ) na těchto menších prostorech; rozdělení se nazývá větvení .
  • Samotné větvení by znamenalo výčet kandidátů řešení hrubou silou a jejich testování všech. Aby se zlepšil výkon vyhledávání hrubou silou, algoritmus B&B sleduje hranice na minimu, které se pokouší najít, a používá tyto hranice k „ prořezání “ prostoru pro vyhledávání, čímž eliminuje kandidátní řešení, která mohou prokázat, že nebudou obsahovat optimální řešení.

Proměna těchto principů v konkrétní algoritmus pro konkrétní optimalizační problém vyžaduje nějaký druh datové struktury, která představuje sady kandidátských řešení. Taková reprezentace se nazývá instance problému. Množinu kandidátních řešení instance I u S I . Reprezentace instance musí mít tři operace:

  • větev ( I ) vytváří dvě nebo více instancí, které každý představují podskupinu S I . (Obvykle jsou podmnožiny disjunktní, aby se zabránilo tomu, aby algoritmus navštívil dvakrát stejné kandidátní řešení, ale to není nutné. Optimální řešení mezi S I však musí být obsaženo alespoň v jedné z podmnožin.)
  • váže ( I ) vypočítá spodní hranici hodnoty jakéhokoliv roztoku kandidátní v prostoru reprezentované I , to znamená, že vázaný ( I ) ≤ f ( x ) pro všechna x v S I .
  • roztok ( I ), určuje, zda I představuje jeden kandidátní řešení. (Volitelně, pokud se tak nestane, může se operace rozhodnout vrátit nějaké proveditelné řešení z rozsahu S I. ) Pokud řešení ( I ) vrátí řešení, pak f (řešení ( I )) poskytuje horní mez pro optimální objektivní hodnotu přes celý prostor proveditelných řešení.

Pomocí těchto operací provede algoritmus B&B rekurzivní vyhledávání shora dolů ve stromu instancí vytvořených operací větve. Při návštěvě instance I zkontroluje, zda je mezní hodnota ( I ) větší než dosud nalezená horní mez; pokud ano, mohu být z vyhledávání bezpečně vyřazen a rekurze se zastaví. Tento krok prořezávání je obvykle implementován udržováním globální proměnné, která zaznamenává minimální horní mez mezi všemi dosud zkoumanými instancemi.

Obecná verze

Následuje kostra generické větve a vázaného algoritmu pro minimalizaci libovolné objektivní funkce f . Abychom z toho získali skutečný algoritmus, vyžaduje se vázaná funkce ohraničení , která počítá dolní hranice f na uzlech vyhledávacího stromu, stejně jako specifické pravidlo větvení. Zde uvedený obecný algoritmus je tedy funkcí vyššího řádu .

  1. Pomocí heuristiky najděte řešení x h problému optimalizace. Uložte jeho hodnotu, B = f ( x h ) . (Pokud není k dispozici žádná heuristika, nastavte B na nekonečno.) B bude označovat dosud nalezené nejlepší řešení a bude použito jako horní hranice pro kandidátní řešení.
  2. Inicializujte frontu tak, aby obsahovala částečné řešení bez přiřazené proměnné problému.
  3. Opakujte, dokud fronta není prázdná:
    1. Vezměte uzel N z fronty.
    2. Pokud N představuje jediné kandidátské řešení x a f ( x ) < B , pak je x zatím nejlepší řešení. Zaznamenejte to a nastavte Bf ( x ) .
    3. Jinak se rozvětvte na N a vytvořte nové uzly N i . Pro každou z těchto možností:
      1. Pokud je vázán ( N i )> B , nedělej nic; protože dolní hranice v tomto uzlu je větší než horní hranice problému, nikdy to nepovede k optimálnímu řešení a lze ji zahodit.
      2. Jinak uložit N i do fronty.

Lze použít několik různých datových struktur fronty . Tato implementace založená na frontě FIFO přináší vyhledávání na šířku . Zásobník (LIFO fronta) přinese do hloubky algoritmus. Nejlepší první větví a mezí algoritmus může být dosaženo použitím prioritní fronty , která třídí uzly na jejich dolní mez. Příkladem vyhledávacích algoritmů s prvním předpokladem s touto premisou je Dijkstrův algoritmus a jeho potomek A * . Varianta hloubky první se doporučuje, když není k dispozici žádná dobrá heuristika pro vytvoření počátečního řešení, protože rychle vytváří úplná řešení, a tedy horní hranice.

Pseudo kód

A C ++ -jako realizace pseudokód z výše uvedeného, je:

// 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 /*bound*/) 
{
    // 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, bound(N_i) > B so we prune the branch; step 3.3.1
            }
        }
    }
    return current_optimum;
}

Ve výše uvedeném pseudokódu, funkce heuristic_solvea populate_candidatesnazývají jako podprogramy musí být podle potřeby k problému. Funkce f ( objective_function) a vázané ( lower_bound_function) jsou považovány za funkční objekty jako psáno, a může odpovídat lambda výrazy , ukazatelů funkcí nebo functors v jazyce C ++, mezi jinými typy vypověditelnými objektů .

Vylepšení

Když je vektor , lze větvové a vázané algoritmy kombinovat s intervalovou analýzou a technikami kontraktorů , aby poskytly zaručené zastřešení globálního minima.

Aplikace

Tento přístup se používá pro řadu NP-hard problémů:

Větvené a vázané může být také základnou různých heuristik . Například si můžete přát zastavit větvení, když se mezera mezi horním a dolním okrajem zmenší na určitou prahovou hodnotu. Používá se, když je řešení „dostatečně dobré pro praktické účely“ a může výrazně snížit požadované výpočty. Tento typ řešení je obzvláště použitelný, když je použitá nákladová funkce hlučná nebo je výsledkem statistických odhadů, a proto není známa přesně, ale spíše je známo pouze to, že leží v rozsahu hodnot se specifickou pravděpodobností .

Vztah k jiným algoritmům

Nau et al. představují zevšeobecnění větve a vazby, které také zahrnuje algoritmy vyhledávání A * , B * a alfa-beta .

Viz také

Reference

externí odkazy

  • LiPS - bezplatný snadno použitelný program GUI určený k řešení problémů s lineárním, celočíselným a cílovým programováním.
  • Cbc - (Coin-or branch and cut) je open-source řešitel celočíselného programování napsaný v C ++.