Jakie są ograniczenia algorytmu wspinaczki i jak je pokonać?

Odpowiedzi:

6

Jak już powiedział @nbro, Hill Climbing to rodzina lokalnych algorytmów wyszukiwania . Tak więc, kiedy powiedziałeś w Hill Climbing w pytaniu, założyłem, że mówisz o standardowym wspinaniu się na wzgórze. Standardowa wersja wznoszenia ma pewne ograniczenia i często utknęła w następującym scenariuszu:

  • Lokalne maksima: Algorytm wspinania się na wzgórze osiągający w pobliżu lokalną maksymalną wartość, zostaje przyciągnięty do szczytu i utknie tam, nie mając innego miejsca .
  • Grzbiety: Są to sekwencje lokalnych maksimów , które utrudniają algorytmowi nawigację.
  • Plateaux: Jest to płaski region przestrzeni państwowej . Ponieważ nie ma podjazdu, algorytm często gubi się na płaskowyżu.

Aby rozwiązać te problemy, opracowano wiele wariantów algorytmów wspinania się na wzgórze. Są to najczęściej używane:

  • Stochastic Hill Climbing wybiera losowo spośród ruchów pod górę. Prawdopodobieństwo wyboru zależy od stromości podjazdu.
  • Wspinaczka pierwszego wyboru implementuje powyższe, generując losowo następców, aż do znalezienia lepszego.
  • Losowo wznawiaj wyszukiwanie wspinaczki po losowo generowanych początkowych ruchach, aż do osiągnięcia celu.

Sukces algorytmów wspinania się na wzgórze zależy od architektury krajobrazu przestrzeni państwowej. Ilekroć jest mało maksimów i płaskowyżów, warianty algorytmów przeszukiwania podjazdów działają bardzo dobrze. Ale w rzeczywistych problemach występuje krajobraz, który wygląda bardziej jak szeroko rozproszona rodzina łysiejących jeżozwierzy na płaskiej podłodze, z miniaturowymi jeżozwierzami żyjącymi na czubku każdej igły jeżozwierzowatej (jak opisano w 4 rozdziale książki Sztuczna inteligencja: A Nowoczesne podejście). Problemy NP-Hard zwykle mają wykładniczą liczbę lokalnych maksimów, które mogą się utknąć.
Podane algorytmy zostały opracowane w celu przezwyciężenia tego rodzaju problemów:

  • Stymulowane wyżarzanie
  • Wyszukiwanie lokalnych wiązek
  • Algorytmy genetyczne

Reference Book - Artificial Intelligence: A Modern Approach

Ugnes
źródło
Dostępnych jest więcej możliwości rozwiązania problemów wspinaczki; mianowicie grupy permutacji, bazy danych wzorców i wyszukiwanie oparte na gramatyce. Korzystają z wiedzy specyficznej dla domeny, aby szybciej wyszukiwać w przestrzeni stanów.
Manuel Rodriguez
Tak @ManuelRodriguez. Algorytmy zależne od wiedzy specyficznej dla domeny dają doskonałe wyniki. Ale starałem się zachować odpowiedź na ogólne problemy, wymieniając kilka sposobów na przezwyciężenie ograniczeń Hill Climb Search.
Ugnes,
5

Wspinaczka nie jest algorytmem, ale rodziną algorytmów „wyszukiwania lokalnego”. Konkretne algorytmy należące do kategorii algorytmów „wspinaczka górska” to 2-opt, 3-opt, 2.5-opt, 4-opt lub ogólnie dowolny N-opt. Więcej informacji na temat niektórych lokalnych algorytmów wyszukiwania (stosowanych w TSP) znajduje się w rozdziale 3 artykułu „ Problem podróżującego sprzedawcy: studium przypadku w optymalizacji lokalnej ” (David S. Johnson i Lyle A. McGeoch).

Tym, co odróżnia jeden algorytm w tej kategorii od drugiej, jest wykorzystywana przez nich „funkcja sąsiedztwa” (innymi słowy sposób, w jaki znajdują rozwiązania sąsiednie dla danego rozwiązania). Należy zauważyć, że w praktyce nie zawsze tak jest: często algorytmy te mają kilka różnych implementacji.

Najbardziej oczywistym ograniczeniem algorytmów wspinania się na wzgórze jest ich natura, to znaczy są to lokalne algorytmy wyszukiwania. Dlatego zwykle po prostu znajdują lokalne maksima (lub minima). Tak więc, jeśli którykolwiek z tych algorytmów już zbliżył się do lokalnego minimum (lub maksimum), a w obszarze rozwiązania lub przestrzeni wyszukiwania istnieje blisko tego znalezionego rozwiązania lepsze rozwiązanie, żaden z tych algorytmów nie będzie w stanie go znaleźć lepsze rozwiązanie. Zasadniczo zostaną uwięzieni.

Lokalne algorytmy wyszukiwania zwykle nie są używane same. Są one używane jako podprogramy innych algorytmów meta-heurystycznych, takich jak symulowane wyżarzanie, iterowane wyszukiwanie lokalne lub w dowolnym algorytmie ant-kolonii. Tak więc, aby przezwyciężyć ich ograniczenia, zwykle nie używamy ich samych, ale używamy ich w połączeniu z innymi algorytmami, które mają charakter probabilistyczny i mogą znaleźć globalne minima lub maksima (np. Dowolny z algorytmów antykolonii).

nbro
źródło
Dobra odpowiedź (+1)! Czy możesz polecić zasób (YouTube, post na blogu, artykuł archiwalny, książka), aby dowiedzieć się więcej o algorytmach antykolonii? Nigdy o tym nie słyszałem i chciałbym mieć ogólne pojęcie o nich.
Martin Thoma,
1
@MartinThoma Obawiam się, że tak naprawdę nie znam bardzo ładnego samouczka na temat ACS. Może możesz zacząć od następującego krótkiego samouczka i odpowiedniej implementacji: cleveralgorithms.com/nature-inspired/swarm/… . Jeśli jesteś zainteresowany bardziej poważnym wdrożeniem, zastosowanym do TSP, to spójrz na ten: aco-metaheuristic.org/aco-code , wdrożony przez Stützle (i inne), jednego z autorów projektu tych technik.
nbro
Pytający wie, jaka jest formalna definicja wspinaczki, ponieważ przeczytał artykuł w Wikipedii. Pytanie zmierza bardziej w kierunku wykorzystania go do sztucznej inteligencji. Wiadomo, że wspinaczka na wzgórze może wyszukiwać tylko w przestrzeni lokalnej, co utrudnia problemy związane z AI. Zwykle wyszukiwanie utknęło w lokalnych optymach, co oznacza, że ​​nie można znaleźć najkrótszej trasy w problemie Podróżującego sprzedawcy.
Manuel Rodriguez
1
@MartinThoma W każdym razie możesz także zajrzeć do prac badawczych. Mogę tylko powiedzieć kilku ważnych badaczy: Dorigo (pierwszy, który wprowadził te techniki, AFAIK), Gambardella i Stützle. Spójrz na ich papiery. Nie jestem pewien, który z nich zasugerować. Jest też książka poświęcona inteligencji roju (autorstwa Bonabeau), jeśli naprawdę chcesz zagłębić się w szczegóły.
nbro