DAA-언덕 등반 알고리즘
이전 장에서 설명한 알고리즘은 체계적으로 실행됩니다. 목표를 달성하려면 최적의 솔루션을 찾기 위해 솔루션을 향한 이전에 탐색 한 하나 이상의 경로를 저장해야합니다.
많은 문제에서 목표를 향한 경로는 관련이 없습니다. 예를 들어, N-Queens 문제에서는 여왕의 최종 구성과 여왕이 추가되는 순서에 대해 신경 쓸 필요가 없습니다.
언덕 오르기
Hill Climbing은 특정 최적화 문제를 해결하는 기술입니다. 이 기술에서는 차선책으로 시작하여 일부 조건이 최대화 될 때까지 솔루션이 반복적으로 개선됩니다.
차선책으로 시작하는 아이디어는 언덕 밑에서 시작하는 것과 비교되며, 해결책을 개선하는 것은 언덕을 걷는 것과 비교되며, 마지막으로 일부 조건을 최대화하는 것은 언덕 꼭대기에 도달하는 것과 비교됩니다.
따라서 언덕 등반 기술은 다음 단계로 간주 할 수 있습니다.
- 문제의 제약에 따라 차선의 솔루션 구축
- 단계별 솔루션 개선
- 더 이상 개선이 불가능할 때까지 솔루션 개선
Hill Climbing 기술은 주로 계산적으로 어려운 문제를 해결하는 데 사용됩니다. 현재 상태와 즉각적인 미래 상태 만 봅니다. 따라서이 기술은 검색 트리를 유지하지 않으므로 메모리 효율적입니다.
Algorithm: Hill Climbing
Evaluate the initial state.
Loop until a solution is found or there are no new operators left to be applied:
- Select and apply a new operator
- Evaluate the new state:
goal -→ quit
better than current state -→ new current state반복적 인 개선
반복 개선 방법에서는 모든 반복에서 최적의 솔루션을 향해 진행하여 최적의 솔루션을 달성합니다. 그러나이 기술은 국소 최대 값을 만날 수 있습니다. 이 상황에서는 더 나은 솔루션을위한 주변 상태가 없습니다.
이 문제는 다른 방법으로 피할 수 있습니다. 이러한 방법 중 하나는 시뮬레이션 된 어닐링입니다.
무작위 재시작
이것은 로컬 옵티마 문제를 해결하는 또 다른 방법입니다. 이 기술은 일련의 검색을 수행합니다. 매번 무작위로 생성 된 초기 상태에서 시작됩니다. 따라서 수행 된 검색 솔루션을 비교하여 최적 또는 거의 최적의 솔루션을 얻을 수 있습니다.
언덕 등반 기술의 문제점
로컬 맥시마
휴리스틱이 볼록하지 않은 경우 Hill Climbing은 글로벌 최대 값 대신 로컬 최대 값으로 수렴 할 수 있습니다.
능선과 골목
목표 기능이 좁은 능선을 만들면 등반가는 능선을 오르거나 지그재그로 골목을 내려갈 수만 있습니다. 이 시나리오에서 등반가는 목표에 도달하는 데 더 많은 시간이 필요한 매우 작은 단계를 수행해야합니다.
고원
검색 공간이 평평하거나 충분히 평평하여 대상 함수에서 반환 된 값이 해당 값을 나타내는 데 기계가 사용하는 정밀도로 인해 인근 지역에 대해 반환 된 값과 구별 할 수 없을 때 고원이 발생합니다.
언덕 등반 기술의 복잡성
이 기술은 현재 상태 만보기 때문에 공간 관련 문제가 발생하지 않습니다. 이전에 탐색 한 경로는 저장되지 않습니다.
Random-restart Hill Climbing 기술의 대부분의 문제에 대해 다항식 시간에 최적의 솔루션을 얻을 수 있습니다. 그러나 NP-Complete 문제의 경우 계산 시간은 로컬 최대 값 수에 따라 지수가 될 수 있습니다.
언덕 등반 기술의 응용
Hill Climbing 기술은 Network-Flow, Traveling Salesman 문제, 8-Queens 문제, 집적 회로 설계 등과 같은 현재 상태가 정확한 평가 기능을 허용하는 많은 문제를 해결하는 데 사용할 수 있습니다.
Hill Climbing은 귀납적 학습 방법에도 사용됩니다. 이 기술은 팀의 여러 로봇 간의 조정을 위해 로봇 공학에서 사용됩니다. 이 기술이 사용되는 다른 많은 문제가 있습니다.
예
이 기술은 출장 세일즈맨 문제를 해결하는 데 적용될 수 있습니다. 먼저 모든 도시를 정확히 한 번 방문하는 초기 솔루션이 결정됩니다. 따라서이 초기 솔루션은 대부분의 경우 최적이 아닙니다. 이 솔루션조차도 매우 열악 할 수 있습니다. Hill Climbing 알고리즘은 이러한 초기 솔루션으로 시작하여 반복적 인 방식으로 개선합니다. 결국 훨씬 더 짧은 경로를 얻을 수 있습니다.