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

Jakie są ograniczenia algorytmu wspinaczki na wzgórze ? Jak możemy pokonać te ograniczenia?

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

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