Wspinaczka górska - Hill climbing

Powierzchnia z tylko jednym maksimum. Techniki wspinaczki górskiej dobrze nadają się do optymalizacji na takich powierzchniach i zbiegną się do globalnego maksimum.

W analizie numerycznej wspinaczka górska jest matematyczną techniką optymalizacji , która należy do rodziny poszukiwań lokalnych . Jest to algorytm iteracyjny, który rozpoczyna się od dowolnego rozwiązania problemu, a następnie próbuje znaleźć lepsze rozwiązanie, wprowadzając stopniową zmianę rozwiązania. Jeśli zmiana daje lepsze rozwiązanie, kolejna stopniowa zmiana jest wprowadzana w nowym rozwiązaniu i tak dalej, aż nie będzie można znaleźć dalszych ulepszeń.

Na przykład wspinaczka górska może być zastosowana do problemu komiwojażera . Łatwo jest znaleźć wstępne rozwiązanie, które obejmie wszystkie miasta, ale prawdopodobnie będzie bardzo słabe w porównaniu z rozwiązaniem optymalnym. Algorytm zaczyna od takiego rozwiązania i wprowadza do niego drobne usprawnienia, takie jak zmiana kolejności odwiedzania dwóch miast. W końcu prawdopodobnie zostanie uzyskana znacznie krótsza trasa.

Wspinaczka górska znajduje optymalne rozwiązania dla problemów wypukłych - dla innych problemów znajdzie tylko lokalne optima (rozwiązania, których nie da się poprawić żadnymi sąsiednimi konfiguracjami), które niekoniecznie są najlepszym możliwym rozwiązaniem ( optymalnym globalnym ) spośród wszystkich możliwych rozwiązań ( przestrzeń poszukiwań ). Przykłady algorytmów rozwiązujących problemy wypukłe przez wspinanie się po wzgórzach obejmują algorytm simplex do programowania liniowego i wyszukiwania binarnego . Aby spróbować uniknąć utknięcia w lokalnych optymalizacjach, można użyć restartów (tj. Powtórne wyszukiwanie lokalne) lub bardziej złożonych schematów opartych na iteracjach (takich jak iterowane wyszukiwanie lokalne ) lub na pamięci (np. Optymalizacja wyszukiwania reaktywnego i wyszukiwanie tabu ) lub na bez pamięci modyfikacje stochastyczne (takie jak symulowane wyżarzanie ).

Względna prostota algorytmu sprawia, że jest on popularnym pierwszym wyborem wśród algorytmów optymalizujących. Jest szeroko stosowany w sztucznej inteligencji do osiągnięcia stanu celu z węzła początkowego. W powiązanych algorytmach używane są różne opcje dla kolejnych węzłów i węzłów początkowych. Chociaż bardziej zaawansowane algorytmy, takie jak symulowane wyżarzanie lub wyszukiwanie tabu, mogą dawać lepsze wyniki, w niektórych sytuacjach wspinaczka górska działa równie dobrze. Wspinaczka po wzgórzach często daje lepsze wyniki niż inne algorytmy, gdy ilość czasu dostępnego do wyszukiwania jest ograniczona, na przykład w przypadku systemów czasu rzeczywistego, o ile niewielka liczba przyrostów zwykle zbiega się z dobrym rozwiązaniem (rozwiązanie optymalne lub bliskie przybliżenie). Z drugiej strony sortowanie bąbelkowe może być postrzegane jako algorytm wznoszenia się po wzgórzu (każda wymiana sąsiednich elementów zmniejsza liczbę nieuporządkowanych par elementów), jednak podejście to jest dalekie od wydajności nawet dla skromnego N, ponieważ liczba wymaganych wymian rośnie kwadratowo.

Wspinaczka po wzgórzach to algorytm dostępny w dowolnym momencie : może zwrócić prawidłowe rozwiązanie, nawet jeśli zostanie przerwane w dowolnym momencie przed jego zakończeniem.

Opis matematyczny

Hill wspinania prób zmaksymalizowania (lub zminimalizowania) docelową funkcję , gdzie jest wektorem ciągłych i / lub wartości dyskretnych. W każdej iteracji wspinaczka górska dostosuje pojedynczy element i określi, czy zmiana poprawi wartość . (Należy zauważyć, że różni się to od metod zejścia gradientowego , które dostosowują wszystkie wartości w każdej iteracji zgodnie z nachyleniem wzniesienia). Podczas wspinaczki po wzniesieniu każda poprawiona zmiana jest akceptowana, a proces jest kontynuowany, dopóki nie można znaleźć żadnej zmiany. poprawić wartość . Mówi się wtedy, że jest „optymalny lokalnie”. ${\ displaystyle f (\ mathbf {x})}$ ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle f (\ mathbf {x})}$ ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle f (\ mathbf {x})}$ ${\ displaystyle f (\ mathbf {x})}$ ${\ displaystyle \ mathbf {x}}$

W dyskretnych przestrzeniach wektorowych każda możliwa wartość może być wizualizowana jako wierzchołek na wykresie . Wspinaczka górska będzie przebiegać zgodnie z wykresem od wierzchołka do wierzchołka, zawsze lokalnie zwiększając (lub zmniejszając) wartość , aż do osiągnięcia lokalnego maksimum (lub lokalnego minimum ) . ${\ displaystyle \ mathbf {x}}$ ${\ displaystyle f (\ mathbf {x})}$ ${\ displaystyle x_ {m.}}$

Warianty

W przypadku prostego pokonywania wzniesień wybierany jest pierwszy bliższy węzeł, natomiast w przypadku wspinaczki na najbardziej stromym wzniesieniu porównuje się wszystkich następców i wybiera ten najbliższy rozwiązaniu. Obie formy zawodzą, jeśli nie ma bliższego węzła, co może się zdarzyć, jeśli w przestrzeni wyszukiwania istnieją lokalne maksima, które nie są rozwiązaniami. Wspinaczka na najbardziej strome wzniesienie jest podobna do wyszukiwania best-first , które polega na wypróbowaniu wszystkich możliwych rozszerzeń bieżącej ścieżki zamiast tylko jednej.

Stochastyczna wspinaczka górska nie sprawdza wszystkich sąsiadów przed podjęciem decyzji, jak się poruszać. Raczej wybiera losowo sąsiada i decyduje (na podstawie stopnia poprawy u tego sąsiada), czy przenieść się do tego sąsiada, czy też zbadać innego.

Zniżanie współrzędnych powoduje przeszukiwanie linii wzdłuż jednego kierunku współrzędnych w bieżącym punkcie w każdej iteracji. Niektóre wersje zstępowania współrzędnych losowo wybierają inny kierunek współrzędnych w każdej iteracji.

Random-restart wspinaczka górska jest meta-algorytmem zbudowanym na bazie algorytmu wspinaczki na wzgórze. Jest również znany jako wspinaczka górska Shotgun . Iteracyjnie wspina się po wzgórzach, za każdym razem z losowym warunkiem początkowym . Najlepsze jest zachowane: jeśli nowa seria wspinaczek górskich daje stan lepszy niż stan zmagazynowany, zastępuje stan zmagazynowany. ${\ displaystyle x_ {0}}$ ${\ displaystyle x_ {m.}}$ ${\ displaystyle x_ {m.}}$

W wielu przypadkach wspinaczka górska z losowym restartem jest zaskakująco skutecznym algorytmem. Okazuje się, że często lepiej jest poświęcić czas procesora na badanie przestrzeni, niż ostrożną optymalizację od stanu początkowego.

Problemy

Maksima lokalne

Powierzchnia z dwoma lokalnymi maksimami. (Tylko jedno z nich to globalne maksimum.) Jeśli wspinacz zaczyna się w złej lokalizacji, może zbiegać się do niższego maksimum.

Wspinaczka górska niekoniecznie spowoduje znalezienie globalnego maksimum, ale zamiast tego może zbiegać się z lokalnym maksimum . Ten problem nie występuje, jeśli heurystyka jest wypukła. Jednakże, ponieważ wiele funkcji nie jest wypukłych, wspinaczka górska może często nie osiągnąć globalnego maksimum. Inne lokalne algorytmy wyszukiwania próbują przezwyciężyć ten problem, takie jak stochastyczne wspinanie się po wzgórzach , przypadkowe spacery i symulowane wyżarzanie .

Pomimo wielu lokalnych maksimów na tym wykresie, globalne maksimum można nadal znaleźć za pomocą symulowanego wyżarzania. Niestety, możliwość zastosowania symulowanego wyżarzania jest specyficzna dla problemu, ponieważ polega na znalezieniu szczęśliwych skoków, które poprawią pozycję. W takich ekstremalnych przypadkach wspinaczka górska najprawdopodobniej przyniesie lokalne maksimum.

Grzbiety i alejki

Grzbiet

Grzbiety są trudnym problemem dla wspinaczy, którzy optymalizują się w ciągłych przestrzeniach. Ponieważ wspinacze górscy dostosowują tylko jeden element w wektorze na raz, każdy krok będzie się poruszał w kierunku wyrównanym do osi. Jeśli funkcja celu tworzy wąski grzbiet, który wznosi się w kierunku nie wyrównanym do osi (lub jeśli celem jest zminimalizowanie, wąska alejka, która opada w kierunku nie wyrównanym do osi), wówczas osoba wspinająca się na wzgórze może wspiąć się tylko na grzbiet (lub zejdź alejką) zygzakiem. Jeśli boki grzbietu (lub alei) są bardzo strome, wspinacz może być zmuszony do zrobienia bardzo małych kroków, gdy zygzakuje w kierunku lepszej pozycji. W związku z tym wejście na grzbiet (lub zejście z alei) może zająć nieracjonalnie długi czas.

Z drugiej strony metody gradientu opadania mogą poruszać się w dowolnym kierunku, w którym grzbiet lub aleja mogą wznosić się lub opadać. W związku z tym spadek gradientu lub metoda gradientu sprzężonego są generalnie preferowane w stosunku do wspinaczki po wzgórzach, gdy funkcja celu jest różniczkowa. Jednak wspinacze górscy mają tę zaletę, że nie wymagają zróżnicowania funkcji celu, więc wspinacze górscy mogą być preferowani, gdy funkcja celu jest złożona.

Płaskowyż

Innym problemem, który czasami pojawia się podczas wspinaczki po wzgórzach, jest płaskowyż. Plateau jest napotykane, gdy przestrzeń wyszukiwania jest płaska lub wystarczająco płaska, aby wartość zwracana przez funkcję docelową była nie do odróżnienia od wartości zwracanej dla pobliskich regionów ze względu na precyzję używaną przez maszynę do reprezentowania jej wartości. W takich przypadkach wspinacz może nie być w stanie określić, w którym kierunku powinien stąpać i może wędrować w kierunku, który nigdy nie prowadzi do poprawy.

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

Algorytm genetyczny kontrastu ; losowa optymalizacja .

Zobacz też

Bibliografia

Russell, Stuart J .; Norvig, Peter (2003), Artificial Intelligence: A Modern Approach (2nd ed.), Upper Saddle River, New Jersey: Prentice Hall, str. 111–114, ISBN 0-13-790395-2

Ten artykuł jest oparty na materiałach zaczerpniętych z Free On-line Dictionary of Computing przed 1 listopada 2008 i włączonych na warunkach „ponownego licencjonowania” GFDL , wersja 1.3 lub nowsza.

Linki zewnętrzne

Wspinaczka górska na Wikibooks

Languages

In other projects