지역 탐색

지역 탐색(local search)은 컴퓨터 과학에서 계산적으로 어려운 최적화 문제를 해결하기 위한 경험적 방법이다. 지역 탐색은 여러 후보 솔루션 중에서 기준을 최대화하는 솔루션을 찾는 것으로 공식화될 수 있는 문제에 사용할 수 있다. 지역 탐색 알고리즘은 최적으로 간주되는 솔루션을 찾거나 시간 제한이 경과할 때까지 지역 변경 사항을 적용하여 후보 솔루션 공간(탐색 공간)에서 솔루션에서 솔루션으로 이동한다.

지역 탐색 알고리즘은 컴퓨터 과학(특히 인공지능), 수학, 운용연구, 공학 및 생물정보학의 문제를 포함하여 수많은 어려운 계산 문제에 널리 적용된다. 지역 탐색 알고리즘의 예로는 WalkSAT, 2-OPT 알고리즘 및 메트로폴리스-헤이스팅스 알고리즘이 있다.^[1]

때로는 지역 탐색 알고리즘을 경사 하강법으로 대체할 수 있지만 경사 하강법은 동일한 계열에 속하지 않는다. 지역 최적화를 위한 반복법이지만 솔루션 공간을 명시적으로 탐색하기보다는 목적 함수의 경사도에 의존한다.

같이 보기

각주

↑ “12LocalSearch.key” (PDF).

[1] “12LocalSearch.key” (PDF).

[1]