Vyhledávání Tabu - Tabu search

Vyhledávání v Tabu je metaheuristická vyhledávací metoda využívající místní vyhledávací metody používané pro matematickou optimalizaci . To bylo vytvořeno Fredem W. Gloverem v roce 1986 a formováno v roce 1989.

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

Hledání v Tabu zvyšuje výkon místního vyhledávání uvolněním jeho základního pravidla. Za prvé, v každém kroku lze akceptovat zhoršující se pohyby, pokud není k dispozici žádný zlepšující se pohyb (jako když je vyhledávání zaseknuto na přísném lokálním minimu ). Kromě toho jsou zavedeny zákazy (dále jen výraz tabu ), které odrazují hledání od návratu k dříve navštíveným řešením.

Implementace vyhledávání tabu využívá paměťové struktury, které popisují navštívená řešení nebo sady pravidel poskytované uživateli. Pokud bylo potenciální řešení dříve navštíveno v určitém krátkodobém období nebo pokud porušilo pravidlo, je označeno jako „ tabu “ (zakázáno), aby algoritmus tuto možnost opakovaně nezohledňoval.

Pozadí

Slovo tabu pochází z tonganského slova a označuje věci, kterých se nelze dotknout, protože jsou posvátné.

Hledání v Tabu (TS) je metaheuristický algoritmus, který lze použít k řešení kombinačních optimalizačních problémů (problémů, kde je požadováno optimální řazení a výběr možností).

Současné aplikace TS pokrývají oblasti plánování zdrojů , telekomunikací, návrhu VLSI , finanční analýzy, plánování, plánování vesmíru, distribuce energie, molekulární inženýrství, logistika, klasifikace vzorů , flexibilní výroba, nakládání s odpady, průzkum nerostů, biomedicínská analýza, ochrana životního prostředí a desítky dalších. V posledních letech vydávaly deníky v nejrůznějších oborech články s návody a výpočtové studie dokumentující úspěchy pomocí vyhledávání tabu při rozšiřování hranice problémů, které lze efektivně řešit - přináší řešení, jejichž kvalita často výrazně převyšuje kvalitu dosaženou dříve použitými metodami. Komplexní seznam aplikací, včetně souhrnného popisu zisků dosažených praktickými implementacemi, najdete v části Poslední vývoj TS a aplikace také v Tabu Search Vignettes .

Základní popis

Hledání v Tabu používá postup místního nebo sousedního vyhledávání k iterativnímu přechodu z jednoho potenciálního řešení na vylepšené řešení v sousedství , dokud není splněno určité kritérium zastavení (obecně limit pokusu nebo prahová hodnota skóre). Postupy místního vyhledávání se často zaseknou v oblastech se špatným skóre nebo v oblastech, kde se skóre zvyšuje. Abychom se vyhnuli těmto úskalím a prozkoumali oblasti vyhledávacího prostoru, které by nebyly ponechány neprozkoumanými jinými místními postupy vyhledávání, prozkoumává tabu search pečlivě sousedství každého řešení, jak postupuje hledání. Řešení přijatá do nového sousedství jsou určována pomocí paměťových struktur. Pomocí těchto paměťových struktur prochází hledání iterativním přechodem od aktuálního řešení k vylepšenému řešení v .

Hledání v Tabu má několik podobností se simulovaným žíháním , protože obě zahrnují možné pohyby z kopce. Ve skutečnosti lze simulované žíhání považovat za speciální formu TS, kde používáme „odstupňovanou držbu“, tj. Tah se stává tabu se specifikovanou pravděpodobností.

Tyto paměťové struktury tvoří takzvaný seznam tabu, sadu pravidel a zakázaná řešení sloužící k filtrování, která řešení budou přijata do sousedství, aby byla prozkoumána. Ve své nejjednodušší podobě je seznam tabu krátkodobá sada řešení, která byla navštívena v nedávné minulosti (méně než iterace před, kde je počet předchozích řešení, která mají být uložena - se také nazývá držba tabu). Obvykle se seznam tabu skládá z řešení, která se změnila procesem přechodu z jednoho řešení na druhé. Pro usnadnění popisu je vhodné rozumět „řešení“, které má být kódováno a představováno takovými atributy.

Druhy paměti

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

  • Krátkodobé: Seznam nedávno zvažovaných řešení. Pokud se potenciální řešení objeví na seznamu tabu, nelze jej znovu navštívit, dokud nedosáhne bodu vypršení platnosti.
  • Střednědobý: Pravidla intenzifikace určená k ovlivnění vyhledávání směrem k nadějným oblastem vyhledávacího prostoru.
  • Long-term: Diversification rules that drive the search into new regions (ie týkající se resetování, když se hledání zasekne na náhorní plošině nebo v neoptimální slepé uličce).

Krátkodobé, střednědobé a dlouhodobé vzpomínky se mohou v praxi překrývat. V rámci těchto kategorií lze paměť dále rozlišovat takovými opatřeními, jako je frekvence a dopad provedených změn. Jedním příkladem střednědobé struktury paměti je ta, která zakazuje nebo podporuje řešení, která obsahují určité atributy (např. Řešení, která obsahují nežádoucí nebo žádoucí hodnoty pro určité proměnné), nebo strukturu paměti, která brání nebo vyvolává určité pohyby (např. Na základě frekvenční paměti) aplikováno na řešení, která sdílejí společné rysy s neatraktivními nebo atraktivními řešeními nalezenými v minulosti). V krátkodobé paměti jsou vybrané atributy v nedávno navštívených řešeních označeny jako „tabu-active“. Řešení, která obsahují aktivní prvky tabu, jsou zakázána. Používají se aspirační kritéria, která přepisují stav tabu řešení, čímž se do povolené sady začlení i jinak vyloučené řešení (za předpokladu, že řešení je „dostatečně dobré“ podle míry kvality nebo rozmanitosti). Jednoduchým a běžně používaným aspiračním kritériem je umožnit řešení, která jsou lepší než aktuálně známé nejlepší řešení.


Samotná krátkodobá paměť může stačit k dosažení řešení, která jsou lepší než ta, která jsou nalezena konvenčními místními metodami vyhledávání, ale pro řešení těžších problémů jsou často nutné střednědobé a dlouhodobé struktury. Vyhledávání v Tabu je často srovnáváno s jinými metaheuristickými metodami - jako je simulované žíhání , genetické algoritmy , algoritmy optimalizace kolonií mravenců, optimalizace reaktivního vyhledávání, řízené místní vyhledávání nebo chamtivé randomizované adaptivní vyhledávání . Kromě toho je vyhledávání tabu někdy kombinováno s jinými metaheuristikami za účelem vytvoření hybridních metod. Nejběžnější hybridní vyhledávání tabu vzniká spojením TS s Scatter Search, třídou populačních procedur, které mají kořeny společné s vyhledáváním tabu a často se používají při řešení velkých problémů s nelineární optimalizací.

Pseudo kód

Následující pseudokód představuje zjednodušenou verzi vyhledávacího algoritmu tabu, jak je popsáno výše. Tato implementace má základní krátkodobou paměť, ale neobsahuje žádné mezilehlé ani dlouhodobé paměťové struktury. Pojem „vhodnost“ označuje hodnocení kandidátského řešení, jak je zakomponováno do objektivní funkce pro matematickou optimalizaci. 

sBest ← s0
bestCandidate ← s0
tabuList ← []
tabuList.push(s0)
while (not stoppingCondition())
    sNeighborhood ← getNeighbors(bestCandidate)
    bestCandidate ← sNeighborhood[0]
    for (sCandidate in sNeighborhood)
        if ( (not tabuList.contains(sCandidate)) and (fitness(sCandidate) > fitness(bestCandidate)) )
            bestCandidate ← sCandidate
        end
    end
    if (fitness(bestCandidate) > fitness(sBest))
        sBest ← bestCandidate
    end
    tabuList.push(bestCandidate)
    if (tabuList.size > maxTabuSize)
        tabuList.removeFirst()
    end
end
return sBest

Řádky 1-4 představují nějaké počáteční nastavení, respektive vytvoření počátečního řešení (případně náhodně zvoleného), nastavení tohoto počátečního řešení jako dosud nejlépe viděného a inicializace seznamu tabu s tímto počátečním řešením. V tomto příkladu je seznam tabu jednoduše struktura krátkodobé paměti, která bude obsahovat záznam prvků navštívených států.

Základní algoritmická smyčka začíná na řádku 5. Tato smyčka bude pokračovat v hledání optimálního řešení, dokud nebude splněna uživatelem stanovená podmínka zastavení (dva příklady takových podmínek jsou jednoduchý časový limit nebo prahová hodnota skóre fitness). Sousední řešení jsou zkontrolována pro prvky tabu na řádku 9. Algoritmus navíc sleduje nejlepší řešení v sousedství, které není tabu.

Fitness funkce je obecně matematická funkce, která vrací skóre nebo jsou splněna aspirační kritéria - například aspirační kritérium lze považovat za nalezený nový vyhledávací prostor). Pokud má nejlepší místní kandidát vyšší fitness hodnotu než aktuální nejlepší (řádek 13), je nastaven jako nový nejlepší (řádek 14). Nejlepší místní kandidát je vždy přidán do seznamu tabu (řádek 16) a pokud je seznam tabu plný (řádek 17), bude moci některým prvkům vypršet platnost (řádek 18). Obecně platí, že prvky ze seznamu vyprší ve stejném pořadí, v jakém jsou přidány. Postup vybere nejlepšího místního kandidáta (i když má horší kondici než sBest), aby unikl místnímu optimálnímu.

Tento proces pokračuje, dokud není splněno kritérium zastavení stanovené uživatelem, a poté je vráceno nejlepší řešení viděné během procesu vyhledávání (řádek 21).

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

Problém obchodního cestujícího (TSP) se někdy používá k zobrazení funkčnosti vyhledávání na tabu. Tento problém klade přímou otázku - vzhledem k seznamu měst, jaká je nejkratší trasa, která navštíví každé město? Pokud jsou například město A a město B vedle sebe, zatímco město C je dále, celková ujetá vzdálenost bude kratší, pokud budou města A a B navštěvována jeden po druhém před návštěvou města C. Od nalezení optimálního řešení je NP-tvrdý , heuristické aproximační metody (jako jsou místní vyhledávání) jsou užitečné pro navrhování téměř optimálních řešení. Pro získání dobrých řešení TSP je nezbytné využít strukturu grafů. Hodnota využití struktury problému je v metaheuristických metodách opakujícím se tématem a vyhledávání tabu se k tomu dobře hodí. Třída strategií spojených s vyhledáváním tabu zvaná metody ejekčního řetězce umožnila efektivně získat vysoce kvalitní řešení TSP

Na druhou stranu lze k nalezení uspokojivého řešení problému obchodního cestujícího použít jednoduché vyhledávání tabu (tj. Řešení, které splňuje kritérium přiměřenosti, i když ne s vysokou kvalitou získanou využitím struktury grafu). Hledání začíná počátečním řešením, které lze vygenerovat náhodně nebo podle nějakého algoritmu nejbližšího souseda . Chcete-li vytvořit nová řešení, vymění se pořadí návštěvy dvou měst v potenciálním řešení. Celková cestovní vzdálenost mezi všemi městy se používá k posouzení toho, jak ideální je jedno řešení ve srovnání s jiným. Aby se zabránilo cykly - tj opakované návštěvě konkrétní sadu řešení - a aby se nestali uvízl v místní optima , roztok se přidává do seznamu tabu, je-li přijat do okolí řešení, .

Nová řešení jsou vytvářena, dokud není splněno určité kritérium zastavení, například libovolný počet iterací. Jakmile se jednoduché vyhledávání tabu zastaví, vrátí nejlepší řešení nalezené během jeho provádění.

Reference

externí odkazy