Jaka jest różnica między Stochastic Hill Climbing a Simulated Annealing?

Nov 24 2020

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

4 nbro Nov 24 2020 at 03:56

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