이 글은 굉장히 공대로운 글이지만 수학 같은거 모르셔도 됩니다 ㅎㅎ 매우 단순화해서 설명하기 때문에, 실제 사용되는 구체적인 알고리즘들과는 조금 차이가 있을 수 있습니다. 먼저 "최적화"의 개념부터 한번 잡고 가볼까요?

- 최적화에 대해서

어떤 문제가 있을 때, 최적의 솔루션을 찾아내는 문제를 "최적화(Optimization)"이라고 부릅니다. 최적화 문제는 어떤 문제를 수식화 한 다음, 가장 좋은 값을 찾아내는 과정입니다.

예를들어서, 좁은 병 속에 믹스너트가 있다고 해 보지요. 원숭이가 이 병 안에서 견과류를 꺼내는 것을 최적화 한다고 하면, 원숭이는 이런 과정을 거치게 되겠지요.

1) 먼저 원숭이의 목적을 정해야 합니다. 최대한 많은 칼로리가 필요하다라든지, 선호도가 가장 높다든지, 이것을 "목적함수" 라고 합니다.

2) 손 안에 최대한 넣을 수 있는 견과류의 용량이 필요하겠죠. 너무 많이 들면 병을 못 빠져나오잖아요? 이것을 "제약식" 이라고 합니다.

3) 원숭이는 어떤 견과류를 얼마나 집을지 결정해야겠죠. 이걸 "결정변수"라고 부릅니다.

4) 만약 믹스너트가 아니고 땅콩만 들어있다면 땅콩의 갯수만 결정하면 되겠죠, 이런 경우를 "단변수 최적화"라고 합니다. 믹스너트면 땅콩 몇개 호두 몇개 아몬드 몇개 이렇게 결정해야겠죠. 이것을 "다변수 최적화"라고 합니다. 대부분의 최적화 문제는 다변수 최적화인 경우가 많습니다.

5) 만약 견과류를 분지를 수가 없이 정수개수로만 가져와야 한다면 "정수계획법"이라고 부릅니다. 척 보기엔 별것 아닌것 같지만 문제의 난이도를 하늘로 밀어올리는 요인이 됩니다.

이렇게 최적값을 찾아내는 문제는 자주 "등산"에 비유되고는 합니다. 다음과 같이 예시를 들어볼게요.



강원도 원주시 인근의 있는 치악산의 지형도입니다. 여기 최고봉은 어디죠? 우리는 치악산의 정상이 비로봉인 것을 알고 있지만, 이것을 모르는 채로, 손에 GPS 계측기 하나 쥐여준 채로 치악산 모처에서 비로봉을 찾는다고 가정을 해 보지요. 우리는 어느 위도, 어느 경도로 가야할까요?

가장 단순한 방법은, 제일 높은 경사를 따라서 등반하면 됩니다. 아무래도 그렇게 계속 올라가다 보면 제일 높은 데가 나오지 않겠어요? 이것을 "경사상승법"(가장 낮은 값을 구하는 경우 "경사하강법")이라고 합니다. 근처에 제일 높은 경사로 쪼끔 올라가서 보고, 또 제일 높은 경사로 쪼끔 올라가보고 하는 방식이죠.

자, 그래서 우리는 제일 높아 보이는 봉우리에 도착했습니다. 경치도 좋은게 여기가 맞는 것 같아요. 그래서 셀카 박고 자랑했다가 한 소리 먹습니다. 거기가 비로봉이 아니라네요? 근처에 있는 천지봉인데, 심지어 2등도 아니라네요. 그래서 온갖 쿠사리를 다 먹었습니다.

바로 이 문제가 최적화 문제에서 자주 나타나는 "지역 최적값" 문제입니다. 분명 주변에서는 가장 좋은 값인데, 이것보다 좋은 값이 있는 것이죠. 경사하강법에서 이 문제가 굉장히 두드러집니다.

그냥 비행기 타고 항공측량 삭 긁어보면 되는거 아냐? 싶을 수 있지만, 변수가 많으면 많을수록 탐색해야 하는 공간 역시 기하급수적으로 늘어나죠. 예를들어 치악산 지하에서 가장 지하수가 많이 나오는 지점은 어디의 몇 미터 아래? 하면 또 땅 아래를 봐야하는데, 이러면 답이 눈에 보이지도 않고, 깊이라는 결정변수가 하나 늘어나니 난이도가 급상승하겠죠.

이래서 보통 최적화 문제는 딱 눈에 보이는 해답을 찾을 수 있는 경우가 드뭅니다. 수학적으로 그게 가능하다고 증명되어있는 소수의 문제를 제외하고는, 보통은 진짜 해답을 구하기가 매우 어려워요. 그래서 나오는 것이 바로 "휴리스틱", 또 "메타 휴리스틱"입니다.

- "휴리스틱"과 "메타 휴리스틱"에 대해서

휴리스틱이라고 하면 좀 있어보이잖아요? 휴리스틱은 경험적으로 답을 찾을 수 있다고 생각되는 간편한 추론법들을 의미합니다. 우리말에서 이와 정확하게 매칭되는 말은 "통빡"입니다. 이래이래 해 보면서 적당히 하면 답이 나오더라고 이게 휴리스틱이구요, 보통 휴리스틱 방법론이라고 하면 이걸 어떻게든 체계화시켜서 써먹을 수 있게 만들어 놓은 거지요.

우리는 일상생활에서 수많은 휴리스틱을 사용하고 있습니다. 예를들어서 스테이크 굽기 판단법들, 고구마가 잘 익었는지 젓가락을 찔러보는 것, 수박 꼭지 상태 보는 것, 오늘은 신경통이 있는 걸 보니 비가 오겠다 같은 것들 있잖아요? 이것들도 일종의 휴리스틱입니다. 확실하게 까보지 않고도 적당히 알 수 있게 해주는 그런 방법들이죠. 어떤 판단법이 최선의 답을 주진 않지만, 써먹을 수 있는 적당한 답을 제공하는 것으로 알려지게 되면 문제없이 사용이 되고 도움도 많이 됩니다. 최선의 답을 찾는데는 너무 지나치게 많은 노력이 들게 되니까요.

요즘 컴퓨터도 좋은데 좀 계산 많이 해도 되지 않나? 싶을 수 있지만, 이 "지나치게 많은 노력"은 우리가 상상하는 수준이 아닙니다. "현재 가장 좋은 컴퓨터로 우주의 탄생부터 지금까지 계산해도 아직 부족한" 이정도지요. 이걸 가지고 기껏 한게 "오늘 서울시 출근 소요 시간 1분 감소" 이런거면 굉장히 억울한 상황이겠죠. 근데 안타깝게도 꽤 많은 문제들의 복잡도가 이쯤 합니다. 그래서 휴리스틱 방법론은 굉장히 광범위하게 사용됩니다.

메타 휴리스틱은 이런 방법론들을 수리적으로 체계화하여 여러 문제에서 함께 사용할 수 있게 만들어 놓은 범용적 알고리즘을 이야기합니다. "범용적 통빡"이라고 번역을 할 수 있겠군요. 이러면 없어보이니 이렇게 번역하지는 않고 그냥 메타 휴리스틱이라고 많이 씁니다. 이 메타 휴리스틱을 가져다가 각 문제에 맞게 개조해서 사용을 하게 되는 것이죠.

메타 휴리스틱에도 굉장히 많은 종류가 있습니다. 오늘은 이 중에 가장 자주 언급되는 5개의 알고리즘에 대해 간단하게 설명해 보도록 하겠습니다.

1. 유전 알고리즘(Genetic Algorithm)

유전자 알고리즘이라고도 많이 불립니다. 줄여서 GA라고도 많이 하구요. 사실상 "가장 널리 쓰이는" 메타 휴리스틱입니다. 그만큼 단순하고 그에 비해 성능도 매우 뛰어나죠. 수학적인 내용이 가장 적은 알고리즘이기도 합니다.

유전 알고리즘은 말 그대로 생물의 유전자들의 교배와 변이를 이용하는 알고리즘입니다. 결정변수들의 집합을 "개체"라고 칭하고, 결정변수 하나는 "염색체"라고 이야기합니다. 예를들어서 우리가 롤 국대 5명을 최적화한다고 예시를 들어 보죠. 대충 4위까지의 팀을 가지고 한번 해본다고 가정을 하겠습니다.

1) 먼저 결정변수들을 유전자형으로 표현합니다. 별건 아니고, 이 그림처럼 하면 됩니다. 이 경우는 팀 로스터가 "개체"가 되고 선수들이 "염색체"가 되겠죠.



2) 가장 먼저 "교배" 과정을 실시합니다. 그림처럼, 개체들을 골라서 무작위 유전자를 서로 교환하는 과정입니다.



3) 다음으로 "변이" 과정을 실시합니다. 개체 내의 무작위 유전자를 변형시키는 과정입니다.



4) 교배와 변이를 거치지 않은 초기의 개체들을 부모 집단이라고 합니다. 그리고 교배/변이 과정을 실시한 후의 집단을 후손 집단이라고 하죠. 이 집단들 중에 적절한 기준을 따라 목적함수를 비교해서, 새로운 부모 집단을 만듭니다. 이 적절한 기준은 굉장히 다양합니다. 부모 집단을 포함하거나 배제할 수 있고, 두개씩 뽑아서 붙여서 이긴 애들 올려보낼 수도 있구요, 제일 잘하는 팀부터 일렬로 4개 끊어서 올릴 수도 있지요.



5) 이 과정을 적절한 횟수 만큼 반복합니다.

이러면 언젠간 무패의 최강팀이 나올 수 있겠죠? 이게 바로 유전 알고리즘입니다. 우리가 "모든 경우의 수"를 다 체크하려면 선수가 20명이니 순열계산하면 1,860,480가지의 경우의 수가 뜨거든요. 이건 좀...그렇잖아요? 그러니 이 방법을 통해 연산량을 많이 줄일 수 있는 것이죠.

이 유전 알고리즘과 유사한 분류로 진화적 특성을 이용하는 메타 휴리스틱들을 통칭해서 "진화 알고리즘"이라고 부릅니다.

2. 모의 담금질 기법(Simulated Annealing)

일반적으로 담금질 기법, SA, 시뮬레이티드 어닐링 등등으로 불리는 기법입니다. 담금질 기법은 매우 단순한 아이디어에서 출발하는데, 전역 최적화에 빠지지 않기 위해 "이 산이 아닌가벼"를 확률적으로 수행해 주는 방법입니다. 담금질은 사실 오역이고 풀림이 맞다고 하더라구요. 뭐 그래도 보통 담금질이라고 하니 그렇게 칭하겠습니다.

아까 치악산 탐색 문제를 다시 생각해 봅시다. 근처 500미터를 대충 찍고, 거기의 고도가 높으면 옮겨가고 낮으면 다시 다른데를 탐색하는 그런 방식을 생각해 봅시다. 근데 이 경우에서, 우리한테 주사위가 있어서 던져서 1이 나오면 더 낮은 데로 가는 거죠. 이게 담금질 기법의 핵심입니다.

아니 올라가기도 바쁜데 왜? 미친건가? 라고 하지만, 이렇게 하다 보면 천지봉에서 여기가 정상이구나! 할 확률은 많이 줄어들겠죠. 다른 봉우리로 넘어갈 확률이 생기는 거니까요.

왜 담금질 기법이라고 하느냐? 이것을 "쇠가 식는 것"에 비유하는 기법이라 그렇습니다. 여기서 우리는 "온도"라는 숫자를 참조합니다. "온도"는 우리가 더 낮은 곳으로 갈 확률입니다. 답에 근접할 수록 쇠는 식어서 온도는 낮아집니다. 만약 충분히 높은 곳에 있다면 이 가능성은 매우 낮겠죠. 예를들어서 우리가 해발 500미터 올라갈때마다 주사위를 하나씩 추가해서, 해발 500미터부턴 주사위를 두 개 굴려서 둘 다 1이 나와야 낮은 데로 향하는 겁니다. 이렇게 되면, 해발 1000미터쯤 되는 천지봉에서도 "내려갈 확률"이 생깁니다. 그러다 보면 천지봉에 갖혀서 비로봉을 못 찾을 확률은 내려가는 겁니다. 이렇게 점점 내려갈 확률을 줄여가며 올라가다 보면 최고봉을 찾을 수 있겠지요. 이것이 담금질 기법입니다.

3. 금기 탐색 기법(Tabu Search)

보통 타부서치라고 부릅니다. 이 기법은 "여기는 가봤는데"라는 리스트를 만들어서, 이 리스트에 있는 곳은 의식적으로 피하는 방식으로 이루어 집니다. 이 리스트를 금기 대기열(Tabu queue)라고 부르고, 이 리스트를 어떻게 만드느냐, 또한 얼마나 많이 만드느냐 역시 중요한 사항입니다. "내가 한번 가봤던 곳은 눈에 흙이 들어가도 안간다!" 했다가 그 한번 가봤던데가 비로봉일 수도 있잖아요? 그래서 시간이 지나면 악감정도 좀 해소해야 하고 그렇습니다.

치악산 탐색 문제를 생각해 보면, 이렇게 예시를 만들 수 있습니다. 우리가 가봤던 곳에서 근처로 계속 500미터씩 이동을 하는데, 좀 높았던 곳에서부터 가로세로 500미터쯤은 한 4번은 무조건 피하는 겁니다. 그러다가 4번 다른델 찾아봐도 여기가 좋더라, 하면 그때 다시 여기로 와보는 것이죠. 이런 방식으로 천지봉을 한번 밟아도 옆 봉우리로 갈 수 있는 것입니다.

보통 메타휴리스틱이라고 했을때는 유전 알고리즘, 모의 담금질, 타부서치 이렇게 3가지를 이야기하는 경우가 많습니다. 가장 잘 알려진 방식들입니다.

4. 입자 군집 최적화(Particle Swarm Optimization)

파티클 스웜, PSO라고 불리는 기법입니다. 이 기법은 굉장히 많은 측량원들이 동시에 치악산에 오르는 기준에 대해 이야기를 하고 있습니다. 옛날엔 인건비에 쓸 돈이 없어서(컴이 후져서) 주목받지 못했는데, 지금은 상황이 많이 나아져서 좀 더 자주 사용되고 있습니다.

우리는 지금까지 치악산을 혼자 탐색해 왔는데, 한 20명의 측량원을 고용해서 GPS를 쥐여주고 산에 뿌려놨습니다. 이 20명의 측량원들은 다음과 같은 방식으로 움직입니다.

출처: https://rpubs.com/argaadya/intro-pso

1) 별다른 자극이 없으면 얘들은 그냥 가던 방향 대로 갑니다. (관성)

2) 내가 다녀 본 데중에 제일 좋은데가 있었는데, 아 거기 가면 뭔가 잘 될거 같아요. 그쪽으로 가고 싶습니다. (개체 최선값 방향)

3) 20명 중에 누군가가 무전기로 신기록 갱신을 외칩니다! 신이 나서 그쪽으로 갑니다. (군집 최선값 방향)

이 세 가지 방향간의 힘겨루기를 통해 각 측량원들이 이동할 곳이 결정이 됩니다. 이렇게 쓱쓱 쓸고 다니다 보면 어딘가 비로봉이 찍힐 확률이 좀 더 늘어날 것 같지 않습니까? 이렇게 여러 개체들의 이동방향을 값에 따라 결정하면서 최적화를 수행하는 것이 입자 군집 최적화입니다. 보시면 아시겠지만, 경사도를 알 필요가 딱히 없다는 것이 장점입니다.

5. 개미 집단 최적화(Ant Colony Optimization)

ACO라고도 부릅니다. 이 문제는 원래 길찾기 문제의 답을 제공하기 위한 문제입니다. 따라서 어떤 문제를 길찾기 문제와 비슷하게 순차적 선택 문제로 변환할 수 있다면 사용할 수 있는 방법이죠.

아이디어는 다음과 같습니다. 개미들이 최단거리를 찾을 때, 보통 더 짧은 거리를 갈 수 있는 것은, 똑같은 확률로 선택을 해도 짧은 거리에는 더 많은 개미가 왕복해서 더 많은 페로몬을 남기기 때문입니다. 개미들은 이 페로몬을 쫓아가면 짧은 거리를 갈 수 있겠죠?



출처: Modification of the Ant Colony Optimization for Solving the Multiple Traveling Salesman Problem, Yousefikhoshbakht et al., 2013.

여기서 이동하는 하나의 개체를 "개미"라고 표현합니다. 알고리즘은 다음과 같이 이루어집니다.

1) 개미가 길을 찾아가게 만듭니다.

2) 개미들이 길을 찾을 때, 페로몬이 많을 수록 갈 확률이 높아지게 설정합니다.

3) 개미들이 이동하는 곳마다 페로몬을 추가합니다.

4) 개미들의 통행이 끝나고, 가장 좋은 결과를 낸 개미가 지나간 길에 페로몬을 추가합니다.

5) 페로몬을 일정량 증발시켜서 줄입니다.

이것을 계속 반복하게 되면 언젠가 "더 좋은 답"에 개미들이 점점 몰리게 될 것을 기대하는 방식의 알고리즘이죠. 처음에 좋았던 솔루션의 경우 나중에 선택받지 못하게 되면 페로몬이 증발시켜서 결국 더 좋은 답에 개미들이 몰릴 테니 말이죠.