힐 클라이밍

힐 클라이밍(hill climbing)은 수치해석학에서 지역 탐색 계열에 속하는 수학적 최적화 기술이다.

문제에 대한 임의의 솔루션으로 시작한 다음 솔루션을 점진적으로 변경하여 더 나은 솔루션을 찾으려고 시도하는 반복 알고리즘이다. 변경으로 인해 더 나은 솔루션이 생성되면 새 솔루션에 또 다른 점진적인 변경이 이루어지며 더 이상 개선 사항을 찾을 수 없을 때까지 계속된다.

예를 들어, 힐 클라이밍은 여행하는 외판원 문제에 적용될 수 있다. 모든 도시를 방문하는 초기 솔루션을 찾는 것은 쉽지만 최적 솔루션에 비해 매우 열악할 가능성이 높다. 알고리즘은 이러한 솔루션에서 시작하여 두 도시를 방문하는 순서를 바꾸는 등 작은 개선을 거친다. 결국에는 훨씬 더 짧은 경로가 확보될 가능성이 높다.

힐 클라이밍에서는 볼록 문제에 대한 최적의 솔루션을 찾는다. 다른 문제의 경우 모든 가능한 솔루션 중에서 반드시 최상의 솔루션(전역 최적)이 될 수는 없는 지역 최적값(인접 구성으로 개선할 수 없는 솔루션)만 찾는다(탐색 공간).

힐 클라이밍을 통해 볼록 문제를 해결하는 알고리즘의 예로는 선형 계획법 및 이진 탐색을 위한 단순 알고리즘이 있다.^[1]:253

지역 최적 상태에 갇히지 않으려면 다시 시작(예: 반복된 지역 탐색)을 사용하거나 반복(예: 반복 지역 탐색), 메모리(예: 반응 탐색 최적화 및 금기 탐색)를 기반으로 하는 더 복잡한 체계를 사용할 수 있다. 메모리가 없는 확률론적 수정(예: 시뮬레이션된 어닐링)

알고리즘의 상대적 단순성으로 인해 최적화 알고리즘 중에서 가장 먼저 선택되는 인기 있는 알고리즘이다. 인공지능에서는 시작 노드에서 목표 상태에 도달하기 위해 널리 사용된다. 관련 알고리즘에서는 다음 노드와 시작 노드에 대한 서로 다른 선택이 사용된다. 담금질 기법 또는 금기 탐색과 같은 고급 알고리즘이 더 나은 결과를 제공할 수 있지만 일부 상황에서는 힐 클라이밍도 잘 작동한다. 힐 클라이밍은 실시간 시스템과 같이 탐색을 수행하는 데 사용할 수 있는 시간이 제한되어 있을 때 일반적으로 적은 수의 증분이 좋은 솔루션(최적 솔루션)에 수렴되는 한 다른 알고리즘보다 더 나은 결과를 생성할 수 있다. 다른 극단적인 경우, 버블 정렬은 힐 클라이밍 알고리즘으로 볼 수 있다(모든 인접 요소 교환은 무질서한 요소 쌍의 수를 감소시킨다). 그러나 이 접근 방식은 필요한 교환 수가 2차적으로 증가하므로 적당한 N에 대해서도 효율적이지 않다.

힐 클라이밍은 언제든지 알고리즘이다. 끝나기 전에 언제든지 중단되더라도 유효한 솔루션을 반환할 수 있다.

• 경사 하강법
• 탐욕 알고리즘
• A* 알고리즘

• Russell, Stuart J.; Norvig, Peter (2003), 《Artificial Intelligence: A Modern Approach》 2판, Upper Saddle River, New Jersey: Prentice Hall, 111–114쪽, ISBN 0-13-790395-2