[메타 휴리스틱] 메타휴리스틱스에서의 초기해

 

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

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

 

 

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

 

 

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

 

---

 

모든 메타휴리스틱스에서 알고리즘을 시작하기 위해서는 초기해가 필요합니다.

 

S-MHs에서 탐색을 시작하기 위해서는 초기해를 설정해야 합니다. 생성 방법은 임의(random) 생성과 휴리스틱(또는 greedy)생성으로 나눌 수 있습니다. 임의 방법은 빠른 시간에 초기해를 구하지만 수렴하는 데 많은 시간이 소요될 수 있습니다. 탐색 속도를 높이기 위하여, 휴리스틱 방법을 사용할 수 있습니다. 이 방법은 대부분의 경우 지역최적에 빨리 도달합니다. 그러나 좋은 초기해가 항상 더 좋은 지역최적해를 찾지는 않습니다. 

 

두 방법에는 해의 품질과 계산소요시간의 절충(trade-off) 관계가 있습니다. 초기해를 찾는 휴리스틱이 단순하거나 효과적이지 않은 경우에는 임의 방법이 좋습니다. 제약이 강하면 임의 방법으로 가능해를 찾기가 어려울 수 있습니다. 이 경우에는 가능해를 생성할 수 있는 휴리스틱을 사용할 수 있습니다.

 

---

 

P-MHs에서는 해집단을 운용함으로써 해 공간에 있는 여러 지역을 동시에 탐사할 수 있습니다. 이들 알고리즘에서 '집단의 다양성(population diversity)' 유지는 해의 개선에 결정적인 역할을 하게 됩니다. 해집단이 정체되면, 즉 다양성을 잃게 되면 탐사능력이 약화되어 좋은 해를 탐색하지 못하게 됩니다. 따라서 P-MHs에서 초기 해집단을 생성할 때, 좋은 해들의 집단보다는 집단의 다양성에 중점을 두어야 합니다. 집단의 다양성은 해들이 얼마나 서로 다른지에 따라 평가됩니다.

 

P-MHs에서 초기해집단은 집단의 다양성을 위해 흔히 임의로 생성합니다. 이 방법은 연속문제인 경우 각 변수(해의 원소) 값의 범위에서 임의의 값을 생성하여 해를 구성하는 것입니다. 이산문제의 경우에도 해의 각 원소가 가질 수 있는 유한개의 이산 값 中에서 임의로 값을 추출하여 해를 구성하는 방법입니다. 

 

이 과정을 집단의 크기만큼 반복하여 해 집단을 구성합니다. 이와 같은 임의 방법이외에 집단의 다양성을 높이는 여러 방법이 있을 수도 있습니다. 연속문제의 경우, 해 공간을 집단의 크기만큼 균등하게 블록으로 나누어, 각 블록에서 하나의 해를 임의로 생성하는 방법을 사용할 수 있습니다. 집단의 다양성을 최적화하는 것 자체가 하나의 최적화문제가 됩니다. 초기집단의 다양화를 위해 계산시간이 너무 많이 소요되는 것은 피해야 합니다.

 

 

 

 

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

 

---

 

 

[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] Expósito-Izquierdo, C., López-Plata, I., & Moreno Vega, J. M. (2015). Problem MetaHeuristic Solver: An educational tool aimed at studying heuristic optimization methods. Computer Applications in Engineering Education, 23(6), 897–909.