Tabu search

Tabu search is een meta-heuristiek optimalisatiealgoritme bedacht door Fred Glover. Het is gebaseerd op Steepest descent algoritme en het taboe verklaren van eerder bezochte oplossingen van het probleem. Het grote verschil met de Steepest descent algoritme is dat Tabu search voor de volgende iteratie niet alleen betere, maar ook een slechtere oplossing mag kiezen. Verder kan Tabu search door oplossingen taboe te verklaren aan lokale minima ontsnappen.

Pseudo-code

Kies een initiële oplossing en bepaal hoe goed die oplossing is

Herhaal

Bepaal de naburige oplossingen die niet taboe zijn en bepaal hoe goed deze zijn

Kies de beste naburige oplossing en plaats de vorige oplossing in de Tabu lijst

Als de nieuwe oplossing beter is onthoud dan de nieuwe oplossing

Tot de stop-conditie vervuld is

Initialisatie

De initiële oplossing wordt willekeurig gekozen of een specifieke oplossing die al een redelijk resultaat geeft, bijvoorbeeld de beste oplossing verkregen met genetisch algoritme of simulated annealing.

Tabu lijst

Er zijn twee verschillende manieren om een vorige oplossing taboe te verklaren. Een daarvan is om bij te houden welke oplossingen Tabu search allemaal al gekozen heeft. Het grote nadeel van deze methode is dat het veel opslagruimte vergt en slechts een oplossing per keer taboe maakt.

Een veel gebruikte methode is een Tabu lijst gebaseerd op recentelijke veranderingen. In deze Tabu lijst worden de verschillen tussen twee opeenvolgende oplossingen voor een bepaald aantal iteraties opgeslagen. Het idee hierachter is dat wanneer het algoritme een bepaalde stap heeft genomen in de oplossingsruimte die (zeer) voordelig was en dat daarom in de nabije toekomst deze stap waarschijnlijk niet ongedaan gemaakt hoeft te worden. Het is daarom niet noodzakelijk om de buuroplossing verkregen door een van de stappen in de Tabu lijst te nemen in een van de volgende iteraties, wat weer rekentijd scheelt. Het nadeel van deze methode is echter dat je een extra parameter krijgt: de lengte van de Tabu lijst. Als deze te lang wordt gekozen dan kan Tabu search geen naburige oplossingen vinden en zal het termineren met een redelijk slechte oplossing. Als het echter te kort gekozen wordt dan zal Tabu search rondom een lokaal minimum blijven hangen.

Terminatie criterium

Er kunnen verschillende criteria gebruikt worden om te termineren. Enkele veel gebruikte terminatie-condities zijn onder meer:

Alle naburige oplossingen zijn taboe verklaard; Hierdoor is er geen set meer met probeer-oplossingen;
Vast aantal iteraties;
De best gevonden oplossing tot nu toe is een lange tijd niet meer verbeterd;
Budget: toegewezen computer tijd/geld verbruikt;
Een combinatie van bovenstaande condities.

Uitbreidingen

Er zijn verschillende uitbreidingen op de standaard Tabu search, waaronder:

diversificatie
intensivering
reactieve Tabu search

Diversificatie

Het grootste nadeel van standaard Tabu search is dat het een lokale methode is. Hierdoor kan een groot deel van de oplossingsruimte genegeerd worden. Met diversificatie wordt bij gehouden welk deel van de oplossingsruimte bezocht is. Wanneer Tabu search getermineerd is, wordt er een nieuwe oplossing gekozen in dat deel van de oplossingsruimte wat nog niet doorzocht is. Dit kan herhaald worden herhaald. Diversificatie maakt van Tabu search dat het een globale optimalisatie algoritme wordt.

Intensivering

Bij intensivering wordt er gekeken welke stappen Tabu search maakt gedurende verschillende iteraties of runs. Als blijkt dat een bepaalde stap in de oplossingruimte vaak gemaakt wordt dan kan dat aangeven dat de oplossing verkregen door het maken van die stap over het algemeen goed is. Deze stap zal, als dat kan, voortaan eerder genomen worden.

Reactieve Tabu search

Tabu search is een algoritme waar de oplossingsruimte niet verandert in de tijd. In de praktijk zijn er echter verschillende problemen waarbij de oplossingsruimte in de tijd wel verandert. Reactieve Tabu search is een uitbreiding van Tabu Search die het mogelijk maakt om Tabu search te gebruiken bij veranderende oplossingruimtes. Dit wordt gedaan door de verschillende parameters, zoals de lengte van de Tabu lijst, dynamisch aan te passen door een simpel feedback schema te gebruiken.

Bronnen, noten en/of referenties

F.W. Glover. Tabu Search - part i. Orsa Journal on Computing, 1(3):190, 1989.
F.W. Glover. Tabu Search - part ii. Orsa Journal on Computing, 2(1):4, 1990.
Alain Hertz, Eric Taillard, Dominique de Werra. A tutorial on Tabu Search. Hier: [1]