힐 클라이밍

섬네일|최대값이 하나만 있는 표면이다. 힐 클라이밍 기술은 이러한 표면을 최적화하는 데 매우 적합하며 전역 최대값으로 수렴된다.
힐 클라이밍(hill climbing)은 수치해석학에서 지역 탐색 계열에 속하는 수학적 최적화 기술이다.

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

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

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

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

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

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

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

수학적 설명

힐 클라이밍은 함수 를 최대화(또는 최소화)하려고 시도하며, 여기서 는 연속 및 이산 값의 벡터이다. 각 반복에서 힐 클라이밍은 의 단일 요소를 조정하고 변경이 의 값을 개선하는지 여부를 결정한다. (이는 각 반복에서 언덕의 기울기에 따라 의 모든 값을 조정하는 경사 하강법과 다르다는 점에 유의한다.) 힐 클라이밍에서는 를 개선하는 모든 변경이 허용되며, 의 값을 개선할 수 있는 변경을 더 이상 찾을 수 없을 때까지 프로세스가 계속된다. 그러면 는 "지역적으로 최적"이라고 말한다.

이산 벡터 공간에서 의 각 가능한 값은 정점으로 시각화될 수 있다. 힐 클라이밍은 그래프를 정점에서 정점으로 따라가며 항상 의 값을 국부적으로 증가(또는 감소)시키다가 지역 최대 (또는 지역 최소) 에 도달한다.

변형

단순 힐 클라이밍에서는 첫 번째로 더 가까운 노드를 선택하는 반면, 최대 경사 힐 클라이밍에서는 모든 후계자를 비교하고 해에 가장 가까운 것을 선택한다. 두 형식 모두 더 가까운 노드가 없으면 실패하는데, 이는 해가 아닌 지역 최대가 탐색 공간에 있을 때 발생할 수 있다. 최대 경사 힐 클라이밍은 현재 경로의 모든 가능한 확장을 시도하는 최상 우선 탐색과 유사하다.

확률적 힐 클라이밍은 이동 방법을 결정하기 전에 모든 이웃을 검사하지 않는다. 대신 무작위로 이웃을 선택하고 (해당 이웃의 개선 정도에 따라) 해당 이웃으로 이동할지 아니면 다른 이웃을 검사할지 결정한다. 첫 번째 선택 힐 클라이밍은 더 나은 이웃이 생성될 때까지 무작위로 이웃을 생성하여 확률적 힐 클라이밍을 구현하며, 이 이웃이 선택된다. 이 방법은 상태에 많은 가능한 후계자(예: 수천 개)가 있을 때 잘 작동한다.

좌표 하강법은 각 반복에서 현재 지점에서 하나의 좌표 방향을 따라 직선 탐색을 수행한다. 일부 버전의 좌표 하강법은 각 반복에서 무작위로 다른 좌표 방향을 선택한다.

무작위 재시작 힐 클라이밍은 힐 클라이밍 알고리즘 위에 구축된 메타 알고리즘이다. 또한 샷건 힐 클라이밍으로도 알려져 있다. 무작위 초기 조건 으로 힐 클라이밍을 반복적으로 수행한다. 최상의 이 유지된다. 힐 클라이밍의 새 실행이 저장된 상태보다 더 나은 을 생성하면 저장된 상태를 대체한다.

문제점

지역 최대
섬네일|260px|두 개의 지역 최대를 가진 표면. (그 중 하나만 전역 최대이다.) 힐 클라이머가 좋지 않은 위치에서 시작하면 낮은 최대로 수렴할 수 있다.

힐 클라이밍은 반드시 전역 최대를 찾지는 못하고 대신 지역 최대로 수렴할 수 있다. 이 문제는 휴리스틱이 볼록하면 발생하지 않는다. 그러나 많은 함수가 볼록하지 않으므로 힐 클라이밍은 전역 최대에 도달하는 데 종종 실패할 수 있다. 다른 지역 탐색 알고리즘은 확률적 힐 클라이밍, 무작위 행보 및 담금질 기법과 같은 이 문제를 극복하려고 시도한다.

섬네일|left|500px|이 그래프에 많은 지역 최대가 있음에도 불구하고 담금질 기법을 사용하여 전역 최대를 찾을 수 있다. 불행히도 담금질 기법의 적용 가능성은 위치를 개선하는 운 좋은 도약을 찾는 데 의존하기 때문에 문제에 따라 다르다. 이러한 극단적인 예에서는 힐 클라이밍이 대부분 지역 최대를 생성한다.

능선과 골목

섬네일|190px|능선

능선은 연속 공간에서 최적화하는 힐 클라이머에게 어려운 문제이다. 힐 클라이머는 한 번에 벡터의 한 요소만 조정하기 때문에 각 단계는 축 정렬 방향으로 이동한다. 목표 함수가 축 정렬되지 않은 방향으로 상승하는 좁은 능선(또는 목표가 최소화하는 경우 축 정렬되지 않은 방향으로 하강하는 좁은 골목)을 생성하는 경우, 힐 클라이머는 지그재그 방식으로만 능선을 오르거나 골목을 내려갈 수 있다. 능선(또는 골목)의 측면이 매우 가파르면 힐 클라이머는 더 나은 위치로 지그재그로 이동할 때 매우 작은 보폭을 취해야 할 수도 있다. 따라서 능선을 오르거나 골목을 내려가는 데 엄청나게 오랜 시간이 걸릴 수 있다.

대조적으로, 경사 하강법은 능선이나 골목이 오르거나 내릴 수 있는 모든 방향으로 이동할 수 있다. 따라서 목표 함수가 미분 가능할 때 켤레기울기법 또는 경사 하강법이 일반적으로 힐 클라이밍보다 선호된다. 그러나 힐 클라이머는 목표 함수가 미분 가능할 필요가 없다는 장점이 있으므로 목표 함수가 복잡할 때 힐 클라이머가 선호될 수 있다.

고원
힐 클라이밍에서 때때로 발생하는 또 다른 문제는 고원이다. 고원은 탐색 공간이 평평하거나, 기계가 값을 나타내는 데 사용하는 정밀도 때문에 대상 함수가 반환하는 값이 주변 영역에 대해 반환되는 값과 구별할 수 없을 정도로 충분히 평평할 때 발생한다. 이러한 경우 힐 클라이머는 어느 방향으로 나아가야 할지 결정할 수 없으며 개선으로 이어지지 않는 방향으로 방황할 수 있다.

 같이 보기 
 경사 하강법
 탐욕 알고리즘
 A* 알고리즘

 출처 
 

 각주 

분류:검색 알고리즘
분류:메타휴리스틱