Stochastic Hill Climbing과 Simulated Annealing의 차이점은 무엇입니까?
나는 지역 검색에 대해 읽고 있습니다 : 언덕 오르기, 그 유형 및 모의 어닐링
언덕 등반 버전 중 하나는 "확률 적 언덕 등반"이며 다음과 같은 정의가 있습니다.
확률 적 언덕 등반은 이동하기 전에 모든 이웃을 검사하지 않습니다. 오히려이 검색 알고리즘은 하나의 인접 노드를 무작위로 선택하고 현재 상태로 선택할지 아니면 다른 상태를 검사할지 결정합니다.
일부 소식통은 로컬 최적화를 피하기 위해 사용할 수 있다고 언급했습니다.
그런 다음 시뮬레이션 된 어닐링과 그 정의에 대해 읽었습니다.
반복 할 때마다 무작위 이동이 선택됩니다. 상황이 개선되면 이동이 수락되고 그렇지 않으면 1 미만의 확률로 수락됩니다.
그렇다면 두 접근 방식의 주요 차이점은 무엇입니까? 확률론은 무작위 (오르막) 후임자 만 선택합니까? (오르막 후계자) 만 선택한다면 어떻게 로컬 옵티마를 피할 수 있습니까?
답변
Russell과 Norvig의 책 (3 판)은이 두 알고리즘 (섹션 4.1.1., p. 122)을 설명하며이 책은 인공 지능에서 검색 알고리즘을 연구 할 때 일반적으로 사용해야하는 참고 자료입니다. 저는 과거에 조합 문제를 해결하기 위해 구현 한 시뮬레이션 어닐링 (SA)에 익숙하지만 확률 적 언덕 등반 (SHC)에 익숙하지 않으므로 SHC를 설명하는 책의 일부를 인용하겠습니다. .
확률 적 언덕 등반 은 오르막 동작 중에서 무작위로 선택합니다. 선택 확률은 오르막길의 가파른 정도에 따라 달라질 수 있습니다. 이것은 일반적으로 가장 가파른 상승보다 더 느리게 수렴하지만 일부 주 풍경에서는 더 나은 해결책을 찾습니다.
따라서 SHC는 무작위로 하나의 "오르막 이동", 즉 목적 함수를 개선하는 움직임을 선택합니다 (예를 들어, 이동하는 세일즈맨 문제 를 해결하려는 경우 "오르막 이동"은 현재 해밀턴주기의 변경 사항 일 수 있습니다. , 새로운 Halmitonian 사이클이 더 짧은 비용을 갖도록) 오르막 이동 중 (목표를 개선하는 일부 이동 세트 중).
에서 시뮬레이션 어닐링 , 당신은 어떤 움직임을 수행합니다. 그 움직임이 더 나은 솔루션으로 이어진다면 항상 더 나은 솔루션을 유지합니다. 더 나쁜 솔루션으로 이어지는 경우 특정 확률로 더 나쁜 솔루션을 수락합니다. 더 나쁜 솔루션 (Russell과 Norvig의 책에서 찾을 수 있음)을 받아들이는 방법과 같은 다른 세부 정보가 있지만 이것은 SA가 SHC와 다르다는 것을 이미 명확히해야합니다. SA는 로컬 최소값에서 벗어나기 위해 더 나쁜 솔루션을 받아 들일 수 있습니다. SHC는 오르막 동작 만 허용합니다.