[0] Meta-heuristic Algorithm이란?

안녕하세요, 코딩하는 물리학자입니다.

본 chapter에서는 다양한 Meta-heuristic Algorithm을 소개하고 어떻게 이용하는지 등을 정리해 보고자 합니다. Meta-heuristic Algorithm은 현재 Software Engineering(SE) 분야에서 꽤 많이 응용되고 있으며, 제 생각에는 SE외의 다양한 분야에도 적용이 가능하지 않을까 생각됩니다.(물리 분야에도 이용해보고 싶은데, 아직 어떻게 이용해야 할지는 잘 모르겠네요ㅜㅜ)

그럼 Meta-heuristic Algorithm을 알아보기 전, Exact Algorithm과 Heuristic Algorithm에 대해 간단히 알아보도록 합시다.

Exact Algorithm vs Heuristic Algorithm

Exact Algorithm이란, 문제의 optimal solution을 항상 구해주는 algorithm을 뜻합니다. 예를 들어, 주어진 숫자들을 sorting하는 문제를 해결하는 Exact Algorithm으로 Selection, Insertion, Quick Sort 등이 있지요. 물론 Computation time은 모두 다르지만, 어떠한 숫자들 집합에 대해서도 이들을 sorting해주므로 이들 모두 Exact Algorithm이라 할 수 있습니다.

반면 Heuristic Algorithm은 optimal solution이 아닌, 이에 충분히 가까운 good solution을 얻는 algorithm입니다. "잉? 그럼 optimal solution을 얻는것도 아닌 것을 왜 쓰냐? 그냥 exact algorithm을 쓰면 되는거 아니냐?" 하실 수 있습니다. 이해를 돕기 위해, 다음 문제를 생각해보지요.

만약 여러분이 일정 영역, 가령 여러분 집 근처에 있는 '포켓스탑'을 최소의 노력으로 돌아다니고 싶다 가정해보도록 합시다.

 

-'포켓몬 고'의 포켓스탑. 근처로 가서 클릭하면 몬스터볼이나 상처약 등 여러 아이템을 제공해준다.

위 문제를 Exact Algorithm으로 푼다면, n개의 '포켓스탑'으로 만들 수 있는 모든 조합에서 걸리는 거리를 구하고 이들에서 가장 작은 경우의 수를 고르면 되겠지요.

하지만, 눈치 빠르신 분들은 아시겠지만, 이 Algorithm의 Computation Time은 모든 조합을 생각해야하므로 O(n!) 이 됩니다. 즉, n이 만일 50개만 되어도 3x10^64이나 되는 엄청난 경우의 수가 된다는 겁니다. 이쯤되면 이거 계산할 시간에 이미 '포켓스탑' 몇 십 번은 돌았겠지요.

Heuristic Algorithm은 이러한 문제에서 짧은 시간에 optimal solution에 '가까운' good solution을 제공해줍니다. 예를 들어, random하게 순서를 배열한 두 경로를 비교하여 그 중 짧은 경로를 남기는 식으로 algorithm을 작성하였다면, 1000번의 iteration 후에는 이중 가장 짧은 경로를 남겼을 겁니다. 이 경로는 최적의 경로는 아닐 수 있지만, 짧은 시간에 '그나마' 좋은 경로가 될 수 있습니다.

위 문제는 TSP(Travelling Salesman Problem)을 조금 바꾼 예제인데, TSP는 Heuristic Algorithm을 적용하는 대표적인 문제입니다. 이후 게시글에서 몇가지 Meta-heuristic Algorithm을 소개하며 TSP에 어떻게 적용이 되는지도 밝혀보겠습니다.

그럼 Meta-heuristic Algorithm은?

이전에 알아본 Exact Algorithm과 Heuristic Algorithm은 모두 problem-dependent, 특정 문제의 solution을 구하기 위한 algorithm이라 볼 수 있습니다. 즉, 숫자들을 sorting하거나 '포켓스탑'의 순서를 정하는 문제 등의 특정 문제를 풀기 위한 Algorithm이라는 것이지요.

- Meta-heuristic이 heuristic이 되는 과정.

Meta-heuristic Algorithm은 Heuristic Algorithm과 같이 good solution을 구하는 Algorithm이지만 problem-independent하다는 차이점이 있습니다. 즉, 특정 문제에 종속되지 않고 다양한 문제에 적용이 가능한 Frame work가 되는 Algorithm이라는 것이지요. 대표적으로 Simulated Annealing, Genetic Algorithm, Particle Swarm Optimization, Ant Colony Optimization 등이 있습니다.

이렇게만 말하면 사실 뭐가 다른지 잘 감이 안오실 겁니다.(저도 그랬으니까요ㄷㄷ) 때문에 이 또한 예제를 살펴봅시다.

Divide and Conquer Algorithm에 대해서는 많이들 들어보셨을 겁니다. 간단히 설명하자면, 해결하고자 하는 문제를 작은 문제들로 나누어 해결하는 방법입니다. 이는 다양한 문제에 적용이 가능한데, 대표적으로 sorting에 적용한 Quick sort, Merge sort 등이 바로 이를 이용한 Algorithm이지요. 조금 더 쉬운 예제로는 자연과학 분야와 공학 분야가 있겠습니다. 자연과학 분야에서 기본 원리를 발견하고, 공학 분야에서 이를 응용하여 여러 문제들을 해결하는 것처럼 말이지요.

Meta-heuristic Algorithm도 이와 마찬가지입니다. 대표적으로 많이 사용되는 Genetic Algorithm은 sorting이나 TSP, NRP 등 많은 문제에 적용이 가능하므로 Meta-heuristic Algorithm이지만 TSP에 적용하는 과정에서 문제에 맞게 몇 가지 규칙을 정하게 되면 Heuristic algorithm이 되는 것입니다.

아래는 Search Based Software Engineering(SBSE) 분야의 여러 논문들이 정리되어 있는 link입니다. 다양한 Meta-heuristic Algorithm이 적용된 사례들을 볼 수 있으니 관심이 있으신 분은 찾아보시면 좋을 듯 합니다.

http://crestweb.cs.ucl.ac.uk/resources/sbse_repository/repository.htm

추가로, Meta는 그리스어로 '사이에', '넘어서' 라는 뜻을 지니는데 Meta-data는 'Data를 위한 Data'가 되고 Metaphor는 phor가 '나르다' 혹은 '전달하다'라는 뜻으로, '전달을 위한 전달'. 즉, '은유'가 되겠지요. 때문에 Meta-heuristic Algorithm은 Heuristic Algorithm을 위한 Algorithm이라는 뜻이 아닐까 생각합니다.

다음 글부터는 그럼 여러 Meta-heuristic Algorithm에 대해 살펴보겠습니다. 

감사합니다.