Vyhledávání se zákazy

Tabu search nebo tabu search je meta-vyhledávací algoritmus využívající lokální vyhledávací metody používané pro matematickou optimalizaci . Algoritmus byl vytvořen Fredem W. Gloverem v roce 1986 [1] a formalizován v roce 1989 [2] [3]

Místní vyhledávání (podle sousedů) bere potenciální řešení problému a kontroluje jeho bezprostřední sousedy (tj. řešení, která jsou podobná až na několik velmi malých detailů) v naději, že nalezne vylepšené řešení. Metody místního vyhledávání mají tendenci uvíznout v neoptimálních oblastech nebo náhorních plošinách, kde je mnoho řešení stejně vhodných.

Odmítnuté vyhledávání zlepšuje výkon místního vyhledávání uvolněním jeho základního pravidla. Pro začátek lze předpokládat zhoršení na každém kroku , pokud nedojde ke zlepšení (podobně jako v případě, kdy se vyhledávání zasekne na místním minimu ). Kromě toho jsou zavedeny zákazy (aka tabu ), aby se zabránilo hledání řešení, která již byla navštívena.

Implementace odepřít vyhledávání používá struktury, které popisují navštívená rozhodnutí nebo sady uživatelských pravidel [2] . Pokud bylo potenciální řešení během krátké doby navštíveno nebo porušuje pravidlo, je označeno jako „ tabu “, aby algoritmus řešení nepřehodnotil.

Slovo tabu pochází z tonžského slova, které znamená věci, kterých by se nemělo dotýkat, protože jsou posvátné [4] .

Taboo search je meta-algoritmus , který lze použít k řešení problémů kombinatorické optimalizace (problémy, kde potřebujete najít optimální řazení a výběr možností).

Současné blokované vyhledávací aplikace se rozšiřují do oblastí, jako je plánování zdrojů , telekomunikace, inženýrství VLSI , finanční analýza, plánování, územní plánování, distribuce energie, molekulární inženýrství, logistika, klasifikace vzorů , flexibilní výroba, nakládání s odpady, vyhledávání nerostů, biomedicínská analýza, ochrana životního prostředí a mnoho dalších. V posledních letech časopisy z mnoha vědních oborů publikovaly akademické práce a počítačové studie, které dokazují úspěch tabuizovaného hledání při rozšiřování hranic problémů, které lze efektivně řešit, a poskytují řešení, která jsou často mnohem kvalitnější než ta, která byla získána dosavadními metodami. . Rozsáhlý seznam aplikací včetně shrnutí výsledku získaného z praktické aplikace naleznete v článku Glovera a Laguny [5] . Moderní vývoj a aplikace tabuizovaného vyhledávání naleznete v článku Tabu Search Vignettes .

Základy

Taboo search používá místní vyhledávání nebo proceduru vyhledávání sousedů k iterativnímu přechodu od jednoho potenciálního řešení k lepšímu řešení v sousedství, dokud není splněno nějaké kritérium zastavení (obvykle počet iterací nebo práh cílového skóre). Místní vyhledávací rutiny se často zaseknou v oblastech se špatnými odhady cíle nebo v oblastech, kde odhad tvoří plošinu (hladký horizontální povrch). Abychom se vyhnuli těmto nástrahám a prozkoumali oblasti vyhledávacího prostoru , které by jinými vyhledávacími postupy zůstaly neprozkoumané, tabuizované vyhledávání pečlivě zkoumá sousedství každého řešení v procesu vyhledávání. Řešení rozpoznaná novými sousedy, , jsou určena pomocí struktur v paměti. Pomocí těchto struktur vyhledávání postupuje iterativním přechodem od aktuálního řešení k vylepšenému řešení ze seznamu .

Tyto struktury tvoří tzv. tabuizované seznamy, soubor pravidel a označených řešení sloužících k filtrování toho, která sousední řešení zpracovat při vyhledávání. Ve své nejjednodušší podobě je seznam tabu krátkodobý soubor rozhodnutí, která byla navštívena v posledních iteracích (méně než iterací, kde se rovná počtu zapamatovaných rozhodnutí a toto číslo se nazývá životnost tabu). Seznam tabu se častěji skládá z rozhodnutí, která byla změněna v procesu přechodu od jednoho rozhodnutí k druhému. Pro snadnou prezentaci je vhodné porozumět „řešení“ zakódovanému a reprezentovanému některými atributy.

Typy paměti

Paměťové struktury používané při vyhledávání tabu lze zhruba rozdělit do tří kategorií [6] :

Krátkodobé, střednědobé a dlouhodobé seznamy se mohou překrývat. V rámci těchto kategorií lze paměť dále rozlišovat podle kritérií, jako je frekvence a dopad provedených změn. Jedním příkladem střednědobé struktury je zákaz nebo podpora rozhodnutí, která obsahují nějaké atributy (například rozhodnutí, která obsahují nežádoucí nebo žádoucí hodnoty některých určitých proměnných) nebo paměťová struktura, která brání nebo generuje některé pohyby (např. na základě četnosti výskytu rysů v perspektivních a neperspektivních řešeních nalezených dříve). V krátkodobé paměti jsou vybrané atributy v nedávno navštívených řešeních označeny jako „tabu-aktivní“. Použití roztoků s tabuisticky aktivními prvky je zakázáno. Ke změně tabuizovaného stavu řešení se používá kritérium odstranění, včetně vyloučených řešení v seznamu povolených (řešení je „dost dobré“ podle míry kvality nebo rozdílu). Jednoduchým a běžně používaným kritériem odstranění je umožnit použití řešení, která jsou lepší než aktuálně známá nejlepší řešení.

Krátkodobá paměť sama o sobě může být dostatečná k tomu, aby vytvořila lepší řešení než konvenční metody lokálního vyhledávání, ale k řešení složitějších problémů jsou často potřeba střednědobé a dlouhodobé struktury [7] . Vyhledávání tabu je často přirovnáváno k jiným meta-algoritmickým metodám, jako je simulovaný algoritmus žíhání , genetické algoritmy , algoritmy mravenčích kolonií , reaktivní vyhledávání, místní vyhledávání pod dohledem nebo chamtivé adaptivní náhodné vyhledávání . Kromě toho je vyhledávání tabu někdy kombinováno s jinými meta-algoritmy za účelem vytvoření hybridních metod. Nejběžnější hybrid vyhledávání tabby vzniká jeho spárováním s rozptylovým vyhledáváním [  8 ] [ 9] , třídou postupů, které mají společné kořeny s tabuizovaným vyhledáváním a často se používají k řešení rozsáhlých nelineárních optimalizačních problémů.

Pseudokód

Následující pseudokód představuje zjednodušenou verzi tabuizovaného vyhledávacího algoritmu, jak je popsáno výše. Tato implementace má nejjednodušší verzi krátkodobé paměti a neobsahuje střednědobé ani dlouhodobé struktury. Termín "fitness" odkazuje na výpočet objektivní funkce pro kandidátní řešení.

sNejlepší ← s0 bestCandidate ← s0 tabuList ← [] tabuList . tlačit ( s0 ) while ( not stopCondition ()) sNeighborhood ← getNeighbors ( nejlepší kandidát ) pro ( s Kandidát v sNeighborhood ) if ( ( not tabuList . obsahuje ( sCandidate )) a ( fitness ( sCandidate ) > fitness ( bestCandidate )) ) bestCandidate ← sCandidate konec konec if ( fitness ( bestCandidate ) > fitness ( sBest )) sNejlepší ← nejlepší Kandidát konec tabuList . tlačit ( nejlepší kandidát ) if ( tabuList . size > maxTabuSize ) tabuList . removeFirst () konec konec vrátit sBest

Řádky 1-4 provádějí počáteční přiřazení, vytvářejí počáteční řešení (možná získané metodami náhodného vyhledávání), nastavují výsledné řešení jako první, na které jsme se podívali, a tímto řešením inicializují seznam tabu. V tomto příkladu je seznam tabu pouze krátkou strukturou, která obsahuje záznamy o navštívených položkách.

Hlavní smyčka začíná na řádku 5. Tato smyčka pokračuje v hledání nejlepšího řešení, dokud nedosáhne uživatelem stanoveného kritéria zastavení (dva příklady takového kritéria jsou jednoduše časový limit nebo práh skóre fitness). Sousední řešení jsou kontrolována na tabu v řádku 8. Algoritmus navíc ukládá nejlepší nezakázaná řešení sousedy.

Cílová funkce fitness je obvykle matematická funkce, která vrací cílové skóre nebo kritérium – například nalezení nového vyhledávacího prostoru [4] lze považovat za cílové kritérium . Pokud má nejlepší místní kandidát vyšší hodnotu fitness, pak je aktuální hodnota nejlepší (řádek 12), nyní je akceptován jako nejlepší (řádek 13). Místní nejlepší kandidát je vždy přidán do seznamu tabu (řádek 15) a pokud je seznam tabu plný (řádek 16), má se za to, že tabu některého prvku již vypršelo (řádek 17). Prvky se obvykle odebírají ze seznamu v pořadí, v jakém do něj byly přidány. Postup vybere nejlepšího místního kandidáta (ačkoli má horší fitness hodnotu než sBest), aby vyskočil z lokálního optima.

Tento proces pokračuje, dokud není získáno uživatelsky definované kritérium zastavení, kdy je vráceno nejlepší řešení, které se v procesu vyskytuje (řádek 20).

Příklad: problém cestujícího prodejce

Problém cestujícího prodejce se někdy používá k ukázce fungování tabuizovaného vyhledávání [7] . Tento problém se ptá, jaká je nejkratší cesta k návštěvě všech měst, pokud je uveden seznam měst? Pokud jsou například město A a město B blízko sebe, ale město C je od sebe daleko, celková délka trasy bude kratší, pokud nejprve navštívíme A ​​a B a poté pojedeme do města C. Protože nalezení optimálního řešení je NP-obtížné , k získání téměř optimálního řešení jsou užitečné heuristické aproximační metody (jako je místní vyhledávání). Pro získání dobrých řešení problému obchodního cestujícího je důležité prozkoumat strukturu grafu. Hodnota zkoumání struktury problému je v metaalgoritmických metodách opakujícím se tématem a tabuizované vyhledávání se k tomu dobře hodí. Třída strategií spojených s tabuizovaným vyhledáváním a tzv. metody ejection  chain umožňuje efektivně získat vysoce kvalitní řešení problému obchodního cestujícího [10] .

Na druhou stranu lze použít jednoduché tabuizované vyhledávání k nalezení uspokojivého řešení problému obchodního cestujícího (tedy řešení, které splňuje kritérium zdatnosti, byť nekvalitní, které se získá po prozkoumání struktury grafu) Hledání začíná počátečním řešením, které může být získáno náhodně nebo podle nějakého algoritmu nejbližšího souseda . Pro vytvoření nových řešení se v potenciálním řešení prohodí pořadí, ve kterém jsou města navštěvována. Celková vzdálenost trasy mezi všemi městy se používá k porovnání, o kolik je jedno řešení lepší než jiné. Aby se zabránilo zacyklení, tedy opětovnému získání určité sady řešení a uvíznutí v lokálním optimu , je řešení přidáno do seznamu zakázaných řešení, pokud je přijato při hledání mezi sousedy, .

Nová řešení jsou vytvářena, dokud nedosáhneme nějakého zastavovacího kritéria, jako je počet iterací. Jakmile se jednoduché tabu vyhledávání zastaví, vrátí to nejlepší řešení, které při provádění nalezlo.

Poznámky

  1. ↑ Glover, 1986 , str. 533–549.
  2. ↑ 1 2 Glover, 1989 , str. 190–206.
  3. ↑ Glover, 1990 , s. 4–32.
  4. ↑ 1 2 Kurzy | Fuzzy-neurální skupina | NC stát ISE . Staženo 16. ledna 2019. Archivováno z originálu 12. ledna 2014.
  5. ↑ Glover, Laguna, 1997 .
  6. ↑ Glover/A Tutorial, 1990 .
  7. ↑ 1 2 Malek, Huruswamy, Owens, Pandya, 1989 .
  8. ↑ Glover, Laguna, Marti, 2000 , str. 653–684.
  9. ↑ Laguna, Marti, 2003 .
  10. ↑ Gamboa, Rego, Glover, 2005 , str. 154–171.

Literatura

  • Fred Glover. Budoucí cesty pro celočíselné programování a odkazy na umělou inteligenci // Počítače a operační výzkum. - 1986. - T. 13 , no. 5 . - doi : 10.1016/0305-0548(86)90048-1 .
  • Fred Glover. Tabu Search – část 1 // ORSA Journal on Computing. - 1989. - svazek 1 , vydání. 2 . - doi : 10.1287/ijoc.1.3.190 .
  • Fred Glover. Tabu Search – část 2 // ORSA Journal on Computing. - 1990. - Vol. 2 , vydání. 1 . - doi : 10.1287/ijoc.2.1.4 .
  • Gamboa D., Rego C., Glover F. Datové struktury a vyhazovací řetězce pro řešení problémů cestujících obchodníků ve velkém měřítku // European Journal of Operational Research. - 2005. - T. 160 , čís. 1 . - doi : 10.1016/j.ejor.2004.04.023 .
  • Glover F., Laguna M. Tabu Search. — Kluwer Academic Publishers. — 1997.
  • Fred Glover. Tabu Search: Tutorial // Rozhraní. — 1990.
  • Malek M., Huruswamy M., Owens H., Pandya M. Techniky sériového a paralelního vyhledávání pro problém cestujícího prodejce. Annals of OR: Propojení s umělou inteligencí. — 1989.
  • Glover F., Laguna M., Marti R. Základy hledání rozptylu a přepojování cest. — Řízení a kybernetika. - 2000. - T. 29. - S. 653-684.
  • Laguna M., Marti R. Scatter Search: Metodologie a implementace v C. - Kluwer Academic Publishers, Boston. — 2003.

Odkazy