[메타 휴리스틱] 확률적 또는 확정적 메타휴리스틱스

 

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

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

 

 

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

 

 

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

 

---

 

초기해가 같으명 항상 같은 결과가 산출되는 알고리즘은 확정적이고, 초기해가 같아도 매번 다른 결과가 나올 수 있으면 확률적입니다. 대부분의 메타휴리스틱스는 확률적(stochastic)입니다. 단지 타부서치(Tabu Search, TS)는 파라미터가 변하지 않는다면 확정적 알고리즘이 됩니다.

 

 

확률적 메타휴리스틱의 매 반복에서 새로운 후보해(들)를 생성할 때, 즉 해가 이동할 때 좋은 해로의 '지역'적 이동과 새로운 해 영역으로의 '전역'적 이동이 확률적으로 고려됩니다. 메타휴리스틱은 '우연'의 성질을 갖는 확률적 탐색으로 다양한 해 공간의 '탐사' 능력을 놓이는데, 이 '탐사'는 발견한 좋은 해의 '이용'과 적절한 균형을 이루어야 합니다. 해 공간의 확률적 탐색은 메타휴리스틱의 주요 특징 中 하나입니다.

 

 

 

 

 

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

 

---

 

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

 

[3] Juan, Angel & Faulin, Javier & Grasman, Scott & Rabe, Markus & Figueira, Gonçalo. (2015). A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems. Operations Research Perspectives.