[메타 휴리스틱] 메타휴리스틱 알고리즘 종료조건

 

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

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

 

 

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

 

 

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

 

---

 

메타휴리스틱스 알고리즘에서 알고리즘이 무한 반복을 하지 않고 합리적인 반복 횟수를 수행한 후 끝낼 수 있도록 종료 조건을 명시해야 합니다.

 

 

 

※ 메타휴리스틱 알고리즘 종료조건은 아래와 같습니다.

 

1) 최대 반복 수(S-MHs에서) 또는 최대 세대 수(P-MHs에서)

 

2) 목적함수 평가의 최대 횟수: S-MHs에서는 이웃해 평가의 최대 횟수, P-MHs에서는 개체 평가의 최대 횟수

 

3) 최대 계산소요 시간

 

4) 해의 개선이 없는 반복 횟수(S-MHs에서) 또는 세대 수(P-MHs에서): 주어진 반복(또는 세대)횟수 동안 해의 개선이 없으면 종료.

 

5) 사전에 최적해를 알거나 그 한계를 아는 경우, 수용 가능한 해에 도달: 주어진 만족할 만한 해에 도달하면 종료

 

특정 메타휴리스딕에서는 그 알고리즘이 가지고 있는 특성에 따라 특정 기준이 사용되기도 합니다. 예를 들자면 SA에서는 파라미터인 온도 T  를 어느 수준까지 낮추는 기준이 주로 사용됩니다.

 

 

 

 

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

 

---

 

 

[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] Subramanian, Kannan & Slochanal, S. & Padhy, Narayana. (2005). Application and Comparison of Metaheuristic Techniques to Generation Expansion Planning Problem. Power Systems, IEEE Transactions on. 20. 466 - 475.