[메타 휴리스틱] 최적화 문제 개요

 

 

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

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

 

 

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

 

 

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

 

---

 

 

최적화 문제는 크게 연속(continuous)변수와 이산(discrete) 변수를 갖는 문제로 분류할 수 있습니다. 이산변수를 갖는 문제를 조합(combinatorial)문제라고 부릅니다.

 

 

 

연속문제에서는 일반적으로 실수의 집합을 찾고, 조합 문제에서는 유한의 집합, 예로 정수, 순열, 그래프 등을 찾습니다. 또한 연속변수와 이산변수를 동시에 갖는 혼합문제도 있습니다. 연속문제를 해결하는 최적화 기법은 크게 선형과 비선형으로 나눌 수 있고, 조합 문제의 최적화 기법은 전역 최적(global optimum)으로 구할 수 있는 정확한 해법과 최적에 가까운 좋은 해를 구하는 근사(approximate)해법으로 분류할 수 있습니다. 최적화 기법은 위의 그림과 같이 분류할 수 있습니다. 

 

선형문제의 해결을 위한 선형계획법이나 이산문제를 위한 분지한계법(branch-and-bound method)과 동적계획법과 같은 정확한 해법은 여러 적용 문제에서 효율적입니다. 그러나 이들 해법은 변수가 많고 높은 비선형성을 갖는 연속문제에서는 최적해를 찾기는 매우 어렵습니다. 또한 문제의 크기에 따라 계산량이 지수적으로 증가하는 대형 조합문제를 정확한 해법으로 해결하는 것은 현실적으로 불가능합니다.

 

최적화는 과학, 공학, 경제학, 경영학 분야에서 일어나는 현실 문제에 많이 적용됩니다. 이들 적용 문제는 주로 규모가 큰 조합이거나 높은 비선형의 최적화 문제가 됩니다. 이러한 최적화문제는 앞에서 언급했듯이 합리적인 시간 내에 전역최적을 찾는 것은 거의 불가능합니다. 이 경우 대안으로 허용하는 시간 내에 전역최적은 아니지만 수락할 수 있는 정도의 좋은 해를 구하는 알고리즘을 사용하는 것입니다. 그사해법에 속하는 휴리스틱(heuristic)은 이를 위한 하나의 대안입니다. 휴리스틱은 합리적인 계산시간 내에 최적해를 보장하지 못하지만 좋은 해를 찾을 가능성이 높은 방법입니다. 적용하는 문제에 따라 그 방법이 달라집니다. 일반적으로 휴리스틱이란 특정한 형태의 문제 해결에 적합하도록 설계된 '특정 휴리스틱'을 말합니다.

 

 

 

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

 

---

 

[References]

 

 

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