Sök genom att klättra till toppen

Att klättra till toppsökningen (hädanefter kallad klättring) är en matematisk optimeringsteknik som tillhör den lokala sökalgoritmfamiljen . Algoritmen är en iterativ metod som börjar med en godtycklig lösning på problemet, och sedan försöker hitta den bästa lösningen genom att ändra ett av elementen i lösningen steg för steg Om lösningen ger en bättre lösning görs en ökning för att få en ny lösning, och det görs tills vi når en punkt där ingen förbättring kan hittas.

Till exempel kan klättring användas för att lösa problemet med resande försäljare . Det är lätt att hitta en initial lösning där säljaren besöker alla platser, men som sannolikt är mycket dålig jämfört med den optimala lösningen. Algoritmen börjar med detta beslut och gör små ändringar i beslutet som ändrar ordningen i vilken de två platserna besöks. I slutändan kommer troligen en betydligt kortare väg att hittas.

Klättring hittar optimala lösningar i konvexa programmeringsproblem , för andra problem hittar algoritmen bara ett lokalt optimum (en lösning som inte kan förbättras genom att flytta till angränsande noder), vilket inte nödvändigtvis är den bästa lösningen ( globalt optimum ) av alla möjliga lösningar inom ( domäner av tillåtna lösningar ). Exempel på algoritmer som löser konvexa problem genom vertexsökning inkluderar simplexmetoden för linjär programmering och binär sökning [1] . Som ett försök att övervinna att fastna i ett lokalt optimum kan du försöka starta sökningen igen (dvs. upprepa den lokala sökningen) eller använda mer komplexa scheman baserade på iteration (som i iterativ lokal sökning ), minneslagring (som i passiv sökning och tabusökning ), eller mindre memorerade stokastiska algoritmmodifikationer (som simulerad glödgning ).

Algoritmens relativa enkelhet gör algoritmen populär bland optimeringsalgoritmer. Det används ofta inom artificiell intelligensteori för att nå ett måltillstånd från en utgångspunkt. Metoden för att välja nästa punkt och startpunkt kan variera, vilket ger ett antal relaterade algoritmer. Medan mer avancerade algoritmer som simulerad glödgning eller tabusökning kan ge bättre resultat, fungerar klättring lika bra i vissa situationer. Klättring presterar ofta bättre än andra algoritmer när söktiden är begränsad, vilket är viktigt i realtidssystem, förutsatt att ett litet antal steg konvergerar till en bra lösning (till det optimala eller nära det). Ett annat extremfall, bubble sort , kan ses som en stigande algoritm (varje permutation av angränsande element minskar antalet oordnade par), och detta tillvägagångssätt är långt ifrån optimalt även för litet N, eftersom antalet permutationer växer kvadratiskt.

Klättring är en tidsbesparande algoritm - den returnerar en giltig lösning även om den avbryts när som helst.

Matematisk beskrivning

Klättring försöker maximera (eller minimera) den objektiva funktionen , där är en vektor av kontinuerliga och/eller diskreta värden. Vid varje iteration justerar uppstigningen ett element och avgör om de gjorda korrigeringarna förbättrar värdet eller inte. (Observera att detta skiljer sig från metoder för gradientnedstigning , som korrigerar alla element i vektorn vid varje iteration enligt uppgraderingen.) Stigande, alla förändringar som förbättras accepteras och processen fortsätter tills vi når en punkt där ingen förbättring kan hittas i . Då säger vi att det är ett "lokalt optimum". $f(\mathbf{x})$ $\mathbf {x}$ $\mathbf {x}$ $f(\mathbf{x})$ $\mathbf {x}$ $f(\mathbf{x})$ $f(\mathbf{x})$ $\mathbf {x}$

I diskreta vektorrum kan alla möjliga värden representeras som en vertex i en graf . Klättring genomkorsar grafen från vertex till vertex, alltid lokalt att öka (eller minska) värdet på funktionen tills ett lokalt maximum (eller lokalt minimum ) nås . $\mathbf {x}$ $f(\mathbf{x})$ $x_{m}$

Alternativ

Enkel uppstigning väljer den första noden i riktning mot vertexet, medan den brantaste uppstigningen jämför alla avkomlingar och väljer noden närmast vertexet. Båda formerna misslyckas om det inte finns någon nod att klättra på, vilket kan hända om det finns ett lokalt maximum som inte är en lösning. Den snabbaste uppstigningen liknar den bästa först-sökningen , som itererar över alla möjliga förlängningar av den aktuella banan, inte bara en.

Climb random search kontrollerar inte alla närliggande noder innan du väljer ett drag. Istället väljs en grannod slumpmässigt och ett beslut fattas (baserat på den förbättring som den granne ger) om man ska flytta mot den noden eller kontrollera en annan nod.

Koordinatnedstigning utför en linjär sökning längs en koordinat från den aktuella punkten vid varje iteration. Vissa varianter av koordinatnedstigning väljer en koordinatriktning slumpmässigt vid varje iteration.

Slumpmässigt återupptagande av uppstigning är en metaalgoritm som byggs ovanpå uppstigningsalgoritmen. Det är också känt som Shotgun Hill-klättring . Algoritmen utför uppstigningen iterativt, varje gång den väljer en slumpmässig initial . Det bästa värdet sparas och om ett nytt klättringsförsök ger ett bättre värde än det memorerade, ersätter det det memorerade tillståndet. $x_{0}$ $x_{m}$ $x_{m}$

Att slumpmässigt återuppta klättring är i många fall en förvånansvärt effektiv algoritm. Det visar sig att det ofta är mer effektivt att spendera CPU-resurser på att utforska utrymmet istället för att noggrant optimera från det ursprungliga tillståndet.

Uppgifter

Lokala maxima

Klättring kommer inte nödvändigtvis att hitta ett globalt maximum, det kan leda till ett lokalt maximum . Det här problemet uppstår inte om funktionen är konvex. Men eftersom inte alla funktioner är konvexa, kanske stigningen inte hittar ett globalt maximum. Andra lokala sökalgoritmer försöker övervinna detta problem, som slumpmässig vertexsökning slumpmässiga vandringar och simulerad glödgningsalgoritm .

Områden och raviner

Åsar är ett svårt problem att bestiga när man optimerar i kontinuerligt utrymme. Eftersom uppstigningen endast ändrar ett element i vektorn åt gången, övergår varje steg endast i riktningen för de numeriska axlarna. Om objektivfunktionen bildar en smal ås som ökar i en annan riktning än koordinataxlarna (vid minimering bildar funktionen en smal klyfta som minskar i en annan riktning än koordinataxlarna), så kan stigningen sicksacka uppåt ås (eller nedför ravinen). Om sidorna av åsen (eller ravinen) är mycket branta kan stigningen tvingas ta mycket små sicksacksteg, vilket kan göra att det tar onödigt lång tid att klättra längs åsen (eller nerför ravinen).

Gradientnedstigningsmetoder kan å andra sidan röra sig i den riktning som en ås reser sig eller en ravin går ner. Därför kommer gradientnedstigning eller konjugatgradientmetoden att vara mer att föredra om den objektiva funktionen är differentierbar. Klättring har dock fördelen att det inte kräver differentierbarhet, så klättring kan vara att föredra när den objektiva funktionen är komplex.

Platå

Ett annat problem som ibland uppstår vid klättring är en platå. En platå uppstår när ytan är tillräckligt platt så att de objektiva funktionsvärdena inte går att skilja från värdena för närliggande noder på grund av begränsningarna i maskinens beräkningsnoggrannhet. I sådana fall kan klättringsalgoritmen inte välja rörelseriktning och kan gå i en riktning som inte leder till en förbättring av den objektiva funktionen.

Pseudokod

Klättringsalgoritm i diskret utrymme currentNode = startNode; loop gör L = NEIGHBORS(currentNode); nästaEval = -INF; nextNode = NULL; för alla x i L if (EVAL(x) > nextEval) nästaNode = x; nästaEval = EVAL(x); if nextEval <= EVAL(currentNode) //Returnera den aktuella noden eftersom det inte finns någon bästa nod returnera aktuellNode; currentNode = nästaNode; Klättringsalgoritm i kontinuerligt utrymme currentPoint = initialPoint; // använder vanligtvis en vektor med noll längd stepSize = initialStepSizes; // använder vanligtvis en vektor av ettor acceleration = vissAcceleration; // använder normalt värde 1.2 kandidat[0] = -acceleration; kandidat[1] = -1 / acceleration; kandidat[2] = 0; kandidat[3] = 1 / acceleration; kandidat[4] = acceleration; loop gör före = EVAL(nuvarandePunkt); gör för varje element i currentPoint bästa = -1; bestScore = -INF; för j från 0 till 4 // försök att iterera över var och en av de 5 kandidaterna currentPoint[i] = currentPoint[i] + stepSize[i] * kandidat[j]; temp = EVAL(aktuellPunkt); currentPoint[i] = currentPoint[i] - stepSize[i] * kandidat[j]; if(temp > bästa poäng) bestScore=temp; bästa = j; om kandidat[bäst] är 0 stepSize[i] = stegSize[i] / acceleration; annan currentPoint[i] = currentPoint[i] + stepSize[i] * kandidat[bäst]; stepSize[i] = stepSize[i] * kandidat[bäst]; // accelerera if (EVAL(currentPoint) - before) < epsilon returnera aktuellPoint;

Se även

lutning nedstigning
Girig algoritm
Osynlig hand
Genomsnittlig förskjutning

Anteckningar

↑ Skiena, 2010 , sid. 253.

Litteratur

Stuart J. Russell, Peter Norvig. Artifical Intelligence: A Modern Approach. - Upper Saddle River, New Jersey: Prentice Hall, 2003. - s. 111-114.
Steven Skiena. The Algoritm Design Manual. — 2:a. - Springer Science + Business Media , 2010. - ISBN 1-849-96720-2 .

Artikeln är baserad på material hämtat från artikeln Free On-line Dictionary of Computing (FOLDOC) licensierad under GFDL (version 1.3) .

Länkar

Algoritmer för grafsökning
Oinformerade metoder	Dubbelriktad sökning Strålsökning Lexikografisk bredd första sökning Utöka första sökningen Sök efter kostnadskriterium Djup första sökning Backtracking sökning Sök genom att klättra till toppen Djupbegränsad sökning Djup-första sökning med iterativ fördjupning
Informerade metoder	Alfa beta-klippning Gren och bunden metod Sök efter första bästa matchning A* B* D* Att hitta en övergångspunkt IDA* Rekursiv sökning på den första bästa matchningen SMA*
Genvägar	Vågalgoritm Bellman-Ford algoritm Dijkstras algoritm Johnsons algoritm Levits algoritm Floyd-Warshall algoritm Kantsökning
Minsta spännträd	Boruvkas algoritm Prims algoritm Kruskals algoritm
Övrig	British Museum Algoritm Edmonds algoritm Trädpassering Algoritmen för närmaste granne i problemet med resande säljare

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powells metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering