[메타 휴리스틱] 지역탐색법(local search)

 

 

이번 글의 내용은 전남대학교 산업공학과 김여근 교수님의 메타휴리스틱 교재 정리 및 참조하였음을 먼저 밝힙니다.

(다른 참조한 논문과 자료들은 아래에 기재되어 있습니다.) 

 

 

혹시 제가 잘못 알고 있는 점이나 보완할 점 있다면 댓글로 알려주시면 감사하겠습니다. 

 

---

 

 

 

※ 지역탐색(local search: LS)법은 가장 오래되고 단순한 최적화기법입니다.

 

 

지역탐색은 가능해 영역에서 하나의 임의 초기해로 시작했습니다. 이 초기해를 현재해(current solution)로 둡니다. 현재해의 이웃(neighborhood)에서 목적함수를 개선하는 해를 찾습니다. 목적함수를 개선하는 이웃해를 찾으면 이를 현재해로 둡니다. 이러한 반복은 이웃에서 더 좋은 해를 찾을 수 없을 때 끝냅니다.

 

여러 지역최적이 있는 문제에 지역탐색법을 적용하면, 하나의 지역최적(local optimum)에 도달하면 끝납니다. 도달하는 지역최적은 초기해에 의해 결정됩니다. 전역최적(global optimum)에 도달할 수 있는 초기해의 영역은 한정되어 있습니다.

 

지역탐색법의 단점은 지역최적에 도달하면 이 지역최적을 벗어나지 못하고 절차를 끝내는 것입니다. 이를 극복하는 방법으로, 초기해를 '임의로' 달리하면서 지역탐색을 여러 번 반복 수행하는 방법을 고려해 볼 수 있습니다. 초기해를 달리하면 다른 지역최적에 도달할 수 있습니다.

 

이 방법은 지역탐색보다 더 좋은 해를 찾을 수 있고, 목적함수 형태가 비교적 단순하면 전역최적도 찾을 수 있습니다. 그러나 이러한 방법은 복잡도가 높고 지역최적이 많은 최적화 문제에서는 비효율적이고 우연에 기대는 것이 됩니다. 중복 탐색을 가능한 회피하고 전역최적을 찾을 가능성이 더 높은 체계적인 방법이 필요합니다.

 

---

 

 

 

지역탐색법은 현재해의 이웃을 집중 탐색하여 지역최적을 찾을 수 있다는 강점이 있으나, 지역최적을 벗어나지 못하여 해공간의 '탐사(exploration)'능력이 매우 약하다는 치명적인 약점을 갖고 있습니다. 넓은 해공간에서 좋은 해 또는 전역최적을 찾기 위해서는 탐색에서 찾은 좋은 해를 '이용(exploitation)'하여 지역 탐색을 '강화(intensification)'하는 한편, 새로운 해 영역 또는 지역 탐색이 상대적으로 적게 이루어진 영역을 '탐사'하여 탐색 영역을 '다양화(diversification)'해야 합니다.

 

탐색의 '강화'와 탐색 공간의 '다양화'는 상충됩니다. 지역탐색은 탐색의 '강화'만 강조하고, 임의 탐색(random search)은 탐색의 '다양화'만을 강조합니다. 메타휴리스틱스에서 탐색의 '강화'와 '다양화'의 균현은 매우 중요합니다. 이는 해 공간의 '탐사'와 좋은 해의 '이용'의 조화를 의미하기도 합니다. 

 

복잡도가 높은 대형의 최적화문제를 해결하는 데 합리적 시간 내에 사용자가 수락할 수 있는 해(최적해 또는 근사 최적해)를 구하는 것은 매우 의미가 있습니다. 이러한 문제는 공학, 자연과학, 사회과학 등 여러 분야에서 쉽게 찾아 볼 수 있습니다.

 

 

 

 

 

긴 글 읽어주셔서 감사합니다.

 

---

 

이 포스트는 "메타 휴리스틱" 책의 내용을 참조 및 공부한 것을 바탕으로 제가 이해한 정보를 추가하여 쓰여졌습니다.