Summary
많은 구성(configuration) 및 최적화(optimization) 문제는 지역 검색으로 표현될 수 있다. 지역 검색은 주어진 상태에서 시작하여 이웃 상태를 탐색하고, 목표 함수를 개선하는 방향으로 상태를 변경하는 방식으로 작동한다.
일반적인 알고리즘 유형 :
- Hill-climbing, continuous optimization :
- 현재 상태의 이웃 중에서 가장 좋은 상태로 이동하는 방식이다. 연속 최적화에서는 기울기 정보를 사용하여 최적의 방향으로 이동한다. - Simulated annealing (and other 확률적 방법stochastic methods) :
- 확률적으로 "나쁜" 이동을 허용하여 지역 최적해에서 벗어나려고 시도한다. 시간이 지남에 따라 나쁜 이동을 허용하는 확률이 감소한다. - Local beam search: multiple interaction searches :
- 여러 검색을 동시에 수행하며, 각 반복에서 가장 좋은 상태들만 유지된다. 이러한 방식은 여러 검색이 서로 정보를 공유하게 된다. - Genetic algorithms: break and recombine states**:
- 상태를 "부모"로 사용하여 새로운 "자식" 상태를 생성하는 방식입니다. 이는 자연 선택의 원리를 사용하여 최적의 솔루션을 찾는다.
많은 기계 학습 알고리즘(ex : 신경망 훈련등의 최적화 문제)은 지역 검색의 형태를 취한다. 이는 매개변수의 최적 값을 찾기 위해 지역 검색 기법을 사용하는 것을 의미한다.