로컬 검색(최적화)

이 글은 일반적인 참고문헌 목록을 포함하고 있지만, 그에 상응하는 인라인 인용구가 충분하지 않기 때문에 대체로 검증되지 않은 상태로 남아 있다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2015년 5월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기)

컴퓨터 과학에서 국지적 검색은 계산적으로 하드 최적화 문제를 해결하기 위한 경험적 접근법이다. 지역 검색은 여러 후보 솔루션 중에서 기준을 극대화하는 해결책을 찾는 것으로 공식화될 수 있는 문제에 사용할 수 있다. 로컬 검색 알고리즘은 최적이라고 판단되는 솔루션이 발견되거나 제한 시간이 경과될 때까지 로컬 변경사항을 적용하여 후보 솔루션(검색 공간)의 공간에서 솔루션에서 솔루션으로 이동한다.

지역 검색 알고리즘은 컴퓨터 공학(특히 인공지능), 수학, 운영 연구, 공학, 생물 정보학 등의 문제를 포함한 수많은 하드 컴퓨터 문제에 폭넓게 적용되고 있다. 로컬 검색 알고리즘의 예로는 트래블 세일즈맨 문제의 2-옵션 알고리즘인 워크SAT와 메트로폴리스-해스팅 알고리즘이 있다.^[1]

예

로컬 검색이 적용된 몇 가지 문제는 다음과 같다.

1. 솔루션이 그래프의 꼭지점 커버인 정점 커버 문제 및 목표는 최소 노드 수로 솔루션을 찾는 것이다.
2. 해결책은 그래프의 모든 노드를 포함하는 사이클이고 목표는 사이클의 전체 길이를 최소화하는 것이다.
3. 후보 해법이 진실 과제인 부울 만족도 문제, 그리고 목표는 할당에 의해 충족되는 조항의 수를 최대화하는 것이다. 이 경우 최종 해결책은 모든 조항에 만족하는 경우에만 사용된다.
4. 해결책이 간호사의 모든 확립된 제약을 만족시키는 교대조치에 대한 할당인 간호사 스케줄링 문제
5. k-medoid 클러스터링 문제 및 기타 관련 시설 위치 문제(로컬 검색 시 최악의 경우에서 가장 잘 알려진 근사비)
6. Hopfield 네트워크에서 안정적인 구성을 찾는 Hopfield Neural Networks 문제.

설명

대부분의 문제들은 검색 공간과 여러 가지 다른 방식으로 목표를 세울 수 있다. 예를 들어, 여행 중인 세일즈맨 문제의 경우 해결책은 사이클이 될 수 있으며, 최대화하는 기준은 노드 수와 사이클 길이를 조합한 것이다. 그러나 해결책도 하나의 경로가 될 수 있고, 순환이 되는 것도 목표의 일부분이다.

로컬 검색 알고리즘은 후보 솔루션에서 시작하여 반복적으로 인접 솔루션으로 이동한다. 이는 검색 공간에 근린관계가 정의되어 있는 경우에만 가능하다. 예를 들어, 꼭지점 커버의 근방은 한 노드에 의해서만 다른 또 다른 꼭지점 커버다. 부울 만족도를 위해, 진실 과제의 이웃들은 보통 변수의 평가에 의해 그것과 다른 진실 과제에 불과하다. 동일한 문제에는 여러 개의 서로 다른 이웃이 정의되어 있을 수 있다. 해결책의 최대 k개 구성요소를 변경하는 것을 포함하는 이웃과의 지역 최적화를 종종 k-opt라고 한다.

일반적으로 모든 후보 솔루션에는 둘 이상의 인접 솔루션이 있다. 즉, 현재 솔루션 근처에 있는 솔루션에 대한 정보만 사용하여 어떤 솔루션으로 이동할 것인지 선택하는 것이 로컬 검색이라는 이름이다. 지역적으로 기준을 극대화하는 방법을 택함으로써 이웃 해법 선택이 이루어질 때 메타휴리스틱은 언덕 등반이라는 이름을 취한다. 인근에 개선된 구성이 없을 경우 로컬 검색은 로컬 최적 지점에 고착된다. 이 국소-최적화 문제는 재시동(초기 조건이 다른 반복된 국소 검색)을 사용하거나, 반복된 국소 검색, 반응형 검색 최적화, 시뮬레이션 방식과 같은 메모리 없는 확률적 수정과 같은 반복에 기반한 더 복잡한 체계를 사용하여 해결할 수 있다.

지역 검색의 종료는 시간 제한에 근거할 수 있다. 또 다른 일반적인 선택은 알고리즘에 의해 발견된 최상의 솔루션이 주어진 수의 단계에서 개선되지 않았을 때 종료하는 것이다. 로컬 검색은 언제든지 알고리즘으로, 종료되기 전에 언제든지 중단되더라도 유효한 솔루션을 반환할 수 있다. 로컬 검색 알고리즘은 일반적으로 근사치 또는 불완전한 알고리즘으로, 알고리즘에 의해 발견된 최선의 솔루션이 최적이 아님에도 검색이 중지될 수 있기 때문이다. 최적의 해결책은 알고리즘이 교차하는 해결책의 근방과 멀리 떨어져 있을 수 있기 때문에 해답의 개선이 불가능하기 때문에 종료하더라도 이러한 일이 발생할 수 있다.

특정한 문제들에 대해, 매우 크고 아마도 기하급수적으로 규모가 큰 이웃들을 고안하는 것이 가능하다. 근린 내에서 가장 좋은 솔루션을 효율적으로 찾을 수 있다면 그러한 알고리즘을 매우 큰 규모의 근린 검색 알고리즘이라고 한다.

참고 항목

로컬 검색은 다음 항목의 하위 필드:

• 메타휴리스틱스
• 확률적 최적화
• 최적화

로컬 검색 내 필드:

• 힐 클라이밍
• 시뮬레이션된 어닐링(로컬 또는 글로벌 검색에 적합)
• 타부 검색
• 후기 수용 힐 클라이밍
• 사후 대응적 검색 최적화(기계 학습과 로컬 검색 경험)

실제 값 검색 공간

실제 값 검색 영역의 로컬 검색을 수행하는 몇 가지 방법이 있다.

• 루우스-자콜라는 균일한 분포와 기하급수적으로 감소하는 검색 범위를 사용하여 현지에서 검색한다.
• 랜덤 최적화는 정규 분포를 사용하여 로컬로 검색.
• 무작위 검색은 현재 위치를 둘러싼 하이퍼스피어를 샘플링하여 로컬로 검색한다.
• 패턴 검색은 기하급수적으로 감소하는 단계 크기를 사용하여 검색 공간의 축을 따라 단계를 수행한다.

참조

참고 문헌 목록

• Battiti, Roberto; Mauro Brunato; Franco Mascia (2008). Reactive Search and Intelligent Optimization. Springer Verlag. ISBN 978-0-387-09623-0. Archived from the original on 2012-03-16.
• Hohs, H.H. and Stutzle, T. (2005) 확률적 국부 검색: 기초와 응용, Morgan Kaufmann.
• Vijay Arya와 Naven Garg와 Rohit Khandekar와 Adam Meyerson과 Kamesh Munagala와 Vinayaka Pandit, (2004): K-Median 및 시설 위치 문제에 대한 현지 검색 휴리스틱스, SIAM 컴퓨팅 저널 33(3)
• Juraj Hromkovich: 어려운 문제에 대한 알고리즘: 조합 최적화, 랜덤화, 근사치 및 휴리스틱스(스프링어) 소개
• 윌 미힐스, 에밀 아츠, 얀 코스트: 로컬 검색의 이론적 측면(스프링어)