언덕 오르기 검색

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

개념

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

종류

쉬운 언덕 오르기 검색

쉬운 언덕 오르기 검색(Simple Hill Climbing)은 탐색 시 현재 노드를 자식 노드와 비교하여 목적 상태와 가장 가까운 노드를 선택할 때, 가장 먼저 찾은 노드를 선택하는 검색 기법이다.

가파른 언덕 오르기 검색

가파른 언덕 오르기 검색(Steepest Hill Climbing)은 모든 자식 노드를 평가한 값을 비교해서 최선의 경로를 찾는 검색 기법이다.

확률적 언덕 오르기 검색

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

최초 선택 언덕 오르기 검색

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

문제

• 지역 최대치(극대값) 문제 (local maxima) : 정상 주변에 정상 보다 낮은 봉우리들이 있을 때, 그 주변 봉우리에 오를 경우 극 곳이 정상인 것으로 판단할 수 있다. 이의 방안은 백트랙킹을 통해 다른 가능한 경로를 탐색하며 이에는 가파른 언덕 오르기검색이 제안된다.

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