Větvené a vázané - Branch and bound
Algoritmy pro vyhledávání grafů a stromů |
---|
Výpisy |
související témata |
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 .
- 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í.
- Inicializujte frontu tak, aby obsahovala částečné řešení bez přiřazené proměnné problému.
- Opakujte, dokud fronta není prázdná:
- Vezměte uzel N z fronty.
- 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 B ← f ( x ) .
- Jinak se rozvětvte na N a vytvořte nové uzly N i . Pro každou z těchto možností:
- 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.
- 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_solve
a populate_candidates
nazý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ů:
- Programování celého čísla
- Nelineární programování
- Problém obchodního cestujícího (TSP)
- Kvadratický problém s přiřazením (QAP)
- Problém s maximální uspokojivostí (MAX-SAT)
- Hledání nejbližších sousedů ( Keinosuke Fukunaga )
- Plánování obchodu
- Problém s řezáním materiálu
- Výpočetní fylogenetika
- Nastavit inverzi
- Odhad parametrů
- Problém s batohem 0/1
- Nastavit problém s krytem
- Výběr funkcí ve strojovém učení
- Strukturovaná předpověď v počítačovém vidění
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é
- Backtracking
- Větev a řez , hybrid mezi metodami větvení a řezu a roviny řezu, který se značně používá k řešení celočíselných lineárních programů .