Lokal sökning (tillfredsställelse av begränsningar)

För att tillfredsställa kraven är lokal sökning en ofullständig metod för att hitta en lösning på ett problem . Den bygger på att iterativt förbättra en tilldelning av variablerna tills alla begränsningar är uppfyllda. I synnerhet ändrar lokala sökalgoritmer vanligtvis värdet på en variabel i en tilldelning vid varje steg. Den nya uppgiften ligger nära den tidigare i uppdragsutrymmet, därav namnet lokal sökning .

Alla lokala sökalgoritmer använder en funktion som utvärderar kvaliteten på uppdraget, till exempel antalet begränsningar som tilldelningen bryter mot. Detta belopp kallas kostnaden för uppdraget. Syftet med lokal sökning är att hitta ett uppdrag med minimal kostnad, vilket är en lösning om det finns någon.

Punkt A är ingen lösning, men ingen lokal flytt därifrån minskar kostnaderna. Men det finns en lösning vid punkt B.

Det finns två klasser av lokala sökalgoritmer. Den första är den av giriga eller icke-randomiserade algoritmer. Dessa algoritmer fortsätter genom att ändra den nuvarande tilldelningen genom att alltid försöka minska (eller åtminstone inte öka) dess kostnad. Huvudproblemet med dessa algoritmer är den möjliga närvaron av platåer , som är regioner i tilldelningsutrymmet där inga lokala drag minskar kostnaderna. Den andra klassen av lokala sökalgoritmer har uppfunnits för att lösa detta problem. De flyr dessa platåer genom att göra slumpmässiga drag, och kallas slumpmässiga lokala sökalgoritmer.

giriga algoritmer

bergsklättring

Den mest grundläggande formen av lokal sökning bygger på att välja den förändring som maximalt minskar kostnaden för lösningen. Denna metod, som kallas hill climbing , fortsätter enligt följande: först väljs en slumpmässig uppgift; sedan ändras ett värde för att maximalt förbättra kvaliteten på den resulterande tilldelningen. Om ingen lösning har hittats efter ett givet antal ändringar väljs en ny slumpmässig uppgift. Algoritmer för bergsklättring kan bara undkomma en platå genom att göra ändringar som inte ändrar kvaliteten på uppdraget. Som ett resultat kan de fastna på en platå där kvaliteten på uppdraget har ett lokalt maxima.

GSAT (greedy sat) var den första lokala sökalgoritmen för tillfredsställelse, och är en form av bergsklättring.

Begränsningsviktning eller utbrytningsmetod

En metod för att fly från ett lokalt minimum är att använda en viktad summa av överträdda begränsningar som ett mått på kostnaden och att ändra vissa vikter när inget förbättrande drag är tillgängligt. Närmare bestämt, om ingen förändring minskar kostnaden för uppdraget, ökar algoritmen vikten av begränsningar som överträds av den aktuella tilldelningen.

På så sätt minskar varje rörelse som annars inte skulle förändra kostnaden för lösningen. Dessutom fortsätter vikten av begränsningar som förblir överträdda för ett stort antal drag att öka. Därför, under ett antal flyttningar som inte uppfyller en begränsning, fortsätter kostnaden för flyttningar till uppdrag som uppfyller denna begränsning att öka.

Tabu-sökning

En nackdel med bergsklättring med rörelser som inte minskar kostnaden är att det kan cykla över uppdrag till samma kostnad. Tabu-sökning övervinner detta problem genom att upprätthålla en lista med "förbjudna" tilldelningar, kallad tabulistan . I synnerhet innehåller tabulistan vanligtvis bara de senaste ändringarna. Mer exakt innehåller den det sista variabel-värdeparet så att variabeln nyligen har tilldelats värdet.

Denna lista uppdateras varje gång uppdraget ändras. Om en variabel tilldelas ett värde läggs variabel-värdeparet till i listan och det äldsta paret tas bort från det. På så sätt innehåller listan bara de senaste tilldelningarna till en variabel. Om ett variabel-värdepar finns i tabulistan, är det förbjudet att ändra den aktuella tilldelningen genom att ställa in variabeln till värdet. Algoritmen kan bara välja det bästa draget bland de som inte är förbjudna. På så sätt kan den inte cykla över samma lösning om inte antalet drag i denna cykel är större än längden på tabulistan.

En spontan promenad

En random walk -algoritm rör sig ibland som en girig algoritm men ibland rör sig slumpmässigt. Det beror på en parameter $p$ , som är ett reellt tal mellan 0 och 1. Vid varje drag, med sannolikhet ${\displaystyle p},$ fortsätter algoritmen som en girig algoritm, och försöker maximalt minska kostnaden för uppdrag. Med sannolikhet $1-p$ ändras dock lösningen på något annat sätt, vilket innebär en viss grad av slumpmässighet.

WalkSAT

Det slumpmässiga draget av WalkSAT ändrar värdet på en slumpvariabel av en slumpmässig överträdd begränsning. För propositionell tillfredsställelse av konjunktiva normalformsformler , som är de ursprungliga inställningarna för denna algoritm, ändrar varje sådan rörelse värdet på variabeln från sant till falskt eller vice versa, och producerar tillfredsställelsen av den överträdda begränsningen. Som för alla slumpmässiga vandringsstrategier, görs ett slumpmässigt drag endast med en given sannolikhet, och ett drag som maximalt minskar kostnaden görs annars.

Simulerad glödgning

Tekniken för simulerad glödgning är baserad på att ändra sannolikheten för att göra en slumpmässig rörelse över en som maximalt minskar kostnaden. Namnet kommer i synnerhet från strategin att minska sannolikheten för att göra slumpmässiga rörelser under exekveringen av algoritmen, och därmed praktiskt taget "frysa" sökutrymmet.

I synnerhet, om förbättringen av kostnaden $d$ för ett drag är negativ (flytten ökar kostnaden), görs detta drag med sannolikhet $e^{-d\cdot T}$ , där $T$ är ett reellt tal. Eftersom sannolikheten för att göra detta drag ökar med $T$ kallas denna parameter temperaturen . Simulerad glödgning minskar denna temperatur över tiden, vilket möjliggör fler slumpmässiga rörelser i början och mindre efter tiden.

Lokal sökning på en cykel cutset

Lokal sökning fungerar vanligtvis på alla variabler, vilket förbättrar en komplett tilldelning till dem. Lokal sökning kan dock också köras på en delmängd av variabler, med någon annan mekanism för de andra variablerna. En föreslagen algoritm fungerar på en cycle cutset , som är en uppsättning variabler som, om den tas bort från problemet, gör den acyklisk.

För varje tilldelning av variablerna i skäruppsättningen har det återstående problemet en skog som primalgraf. Som ett resultat kan det lösas effektivt. För att styra lokal sökning används en algoritm som upptäcker det minimala antalet begränsningar som kan överträdas i stället för en tillfredsställbarhetsalgoritm för skogsdelen av problemet.

Detta minimala antal hittas genom att bestämma kostnaden för varje variabeluppdrag. Denna kostnad är det minimala antalet begränsningar som överträds av en tilldelning av variablerna i underträdet med rötter i variabeln, när variabeln tar det givna värdet. Denna kostnad kan beräknas enligt följande. Om $Cost(x=a)$ anger kostnaden för uppdraget $x=a$ och $y_{1 },\ldots ,y_{n}$ är barn till $x$ , följande formel gäller. I denna formel $Violates(x=a,y_{i}=b)$ 0 eller 1 beroende på om tilldelningen $x=a,y_{i}=b$ bryter mot begränsningen mellan $x$ och $y$ .

Cost(x=a)=\sum _{i=1,\ldots ,n}\min _{y_{i}=b}(Kostnad(y_{i}=b)+Brott (x=a,y_{i}=b))

Kostnaden för variabler i cutsetet är noll, och dessa variabler antas endast få ta sitt givna värde. Med dessa antaganden tillåter ovanstående formel att beräkna kostnaden för alla variabla utvärderingar genom att iterativt fortsätta nerifrån och upp från löven till skogens rötter.

Kostnaden för variabel utvärdering kan användas av lokal sökning för att beräkna kostnaden för en lösning. Kostnaden för värden på skogens rötter är verkligen det minimala antalet överträdda begränsningar i skogen för dessa givna värden. Dessa kostnader kan därför användas för att utvärdera kostnaden för tilldelningen till cutset-variablerna och för att uppskatta kostnaden för liknande uppdrag på cutset-variablerna.

externa länkar

Forcerad tillfredsställande CSP och SAT Benchmarks av modell RB

Dechter, Rina (2003). Constraint Processing . Morgan Kaufmann. ISBN 978-1-55860-890-0 .