Stochastic Hill Climbing ogólnie radzi sobie gorzej niż Steepest Hill Climbing , ale w jakich przypadkach ten pierwszy działa lepiej?
Algorytmy najbardziej stromego wznoszenia działają dobrze dla optymalizacji wypukłej. Jednak rzeczywiste problemy są zwykle typu niewypukłego: istnieje wiele pików. W takich przypadkach, gdy algorytm rozpoczyna się od rozwiązania losowego, prawdopodobieństwo, że osiągnie jeden z lokalnych pików, zamiast globalnego piku, jest wysokie. Ulepszenia takie jak Symulowane wyżarzanie poprawiają ten problem, umożliwiając algorytmowi odejście od lokalnego piku, a tym samym zwiększając prawdopodobieństwo znalezienia globalnego piku.
Oczywiście, dla prostego problemu z tylko jednym szczytem, najbardziej strome podejście do wspinaczki jest zawsze lepsze. Może także użyć wczesnego zatrzymania, jeśli zostanie znaleziony globalny szczyt. Dla porównania, symulowany algorytm wyżarzania faktycznie odskoczyłby od globalnego szczytu, wróciłby i odskoczyłby ponownie. Powtarzałoby się to, aż ostygnie wystarczająco lub zakończy się określona liczba iteracji.
Rzeczywiste problemy dotyczą hałaśliwych i brakujących danych. Stochastyczne podejście do wspinaczki, choć wolniejsze, jest bardziej odporne na te problemy, a procedura optymalizacji ma większe prawdopodobieństwo osiągnięcia globalnego szczytu w porównaniu z algorytmem najbardziej stromego wspinania się na wzgórze.
Epilog: To dobre pytanie, które rodzi trwałe pytanie podczas projektowania rozwiązania lub wyboru między różnymi algorytmami: kompromis kosztów obliczeniowych wydajności. Jak można się spodziewać, odpowiedź jest zawsze: zależy od priorytetów algorytmu. Jeśli jest częścią jakiegoś internetowego systemu uczenia się, który działa na partii danych, wówczas istnieje silne ograniczenie czasowe, ale słabe ograniczenie wydajności (kolejne partie danych skorygują się pod kątem błędnego błędu wynikającego z pierwszej partii danych). Z drugiej strony, jeśli jest to zadanie uczenia się offline z dostępnymi wszystkimi dostępnymi danymi, głównym ograniczeniem jest wydajność, a wskazane jest podejście stochastyczne.
Zacznijmy od kilku definicji.
Wspinaczka jest algorytmem wyszukiwania, który po prostu uruchamia pętlę i ciągle przesuwa się w kierunku zwiększania wartości, czyli pod górę. Pętla kończy się, gdy osiąga szczyt i żaden sąsiad nie ma wyższej wartości.
Stochastyczne wspinanie na wzgórze , wariant wspinaczki na wzgórze, wybiera losowe spośród ruchów pod górę. Prawdopodobieństwo wyboru może się różnić w zależności od stromości podjazdu. Dwie znane metody to: Działa zgodnie z filozofią „Jeśli się nie powiedzie, spróbuj ponownie”.
Teraz twoja odpowiedź. Stochastyczne wspinanie pod górę może w wielu przypadkach być lepsze
wspinaczka pierwszego wyboru: generuje losowo następców, dopóki nie zostanie wygenerowana jedna lepsza niż obecny stan. * Uważane za dobre, jeśli państwo ma wielu następców (jak tysiące lub miliony).
Losowe wznawianie wspinaczki na wzgórze:
. Rozważ następujący przypadek. Obraz przedstawia krajobraz w przestrzeni stanów. Przykład przedstawiony na zdjęciu pochodzi z książki Artificial Intelligence: A Modern Approach .
Załóżmy, że jesteś w punkcie pokazanym przez bieżący stan. Jeśli zastosujesz prosty algorytm wspinania się na wzgórze, osiągniesz lokalne maksimum i algorytm się skończy. Chociaż istnieje stan o bardziej optymalnej wartości funkcji celu, ale algorytm nie osiąga go, ponieważ utknął na lokalnym maksimum. Algorytm może również utknąć na płaskich lokalnych maksimach.
Losowy restart wspinaczki pod górę prowadzi serię wyszukiwań wspinaczki od losowo wygenerowanych stanów początkowych, aż do znalezienia stanu celu.
Sukces wspinaczki górskiej zależy od kształtu krajobrazu przestrzeni państwowej. W przypadku, gdy jest tylko kilka lokalnych maksimów, płaskie płaskowyże; losowe wznowienie wspinaczki na wzgórze bardzo szybko znajdzie dobre rozwiązanie. Większość rzeczywistych problemów ma bardzo trudny krajobraz w przestrzeni stanów, co sprawia, że nie nadają się do użycia algorytmu wspinaczki na wzgórzu ani żadnego z jego wariantów.
UWAGA: Algorytm Hill Climb może być również użyty do znalezienia wartości minimalnej, a nie tylko wartości maksymalne. W odpowiedzi użyłem terminu maksimum. Jeśli szukasz wartości minimalnych, wszystkie rzeczy będą odwrotne, w tym wykres.
Też jestem nowy w tych koncepcjach, ale w moim rozumieniu Stochastic wspinaczka na wzgórze działałaby lepiej w przypadkach, w których czas obliczeń jest cenny (obejmuje obliczenie funkcji fitness), ale tak naprawdę nie jest konieczne osiągnięcie najlepszego możliwe rozwiązanie. Osiągnięcie nawet lokalnego optimum byłoby w porządku. Roboty działające w roju byłyby jednym z przykładów, w których można to wykorzystać.
Jedyną różnicą, którą widzę w najbardziej stromym wspinaniu się na wzgórze, jest to, że przeszukuje on nie tylko sąsiednie węzły, ale także następców sąsiadów, podobnie jak algorytm szachowy szuka wielu dalszych ruchów do przodu, zanim wybierze najlepszy ruch.
źródło
źródło