[메타 휴리스틱] 메타휴리스틱의 특징

 

 

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

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

 

 

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

 

---

 

 

 

 

※ 메타휴리스틱스(metaheuristics)는 3가지 특징을 가지고 있습니다.

 

첫째, 메타휴리스틱스는 좋은 해를 탐색함과 동시에 지역최적에서 벗어나 해공간을 강건하게 탐색할 수 있는 프로세스와 전략을 갖는 해법입니다. 메타휴리스틱스는 탐색 과정에서 발견한 좋은 해 주위의 탐색을 강화하는 전략과 함게, 지역최적에서 벗어나 탐색하지 않은 해 공간으로 탐색영역을 다양화하는 전략을 가집니다. 탐색을 강화하면 탐색의 다양화가 약화됩니다. 그 역도 성립합니다. 따라서 메타휴리스틱스 설계 시에 상충되는 이들 두 전략의 조화로운 상호작용에 관심을 가져야 합니다.

 

둘째, 여러 메타휴리스틱스는 '자연 현상'을 모방하고 있으며, 과거 탐색에서 얻은 경험이나 정보를 '기억'하거나 '전달'하여 다음 탐색에 이용되고 있습니다.

 

셋째, 메타휴리스틱스에서는 해 탐색 과정을 '반복'하는 데, 매 반복에서 기존의 지역탐색처럼 '단일해를 기반(single-solution based)'으로 하는 경우도 있으나, 여러 메타휴리스틱스는 '해 집단을 기반(population-based)'으로 하고 있습니다. 해 집단을 운용함으로써 해 공간의 여러 지역을 동시에 탐색할 수 있습니다. 단일해를 운용하는 메타휴리스틱스는 이웃(neighborhood) 탐색기법을 주로 사용하고 있습니다.

 

 

---

 

 

위의 특징들을 요약하면, 대부분의 메타휴리스틱스는 자연 현상에서 영감을 얻어 개발되었고, 예외도 있지만 대부분 과거 탐색(경험)에서 얻은 정보를 다음 탐색에 이용합니다. 또한 효율적이고 효과적인 탐색을 위하여, 지역최적을 벗어나 지금까지 탐색하지 않았거나 탐색이 적게 이루어진 영역을 탐색할 수 있는 전략과 더불어, 탐색에서 발견한 좋은 해 주위를 집중적으로 탐색할 수 있는 기법을 가지고 있어야 합니다.

 

어떤 방법이 범용 알고리즘의 틀(메타휴리스틱)로 사용되기 위해서는 다음 조건들을 만족해야 합니다. 먼저, 단순성, 명확성, 범용성입니다. 원리는 가능한 단순 명료해야 하며, 절차는 정확해야 하고, 적용분야는 넓고 다양해야 합니다. 다음은 효율성과 효과성으로, 다양한 유형의 문제에 대해 적절한 계산시간 내에 (효율성) 최적해나 근사 최적해를 제공(효과성)할 수 있어야 합니다. 또한 해의 품질을 높이기 위하여 사용자가 문제에 관한 지식을 알고리즘에 반영(상호작용성)할 수 있어야 합니다.

 

이들 메타휴리스틱스가 갖추어야 할 조건은 바로 메타휴리스틱스의 장점으로 볼 수 있습니다. 이외에도 메타휴리스틱스는 목적함수의 변경과 제약식의 추가가 용이하여 적용의 유연성이 높다는 강한 장점을 가지고 있습니다. 이는 위에서 언급한 범용성에 해당합니다. 고전적 최적화기법에서는 목적함수와 제약식에 따라 문제 해결을 위한 기법이 달라집니다. 이에 반해 메타휴리스딕은 목적함수와 제약식에 대한 특정 요건을 요구하지 않습니다. 또한 메타휴리스틱 알고리즘 중에는 연속최적화보다는 조합최적화에 더 적합하거나 또는 그 반대인 경우도 있으나, 여러 메타휴리스틱스(예로 진화알고리즘)는 두 유형의 문제에 모두 적용 가능합니다. 그리고 메타휴리스틱은 다봉(multimodal)최적화의 다목적(multi objective) 최적화에서 각각 여러 지역최적해와 다양한 비지배된(non dominated)해를 구하는 데 효과적입니다.

 

 

 

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

 

---

 

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