[메타 휴리스틱] 집단 기반과 단일해 기반 메타휴리스틱스

 

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

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

 

 

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

 

 

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

 

---

 

매 반복에서 운용하는 후보해(candidate solutions)의 수에 따라 집단 기반 메타휴리스틱스(population-based metaheuristics: P-MHs)와 단일해 기반 메타휴리스틱스(single-solution based metaheuristics: S-MHs)로 분류할 수 있습니다. 매 반복(세대)에서 복수의 후보해로 구성된 집단을 운용하는 집단 기반 메타휴리스틱스에는 진화 알고리즘(EA), ACO, PSO, HS, ABS, AIS 등 많은 알고리즘이 있습니다.

 

 

메타휴리스틱스의 가장 큰 특징 中 하나는 많은 알고리즘들이 집단 기반을 사용하고 있다는 것입니다. 여러 개체(후보해)로 구성된 집단을 운용함으로써 자연스럽게 여러 해공간을 동시에 '탐사'할 수 있는 강점을 갖는 것입니다. 또한 이들 집단 기반 메타휴리스틱스에는 여러 개체가 탐색에서 얻은 정보를 다음 세대의 탐색에 이용하여 더 좋은 해나 전역최적으로 향하도록 하는 메커니즘이 내제되어 있습니다.

 

---

 

 

매 반복에서 단일해를 운용하는 메타휴리스틱은 현재해의 이웃에서 해를 탐색하여 해를 이동시키는 기법으로, 지역탐색에 기반을 둔 알고리즘입니다. 이를 이웃 메타휴리스틱스이라 부르기도 합니다. SA, TS, ILS, VNS, GLS가 이에 속합니다. 이들 기법의 핵심은 지역최적을 벗어나 효과적인 '탐사'를 할 수 있는 전략입니다. 이들 알고리즘에는 지역탐색의 강점인 지역탐색을 '강화'하는 전략과, 지역 최적을 벗어날 수 있는 탐색의 '다양화' 전략('탐사' 전략)이 결합되어 있습니다. 그리고 흔히 지역최적을 탐색하는 데 많은 계산시간이 소요되기 때문에 이를 줄이는 전략이 고려됩니다.

 

 

대부분의 S-MHs에서는 먼저 지역탐색을 하여 지역최적을 찾고, 다음에 해공간의 탐색을 '다양화'하는 과정을 반복합니다. 반면에 P-MHs는 해 집단을 이용하여 탐색을 동시에 행하기 때문에 해공간의 탐색 '다양화'가 좋은 해의 '이용' (탐색의 '강화')보다 우선시 된다고 볼 수 있습니다. S-MHs은 탐색의 '강화'에, P-MHs는 탐색의 '다양화'에 좀 더 무게를 두고 있습니다. 따라서 각 기법이 갖는 강점을 이용하여 다른 메타휴리스틱 또는 수리계획법, 기계학습기법, 데이터마이닝기법 등과 결합한 다양한 형태의 잡종(hybrid) 메타휴리스틱이 제안되고 있습니다.

 

 

 

 

 

 

 

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

 

---

 

[References]

 

[1] Y. Kim. (2017). 메타휴리스틱스, Metaheuristics

 

[2] Nanda, S. J., & Panda, G. (2014). A survey on nature inspired metaheuristic algorithms for partitional clustering. Swarm and Evolutionary Computation, 16, 1–18.