2021/01/16

Differential Evolution 알고리즘


 함수 최적화 관련해서 요즘은 어떤 알고리즘을 사용하나 구글링했더니 Differential Evolution(DE; 차분 진화 알고리즘)이란 놈이 있더라. meta-heuristic 최적화 알고리즘들은 앞서 다루었던 Genetic Algorithm(GA)과 같이 참신한 아이디어들이 많이 녹아 있다. 물리적 현상이나 생태 환경을 모사해서 알고리즘을 만든 것들이 많다. 담금질 원리를 적용한 Simulated Annealing(SA)이나 새들이 떼지어 날아 다니는 행태를 모사한 Particle Swarming Optimization(PSO), 개미들이 페로몬을 이용해 먹이를 지름길로 운반하는 것을 모사한 Ant Colony Optimization(ACO) 같은 것들이 대표적이다. DE란 놈도 뭔가 참신한 아이디어가 있으리란 생각에 공부해 보기로 했다. 처음엔 GA의 변종인가 싶었는데 머 변종이 아니라고 할 수는 없지만 다른 놈이라고 보는게 좋을 듯. GA에서 아이디어를 얻어서 mutation/crossover/selection operation 들을 정의한 듯 한데 전반적인 동작 방식은 다르다. 다만, crossover는 GA의 crossover와 동일하다. 

흠, DE의 아이디어도 참신할 뿐만 아니라, 원 저자들(Storn and Price, 1997) 주장처럼 간단하고 견실하면서도 빠른 최적화 알고리즘이더라. 함수 최적화에는 이보다 더 좋은 알고리즘이 있을까 싶을 정도다. GA에서 테스트했던 함수들을 가지고 DE로 돌렸더니 모두 200% 만족이다. 그래서, 이놈을 가지고 TSP 문제를 테스트해 보기로 했다.

Differential Evolution(DE) Algorithm

이 놈도 GA와 같이 최초에  Np개의 최적 해 후보 들에 대한 random population을 만들어 놓고 시작한다. 세대가 시작되면 population 내의 각 개체 vector들을 조건에 따라 갱신한다. 먼저, 시험 벡터(trial vector)를, population 내에서 현재 vector가 아닌 중복되지 않는 세 놈을 random하게 골라서, 한 놈이 이동시킬 기준점(X_r1)이라 치고 다른 두 놈(X_r2, X_r3)의 vector 차를 사전에 정한 비율(F; scaling/mutation factor)로 기준점 벡터에 더해서 만든다(mutation). 시험 벡터(T = [t_1, t_2, ..., t_Dim]) 는 현재 벡터(X_i)와는 독립적으로 생성되므로 돌연변이라 할 수 있다. 그리고 나서 이 놈을 현재 벡터와 crossover 확률(CR)에 따라 교합시켜 새로운 후보 벡터를 만든다(crossover). 이 놈의 cost가 현재 벡터의 cost 보다 낮을 때만 현재 벡터를 대치시킨다(selection). 원래 DE의 식들을 간소화 시킨 아래 두 개의 식이 모든 걸 말해 준다.

t_j = x_i,j                        <= if rand(0,1) > CR // Crossover

  x_r1,j + F*(x_r2,j - x_r3,j) <= else // Mutation

  (단, j = 1, 2, ..., Dim | CR:(0,1], F:[0,2])

X_i = T                            <= if cost(T) < cost(X_i) // Selection

  (단, i = 1, 2, ..., Np | i != r1 != r2 != r3) 

즉, 첫 번째 식에서 두 벡터 간의 차(difference)를 이용해 만들어진 만들어진 시험 벡터를 사용하고, 위의 과정을 현재 세대(g)의 population 내 모든 벡터들(i = 1, 2, ..., Np)에 대해 반복한 후, GA와 같이 g = 1, 2, ..., 최대 세대수까지 다시 반복하기 때문에 Differential Evolution이라 이름 붙인듯 하다. 이는 Gradient Descent(경사하강법)와 유사한 원리인데 population 내에서 random하게 골라낸 놈들을 이용한다는 아이디어이다. GA의 아이디어는 세대가 지날수록 부모 세대 교배를 통해 자손 세대의 우량 유전자가 급격히 늘어나도록 하는 것인데, DE는 현재 세대의 population 내에서 우량한 놈들을 새로 만들어 내면서 세대가 지나면서 계속 우량한 놈들이 늘어나도록 유도하는 점이 다르다. 위에서 세 놈을 고를 때 현재 벡터와 겹치지만 않으면 이미 새로 만들어진 벡터들을 이용해서 새로운 놈이 만들어질 수 있는 구조이기 때문에 수렴이 된다면 GA보다 훨씬 빠르게 수렴하리라 예상할 수 있다. 하지만 GA 관점에서 보면 이 과정은 자칫 유전자 다양성을 떨어뜨릴 우려가 있다.

위의 식에서 알 수 있듯이 DE는 식 자체도 단순 직관적이거니와 알고리즘에 영향을 주는 매개변수가 Np(population size)와 F(scaling factor), CR(crossover probability) 3개 뿐이다. Np는 독립변수의 차원 수(Dimension)에 따라 달라질텐테 너무 작으면 안되지만 GA에서와는 달리 너무 커도 안좋다. 최대 10*Dimension인 듯하다. TSP 문제를 시험해 보니 Np = 30개로도 42개 도시 최단 경로 문제까지는 해결할 수 있더라. 하지만, DE의 가장 큰 단점이 F와 CR 값에 굉장히 민감하단다. Np는 상대적으로 덜 민감한 편이다. 사실, GA와 마찬가지로 난수 vector population을 사용하기 때문에 초기 난수 분포가 역시 중요한 역할을 한다. 

DE는 원 저자들이 DE/x/y/z 같이 변형에 대한 표기법까지 만들어 두었다. x는 차(difference)로 시험벡터 만들 때 기준점 vector가 random이냐 best냐를, y는 위에서는 1개의 차만 사용했지만, 겹치지 않는 다른 두 놈을 더 뽑아 그 차를 더할 수도 있는데 이 경우 2가 된다. z는 crossover 방식이 binomial이냐 exponential이냐를 나타낸다. binomial은 CR 확률에 따라 uniform하게 두 벡터를 섞는 것이다. exponential은 GA의 2-point crossover와 유사하다.  위의 첫번째 식은 DE/rand/1/bin으로 표준 DE라고 할 수 있다. 실제로 테스트해 보니 TSP에는 DE/rand/*/exp가 낫더라.

최적화란 말 자체가 내포하고 있듯이 득이 있으면 실이 있기 마련이다. 그 균형점을 찾는 것이 최적화의 목표이다. 최적화 알고리즘 내에서도 매개 변수 자체에 대한 최적화 문제가 항상 발생하게 된다. local search를 이용해 최적해(global minimum) 가까이 수렴하도록 하는 것과 local minima에 빠지지 않도록  돌연변이 등을 통해 현재 구간 밖에서 최적해를 탐색하도록 하는 것을 절충 해야 한다(balance between exploitation and exploration; intensification vs. diversification). 이것이 조화가 잘 되는 알고리즘이 좋은 알고리즘인데 진화적 알고리즘(Evolutionary Algorithm)들은 대체로 이런 점을 고려해서 만들어졌다.

Traveling Salesman Problem(TSP) 테스트

TSP 문제에 도전해 본 적은 없었는데 막상 해 보니 재미있더라. 그런데, 전에 인터넷에서 스치듯이 지나쳐서 확실하지는 않은데 TSP 문제를 수학적으로 해결할 수 있는 방법이 나왔다나(다시 구글링했는데 못찾겠다)... 그래서 더이상 NP-hard한 문제가 아닐 수도 있다는... 이것만 연구하는 사람들도 꽤나 많았고 지금도 있을 것이다. 실제 산업 현장에서도 많이 발생하는 전형적인 조합 최적화 문제이기 때문이다. Linear Programming(LP)으로도 풀 수 있지만 도시 수가 늘어날수록 GA와 같은 meta-heuristic 알고리즘이 더 효율적이다.

TSP는 외판원이 n개의 도시를 순차적으로 방문해서 돌아오는 최단 거리 경로 찾기 문제이다. TSPLIB 사이트에 문제 data 파일 들과 답이 있다. 답은 오래된 것들이라 최적해가 아닐 수도 있다. 모든 도시들에서 가는 길과 오는 길이 같다면 Symmetric 문제가 되어 경로의 가지 수는 n!/2가 된다. 도시 경로 문제 data 파일(도시 좌표가 들어 있는 일반 text 파일임)들을 보면 berlin52.tsp와 같이 도시 수가 붙어 있다. 이 파일들은 출발지를 포함하기 때문에 방문 경로 수는 berlin52 문제의 경우 (52-1)!/2 = 7.75x10^65 가지 수이다. 65개의 0이 붙어 있는 숫자라 감이 안잡히겠지만 현재의 웬만한 수퍼 컴퓨터로도 최소 백만년은 걸려야 모든 경로 거리를 계산할 수 있단다. data 파일을 읽어서 DE로 돌려 보았는데 berlin52 문제부터는 내 그닥 PC에서 보통 너댓 시간 이상 걸리고 site에 게시된 7542의 근처인 7666까지 겨우 1번 성공했다. dantzig42(경로 수: 1.67x10^49)까지는 거의 최적해를 1초 ~ 5분 내에 구할 수 있더라. 시간 편차가 심한 이유는 난수를 사용하고 테스트 조건이 바뀔 수 있기 때문이다. 운이 좋으면 금방 답이 나오고, 운이 나쁘면 만족스러운 답을 얻지 못할 수도 있다. 도시 10개 차이가 경로 수로는 10^16가지 만큼이나 차이가 난다. 아래는 DE가 구한 도시 간 최단 경로 그래프이다. site에 게시된 699보다 나은 최저 값을 쉽게 자주 찾아낸다. 이 경로가 최단 경로일까?

이제 DE로 풀어 보자. random population은 쉽게 만들 수 있다. 도시가 10개라면 10개 독립 변수가 있는 셈인데 도시에 0 ~ 9까지 id를 부여해서 도시 경로 vector를 만들어 주면 된다. 이 놈은 GA의 염색체와 동일하다. 단, 이 벡터 내에서 도시들은 방문 순서가 random하게 조합되어야 하고 한 번씩만 방문할 것이기 때문에 id가 중복돼선 안된다. 그냥 0~9까지 숫자를 채우고 random shuffling해 주면 한 개의 경로 벡터가 생성된다. population size가 30개라면 30개 경로 벡터를 이런 식으로 만들면 된다.  cost는 위의 그래프에서와 같이 연결된 두 도시 간의 거리(Euclidean distance)들을 모두 합산하면 된다.

GA의 경우엔 TSP에 도전한 사례가 많기 때문에 다양한 crossover operator들이 연구되었다. DE의 경우엔 위의 첫번째 식을 사용하면 된다. 두 경로 벡터 간의 차를 구해서 다른 경로 벡터에 더해주면 된다. 다만, 이 경우에 음수 값이 발생하게 되고, F 값을 곱해 주기 때문에 새로운 경로 벡터 생성시 실수를 정수로 바꿔주어야 하며, 결과 값인 도시 id가 중복되는 경우가 발생할 수 있다. 음수 값이 의미하는 것은 출발한 도시에서 반대 방향으로 가면 된다는 뜻이다. 이것은 Circular Queue에서 modulo index를 구하는 것과 같다. 도시 id가 중복되는 문제는 GA에서 crossover operator들이 널리 사용하는 방법처럼 중복이 발생하면 부모 벡터의 중복되지 않는 id들을 순서대로 채워 넣으면 된다. 경로의 도시 순서 조합을 최적화하는 것이기 때문에 합리적인 방법이다. 즉, 위의 첫째 식에서 기준점 벡터(X_r1)를 부모 벡터로 사용했다. 

이 후 과정은 population 내의 모든 경로 벡터에 대해 위의 과정을 반복하고 나서, GA에서와 같이 cost 값이 수렴할때까지 세대를 반복하면 된다. DE는 GA에 비해 상당히 작은 population을 사용하기 때문에 수렴이 잘되는 편이다. 하지만 이렇게 얻어진 값이 최적 해에 가까운지는 남들의 결과와 비교해보지 않고는 장담할 수 없다.

아래 그래프는 위의 dantzig42 경로 최적화 문제 해결에 DE가 몇세대를 허비하는지 보여 준다.  population size가 30개이므로 nfe(the number of function evaluations)는 2,000세대 x 30 = 60,000번 정도이다. local minima에서 벗어날 수 있도록 2%의 swap mutation을 적용했다. swap mutation은 두 유전자(도시)를 random하게 뽑아서 순서를 바꿔주는 방식이다.

그런데, DE를 테스트하면서 돌리다보니 맨 앞의 그래프보다 더 짧은 경로를 찾아내서 비교 목적으로 첨부한다. 이 놈을 발견하기 전에는 육안으로 쉽게 최적 해인지 알수 있을 거라 생각했었다. 아래 그래프가 dantzig42 최단 경로일까???


사실, 위의 결과까지는 binomial crossover 방식을 사용한 것인데 이 글을 쓰고 나서 다시 exponential crossover 방식을 사용해 보니 dantzig42 문제의 최단 거리는 679.202인 듯하다. 왼쪽 맨 꼭대기부터 오른쪽으로 4개의 점(3개의 선분 중 첫째와 셋째)을 달리 이으면 된다.

결론적으로, DE에서 F와 CR 뿐만 아니라, Np와 crossover 방식까지도 주어진 최적화 문제에 맞게 tuning이 필요하다. 이 중에서도 F와 CR은 더더욱 민감하다. 그래서 찾아보니 Self-adaptive DE에 대한 연구가 많았더라. 사실, 간단히 만들어서 테스트도 해 봤는데 그럭저럭 쓸만한 편이다. 말인 즉슨 모든 최적화 문제에 적용할 수 있는 Self-adaptive DE는 만들기 어렵다는 뜻이다. 

맺음말

TSPLIB 사이트의 문제들 중에서 그나마 내 PC에서 다양하게 테스트해 볼 수 있는 경우는 dantzig42까지이다. 변수 수가 적을 경우에는 DE가 매우 훌륭한 최적화 알고리즘이라 할 수 있다. 하지만, 변수 수가 늘어나면 복잡도가 지수적으로 증가하게 되기 때문에 DE가 좋은지 장담할 수 없다. berlin52를 (내 그닥 PC가) 밤새워 여러 번 돌려 본 결과는 좋지 않더라. 순수 GA의 경우 15만개 size의 population을 사용해서 24세대 만에 berlin52 문제를 해결했다더라. nfe로 따지면 대략 360만회 만에 해결한 셈인데 DE는 천만 번을 넘어도 좋은 해를 구하기 어렵더라.

요즘 Deep Learning에서 사용하는 parameter 수가 일억 개는 보통(?)이고 십억 개 이상을 넘보고  있단다. 겨우 42개 parameter가지고 깔작대봐야 머 큰 의미는 없다. 그렇다고 비관할 필요는 없다. PC로도 충분히 배울 수 있고 효율적인 알고리즘은 언제나 필요한 법이다. 사실 대기업에 준하는 회사가 아니고서 일억 개 변수를 사용해 볼 수 있는 서버를 보유한 회사가 그리 많지는 않을 것이다. 어쨌든 대자본이 인공지능을 점령하는 것은 시간 문제이다. 인공지능이 대자본을 점령하는 것도 시간 문제라 본다. 적자 생존 원리에 따라 기계가 적자가 될 수도 있을 것이다. 그것도 우주의 관점에서 보면 대수로운 일도 아니다. 누군가는 죽고 누군가는 살아 남는 일들은 늘상 우주에서 벌어지는 일이다. 코로나 바이러스에 걸려 죽든 교통 사고로 죽든 죽는게 중요한 것이 아니라, 오늘을 어떻게 살아 갈 것인가가 더 중요한 문제이다.