지역 최적

개념

지역 최적은 주변 상태들보다 좋아 보이지만 전체 상태 공간에서 가장 좋은 해는 아닌 상태이다. 언덕등반 탐색이 자주 빠지는 문제이다.

최대화 문제에서 $s^{\ast }$가 지역 최적이면 주변 상태 집합 $N(s^{\ast })$에 대해 다음을 만족한다.

$$f(s^{\ast })\ge f(s),\forall s\in N(s^{\ast })$$

왜 생기는가

언덕등반 탐색은 현재보다 더 좋은 상태로만 이동하려고 한다. 그런데 전체 최적해에 가려면 일시적으로 평가값이 나빠지는 방향으로 이동해야 할 수도 있다. 이때 알고리즘은 더 이상 나아갈 수 없다고 판단하고 멈춘다.

해결 방향

다른 후보를 저장하는 최상 우선 탐색, 비용까지 함께 고려하는 A star 알고리즘, 랜덤성을 섞는 방법 등이 지역 최적 문제를 완화할 수 있다.