[용어] hill-climbing(언덕 오르기) 탐색 알고리즘

 

 

(개념) 현재 상태에서 출발해 이웃 상태들을 평가하고, 더 나은 이웃으로 계속 이동하는 국소 탐색(local search) 알고리즘

 

더 이상 개선되는 이웃이 없으면 그 자리에서 멈춥니다. 위 그림처럼 탐색 공간을 지형으로 비유하면, 지금 서 있는 곳에서 "위로만" 이동하다가 가장 가까운 봉우리에 도달하면 멈추는 방식.

 

 

일정 관리, 외판원 문제(TSP) 근사해, 신경망 구조 탐색(NAS), 하이퍼파라미터 튜닝, 게임 AI의 휴리스틱 탐색, 물류·생산 공정 최적화 등 — 정확한 최적해보다 "충분히 좋은 해"를 빠르게 얻어야 하는 상황에서 폭넓게 쓰입니다.

 

가능성(강점)

• 구현이 단순함 — 현재 상태 하나만 유지하면 되므로 메모리 사용이 매우 적음
• 계산 비용이 낮음 — 이웃 평가만 반복하면 되어 큰 탐색 공간에서도 빠르게 동작
• 탐색 공간이 매끄러운(unimodal) 경우 효과적 — 봉우리가 하나뿐인 문제에서는 전역 최적점에 잘 도달함

한계

• 지역 최적점(local optimum)에 갇힘 — 그림의 왼쪽 낮은 봉우리처럼, 전역 최적점보다 낮은 봉우리에서 멈춰버릴 수 있음
• 평지(plateau) — 이웃 해들의 값이 모두 같으면 어느 방향으로 가야 할지 판단 불가
• 능선(ridge) — 최적 경로가 좁고 대각선 형태일 때 지그재그로 비효율적으로 움직임

한계를 보완하는 변형들 (가능성을 넓히는 방법)

• 무작위 재시작(random-restart): 서로 다른 시작점에서 여러 번 반복해 더 나은 봉우리를 찾을 확률을 높임
• 확률적 hill climbing(stochastic): 개선되는 이웃 중 무작위로 선택해 다양성 확보
• first-choice hill climbing: 모든 이웃을 다 보지 않고 개선되는 첫 이웃을 바로 선택 — 이웃이 매우 많을 때 효율적
• 담금질 기법(simulated annealing): 일정 확률로 더 나쁜 해도 수용해 지역 최적점을 탈출할 여지를 둠
• 타부 탐색(tabu search): 최근 방문한 상태를 금지 목록에 넣어 같은 곳을 맴돌지 않게 함