Administreret lokal søgning

Guided Local Search ( GLS ) er en metaheuristisk  søgemetode , det vil sige en metode oven på den lokale søgealgoritme for at ændre dens adfærd.

Guidet lokal søgning bygger sanktioner under søgningen og bruger dem til at hjælpe lokale søgealgoritmer med at komme væk fra lokale minimumskrav og (næsten) horisontale områder. Når den lokale søgealgoritme rammer et lokalt minimum, ændrer GLS objektivfunktionen med et særligt skema (forklaret nedenfor). Den lokale søgning arbejder så på denne øgede objektive funktion, som er konstrueret til at tage den ud af det lokale optimum. Nøglespørgsmålet er, hvordan man ændrer den objektive funktion.

Guidet lokal søgning blev foreslået af  Voudouris og Tsang [1] .

Oversigt

Løsningsegenskaber

For at anvende GLS skal løsningsegenskaber defineres for et givet problem. Løsningsegenskaber er defineret for at skelne mellem løsninger med forskellige karakteristika, så områder med lighed omkring det optimale kan genkendes og udelukkes. Valget af løsningsegenskaber afhænger af typen af ​​problem og også af søgealgoritmer. For hver ejendom er der defineret en prisfunktion .

Hver ejendom er forbundet med en straf (i første omgang 0), der repræsenterer antallet af gange, ejendommen rammer det lokale minimum.

Egenskaber og priser kommer ofte lige sammen med den objektive funktion. For eksempel i problemet med rejsende sælger kan "ruten fra by X går direkte til by Y" opfattes som en ejendom. Afstanden mellem X og Y kan defineres som prisen. I SAT- og vægtede MAX-SAT- problemer egenskaber være "udsagn C opfylder de aktuelle variabeltildelinger".

På implementeringsniveau definerer vi for hver ejendom en karakteristisk funktion , der angiver, om ejendommen er til stede i den aktuelle løsning eller ej. er 1, hvis løsningen indeholder egenskaben , ellers 0.

Selektive strafændringer

GLS beregner brugsbøder for hver ejendom. Når den lokale søgealgoritme returnerer det lokale minimum x, straffer GLS alle de egenskaber (ved at øge ejendomsstraffen), der findes i løsningen, og som har den maksimale nytteværdi som defineret nedenfor.

Ideen er at straffe ejendomme, der har høje priser, selvom nytten af ​​at gøre det falder, når ejendommen straffes ofte.

Finde en forøget omkostningsfunktion

GLS bruger omkostningsfunktionsforøgelse (defineret nedenfor) for at tillade kontrol af den lokale søgealgoritme at komme ud af det lokale minimum ved at straffe de egenskaber, der er repræsenteret i det lokale minimum. Tanken er at gøre det lokale minimum dyrere end det omkringliggende søgerum, hvor disse ejendomme ikke er til stede.

Parameteren kan bruges til at ændre intensiteten af ​​søgningen efter løsninger. Højere værdier vil resultere i en bredere søgning, hvor vandrette områder og dale bliver set mere groft. En lav værdi vil resultere i en mere detaljeret søgning i vandrette områder og dale. Koefficienten bruges til at gøre strafdelen af ​​den objektive funktion mere afbalanceret med hensyn til ændringer i den objektive funktion, og afhænger af opgaven. En simpel heuristik til tildeling er blot at registrere den gennemsnitlige ændring i objektivfunktionen op til det første lokale minimum og derefter indstille til denne værdi divideret med antallet af GLS-egenskaber i problemet.

Administrerede lokale søgeudvidelser

Mills (2002) beskrev en udvidet guidet lokal søgning (EGLS), der bruger tilfældige bevægelser og et brugskriterium specifikt designet til strafbaserede ordninger. Den resulterende algoritme forbedrer stabiliteten af ​​GLS med hensyn til parameterspredning, især i tilfælde af et kvadratisk tildelingsproblem . En større version af GLS-algoritmen, der bruger minimal konfliktstigning [2] og delvist er baseret på GENET til tilfredsstillelse og optimering af begrænsninger, blev implementeret i projektet Computer Aided Constraint Programming .

Alsheddy (2011) udvidede guidet lokal søgning efter multiobjektiv optimering og demonstrerede dens brug i planlægningen.

Relaterede værker

GLS blev bygget på GENET-systemet udviklet af Chang Wang, Edward Tsang og Andrew Davenport.

Breakout-metoden ligner meget GENET. Det blev designet til at opfylde begrænsningerne i [3] [4] .

Afvist søgning er en klasse af søgemetoder, der kan implementeres til specifikke metoder. GLS kan opfattes som et særligt tilfælde af tabusøgning .

Ved at bruge GLS oven på en genetisk algoritme introducerede Tung-leng Lau Guided Genetic Programming (GGA) .  Det er med succes blevet anvendt til generel tildeling (til tidsplaner), processorkonfiguration og RF-tildeling (militær).

Choi, Lee og Stucky [5] præsenterede GENET som en lagrangiansk søgning.

Noter

  1. ↑ Skobtsov og Fedorov ( Skobtsov, Fedorov 2013 , 28) henviser til artiklen ( Voudouris 29-39), selvom Tsang selv skriver:,, Tsang 2001 Startende med GENET udviklede vi mange mellemliggende algoritmer såsom Tunneling Algorithm og endte med den administrerede lokale søgealgoritme, der præsenteres i denne artikel." Vi taler om en artikel fra 1995 ( Voudouris, Tsang 1995 )
  2. ↑ Minton, Johnston, Philips, Laird, 1992 , s. 161-205.
  3. ↑ Yokoo, Hirayama, 1996 , s. 401-408.
  4. ↑ Zhang, Wittenborg, 2002 .
  5. ↑ Choi, Lee, Stuckey, 2000 , s. 1-39.

Litteratur

Links