|
||
Metoda zakázaného prohledávání je další formou horolezeckého algoritmu. U horolezeckého algoritmu může dojít k zacyklení - po určitém počtu kroků se metoda vrací k lokálnímu extrému. Metoda zakázaného prohledávání se snaží předejít uvíznutí v lokálním extrému tím, že v algoritmu je udržována krátkodobá paměť.
V této paměti jsou ukládány inverzní transformace k transformacím použitým v předcházejících krocích. Zakázaný seznam transformací je omezen svou maximální velikostí. Jestliže transformace patří do zakázaného seznamu, pak se nemůže používat v lokální minimalizaci v rámci okolí aktuálního řešení. [12]
V našem případě bude výpočet všech bodů v okolí aktuálního řešení pomocí transformací nahrazen vygenerováním náhodných prvků v tomto okolí. Jedná se o to, že v případě, kdy jsou definičním oborem souřadnic rozhodovacích proměnných reálná čísla, by bylo časově náročné ohodnotit všechna řešení v okolí aktuálního řešení (prvku), pokud by simulační experiment trval dlouho.
Seznam zakázaných transformací bude v následujícím algoritmu obsahovat prvky, které již byly v posledních předchozích krocích vygenerovány, a tudíž nejsou akceptovány jako nové řešení.
Velikost seznamu zakázaných prvků ovlivňuje schopnost algoritmu vymanit se z lokálního optima. Pokud bude definována malá délka seznamu, může dojít k zacyklení algoritmu. Naproti tomu příliš velká délka seznamu může vést k přeskočení nadějných lokálních optim. [17]
Jedná se tedy o intenzifikaci (exploataci) a diverzifikaci (exploraci) algoritmu při vyhledávání globálního optima.
Stejně jako v případě horolezeckého algoritmu lze algoritmus spustit několikrát z náhodně vygenerovaných počátečních řešení. U této formy algoritmu lze využít k zaznamenání nalezených kvalitních řešení množinu optim. Jako výsledek bude namísto jednoho řešení poskytnuto několik řešení, ze kterých si uživatel vybere jemu nejvíce vyhovující.
TabuSearch - v počátku algoritmu (viz 
) je vygenerování počátečního přípustného řešení na základě rovnoměrného rozdělení - inicializace (řádek 2). Počáteční přípustné řešení je v této fázi algoritmu zároveň jediným dosud nalezeným nejlepším prvkem (řádek 3). Dalším krokem je vytvoření prázdného seznamu, který bude obsahovat specifikovaný počet přechozích zakázaných prvků (řádek 4). Délka tohoto seznamu bude udržována konstantní tím způsobem, že při dosažení nebo překročení délky seznamu (řádek 12), bude odstraněn první prvek (nejstarší prvek) tohoto seznamu (řádek 13). Generovaní nového prvku v okolí dosud nalezeného nejlepšího prvku (řádek 7) je prováděno pomocí mutace. Protože se mohlo stát, že nový prvek byl vygenerován mimo hranice prohledávaného prostoru, je užita opravná metoda, která zajistí přepočtem souřadnic rozhodovacích proměnných umístění prvku do prohledávaného prostoru (řádek 8). Pokud nový prvek byl již v předchozích krocích (je definováno, kolik předchozích kroků se má pamatovat) vygenerován, prvek je zamítnut a dochází k vygenerování dalšího prvku. Pokud nový prvek není nalezen v seznamu zakázaných prvků (řádek 9), je následně podroben srovnání, zda je lepší než dosud nejlepší nalezené řešení (řádek 10). Porovnání se děje na základě hodnoty účelové funkce u obou prvků. Pokud byl nový prvek lepší než nejlepší dosavadní nalezené řešení, je toto řešení nahrazeno novým prvkem (řádek 11). Nový prvek je poté zařazen do seznamu zakázaných prvků (řádek 14). Výsledkem poskytovaným algoritmem při splnění kritéria ukončení (řádek 6) je nalezený nejlepší prvek (řádek 17).
Zakázaný seznam se používá ke konstrukci modifikovaného sousedství, které neobsahuje řešení vzniklá zakázanými transformacemi. Výjimku tvoří aspirační kritérium (Aspiration Criterion) povolující zakázanou transformaci v případě, že by vzniklé sousední řešení poskytlo lepší hodnotu účelové funkce než dosud nejlepší řešení. [16]