[메타 휴리스틱] 과거의 탐색 '기억'을 이용하는 메타휴리스틱스

 

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

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

 

 

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

 

 

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

 

---

 

대부분의 메타휴리스틱에서는 과거의 탐색 경험을 저장 또는 기억하여 미래의 탐색에 이용합니다. 이는 해공간의 효율적 탐색을 위한 것으로 메타휴리스틱의 중요한 성질 중 하나입니다. 타부서치는 기억을 명시적으로 사용(단기기억, 중기기억, 장기 기억)하여 탐색합니다. ACO에서는 과거 탐색 정보를 축척하여 이용하고, PSO에서는 자신과 군집의 가장 좋은 경험을 기억하여 이용합니다.

 

---

 

 

또한 진화알고리즘에서는 염색체에 과거 탐색정보(조상의 유전자)가 자손에게 상속되면서 그 기억이 부분적으로 이용된다고 볼 수 있습니다. 반복지역탐색(ILS)에도 기억을 이용할 수 있으며, 유도지역탐색(GLS)에도 과거의 지역탐색 결과를 이용하고 있습니다. 기억을 이용하지 않는 알고리즘에는 SA와 지역탐색(local search)이 있습니다. 이들 두 탐색에서 다음 탐색은 단지 현 탐색에 의해서만 영향을 받습니다.

 

메타휴리스틱스에서 과거 탐색 정보(기억)가 미래 탐색에 어떻게 영향을 미치는 지에 대한 이해가 중요합니다. 즉 이들 정보가 탐색의 '다양화'와 '강화'(또는 해 공간의 '탐사'와 좋은 해의 '이용')에 작용하는 메커니즘에 대한 이해가 중요합니다. 

 

 

 

 

 

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

 

---

 

[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.