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

저번 글에서 Meta-heuristic Algorithm이 무엇인지에 관하여 알아보았으니 본 게시글부터 어떤 Algorithm들이 있는지에 대해 살펴보고자 합니다.

특히 이번 글에서는 많이 알려진 Meta-heuristic Algorithm 중 하나인 Simulated Annealing(SA)에 대해 알아보겠습니다.

Local Search?

 Simulated Annealing은 Local search 방법 중 하나입니다. Local search 방법은 다음과 같은 특징을 가지고 있습니다.

• Single solution으로부터 시작한다.

• 현재 solution 주변 neighbour를 조사하여, 만일 현재보다 낫다면 그 neighbour로 state를 옮긴다.

Simulated Annealing?

Simulated Annealing이 무엇인지, 대체 어떻게 나온 Algorithm인지 이해하기 위해 Annealing이 뭔지에 대한 느낌을 잡아봅시다.

- Simulated Annealing...?

SA에 대해 구글에 검색해보면 이에 대한 번역으로 '담금질 기법'이란 용어가 함께 나오는 것을 볼 수 있습니다. 잉? 갑자기 웬 담금질? 바로 이 Simulated Annealing이 금속의 냉각에서 아이디어를 얻어 만들어진 Algorithm이기 때문입니다. '담금질'이란, 고온의 금속을 냉각시켜 굳히는 과정을 말하는데요. 높은 온도의 금속이 식으며 단단해지는 이 과정에서 원자들은 자신의 Energy가 더 작아지는 State를 찾아가게 됩니다.

- 온도가 내려감에 따라 더 낮은 Energy state를 찾아 움직인다.

위의 그림은 이 과정을 꽤 잘 나타내주고 있습니다. 위의 세부그림(공이 그려진 작은 그림들)의 세로축은 Energy (Objective function), 가로축은 variable이고 작은 공들은 particle들이라고 생각해봅시다. 시간이 지나며 온도가 낮아짐에 따라 particle들은 낮은 Energy를 갖는 state를 찾아 움직이고, 시간이 충분히 지나면 Local Minima에 안착하게 됩니다.

즉, SA는 고온의 금속이 식으며 Energy를 최소화하는 것과 같이, 주어진 Objective Function을 최소화하는 state를 구할 수 있지 않을까? 하는 아이디어에서 나온 Algorithm입니다. 이와 비슷한 방법으로 Metropolis-Hastings Algorithm이 있는데 이는 추후 Bayesian Inference 항목에서 기회가 된다면 소개해드리겠습니다.

Pseudo Code

자, Simulated Annealing이 '담금질'의 원리를 이용하여 더 낮은 objective function 값을 얻겠다는 것은 알겠는데, 어떻게 이를 적용하겠다는 것일까요? 아래의 Pseudo Code와 함께 알아보겠습니다.

- (좌) Simulated Annealing (우) Acceptance ratio

※ 덤 !

1) 담금질을 한다고 금속의 원자들이 최소의 Energy를 갖는 State(Global Minimum)로 가는 것은 아닙니다. 온도를 매우 서서히 조심스럽게 낮추며 최대한 낮은 Local Minimum에 도달하도록 해야 합니다. 드라마나 소설에서 보면 좋은 무기를 만들기 위해 대장장이들이 담금질을 여러번 하는 것을 볼 수 있을텐데, Local Minimum에 빠진 금속 원자들을 움직여 최대한 Global Minimum에 이르게 하기 위함입니다.

2) 최근 논문에 따르면, 대부분 우리가 생각하는 Local Minimum은 사실 Saddle Point라고 합니다. high dimension의 상황에서 사실 Local Minimum은 매우매우 드문 상황이기 때문. Saddle Point인데 빠져나오는 속도가 너무 느려서 Local Point라 착각하는 것이라고.... (뭐 사실 나오는 속도가 너무 느리면 사실 그거나 그거나 싶긴 하다만;)

논문 : Y.N.Dauphin et al, Identifying and attacking the saddle point problem in high-dimensional non-convex optimization, NIPS 2014

주소 : http://papers.nips.cc/paper/5486-identifying-and-attacking-the-saddle-point-problem-in-high-dimensional-non-convex-optimization

논문에 대한 설명 : https://darkpgmr.tistory.com/148 (개인적으로 자주 참고하는 blog입니다.)

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

본 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에 대해 살펴보겠습니다. 

감사합니다.