I detta dokument presenteras de grundläggande principerna bakom tabu sökning som en strategi för kombinatoriska optimeringsproblem. Tabu sökande har uppnått imponerande praktiska framgångar i applikationer som sträcker sig från schemaläggning och datorkanalbalansering till klusteranalys och rymdplanering, och på senare tid har visat sitt värde i att behandla klassiska problem som resande säljare och graf färgproblem. Strategin är dock fortfarande i sin linda, och det återstår fortfarande en hel del att upptäcka om dess mest effektiva genomförandeformer och om det spektrum av problem som den är bäst lämpad för. I detta dokument åtar sig man att presentera de viktigaste idéerna och resultaten hittills och att ange utmaningar för framtida forskning. Del I i denna studie visar de grundläggande principerna, allt från korttidsminnesprocessen i kärnan av sökningen till de mellanliggande och långsiktiga minnesprocesserna för att intensifiera och diversifiera sökningen. Här ingår illustrativa datastrukturer för att genomföra de tabuvillkor (och tillhörande aspirationskriterier) som ligger till grund för dessa processer. Del I avslutas med en diskussion om probabilistisk tabusökning och en sammanfattning av beräkningserfarenhet för en mängd olika tillämpningar. Del I1 i denna studie (för att framträda i ett senare nummer) undersöker mer avancerade överväganden, tillämpar de grundläggande idéerna på speciella miljöer och beskriver en dynamisk rörelsestruktur för att försäkra ändlighet. Del I1 beskriver också tabu sökmetoder för att lösa problem med blandade heltal programmering och ger en kort sammanfattning av ytterligare praktisk erfarenhet, inklusive användningen av tabu sökning för att vägleda andra typer av processer, såsom de av neurala nätverk. T a b u sökning är en strategi för att lösa kombinatoriska optimeringsproblem vars tillämpningar sträcker sig från grafteori och matrisinställningar till allmänna rena och blandade heltal programmeringsproblem. Det är en adaptiv procedur med förmågan att använda sig av många andra metoder, såsom linjära programmeringsalgoritmer och specialiserade heuristiker, som den leder till att övervinna begränsningarna av lokal optimalitet. Tabu sökning har sitt ursprung i kombinatoriska förfaranden tillämpas på icke-linjära täcka problem i slutet av 1970~,[~1 och därefter tillämpas på en mångfald av problem som sträcker sig från schemaläggning och datorkanalbalansering till klusteranalys och rymdplanering."3.4,6.71 Senaste forsknings- och beräkningsjämförelser som involverar resande säljare, graffärgning, arbetsbutiksflöde sekvensering, integrerad kretsdesign och tidsingivande problem har också avslöjat förmågan av tabu sökning för att få högkvalitativa lösningar med blygsam beräkningsansträngning, allmänt dominerande alternativa metoder testade. ['. Det är ingen fara. - Jag vet inte. 12-13. En ny oberoende utveckling av flera av dess idéer [lol har också framgångsrikt tillämpats på maximal tillfredsställelse problem.[''] Sådana tillämpningar, för problem som varierar i storlek från hundratals till miljontals variabler, utarbetas i avsnitt 10.
Tabu search (TS) algoritm REF är en mycket speciell algoritm som vanligtvis används för att lösa kombinatoriska optimeringsproblem.
Tabu Search - Part I
{'venue': 'INFORMS J. Comput.', 'journal': 'INFORMS J. Comput.', 'mag_field_of_study': ['Computer Science']}