언덕 오르기 검색

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

개념

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

종류

쉬운 언덕 오르기 검색

• 알고리즘

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

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

가파른 언덕 오르기 검색

• 알고리즘

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

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

확률적 언덕 오르기 검색

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

최초 선택 언덕 오르기 검색

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

문제

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

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

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

특징

• 변형 생성 및 테스트  : 언덕 오르기 검색 기법은 생성 및 테스트 방법의 변형이다. 생성 및 테스트 방법은 피드백을 생성하여 검색 공간에서 이동할 방향을 결정하는 데 도움이 된다.

• 욕심 접근  : 언덕 오르기 검색 기법은 비용을 최적화 하는 방향으로 움직인다.

• 역 추적 없음  : 이전 상태를 기억하지 않기 때문에 검색 공간을 역추적하지 않는다.

참고 자료

• 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
• Gusti Ahmad Fanshuri Alfarisy, 〈What is the difference between Stochastic Hill Climbing and First Choice Hill Climbing?〉, 《stackoverrun》, 2018-07-30
• 메정, 〈탐색 - 경험적기법(언덕등반기법, 최고우선탐색, 빔탐색, A알고리즘, A*알고리즘)〉, 《티스토리》, 2020-03-27
• 〈Steepest Hill Climbing에서 Stochastic Hill Climbing을 언제 선택해야합니까? 〉, 《QAStack》

같이 보기

• 알고리즘

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

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 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 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반