Jaka jest różnica między Stochastic Hill Climbing a Simulated Annealing?
Czytam o wyszukiwaniu lokalnym: wspinaczka górska i jej rodzaje oraz symulowane wyżarzanie
Jedną z wersji wspinaczki górskiej jest „wspinaczka stochastyczna”, która ma następującą definicję:
Wspinaczka stochastyczna nie sprawdza się dla wszystkich sąsiadów przed ruchem. Raczej ten algorytm wyszukiwania wybiera losowo jeden węzeł sąsiedni i decyduje, czy wybrać go jako stan bieżący, czy zbadać inny stan
Niektóre źródła wspominają, że można go wykorzystać, aby uniknąć lokalnych optima.
Następnie czytałem o symulowanym wyżarzaniu i jego definicji:
W każdej iteracji wybierany jest losowy ruch. Jeśli to poprawia sytuację, ruch jest akceptowany, w przeciwnym razie jest akceptowany z pewnym prawdopodobieństwem mniejszym niż 1
Jaka jest więc główna różnica między tymi dwoma podejściami? Czy stochastyczny wybiera tylko losowego (pod górę) następcę? Jeśli wybierze tylko (następców pod górę), to w jaki sposób unika lokalnych optima?
Odpowiedzi
Książka Russella i Norviga (3. wydanie) opisuje te dwa algorytmy (sekcja 4.1.1., S. 122), a ta książka jest odniesieniem, z którego należy zasadniczo korzystać podczas studiowania algorytmów wyszukiwania w sztucznej inteligencji. Jestem zaznajomiony z symulowanym wyżarzaniem (SA), biorąc pod uwagę, że wdrożyłem go w przeszłości, aby rozwiązać problem kombinatoryczny, ale nie jestem zbyt zaznajomiony z stochastycznym wspinaniem się po wzgórzu (SHC), więc zacytuję części książki, które opisują SHC .
Stochastyczna wspinaczka górska wybiera losowo spośród ruchów pod górę; prawdopodobieństwo wyboru może się zmieniać wraz ze stromością ruchu pod górę. Zwykle zbiega się to wolniej niż najbardziej strome podejście, ale w niektórych krajobrazach państwowych znajduje lepsze rozwiązania.
Tak więc SHC wybiera losowo jeden „ruch pod górę”, tj. Ruch, który poprawia funkcję celu (na przykład, jeśli próbujesz rozwiązać problem komiwojażera , „ruch pod górę” może oznaczać dowolną zmianę w obecnym cyklu Hamiltona , rozwiązanie, dzięki któremu nowy cykl halmitoński ma mniejszy koszt) wśród ruchów pod górę (a więc wśród niektórych zestawów ruchów poprawiających cel).
W symulowanym wyżarzaniu wykonujesz jakiś ruch. Jeśli ten ruch prowadzi do lepszego rozwiązania, zawsze zachowujesz lepsze rozwiązanie. Jeśli prowadzi to do gorszego rozwiązania, akceptujesz to gorsze rozwiązanie z pewnym prawdopodobieństwem. Są inne szczegóły, takie jak to, jak akceptujesz gorsze rozwiązanie (które można znaleźć w książce Russella i Norviga), ale to już powinno wyjaśnić, że SA różni się od SHC: SA może zaakceptować gorsze rozwiązania, aby uciec od lokalnych minimów, podczas gdy SHC akceptuje tylko ruchy pod górę.