Hill klatring - Hill climbing

En overflate med bare ett maksimum. Hill-klatring teknikker er godt egnet for å optimalisere over slike overflater, og vil konvergere til det globale maksimum.

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

En overflate med to lokale maksimum. (Bare en av dem er det globale maksimumet.) Hvis en fjellklatrer begynner på et dårlig sted, kan den konvergere til det nedre maksimumet.

Å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 .

Til tross for de mange lokale maksimumene i denne grafen, kan det globale maksimum fremdeles bli funnet ved hjelp av simulert gløding. Dessverre er anvendelsen av simulert gløding problemspesifikk fordi den er avhengig av å finne heldige hopp som forbedrer posisjonen. I slike ekstreme eksempler vil høyklatring sannsynligvis gi et lokalt maksimum.

Rygger og smug

En rygg

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