Søg med forbud

Tabusøgning eller tabusøgning er en metasøgningsalgoritme, der bruger lokale søgemetoder , der bruges til matematisk optimering . Algoritmen blev skabt af Fred W. Glover i 1986 [1] og formaliseret i 1989 [2] [3]

Lokal søgning (af naboer) tager en potentiel løsning på et problem og tjekker dens umiddelbare naboer (det vil sige løsninger, der ligner hinanden bortset fra nogle få meget små detaljer) i håb om at finde en forbedret løsning. Lokale søgemetoder har en tendens til at sidde fast i suboptimale regioner eller plateauer, hvor mange løsninger er lige velegnede.

Afvist søgning forbedrer ydeevnen af ​​lokal søgning ved at slække på dens grundlæggende regel. For det første kan forringelse antages på hvert trin, hvis der ikke er nogen forbedring (svarende til tilfældet, hvor søgningen sætter sig fast på et lokalt minimum ). Derudover indføres forbud (alias tabuer ) for at forhindre søgningen efter løsninger, der allerede er besøgt.

Implementeringen af ​​deny search bruger strukturer, der beskriver besøgte beslutninger eller brugerregelsæt [2] . Hvis en potentiel løsning er blevet besøgt i løbet af en kort periode, eller den overtræder en regel, markeres den som " tabu ", så algoritmen ikke genovervejer løsningen.

Ordet tabu kommer fra et tongansk ord, der betyder ting, der ikke bør røres, fordi de er hellige [4] .

Tabu-søgning er en meta-algoritme , der kan bruges til at løse kombinatoriske optimeringsproblemer (problemer, hvor du skal finde den optimale rækkefølge og valg af muligheder).

Nuværende spærrede søgningsapplikationer strækker sig til områder som ressourceplanlægning , telekommunikation, VLSI-teknik , finansiel analyse, planlægning, fysisk planlægning, energidistribution, molekylær konstruktion, logistik, mønsterklassificering , fleksibel fremstilling, affaldshåndtering, mineralprospektering, biomedicinsk analyse, miljøbeskyttelse og mange andre. I de senere år har tidsskrifter inden for mange videnskabsområder offentliggjort akademiske artikler og beregningsstudier, der viser tabubesøgningens succes med at udvide grænserne for problemer, der kan løses effektivt, hvilket giver løsninger, der ofte er langt bedre i kvalitet end dem, der er opnået med hidtil metoder . En omfattende liste over applikationer, herunder et resumé af resultatet opnået ved praktisk anvendelse, kan findes i artiklen af ​​Glover og Laguna [5] . Moderne tabubelagte søgeudviklinger og applikationer kan findes i artiklen Tabu Search Vignettes .

Grundlæggende

Tabu-søgning bruger en lokal søgning eller nabosøgningsprocedure til iterativt at flytte fra en potentiel løsning til en bedre løsning i nabolaget, indtil et eller andet stopkriterium er opfyldt (normalt antallet af iterationer eller en målscoretærskel). Lokale søgerutiner sætter sig ofte fast i områder med dårlige målskøn eller i områder, hvor estimatet danner et plateau (glat vandret overflade). For at undgå disse faldgruber og udforske områder af søgeområdet, som ville blive efterladt uudforsket af andre søgeprocedurer, undersøger tabusøgning omhyggeligt området omkring hver løsning i søgeprocessen. Løsningerne genkendt af de nye naboer, , bestemmes ved hjælp af strukturer i hukommelsen. Ved at bruge disse strukturer skrider søgningen frem ved iterativt at flytte fra den aktuelle løsning til den forbedrede løsning fra listen .

Disse strukturer danner såkaldte tabulister, et sæt regler og mærkede løsninger, der bruges til at filtrere, hvilke naboløsninger, der skal behandles, når der søges. I sin enkleste form er en tabuliste et kortsigtet sæt af beslutninger, der er blevet besøgt i de sidste iterationer (mindre end iterationer, hvor det svarer til antallet af huskede beslutninger, og dette tal kaldes tabubelagt levetid). Oftere består tabulisten af ​​beslutninger, der er blevet ændret i processen med at flytte fra en beslutning til en anden. Det er praktisk for at lette præsentationen at forstå "løsningen", der er kodet og repræsenteret af nogle attributter.

Hukommelsestyper

Hukommelsesstrukturerne brugt i tabusøgning kan groft opdeles i tre kategorier [6] :

Kort-, mellem- og langsigtede lister kan overlappe hinanden. Inden for disse kategorier kan hukommelsen differentieres yderligere ved kriterier såsom hyppigheden og virkningen af ​​de foretagne ændringer. Et eksempel på en struktur på mellemlang sigt er forbuddet eller opmuntringen af ​​beslutninger, der indeholder nogle attributter (f.eks. beslutninger, der inkluderer uønskede eller ønskværdige værdier af nogle bestemte variabler) eller en hukommelsesstruktur, der forhindrer eller genererer nogle bevægelser (f.eks. , baseret på hyppigheden af ​​forekomst af funktioner i potentielle og ikke-lovende løsninger fundet tidligere). I korttidshukommelsen er udvalgte attributter i nyligt besøgte løsninger markeret som "tabu-aktive". Det er forbudt at bruge løsninger med tabu-aktive elementer. For at ændre tabubelagt status for en løsning anvendes et fjernelseskriterium, inklusive de udelukkede løsninger på den tilladte liste (løsningen er "god nok" i henhold til mål for kvalitet eller forskel). Et simpelt og almindeligt anvendt fjernelseskriterium er at tillade brug af løsninger, der er bedre end den aktuelt kendte bedste løsning.

Korttidshukommelsen alene kan være tilstrækkelig til at producere en løsning, der er bedre end den, der findes ved konventionelle lokale søgemetoder, men mellemlange og langsigtede strukturer er ofte nødvendige for at løse mere komplekse problemer [7] . Tabu-søgning sammenlignes ofte med andre meta-algoritmiske metoder såsom simuleret annealing -algoritme , genetiske algoritmer , myrekoloni-algoritmer , reaktiv søgning, overvåget lokal søgning eller grådig adaptiv tilfældig søgning . Derudover kombineres tabusøgning nogle gange med andre metaalgoritmer for at skabe hybride metoder. Den mest almindelige tabby-søgningshybrid opstår ved at parre den med scatter-søgning [  8 ] [ 9] , en klasse af procedurer, der har fælles rødder med tabusøgning og ofte bruges til at løse ikke-lineære optimeringsproblemer i stor skala.

Pseudokode

Den følgende pseudokode repræsenterer en forenklet version af tabu-søgealgoritmen som beskrevet ovenfor. Denne implementering har den enkleste version af korttidshukommelse og indeholder ikke mellem- eller langsigtede strukturer. Udtrykket "fitness" refererer til beregningen af ​​en objektiv funktion for en kandidatløsning.

sBest ← s0 bedste kandidat ← s0 tabulist ← [] tabulist . tryk ( s0 ) while ( not stoppingCondition ()) sNeighborhood ← getNeighbors ( bestCandidate ) for ( sCandidate in sNeighborhood ) if ( ( ikke tabuList . indeholder ( sCandidate )) og ( fitness ( sCandidate ) > fitness ( bestCandidate )) ) bestCandidate ← sCandidate ende ende if ( fitness ( bestCandidate ) > fitness ( sBest )) sBedste ← bedstekandidat ende tabulist . push ( bedste kandidat ) if ( tabuList . størrelse > maxTabuSize ) tabulist . fjern først () ende ende returner sBest

Linje 1-4 laver indledende opgaver, laver en indledende løsning (måske opnået ved tilfældige søgemetoder), indstiller den resulterende løsning som den første, der blev set på, og initialiserer tabulisten med denne løsning. I dette eksempel er tabulisten kun en kortvarig struktur, der indeholder en registrering af de besøgte genstande.

Hovedsløjfen starter ved linje 5. Denne løkke fortsætter med at søge efter den bedste løsning, indtil den når et brugerspecificeret stopkriterium (to eksempler på et sådant kriterium er blot en tidsbegrænsning eller en fitnessscoretærskel). Naboløsninger tjekkes for tabuer i linje 8. Derudover gemmer algoritmen de bedste ikke-forbudte løsninger af naboer.

Fitness objektivfunktionen er normalt en matematisk funktion, der returnerer en målscore eller et kriterium - for eksempel kan det at finde et nyt søgerum [4] betragtes som målkriteriet . Hvis den bedste lokale kandidat har en højere fitnessværdi, så er den aktuelle værdi den bedste (linje 12), den accepteres nu som den bedste (linje 13). Den lokale bedste kandidat tilføjes altid til tabulisten (linje 15), og hvis tabulisten er fuld (linje 16), anses et elements tabu for at være udløbet (linje 17). Typisk fjernes elementer fra listen i den rækkefølge, de blev tilføjet til den. Proceduren vælger den bedste lokale kandidat (selvom den har en dårligere fitnessværdi end sBest) for at springe ud af det lokale optimum.

Denne proces fortsætter, indtil et brugerdefineret stopkriterium er opnået, på hvilket tidspunkt den bedste løsning, der er stødt på i processen, returneres (linje 20).

Eksempel: problemet med den rejsende sælger

Problemet med den rejsende sælger bruges nogle gange til at vise, hvordan en tabubelagt søgning fungerer [7] . Dette problem spørger, givet en liste over byer, hvad er den korteste vej til at besøge alle byerne? For eksempel, hvis by A og by B ligger tæt på hinanden, men by C er langt væk fra hinanden, bliver den samlede rutelængde kortere, hvis vi først besøger A og B og derefter går til by C. at finde den optimale løsning er NP-hård , heuristisk-baserede tilnærmelsesmetoder (såsom lokal søgning) er nyttige til at opnå en næsten optimal løsning. For at få gode løsninger på det rejsende sælgerproblem er det vigtigt at undersøge grafens struktur. Værdien af ​​problemstrukturudforskning er et tilbagevendende tema i metaalgoritmiske metoder, og tabusøgning er velegnet til dette. Klassen af ​​strategier forbundet med tabubelagte søgninger og kaldet ejection  chain-metoder gør det muligt at opnå højkvalitetsløsninger på det rejsende sælgerproblem effektivt [10] .

På den anden side kan simpel tabusøgning bruges til at finde en tilfredsstillende løsning på det rejsende sælgerproblem (altså en løsning, der opfylder fitnesskriteriet, dog af lav kvalitet, som opnås efter at have undersøgt grafens struktur) Søgningen begynder med en indledende løsning, som kan opnås tilfældigt eller i henhold til en slags nærmeste nabo-algoritme . For at skabe nye løsninger byttes rækkefølgen, som byerne besøges i, i den potentielle løsning. Den samlede ruteafstand mellem alle byer bruges til at sammenligne, hvor meget bedre en løsning er end en anden. For at forhindre looping, det vil sige genindhentning af et bestemt sæt af løsninger, og sidde fast i det lokale optimum , tilføjes en løsning til listen over forbudte løsninger, hvis den accepteres ved søgning blandt naboer, .

Der skabes nye løsninger, indtil vi når et stopkriterium, såsom antallet af iterationer. Så snart den simple tabusøgning stopper, returnerer den den bedste løsning, den fandt under udførelsen.

Noter

  1. ↑ Glover, 1986 , s. 533-549.
  2. ↑ 1 2 Glover, 1989 , s. 190-206.
  3. ↑ Glover, 1990 , s. 4-32.
  4. ↑ 1 2 Kurser | Fuzzy-Neural Group | NC stat ISE . Hentet 16. januar 2019. Arkiveret fra originalen 12. januar 2014.
  5. ↑ Glover, Laguna, 1997 .
  6. ↑ Glover/A Tutorial, 1990 .
  7. ↑ 1 2 Malek, Huruswamy, Owens, Pandya, 1989 .
  8. ↑ Glover, Laguna, Marti, 2000 , s. 653-684.
  9. ↑ Laguna, Marti, 2003 .
  10. ↑ Gamboa, Rego, Glover, 2005 , s. 154-171.

Litteratur

  • Fred Glover. Fremtidige veje til heltalsprogrammering og links til kunstig intelligens // Computere og operationsforskning. - 1986. - T. 13 , no. 5 . - doi : 10.1016/0305-0548(86)90048-1 .
  • Fred Glover. Tabu Search – Del 1 // ORSA Journal on Computing. - 1989. - Vol. 1 , udgave. 2 . - doi : 10.1287/ijoc.1.3.190 .
  • Fred Glover. Tabu Search – Del 2 // ORSA Journal on Computing. - 1990. - Vol. 2 , udgave. 1 . - doi : 10.1287/ijoc.2.1.4 .
  • Gamboa D., Rego C., Glover F. Datastrukturer og udstødningskæder til løsning af problemer med rejsende sælger i stor skala // European Journal of Operational Research. - 2005. - T. 160 , no. 1 . - doi : 10.1016/j.ejor.2004.04.023 .
  • Glover F., Laguna M. Tabu Search. — Kluwer Academic Publishers. – 1997.
  • Fred Glover. Tabu Search: A Tutorial // Interfaces. - 1990.
  • Malek M., Huruswamy M., Owens H., Pandya M. Serielle og parallelle søgeteknikker til problemet med rejsende sælger. Annals of OR: Forbindelser med kunstig intelligens. – 1989.
  • Glover F., Laguna M., Marti R. Fundamentals of Scatter Search and Path Relinking. — Kontrol og kybernetik. - 2000. - T. 29. - S. 653-684.
  • Laguna M., Marti R. Scatter Search: Methodology and Implementations in C. - Kluwer Academic Publishers, Boston. – 2003.

Links