Hill klatring - Hill climbing
Graf og tre søkealgoritmer |
---|
Oppføringer |
relaterte temaer |
I numerisk analyse er fjellklatring en matematisk optimaliseringsteknikk som tilhører familien til lokalt søk . Det er en iterativ algoritme som starter med en vilkårlig løsning på et problem, og deretter prøver å finne en bedre løsning ved å gjøre en trinnvis endring av løsningen. Hvis endringen gir en bedre løsning, gjøres en ny trinnvis endring av den nye løsningen, og så videre til ingen ytterligere forbedringer kan bli funnet.
For eksempel kan bakkeklatring brukes på det reisende selgerproblemet . Det er lett å finne en innledende løsning som besøker alle byene, men som sannsynligvis vil være veldig dårlig sammenlignet med den optimale løsningen. Algoritmen starter med en slik løsning og gjør det små forbedringer, for eksempel å bytte rekkefølgen to byer besøkes i. Etter hvert vil det sannsynligvis oppnås en mye kortere rute.
Åkeklatring finner optimale løsninger for konvekse problemer - for andre problemer finner den bare lokale optima (løsninger som ikke kan forbedres av noen nabokonfigurasjoner), som ikke nødvendigvis er den beste mulige løsningen (det globale optimale ) av alle mulige løsninger ( den søke plass ). Eksempler på algoritmer som løser konvekse problemer ved å klatre i bakken inkluderer simpleksalgoritmen for lineær programmering og binærsøk . For å forsøke å unngå å bli sittende fast i lokal optima, kan man bruke omstart (dvs. gjentatt lokalt søk), eller mer komplekse ordninger basert på iterasjoner (som iterert lokalt søk ), eller på minne (som reaktiv søkoptimalisering og tabusøk ), eller på minneløse stokastiske modifikasjoner (som simulert annealing ).
Den relative enkelheten til algoritmen gjør det til et populært førstevalg blant optimaliseringsalgoritmer. Den brukes mye i kunstig intelligens , for å nå en måltilstand fra en startnode. Ulike valg for neste noder og startnoder brukes i relaterte algoritmer. Selv om mer avanserte algoritmer som simulert annealing eller tabu-søk kan gi bedre resultater, fungerer bakkeklatring i noen situasjoner like bra. Åkeklatring kan ofte gi et bedre resultat enn andre algoritmer når tiden som er tilgjengelig for å utføre et søk er begrenset, for eksempel i sanntidssystemer, så lenge et lite antall trinn vanligvis konvergerer til en god løsning (den optimale løsningen eller en nær tilnærming). På den andre ytterpunkten kan boblesorter ses på som en bakkeklatringalgoritme (hver tilstøtende elementutveksling reduserer antall uordnede elementpar), men denne tilnærmingen er langt fra effektiv for selv beskjedne N, ettersom antall utvekslinger som kreves vokser kvadratisk.
Åkeklatring er en algoritme når som helst : den kan returnere en gyldig løsning selv om den blir avbrutt når som helst før den avsluttes.
Matematisk beskrivelse
Stige forsøk på å maksimere (eller minimere) et mål funksjon , der er en vektor med kontinuerlig og / eller diskrete verdier. Ved hver iterasjon vil bakkeklatring justere et enkelt element i og avgjøre om endringen forbedrer verdien av . (Merk at dette skiller seg fra metoder for stigningsnedstigning , som justerer alle verdiene i hver iterasjon i henhold til stigningen til bakken.) Med stigning i bakker aksepteres endring som forbedrer seg , og prosessen fortsetter til ingen endring kan bli funnet for å forbedre verdien av . Da sies det å være "lokalt optimalt".
I diskrete vektorrom kan hver mulige verdi for visualiseres som et toppunkt i en graf . Åkeklatring vil følge grafen fra toppunkt til toppunkt, og øker alltid (eller synker) verdien på lokalt til et lokalt maksimum (eller lokalt minimum ) er nådd.
Varianter
I enkel bakkeklatring blir den første nærmere noden valgt, mens i bratteste stigning bakkeklatring blir alle etterfølgere sammenlignet og den nærmeste løsningen blir valgt. Begge skjemaene mislykkes hvis det ikke er noen nærmere node, noe som kan skje hvis det er lokale maksimum i søkeområdet som ikke er løsninger. Bratteste stigning bakkeklatring ligner på best-first-søk , som prøver alle mulige utvidelser av den nåværende stien i stedet for bare en.
Stokastisk fjellklatring undersøker ikke alle naboer før de bestemmer seg for hvordan de skal bevege seg. Snarere velger den tilfeldig en nabo, og bestemmer (basert på forbedringsmengden i den naboen) om han skal flytte til naboen eller undersøke en annen.
Koordinatnedstigning gjør et linjesøk langs en koordinatretning på det nåværende punktet i hver iterasjon. Noen versjoner av koordinatstigning velger tilfeldig en annen koordinatretning hver iterasjon.
Tilfeldig omstart bakkeklatring er en metalgoritme bygget på toppen av bakkeklatringalgoritmen. Det er også kjent som Shotgun hill climb . Det går iterativt i stigning, hver gang med en tilfeldig starttilstand . Det beste opprettholdes: hvis et nytt løp med åsklatring gir bedre enn lagret tilstand, erstatter det lagret tilstand.
Tilfeldig omstart bakkeklatring er i mange tilfeller en overraskende effektiv algoritme. Det viser seg at det ofte er bedre å bruke CPU-tid på å utforske plassen, enn å nøye optimalisere fra en opprinnelig tilstand.
Problemer
Lokale maksimum
Åsklatring vil ikke nødvendigvis finne det globale maksimumet, men kan i stedet konvergere til et lokalt maksimum . Dette problemet oppstår ikke hvis heuristikken er konveks. Ettersom mange funksjoner ikke er konvekse, kan det ofte hende at klatring ikke klarer å nå et globalt maksimum. Andre lokale søkealgoritmer prøver å overvinne dette problemet, for eksempel stokastisk bakkeklatring , tilfeldige turer og simulert gløding .
Rygger og smug
Rygger er et utfordrende problem for fjellklatrere som optimaliserer seg i kontinuerlige rom. Fordi bakkeklatrere bare justerer ett element i vektoren om gangen, vil hvert trinn bevege seg i en aksejustert retning. Hvis målfunksjonen skaper en smal møne som stiger opp i en ikke-akset justert retning (eller hvis målet er å minimere, en smal bakgate som synker i en ikke-akse-justert retning), kan bakkeklatreren bare stige oppover rygg (eller nedover bakgate) ved sikksakk. Hvis sidene av ryggen (eller bakgate) er veldig bratte, kan bakkeklatreren bli tvunget til å ta veldig små skritt når den sikksakkes mot en bedre posisjon. Dermed kan det ta urimelig lang tid før den stiger opp på ryggen (eller går nedover smuget).
Derimot kan gradientnedstigningsmetoder bevege seg i hvilken som helst retning at ryggen eller bakgaten kan stige opp eller ned. Derfor foretrekkes gradvis nedstigning eller den konjugerte gradientmetoden generelt fremfor å klatre når målfunksjonen er forskjellig. Bakkeklatrere har imidlertid fordelen av ikke å kreve at målfunksjonen skal kunne differensieres, så bakkeklatrere kan være å foretrekke når målfunksjonen er kompleks.
Platå
Et annet problem som noen ganger oppstår med å klatre, er et platå. Et platå oppstår når søkeområdet er flatt, eller tilstrekkelig flatt til at verdien som returneres av målfunksjonen ikke skiller seg fra verdien som returneres for nærliggende regioner på grunn av presisjonen som brukes av maskinen til å representere verdien. I slike tilfeller klatrer kanskje ikke bakken i hvilken retning den skal gå, og kan vandre i en retning som aldri fører til forbedring.
Pseudocode algorithm Discrete Space Hill Climbing is currentNode := startNode loop do L := NEIGHBORS(currentNode) nextEval := −INF nextNode := NULL for all x in L do if EVAL(x) > nextEval then nextNode := x nextEval := EVAL(x) if nextEval ≤ EVAL(currentNode) then // Return current node since no better neighbors exist return currentNode currentNode := nextNode
algorithm Continuous Space Hill Climbing is currentPoint := initialPoint // the zero-magnitude vector is common stepSize := initialStepSizes // a vector of all 1's is common acceleration := someAcceleration // a value such as 1.2 is common candidate[0] := −acceleration candidate[1] := −1 / acceleration candidate[2] := 1 / acceleration candidate[3] := acceleration bestScore := EVAL(currentPoint) loop do beforeScore := bestScore for each element i in currentPoint do beforePoint := currentPoint[i] bestStep := 0 for j from 0 to 3 do // try each of 4 candidate locations step := stepSize[i] × candidate[j] currentPoint[i] := beforePoint + step score := EVAL(currentPoint) if score > bestScore then bestScore := score bestStep := step if bestStep is 0 then currentPoint[i] := beforePoint stepSize[i] := stepSize[i] / acceleration else currentPoint[i] := beforePoint + bestStep stepSize[i] := bestStep // accelerate if (bestScore − beforeScore) < epsilon then return currentPoint
Kontrast genetisk algoritme ; tilfeldig optimalisering .
Se også
Referanser
- Russell, Stuart J .; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2. utg.), Upper Saddle River, New Jersey: Prentice Hall, s. 111–114, ISBN 0-13-790395-2
Denne artikkelen er basert på materiale hentet fra Free On-line Dictionary of Computing før 1. november 2008 og innlemmet under "resicensing" vilkårene i GFDL , versjon 1.3 eller nyere.
Eksterne linker
- Hill klatring på Wikibooks