언덕 오르기 검색

언덕 오르기 검색은 수치 분석에서 지역 검색 패밀리에 속하는 수학적 최적화 기술을 말하며, 깊이 우선 탐색기법(DFS, Depth - first search)을 기초로 하여 휴리스틱을 적용한 탐색기법이다. 현재 상태와 자식 노드와의 거리 혹은 비용에 따라 정렬한 후 각 단계의 선택이 이전 단계의 상태보다 나은지를 평가하는 것이다.

개념

언덕 오르기 검색은 검색 알고리즘으로, 평가함수(evaluation function or objective function)를 사용하여 평가함수 값을 증가·감소시키는 방향으로 나가는 탐색 전략이다. 깊이우선탐색기법(DFS)에 평가함수를 활용한 형태로, 최단 경로의 대한 보장이 없고, 국부최대가 존재할 수 있다. 전체 탐색 공간에 대하여 다른 곳에 더 좋은 경로가 있음에도 한 곳에서만 최대인 곳을 찾는 극대값이다. 이는 과정 회복이 불가능하며 만약 선택한 가지에서 점수가 모두 동점일 경우에는 선택할 경로가 없고, 랜덤 선택을 해야한다. 현재 노드에서 확장 가능한 이웃 노드들 중에서 휴리스틱에 의한 평가 값이 가장 좋은 것 하나만을 선택해서 확장해 가는 탐색 방법으로, 지역 탐색(local search), 휴리스틱 탐색(heuristic search), 그리디 알고리즘(greedy algorithm)이라고도 한다. 여러 개의 확장 중인 노드들을 관리하지 않고, 현재 확장 중인 노드만을 관리하며, 출발위치·상태에 따라 최적이 아닌 낮은 정상, 국소 최적해(local optimal solution)에 빠질 가능성이 있다. 언덕 오르기 검색 기법은 고도 값이 증가하는 방향으로 지속적으로 이동하여 산의 정상 또는 문제에 대한 최상의 솔루션을 찾는 지역 검색 알고리즘이다. 더 높은 값을 가진 이웃이 없는 피크 값에 도달하면 종료된다. 언덕 오르기 검색 알고리즘은 수학 문제를 최적화 하는데 사용되는 기술로, 널리 논의된 예 중 하나는 영업 사원이 이동하는 거리를 최소화해야하는 여행사 문제이다. 욕심 많은 지역 검색이라고도 불리며, 그 주변을 넘어서는 안 되고, 바로 좋은 이웃 지역만 본다. 언덕 오르기 알고리즘의 노드에는 상태와 가치 두 가지 구성 요소가 있으며, 언덕 오르기 검색 기법은 주로 우수한 휴리스틱을 사용할 수 있을 때 사용된다. 이 알고리즘에서는 단일 현재 상태만 유지하므로 검색 트리나 그래프를 유지 관리하고 처리할 필요가 없다. 언덕 오르기 검색의 원리는 단순히 루프를 실행하고 값이 증가하는 방향 즉 오르막 방향으로만 지속적으로 이동한다. 루프가 피크에 도달하고 더 높은 값을 가진 이웃이 없으면 루프가 종료된다. 언덕 등반의 변형인 확률적 언덕 오르기 검색은 오르막길에서 무작위로 선택한다. 선택의 가능성은 오르막길의 가파른 정도에 따라 달라질 수 있다. 확률론적 언덕 오르기는 실제로 많은 경우에 더 잘 수행할 수 있다. 언덕 오르기 검색 알고리즘을 사용하면 최대값뿐만아니라 최소값도 찾을 수 있다. 그렇게 문제의 종류나 평가 함수 정의에 따라서 최소·최대의 평가 함수를 가지는 노드를 선택해나가는 방법이다.

공간 구성

• 로컬 최대 값 (Local Maxima) : 주변 상태보다 나은 상태를 말하지만, 이보다 더 나은 상태인 전역 최대 값이 있는데 이 상태는 목적 함수의 값이 이웃보다 높기 때문에 더 좋다.

• 글로벌 최대 (Global Maxima) : 상태 공간 다이어그램에서 가능한 최상의 상태를 말하며, 이것은 이 상태에서 목적 함수가 가장 높은 값을 갖는다.

• 고원·평평한 극대 최대 값 (Plateau/flat local maxima) : 인접 상태의 값이 같은 평평한 상태 공간 영역을 말한다.

• 릿지 (Ridge) : 이웃보다 높지만 경사가 있는 지역이다. 특별한 종류의 로컬 최대 값을 말한다.

• 현재 상태 (Current state) : 검색 중에는 현재 존재하는 상태 공간 다이어그램 영역을 말한다.

특징

먼저, 언덕 오르기 검색기법은 휴리스틱 기능을 사용할 수 있는 정보를 기반으로 검색 알고리즘에 있는 모든 잠재적인 대안을 위한 것으로, 알고리즘이 솔루션에 가장 적합한 경로를 선택하도록 도와주는 휴리스틱 검색 수행을 한다. 다음으로 언덕 오르기 검색 기법은 생성 및 테스트 방법의 변형이라는 특징을 갖는다. 생성 및 테스트 방법은 피드백을 생성하여 검색 공간에서 이동할 방향을 결정하는 데 도움이 된다. 세 번째로, 언덕 오르기 검색 기법은 비용을 최적화 하는 방향으로 움직인다. 다음으로, 언덕 오르기 검색기법은 역 추적이 없는데, 이전 상태를 기억하지 않기 때문에 검색 공간을 역추적하지 않는다. 그리고 언덕 오르기 검색 기법은 피드백 메커니즘 즉, 이전 계산의 피드백은 다음 동작 과정을 결정하는 데 도움된다. 또한, 탐욕 알고리즘으로 알고리즘은 비용을 최적화 하는 방향으로 이동하는데 즉, 로컬 Maxima/Minima 를 찾는 것이다.

알고리즘

알고리즘 설명1

1. 시작할 곳을 고른다.
2. 오르막으로 가는 모든 단계를 수행한다.
3. 더 이상 오르막 계단이 없으면 중지하고, 그렇지 않으면 오르막길을 계속 걷는다.

알고리즘 설명2

1. 루트 노드를 큐Q에 넣어 첫 번째 요소로 하고 깊이우선 탐색을 수행한다.
2. Q가 비어 있거나 목표에 이를 때까지 수행한다. Q에 있는 첫 번째 요소가 목표인지를 결정한다. 만약 목표가 아니라면 Q에서 첫 번째 요소를 제거하고, 그 자식 노드들을 잔여거리(remaining distance)에 따라 정렬(sort)하고, 정렬된 리스트를 Q의 앞쪽에 배치한다. 목표가 아닌 상태에서 자식노드가 없으면 부모노드로 간다.
3. 만약 목표에 도달하면 성공이고, 그렇지 않으면 실패이다.

종류

최초 선택 언덕 오르기 검색

최초 선택 언덕 오르기 검색(First-Choice Hill Climbing)은 방문했던 이웃이거나 계산된 것이 아닌, 처음에 발견한 더 나은 상태를 선택한다. 즉, 최초 선택 언덕 오르기 검색은 무작위로 생성된 이웃에서 첫 번째로 더 나은 지역을 선택한다. 현재 상태보다 나은 후자가 생성될 때까지 후임자를 무작위로 생성하여 확률적 언덕 오르기 검색을 구현하는 것이다. 만약 현재 지역에 많은 이웃 즉, 후자가 있다면 최초 언덕 오르기 검색이 좋은 전략이 될 것이다. 예를 들면, 현재 상태가 검색 공간에서 10,000 개의 이웃을 갖는 경우나 현 상태가 여러번 또는 처음 방문한 후 더 좋은 이웃 상태를 찾은 후 즉시 선택한다. 최초 선택 언덕 오르기 검색은 현재 상태에 많은 이웃이 있는 경우 좋은 전략이 된다.

간단한 언덕 오르기 검색

• 알고리즘

1. 초기 상태를 평가하고 목표 상태인 경우 성공을 리턴하고 중지한다.
2. 루프 솔루션을 찾거나 신청할 새 운영자가 없을 때까지 루프한다.
3. 운영자를 선택하고 현재 상태에 적용한다.
4. 새로운 상태를 확인한다.(목표 상태인 경우 성공을 리턴하고 종료한다. / 그렇지 않으면 현재 상태보다 낫다면 새 상태를 현재 상태로 지정한다. / 그렇지 않으면 현재 상태보다 나쁘지 않으면 2단계로 돌아간다.)
5. 종료한다.

간단한 언덕 오르기 검색(Simple Hill Climbing)은 탐색 시 현재 노드를 자식 노드와 비교하여 목적 상태와 가장 가까운 노드를 선택할 때, 가장 먼저 찾은 노드를 선택하는 검색 기법이다. 언덕 오르기 검색 기법을 구현하는 가장 간단한 방법으로, 한 번에 인접 노드 상태만 평가하고 현재 비용을 최적화하여 현재 상태로 설정하는 첫 번째 노드 상태를 선택한다. 그것은 후속 상태인지 확인하고, 현재 상태보다 더 좋으면 다른 상태로 이동한다. 이 쉬운 언덕 오르기 검색기법은 시간 소모가 적으며, 최적의 솔루션이 아니고, 해결책이 보장되지 않는다.

가파른 언덕 오르기 검색

• 알고리즘

1. 초기 상태를 평가하고 목표 상태인 경우 성공을 리턴하고 중지한다. 그렇지 않으면 현재 상태를 초기 상태로 만든다.
2. 솔루션을 찾거나 현재 상태가 변경되지 않을 때까지 반복한다.(SUCC를 현재 상태의 후속 작업이 그보다 나은 상태로 둔다. / 현재 상태에 적용되는 각 연산자의 경우에 새연산자를 적용하고 새 상태를 생성하고, 새로운 상태를 평가한다. 목표 상태인 경우 반환하고 종료한 다음 SUCC와 비교한 후 SUCC보다 나은 경우 새 상태를 SUCC로 설정한다. 만약 SUCC가 현재 상태보다 나은 경우에는 현재 상태를SUCC로 설정한다.)
3. 종료

가파른 언덕 오르기 검색(Steepest Hill Climbing)은 모든 자식 노드를 평가한 값을 비교해서 최선의 경로를 찾는 검색 기법이다. 쉬운 언덕 오르기 검색 기법의 변형으로, 현재 상태의 모든 인접 노드를 검사하고 목표 상태에 가장 가까운 하나의 인접 노드를 선택한다. 이 기법은 여러 이웃을 검색할 때 더 많은 시간을 소비한다.

확률적 언덕 오르기 검색

• 알고리즘

1. 방향에 관계없이 비용 함수를 줄일 수 있는 상태를 찾는 과정에서 탐욕스러운 접근 방식을 사용한다.
2. 예상 솔루션과 테스트 알고리즘을 생성하는 변형으로 간주되는데, 먼저 최적의 솔루션을 생성하고 예상 여부를 평가한다. 예쌍한대로 발견되면 중지하고 아니면 다시 해결책을 찾는다.
3. 이전 공간을 기억할 메모리가 없기 때문에 역 추적 방식을 수행하지 않는다.

확률적 언덕 오르기 검색(Stochastic Hill Climbing)은 이동하기 전에 모든 이웃을 검사하지 않으며, 오히려 이 확률적 언덕 오르기 검색기법은 하나의 이웃 노드를 무작위로 선택하여 현재 상태로 선택할지 아니면 다른 상태를 검사할지를 결정한다. 즉, 모든 이웃에서 더 나은 지역에서 무작위로 더 좋은 지역을 선택하는 검색 방법으로, 선택 가능성은 일반적으로 가파른 정도에 따라 달라진다. 일반적으로 가장 가파른 상승보다 느리게 수렴하지만 일부 지역에서는 더 나은 솔루션을 찾는다. 예를 들어, 특정 지역에서 여러 번 방문·생성된 이웃이나 솔루션을 통해 더 나은 이웃·솔루션을 찾은 경우 현재 상태와 새로운 더 나은 솔루션 간의 확률에 따라 임의로 선택할 수 있다.

언덕 오르기 검색의 기술응용

언덕 오르기 검색의 기술은 현재 상태가 네트워크 흐름, 출장 세일즈맨 문제, 8-퀸즈 문제, 집적회로 설계 등과 같은 정확한평가 기능을 허용하는 많은 문제를 해결하는 데 사용될 수 있다. 언덕 오르기 검색의 알고리즘을 사용하여 최적의 솔루션을 찾을 수 있는 다양한 마케팅 영역에서 팀 관리에 도움이 될 수 있는데, 판매원이 하루에 방문한 장소에서 소요되는 이동시간은 이 알고리즘이 최적화되어있다. 언덕 오르기 검색은 귀납적 학습 방법에도 사용되는데, 이 기술은 팀에서 여러 로봇 사이의 조정을 위해 로봇 공학에 사용된다. 로봇 시스템에서 주로 사용되어 시스템이 팀으로 작동하고 조정을 유지하는데 도움이 된다. 이 외에도 다른 문제에 많이 사용되는데 대표적으로 출장 중인 판매원 문제를 해결하는 데 적용할 수 있다. 먼저 모든 도시를 정확히 한 번 방문하는 초기 솔루션이 결정되고, 이 초기 솔루션은 대부분 경우에 최적이 아니다. 이 솔루션 조차 열악할 수 있으며 언덕 오르기 검색 알고리즘은 이러한 초기 솔루션으로 시작하여 반복적인 방법으로 개선한다. 그러면 결국에는 훨씬 더 짧은 경로를 얻을 수 있다.

대표문제

• 출장 세일즈맨 문제 (TSP) : 출장 세일즈맨 문제는 Travelling Salesman Problem 으로 'TSP'라고도 한다. 물건을 판매하기 위해 여행하는 세일즈맨의 문제로, 물건을 팔기 위해서 어떤 도시를 먼저 방문해서 최소한의 비용으로 도시들을 모두순회하고 돌아올 수 있는지를 구하는 문제이다. 출장 세일즈맨 문제(TSP)는 NP-난해(NP-Hard)의 가장 대표적인 문제로 Nondeterministic Polynomial - Hard의 약자이다. 다항식으로 표현될 수 있을 지의여부가 아직 알려지지 않았다는 의미로, NP-난해란 출장 세일즈맨 문제와 같이 모든 경우의 수를 일일히 확인해보는 방법 이외에는 다항식처럼 답을 풀이할 수 없는 문제들을 말한다.

• 8-퀸 문제 (Eight-Queens Problem) : 8-퀸 문제는 여덟 여왕 퍼즐에 대해 자체의 회전 및 반사를 제외하고 유일한 대칭 솔루션이다. 8개의 퀸즈 퍼즐은 체스 퀸을 8 x 8 체스 판에 놓아 두 명의 여왕이 서로를 위협하지 않는 문제이다. 따라서, 해를 구하기 위해 두 개의 여왕이 같은 행, 열 또는 대각선을 공유하지 않아야 한다. 8x8 보드에 8개의 퀸의 4,426,165,368의 가능한 배열이 있지만 92개의 솔루션만 있기때문에 문제는 계산 비용이 많이 들 수 있다. 이 8-퀸 문제에 대한 모든 솔루션을 찾는 것은 간단하지만 사소한 문제의 좋은 예이다.

문제점

언덕 오르기 검색 기법의 단점은 유사한 상황이 생길 수 있다는 점이다. 작은언덕(foothill)에서 시작할 경우는 그 지점에서 너무 많은 시간을 소비하여 목표에 이르지 못할 것이다. 고원의 평지(plateaus)와 같은 평탄한 곳에서는 비교할 대상을 찾지 못해 어떤 방향으로 가야할지 결정하지 못하고 목적없이 방황할 수 있다. 어느 완만한 산등성이(ridge)에서는 목표인지 알고 내려올 수 있겠지만 정상이 아닌 것이다.

• 로컬 최대 값 (Local Maximum) : 로컬 최대 값은 주변의 각 상태보다 나은 풍경의 피크 상태이지만 로컬 최대 값보다 높은 다른 상태도 있다. 정상 주변에 정상 보다 낮은 봉우리들이 있을 때, 그 주변 봉우리에 오를 경우 그 곳이 정상인 것으로 판단할 수 있다. 이에 해결방안은 백트랙킹을 통해 다른 가능한 경로를 탐색하며 이에는 가파른 언덕 오르기검색이 제안된다. 역 추적 기술은 상태 공간에서 지역 최대의 솔루션이 될 수 있어, 알고리즘이 검색 공간을 역 추적하고 다른 경로도 탐색할 수 있도록 유망한 경로 목록을 작성한다.

• 능선 문제 (ridge) : 능선은 지역 최대 값의 특수한 형태로, 주변 지역보다 높은 지역을 갖고 있지만 자체적으로 경사가 있으며 한 번에 도달할 수 없다. 날카로운 능선 상에 위치하고 있을 때 정해진 동·서·남·북 어느 방향으로 이동하더라도 고도가 낮아져서 정상으로 오판하게 되는 문제이다. 이동방향의 해상도와 관련된 문제로, 지역 최대치가 연이어 있는 상황에 해당한다. 이에 검사 방향을 늘리거나 연산자들을 조합하여 적용한 결과를 사용해야하는 방안이 있다. 양방향 검색을 사용하거나 다른 방향으로 이동하면 이 문제를 개선할 수 있다.

• 고원(대지) 문제 (plateau; shoulder) : 고원은 현재 상태의 모든 인접 상태 즉 사방이 모두 동일한 값을 포함하는 검색 공간의 평평한 영역으로, 이동하기에 가장 적합한 방향을 찾지 못 한다. 고원 지역에서 언덕 오르기 검색이 손실될 수 있다. 산 중턱에 존재하는데 모두 동일해서 판단할 수 없는 평평한 영역에 도달했을 경우, 어느 방향으로 이동해도 현재 상황을 개선할 수 없다. 이에 동일 연산자를 반복 적용한 결과를 토대로 진행 방향을 결정해야하는 방안을 세운다. 안정을 위한 해결책은 문제를 해결하기 위해 검색하는 동안 큰 단계나 아주 작은 단계를 수행하는 것으로, 알고리즘이 고원이 아닌 영역을 찾을 수 있도록 현재 상태에서 멀리 떨어진 상태를 무작위로 선택하면 된다.

시뮬레이션 어닐링

더 낮은 값으로 이동하지 않는 언덕 오르기 검색기법은 로컬 최대 값에 도달할 수 있기 때문에 불완전한 것으로 보장된다. 알고리즘이 후임자를 이동하여 임의의 보행을 적용하면 완료되지만 효율적이지 않을 수 있다. 시뮬레이션 어닐링은 효율성과 완전성을 모두 제공하는 알고리즘이다. 기계적으로, 어닐링이라는 용어는 금속 또는 유리를 고온으로 경화시킨 후 점진적으로 냉각시키는 과정을 말하는데, 금속이 저에너지 결정 상태에 도달하게 한다. 알고리즘이 최상의 움직임을 선택하는 대신 임의의 움직임을 선택하는 시뮬레이션 어닐링에 동일한 프로세스가 사용된다. 무작위 이동이 상태를 개선하면 동일한 경로를 따르고 그렇지 않으면, 알고리즘은 확률이 1보다 작은 경로를따르거나 내리막 길로 이동하여 다른 경로를 선택한다.

참고 자료

• CTcather, 〈2장 탐색〉, 《네이버 블로그》, 2015-05-18
• user5492770, 〈Stochastic hill climbing vs first-choice hill climbing algorithms〉, 《stackoverrun》, 2016-08-08
• 빨간당무, 〈Simple hill climbing, Steepest hill climbing (쉬운 언덕 등반과 가파른 언덕 등반)〉, 《티스토리》, 2017-04-15
• Md. Abu Nafee Ibna Zahid, 〈Stochastic hill climbing vs first-choice hill climbing algorithms〉, 《stackoverflow》, 2018-03-04
• sammiberk, 〈Eight-Queens Problem〉, 《GitHub》, 2018-05-21
• Gusti Ahmad Fanshuri Alfarisy, 〈What is the difference between Stochastic Hill Climbing and First Choice Hill Climbing?〉, 《stackoverrun》, 2018-07-30
• 박준화 JunHwa Park, 〈인공지능- 탐색과 최적화 - 정보이용 탐색〉, 《티스토리》, 2019-10-05
• 메정, 〈탐색 - 경험적기법(언덕등반기법, 최고우선탐색, 빔탐색, A알고리즘, A*알고리즘)〉, 《티스토리》, 2020-03-27
• 〈Steepest Hill Climbing에서 Stochastic Hill Climbing을 언제 선택해야합니까? 〉, 《QAStack》
• Java T Point 공식 홈페이지 - https://www.javatpoint.com/hill-climbing-algorithm-in-ai

같이 보기

• 알고리즘

이 언덕 오르기 검색 문서는 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 BM25 • FAISS • 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 벡터검색 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 역문서빈도(IDF) • 용어빈도(TF) • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반