언덕 오르기 검색 편집하기

언덕 오르기 검색은 검색 [[알고리즘]]으로, 평가함수(evaluation function or objective function)를 사용하여 평가함수 값을 증가·감소시키는 방향으로 나가는 탐색 전략이다. 깊이우선탐색기법(DFS)에 평가함수를 활용한 형태로, 최단 경로의 대한 보장이 없고, 국부최대가 존재할 수 있다. 전체 탐색 공간에 대하여 다른 곳에 더 좋은 경로가 있음에도 한 곳에서만 최대인 곳을 찾는 극대값이다. 이는 과정 회복이 불가능하며 만약 선택한 가지에서 점수가 모두 동점일 경우에는 선택할 경로가 없고, 랜덤 선택을 해야한다.<ref>메정, 〈[https://it-hhhj2.tistory.com/30 탐색 - 경험적기법(언덕등반기법, 최고우선탐색, 빔탐색, A알고리즘, A*알고리즘)]〉, 《티스토리》, 2020-03-27</ref> 현재 노드에서 확장 가능한 이웃 노드들 중에서 휴리스틱에 의한 평가 값이 가장 좋은 것 하나만을 선택해서 확장해 가는 탐색 방법으로, 지역 탐색(local search), 휴리스틱 탐색(heuristic search), 그리디 알고리즘(greedy algorithm)이라고도 한다. 여러 개의 확장 중인 노드들을 관리하지 않고, 현재 확장 중인 노드만을 관리하며, 출발위치·상태에 따라 최적이 아닌 낮은 정상, 국소 최적해(local optimal solution)에 빠질 가능성이 있다.<ref>박준화 JunHwa Park, 〈[https://everyyy.tistory.com/79 인공지능- 탐색과 최적화 - 정보이용 탐색]〉, 《티스토리》, 2019-10-05</ref> 언덕 오르기 검색은 고도 값이 증가하는 방향으로 지속적으로 이동하여 산의 정상 또는 문제에 대한 최상의 솔루션을 찾는 지역 검색 알고리즘이다. 더 높은 값을 가진 이웃이 없는 피크 값에 도달하면 종료된다. 언덕 오르기 검색은 수학 문제를 최적화 하는데 사용되는 기술로, 널리 논의된 예 중 하나는 영업 사원이 이동하는 거리를 최소화해야하는 여행사 문제이다. 욕심 많은 지역 검색이라고도 불리며, 그 주변을 넘어서는 안 되고, 바로 좋은 이웃 지역만 본다. 언덕 오르기 알고리즘의 노드에는 상태와 가치 두 가지 구성 요소가 있으며, 언덕 오르기 검색은 주로 우수한 휴리스틱을 사용할 수 있을 때 사용된다. 이 알고리즘에서는 단일 현재 상태만 유지하므로 검색 트리나 그래프를 유지 관리하고 처리할 필요가 없다.<ref name=자바포인트>Java T Point 공식 홈페이지 - https://www.javatpoint.com/hill-climbing-algorithm-in-ai</ref> 언덕 오르기 검색의 원리는 단순히 루프를 실행하고 값이 증가하는 방향 즉 오르막 방향으로만 지속적으로 이동한다. 루프가 피크에 도달하고 더 높은 값을 가진 이웃이 없으면 루프가 종료된다. 언덕 등반의 변형인 확률적 언덕 오르기 검색은 오르막길에서 무작위로 선택한다. 선택의 가능성은 오르막길의 가파른 정도에 따라 달라질 수 있다. 확률론적 언덕 오르기는 실제로 많은 경우에 더 잘 수행할 수 있다. 언덕 오르기 검색을 사용하면 최대값뿐만아니라 최소값도 찾을 수 있다.<ref> 〈[https://qastack.kr/ai/4000/when-to-choose-stochastic-hill-climbing-over-steepest-hill-climbing  Steepest Hill Climbing에서 Stochastic Hill Climbing을 언제 선택해야합니까? ]〉, 《QAStack》</ref> 그렇게 문제의 종류나 평가 함수 정의에 따라서 최소·최대의 평가 함수를 가지는 노드를 선택해나가는 방법이다.<ref>CTcather, 〈[https://m.blog.naver.com/PostView.nhn?blogId=wallabi&logNo=220363198488&proxyReferer=https:%2F%2Fm.search.naver.com%2Fsearch.naver%3Fquery%3D%25EC%2596%25B8%25EB%258D%2595%2B%25EB%2593%25B1%25EB%25B0%2598%2B%25EA%25B8%25B0%25EB%25B2%2595%26where%3Dm%26sm%3Dmtp_hty.top 2장 탐색]〉, 《네이버 블로그》, 2015-05-18</ref>

언덕 오르기 검색은 휴리스틱 기능을 사용할 수 있는 정보를 기반으로 검색 알고리즘에 있는 모든 잠재적인 대안을 위한 것으로, 알고리즘이 솔루션에 가장 적합한 경로를 선택하도록 도와주는 휴리스틱 검색 수행을 한다. 또한, 생성 및 테스트 방법의 변형이라는 특징을 가지며, 이 언덕 오르기 검색은 생성 및 테스트 방법은 피드백을 생성하여 검색 공간에서 이동할 방향을 결정하는 데 도움이 된다. 탐욕 알고리즘으로 비용을 최적화 하는 방향으로 움직여 로컬 최대 값 최소 값을 찾으며, 이는 이전 상태를 기억하지 않기 때문에 검색 공간을 역추적하지 않는다.<ref name=자바포인트></ref> 마지막으로, 피드백 메커니즘 즉, 이전 계산의 피드백은 다음 동작 과정을 결정하는 데 도움된다.<ref>EDUCBA 공식 홈페이지 - https://www.educba.com/hill-climbing-in-artificial-intelligence/ ''Hill Climbing in Artificial Intelligence'' </ref>

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

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

# 예상 솔루션과 테스트 알고리즘을 생성하는 변형으로 간주되는데, 먼저 최적의 솔루션을 생성하고 예상 여부를 평가한다. 예상한대로 발견되면 중지하고 아니면 다시 해결책을 찾는다.  

확률적 언덕 오르기 검색(Stochastic Hill Climbing)은 이동하기 전에 모든 이웃을 검사하지 않으며, 오히려 이 확률적 언덕 오르기 검색은 하나의 이웃 노드를 무작위로 선택하여 현재 상태로 선택할지 아니면 다른 상태를 검사할지를 결정한다.<ref name=자바포인트></ref> 즉, 모든 이웃에서 더 나은 지역에서 무작위로 더 좋은 지역을 선택하는 검색 방법으로, 선택 가능성은 일반적으로 가파른 정도에 따라 달라진다. 일반적으로 가장 가파른 상승보다 느리게 수렴하지만 일부 지역에서는 더 나은 솔루션을 찾는다.<ref name=스택오버플로우>Md. Abu Nafee Ibna Zahid, 〈[https://stackoverflow.com/questions/38825027/stochastic-hill-climbing-vs-first-choice-hill-climbing-algorithms ''Stochastic hill climbing vs first-choice hill climbing algorithms'']〉, 《stackoverflow》, 2018-03-04</ref> 예를 들어, 특정 지역에서 여러 번 방문·생성된 이웃이나 솔루션을 통해 더 나은 이웃·솔루션을 찾은 경우 현재 상태와 새로운 더 나은 솔루션 간의 확률에 따라 임의로 선택할 수 있다.<ref name=확률대최초>Gusti Ahmad Fanshuri Alfarisy, 〈[https://stackoverrun.com/ko/q/12784171 ''What is the difference between Stochastic Hill Climbing and First Choice Hill Climbing?'']〉, 《stackoverrun》, 2018-07-30</ref>  

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

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

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