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로도 충분히 배울 수 있고 효율적인 알고리즘은 언제나 필요한 법이다. 사실 대기업에 준하는 회사가 아니고서 일억 개 변수를 사용해 볼 수 있는 서버를 보유한 회사가 그리 많지는 않을 것이다. 어쨌든 대자본이 인공지능을 점령하는 것은 시간 문제이다. 인공지능이 대자본을 점령하는 것도 시간 문제라 본다. 적자 생존 원리에 따라 기계가 적자가 될 수도 있을 것이다. 그것도 우주의 관점에서 보면 대수로운 일도 아니다. 누군가는 죽고 누군가는 살아 남는 일들은 늘상 우주에서 벌어지는 일이다. 코로나 바이러스에 걸려 죽든 교통 사고로 죽든 죽는게 중요한 것이 아니라, 오늘을 어떻게 살아 갈 것인가가 더 중요한 문제이다.

유전 알고리즘을 이용한 함수 최적화

 

뜬금없이 먼가 떠올랐을때 해봐야 직성이 풀리는 못된 버릇이 있다. 세살 버릇 여든 간다. 오늘은 코로나 뉴스를 보다가, 소시적 원서를 질러 독학했던 유전 알고리즘(Genetic Algorithm; GA)이 문득 떠올랐다. 당시에도 여러가지 해보고 싶은게 많았지만 본류 주제가 아니었기에 접고 있었다. 그 중 하나가 실수(real number)를 쉽게 다루는 방법에 대한 것이다. 다변수 목적 함수(multi-variable objective function)의 최적화 문제를 풀기 위한 GA가 단변수 목적 함수(uni-variable objective function)에 대한 GA보다 오히려 단순하다. 다변수 함수에서는 변수 각각을 유전자(gene)로 간주하면 되지만, 단변수 함수에서는 유전자를 어떻게 encoding 할 지 고민해야 한다. 논문들을 보면 실수를 string으로 encoding해서 유전자로 사용했었다. 하지만, 당시에도 컴퓨터가 기본적으로 모든 숫자들을 binary로 encoding해서 사용하고 있는데 또 다시 encoding하는 것이 굉장히 불합리하다고 생각했다. 흠, 그래서 이 문제도 해결하고 보다 일반적으로 함수 최적화 문제를 풀 수 있는 GA를 만들어 보기로 했다.

GA는 매우 단순하면서도 효율적인 최적화 알고리즘이다. TSP(Travelling Salesman Problem: 영업사원이 n개의 도시를 순차적으로 방문 후 돌아오는 최단 경로 문제로 n! 갯수의 거리계산이 필요)와 같은 NP-hard한 조합 최적화 문제도 빠른 시간 안에 준 최적(suboptimal) 경로 조합을 찾아낼 수 있어서 많이 활용되기 시작했다. GA는 구현하기도 쉬워서 장난감으로 갖고 놀기에 좋은데, 장난감 치고는 더 대단한 일을 할 수 있는 놈이다. 목적 함수와 주요 독립 변수만 알고 있다면 대부분의 경우 전역 최적값(global optimum)에 근접한 해를 구할 수 있기 때문이다. 목적 함수에 대한 제약 조건(constraints)들이 있다면 더더욱 정확한 최적값을 얻을 수 있다. 이것은 과거의 전통적인 최적화 기법들과는 상반되는 것들이다. 즉, 함수의 연속성, 미분 가능성, 단극성(unimodality) 등 전통적인 최적화 기법들이 요구하는 제약사항들을 GA가 모두 극복할 수 있기 때문이다. 가령, 인공신경망을 학습시키려면 cost/loss function에 대한 미분 가능 여부가 걸림돌이 된다. GA 관점에서는 복잡한 인공신경망 목적 함수를 최소화하는 weights 값들을 구하는 문제로 귀결된다. 더구나 인공신경망에서 항상 문제가 되는 local minima에 대한 문제도 GA가 해결해 줄 수 있다. 사실, 이 부분도 소시적에 시도해 보고 싶었던 것 중의 하나였다. 인공신경망을 GA로 학습시키는 것 말이다. 혹시나 해서 구글링해 보니, 최근까지도 연구가 진행되고 있다. Reinforcement Learning에서도 학습 시키기 위해서 미분 가능하지 않은 목적 함수들을 채용할 수 있다는 점에서 매우 고무적이다. 인공신경망을 GA로 학습시킬 수 있다면 Deep Learning에도 굉장히 큰 변화를 가져올 것이다. 학습 시간을 줄이는 것은 물론이고 다양한 cost function을 사용할 수 있을 것이기 때문이다. 또한, real-time dynamic learning까지 가능할 수도 있다.

사실, 실생활에서 단변수 목적 함수를 사용할 일은 거의 없다. 흔히 사용되는 1차(1st order 또는 linear) 최소 제곱(자승)법(Least Squares Method/Regression)도 2변수 목적함수를 최적화하는 문제가 된다. 편미분을 이용해서 주어진 데이터를 가지고 최적의 직선 방정식(y = ax + b)을 구할 수 있다. 가령, 날짜별 코로나 신규 확진자 추이 데이터를 가장 잘 반영한 직선 방정식을 전통적인 최적화 기법으로 쉽게 구할 수 있다는 야그다. 하지만, 이 직선으로 내일 신규 확진자가 몇명일지 추정하기는 쉽지 않을 것이다. 시간별 확진자 수는 비선형적으로 증가하기 때문이다. 즉, 고차(higher order/non-linear) 목적 함수에 대한 최적화 문제로 귀결된다. 목적 함수가 비선형이 되는 순간 전통적인 최적화 기법들은 많은 제약이 뒤따르게 된다. 하지만, 단변수 목적 함수는 GA를 이해하고 알고리즘 자체를 개선하는데 매우 도움이 되기 때문에 단변수 함수 최적화에 GA를 사용하는 것 자체도 의미가 있다. 우리가 함수 그래프를 그려 볼 수 있는 것은 기껏해야 독립 변수가 2개까지인 경우이다. 독립 변수가 2개이면 3차원 그래프를 보아야 한다. 3차원 그래프도 유용하지만 2차원 그래프를 보면 훨씬 쉽게 함수를 이해할 수 있다. 이것이 단변수 함수 최적화가 갖는 의미다.

Genetic Algorithm(GA)

먼저, 알고리즘 자체를 간단히 살펴 보자. GA는 찰스 다윈의 자연선택설을 모방하여, random 염색체 군에서 선택(selection) - 교합(crossover) - 돌연변이(mutation)를 통해 새로운 세대의 염색체 군을 만드는 과정을 반복함으로써 세대가 지날수록 우량 염색체만 살아 남도록 하는 알고리즘이다. 자연의 진화 방식에 내재된 최적화 기법을 모사한 진화적 알고리즘(evolutionary algorithm) 중 하나이다. 이 때문에 GA를 흔히 meta-heuristic(반 경험적) 알고리즘이라 한다. 인공신경망과 유사하게 수학적으로 해석하기도 쉽지 않고 그렇다고 경험적으로 증명되었다고 치부해 버릴 수도 없다는 의미이다. 실제 GA 구현 방법은 차이가 날 수 있지만 원리는 동일하다. 아래는 GA의 대략적인 순서다. 

1. 유전자들(genes)을 염색체(chromosome)로 encoding

2. random 염색체들로 population 생성 및 fitness(우량도/적합도; 목적 함수 계산 값) 계산

3. fitness가 높은 순(또는 cost가 낮은 순)으로 염색체 정렬

4. 우량한 염색체들을 선택 교배(mate)시켜서 새로운 세대(generation) 생성

   4-1. elite 염색체 일부 복제하여 신세대 생성

   4-2. 상위 fitness 염색체들 간 random 교합(crossover) 후 신세대 생성 및 fitness 계산

   4-3. 돌연변이(mutation)로 신세대 생성 및 fitness 계산

5. 3 ~ 4의 과정을 사전에 정한 최대 세대 수 또는 종료 조건 만족시까지 반복

참고로, 대부분의 최적화 문제들은 cost를 최소화하는 것이기 때문에 GA의 fitness를 cost로 전환하여 사용하는 것이 좋다. fitness를 최대화하는 것은 cost를 최소화하는 것과 같다. 물론 목적 함수에 -1을 곱해서 사용해도 된다. 부가적으로 GA의 용어들을 최적화 용어로 대치하자면, 유전자는 목적 함수에 영향을 주는 요인이다. 다변수 함수라면 독립변수 각각에 해당된다. 염색체는 유전자들의 결합체이다. 교배시 필요한 하나의 개체이다. 다변수 함수에서는 최적 해의 후보 값 vector가 된다. 이 독립변수 vector 조합으로 목적 함수에 의해 fitness 값을 계산할 수 있게 된다.

GA에서는 난수(random number)들이 중요한 역할을 한다. 초기 염색체 population이 GA가 최적 해를 찾는데 큰 영향을 준다. 최적해의 후보를 탐색하는 관점에서 보면 가능한 모든 범위에서 균일한 난수가 생성되는게 좋다. 이 들이 대표 선수가 되어 좋은 유전자를 후대에 물려주게 된다. 하지만, GA 자체는 빠른 알고리즘이기 때문에 여러 번 돌려 보는게 더 나을 수도 있다. GA의 가장 큰 단점은 알고리즘 종료 조건을 설정하기 어렵다는 것이다. 처음엔 모두 다른 염색체들로 시작했는데 세대가 늘어날수록 우량 염색체가 다수를 차지하게 된다. 수렴하다가 더 좋은 값으로 바뀔 수도 있기 때문에 세대간 목적함수 값을 비교하기 어렵다. 목적함수 평균값에 대한 오차나 우량염색체 비율 등이 종료조건 후보가 될 수는 있지만 실제 돌려 보면 최대 세대수를 정해 놓고 돌리는게 더 나을 경우가 많다. 이것은 돌연변이를 사용해야 하기 때문에 발생하는 문제이다. 다른 최적화 알고리즘들과 마찬가지로 GA에 영향을 주는 매개 변수들이 있다. population 염색체 개체 수, crossover 확률, mutation 확률, 최대 세대 수, 탐색 구간 같은 것들이다. 좋은 방법은 처음엔 부정확하지만 빠르게 GA를 한번 돌려서 suboptimal 해를 구하고 나서 탐색 구간을 좁혀준 후 GA를 한번 더 돌리면 매우 정확한 값을 얻을 수 있다.

GA에서 실수형(real-number type) 단변수 및 다변수 사용

GA의 단변수는 64bit 실수를 사용하면 되므로 c++에서는 double type을 사용하면 된다. 앞서 얘기했듯이 컴퓨터는 이미 실수를 binary로 encoding해서 사용하고 있다. 우리는 이 놈이 염색체라고 보고 유전자들을 어떻게 선택 - 교합 - 돌연변이 시킬지를 알아내면 된다. 64bit encoding된 실수의 binary 형식을 알기 위해 Wikipedia를 참조할 필요가 있다.

아래는 교배(mate)함수를 구현한 것이다. size가 1일때가 Wikipedia를 참조해서 만든 단변수일 때 교배 방법이고 다변수에 대해서도 일관된 logic을 적용하였다. 너무나 간단한데 첨엔 이게 잘 돌아갈까 스스로 의심도 했지만 실제 GA를 돌려보니 단변수 함수의 전역 최적 해의 근사값을 너무도 잘 구해 내더라. 수치 해(numerical solution)로써 정확도 면에서도 손색이 없을 정도다. 참고로, Real64 type은 double과 uint64_t의 union type이다. 즉, 유전자 조작은 bit 연산으로 수행하고 fitness(목적 함수) 계산시에는 걍 double 값을 사용하겠다는 것이다. 좀 관심이 있는 사람들은 아래의 logic에서 몇가지 특이 사항을 발견할 수도 있을 것이다. 다변수의 경우엔 변수 갯수만큼 실수형 배열이나 아래와 같이 vector를 사용하면 된다.

  Chromosome mate(const Chromosome& another) {
    if(size == 1) {
      Real64 chro;
      for(int i = 52; i < 64; ++i) {
        float p = random_int(0, 100) / 100.0;
        if(p < (1 - pMutation) / 2) chro.i |= chromosome.i & (1 << i);
        else if(p < 1 - pMutation) chro.i |= another.chromosome.i & ( 1 << i);
        else chro.d = mutate();
        //else chro.i |= (chromosome.i ^ (1 << i)) & (1 << i);
      }
      //unsigned nan = (chro.i >> 52);
      //if(nan == 0x7ff || nan == 0xfff) chro.i ^= (1ul << 52); // NaN or INF
      return Chromosome(chro);
    }
    else {
      std::vector<double> gv;
      for(int i = 0; i < size; ++i) {
        float p = random_int(0, 100) / 100.0;
        if(p < (1 - pMutation) / 2) gv.push_back(xv[i]);
        else if(p < 1 - pMutation) gv.push_back(another.xv[i]);
        else gv.push_back(mutated_gene(i));
      }
      return Chromosome(gv);
    }
  }

전체 알고리즘을 구현하는 것은 별로 어렵지 않기 때문에 관심이 있는 사람들은 직접 구현해 보길 권한다. 흠, 나는 자주 바퀴를 다시 발명하기를 권하는데 일반적으로는 권장하지 않는 가이드이다. 하지만 고집하는 이유는, 자신이 만든 것에 사람들은 애착을 느끼게 되고 이것이 삶이나 행동에 큰 변화를 줄 수 있다는 믿음 때문이다. 더구나 직접 만들어 보면 남의 것을 사용하던 때와 굉장히 다르다는 것을 깨닫게 된다. 기존의 바퀴에 개선의 여지가 여전히 많다는 것도 자연스럽게 깨칠 수 있다. 이런 것은 누가 가르쳐 줄 수도 없는 것들이다. 

GA 테스트 결과

아래 그래프는 단변수 목적 함수인 y = (x^4 + 2*x^3 - 3*x^2 + 13)^2 - 5를 구글링해서 Firefox로 capture 한 것이다. 흠, 우연히 그래프를 우클릭했는데 capture 기능을 발견해서 당장 써먹는다.

이 함수의 전역 최소값은 아래 그래프에서 GA가 72번째 세대에서 수렴한 [x', Cost'] = (-2.188332, -4.63122) 값과 거의 일치함을 알 수 있다.

이 함수말고도 주기 함수나 불연속 함수 등 몇가지 단변수 함수의 전역 최소값 구하기를 GA로 돌려 보았는데 너무도 잘 찾을뿐 아니라 값들도 상당히 정확하다. 주기 함수의 경우 범위에 대한 constraint를 주면 더 정확한 x 값을 찾아낸다.

독립변수가 2개인 경우까지는 그래프 구글링을 통해 대략 최적값이 맞는지 확인할 수 있다. 아래는 Rosenbrock 함수로 알려진 z = 100*(x^2-y)^2 + (1-y)^2 함수를 구글링한 것이다. 전역 최소값 [x', y', z'] = (1, 1, 0) 또는 (-1, 1, 0)이다. 이 놈은 local minima에 빠져서 global 최소값을 찾기 어려운 놈으로 테스트하기 좋은 2변수 함수이다. 구글링해보면 이놈을 어떻게 보는게 좋을지도 고민하게 되는 상당히 난감한 놈이다. 이 놈을 GA로 돌려 보면 초기 난수 분포에 따라 최종 결과가 달라지긴 하지만 전역 최소값에 근사한 값들을 어려움없이 잘 찾아낸다.

간단한 데이터를 가지고 GA로 linear regression을 해 보니 대체로 잘 된다. 변수 범위를 지정하면 편미분으로 구한 정확한 값과 거의 일치하더라. 구글링해 보니 고차(higer-order) regression 문제도 GA로 해결한 사례들이 꽤 있더라.

3변수 이상 다변수 목적함수인 경우에도 GA를 많이들 써먹고 있다. GA 테스트는 할 수 있지만 결과가 맞는지는 남들이 구한 최적 값과 비교해야 하는 난감함이 따른다. 구글링해서 한가지 돌려 봤는데 잘 맞더라. 흠, 아무튼 이제 Deep Learning에 GA를 테스트할 일이 남았는데 언제쯤 할지는... Deep Learning 분야는 상대적으로 학습이 잘됐는지 확인할 수 있는 방법들이 있어서 오히려 편할 수 있다. 

참고로, 3변수 이내에서는 population 크기를 1000으로 하고 1000세대까지 웬만한 PC에서 돌려도 거의 1분 내에 답을 찾을 것이다.

c++20 Coroutine 배우기

올해 말까지는 c++20 표준이 공표될거라 해서 Big 4라 불리는 놈 중 하나인 Coroutine에 대해 배워 보기로 했다. 이 놈에게 관심을 가진 이유는 비동기 처리를 쉽게 할 수 있어 보여서다. 이를 테면 Signal & Slots를 callback을 사용하지 않고 구현할 수도 있을까 하는 궁금증... 

결론적으로 모든 것을 대체할 수는 없다는 생각에 이르렀지만 활용 범위는 꽤 늘어날 듯 싶다. 당장 게임 같은 곳에서는 UI와 로직을 분리할 수 있어서 꽤나 유용할 듯 싶다. 이외에도 이벤트 처리, generator, lazy-evaluation 알고리즘, 네트워크 등의 비동기 I/O에 활용될 수 있다. Asio 네트워크 라이브러리에서는 10년 전부터 매크로를 이용해서 c++20의 코루틴 구현 방식인 stackless 코루틴을 사용해왔단다. 세상엔 대단한 넘들이 많다. c++20의 코루틴은 pointer를 처음 배우는 것만큼 배우기도 쉽지 않다. 뭐, 알고 나면 별거 아닌게 되지만...

코루틴에 대해 제대로 정리하려면 너무 길어지므로, 이 글은 간단한 예 하나 만들어 본 것을 정리하는데 그친다. c++20의 코루틴이 복잡한 이유는 컴파일러가 생성해 주는 일종의 coroutine framework에 맞추어서 코딩해야 하기 때문이다. 숨겨진 로직이 많다는 것이다. 나중에 cppcoro와 같은 라이브러리가 표준으로 채택되면 사용자들은 동작 방식보다는 활용 방법만 배우면 될 것이다.   

코루틴 이해

Coroutine은 원래 main 루틴이 아닌  모든 subroutine을 포함하는 개념이란다. 좁은 의미로는 진입 지점을 여러 개 가질 수 있는 함수가 코루틴이다. 기존 함수는 시작(by-call)과 끝(return)만 있는데, 중단(suspend)했다가 다시 재개(resume)할 수 있는 기능이 추가된 함수로 이해하면 된다. suspend/resume이 필요한 이유는 실행 흐름을 비동기(asynchronous) 방식으로 제어하기 위해서이다. 결국, 코루틴은 실행 흐름을 논리적으로 제어하기 위한 함수이다. 좀 깊이 들어 가면 선점형(pre-emptive) 스케쥴링과 협력적(cooperative) 스케쥴링에 의한 multi-tasking 개념을 이해해야 한다. Thread와는 독립적인 개념인데, 기본적으로는 하나의 thread로 멀티태스킹을 할수 있다고 보면 된다. 비동기 네트워크 서버가 단일 쓰레드로 다수의 클라이언트를 처리하는 것을 떠올리면 된다.

3가지 키워드인 co_await, co_yield, co_return 중 하나라도 사용된 함수는 코루틴이 된다. main() 함수는 코루틴이 아니므로 3가지 키워드를 직접 사용할 수 없다. 코루틴 framework은 Promise Interface, Awaitable Interface, Coroutine Handle의 3가지 API를 이해해야 한다.  앞의 두 인터페이스는 사용자가 작성해야 한다. Handle은 컴파일러 내장 함수이고 <coroutine> 표준헤더를 참고하면 된다. Promise Interface는 코루틴 객체 class 내에 정의하여 코루틴의 동작 방식을 제어한다. Awaitable Interface는 co_await 키워드가 어떻게 동작할 지 정의하기 위한 것이다.  Handle은 코루틴의 재개(resume)와 소멸(destroy), 현재 상태(done), 메모리상의 위치(address) 등에 대한 인터페이스이다. 3가지 키워드는 3가지 API를 적절하게 사용하기 위해 필요한 것이다.

코루틴 사용 예

class SimpleTask
{
public:
  struct promise_type;
  using coro_handle = coroutine_handle<promise_type>;
  struct promise_type {
    auto get_return_object() { return SimpleTask{coro_handle::from_promise(*this)}; }
    auto initial_suspend() { return suspend_never{}; }
    auto return_void() { return suspend_never{}; }
    auto final_suspend() { return suspend_always{}; }
    void unhandled_exception() { std::terminate(); }
  };

  SimpleTask(SimpleTask&& r) = default; // ensure copy elision
  ~SimpleTask() { if(m_handle) m_handle.destroy(); }
  bool resume() { if(!m_handle.done()) m_handle.resume(); return !m_handle.done(); }

private:
  explicit SimpleTask(coro_handle handle) : m_handle(handle) {}
  coro_handle m_handle;
};

// For AsyncTimer, the total time required for coro_simple() should be 3 seconds???
// If you think so, try to make it~!!!
SimpleTask coro_simple()
{
  std::cout << "Hello\n";
  co_await 3s;
  std::cout << "  after 3 sec ...\n";
  co_await 2s;
  std::cout << "  after 5 sec ...\n";
  co_await 1s;
  std::cout << "  after 6 sec ...\n";
  std::cout << "Coroutine~!\n";
}

int main()
{
  std::cout << "+++ Start\n";
  SimpleTask task = coro_simple();
  while(task.resume());
  std::cout << "--- End\n";
}

위의 소스에서 coro_simple() 함수에 co_await 키워드가 사용됐으므로 코루틴이다. 코루틴 반환 객체(간단히, 코루틴 객체)인 SimpleTask class내에 정의된 promise_type이 Promise Interface이다. 일반 함수와 달리 SimpleTask를 return하는 부분이 안보이지만 컴파일이 잘 된다. 실제로 SimpleTask객체를 promise.get_return_object() 인터페이스 함수를 통해 코루틴 최초 중단 시와 완료 시 내부에서 반환하기 때문이다. co_await 키워드만 사용했지만 함수 맨 끝에 co_return이 있는 것과 같다. 일반 void 함수 끝에 return을 사용하지 않아도 되는 것과 유사하다. 사실, SimpleTask class는 미래엔 라이브러리로 제공될 부분이다. 사용자는 그것들을 이용하는 방법만 알면 된다.

c++은 너무 유연해서 코루틴도 일반 함수처럼 동작할 수 있지만, 기본적으로 코루틴은 한 번 이상 중단/재개가 일어난다고 보면 된다.  코루틴이 중단 된다고 프로그램이 중단되는 것이 아니다. 중단하는 이유는 원하는 결과를 기다리기 위한 것이다. 코루틴이 비동기적이라고 하는 이유이다. 가령 위의 co_await 3s; 부분은 코루틴을 중단하고 3초간 기다리라는 것이다. 중단되면 실행흐름이 caller인 main() 함수로 돌아간다. while 문에서 코루틴을 재개해서 중단된 지점에서 다시 시작하도록 한다.

Promise Interface

Promise Interface는 promise_type을 통해 코루틴 실행시 중단 및 재개 지점에서 호출되는 interface method 들을 정의하고 코루틴 자체의 동작 방식을 제어한다. std::future<>와 함께 쓰이는 std::promise<>와 유사하지만 좀더 확장된 개념으로 보면 된다. promise_type 객체는 "약속"이라는 이름과 같이 비동기 함수 호출시 어떤 상태 값을 넘기기로 사전에 약속한 객체라고 이해하면 될듯하다.

즉, 컴파일러가 코루틴 키워드 하나를 만나면 Promise Interface를 통해 아래의 pseudo-code와 같은 전체 코루틴 골격을 만들어 준다. 사용자가 작성한 코루틴 코드 전후로 뭔가를 co_await 하고 있다.

코루틴 함수가 호출되면 필요시 Coroutine Frame을 heap에 allocation 하고 promise_type 객체를 생성하는 등 컴파일러가 해주는 일이 많은데 아래 소스의 링크를 참고하자. 참고로 Coroutine Handle은 Coroutine Frame에 대한 pointer이다. 아래의 로직에서 initial/final suspend() 함수 내에서 코루틴이 중단/재개 될 수 있다고 보면 된다.

// Psuedo-code for Coroutine
// - source: https://lewissbaker.github.io/2018/09/05/understanding-the-promise-type

{
  co_await promise.initial_suspend();  // 사용자 코드 실행 전 뭔가 기다린다.
  try
  {
    <body-statements>                  // 사용자 코드(coro_simple() body) 실행
  }
  catch (...)
  {
    promise.unhandled_exception();     // 예외 처리
  }
  
FinalSuspend:
  co_await promise.final_suspend();    // 사용자 코드 실행 후에도 뭔가 기다린다. 
}

Awaitable Interface

이제 Awaitable Interface도 마저 예를 통해 보자. 3가지 키워드 중 co_await는 overloading이 가능한 단항 연산자(unary operator)이다. 위의 코루틴 pseudo-code에서도 co_await가 뭔가 중요한 일을 하고 있다. Awaitable은 co_await 연산을 적용할 수 있는 c++20 Concept(특정 조건들을 충족하는) type이다. Awaiter type은 Awaitable type의 3가지 Interface 함수를 구현한 Concept type이다. 아래 소스에 3가지 함수가 나타나 있다. 이들은 코루틴이 중단 후 caller에게 돌아갈 지 아니면 코루틴을 재개(resume)할지 제어하기 위한 것이다.

참고로, 아래의 소스는 co_await 연산자 overloading을 통해 시간이 입력값인 경우 AsyncTimer로 동작하도록 하기 위한 것이다. 생각보다 AsyncTimer가 코루틴에서 제대로 동작하도록 만들기 어렵다는 것을 알았다. 그래도 나름 간단하게 사용할 수 있어서 편한 점도 있다. 보통은 코루틴 객체 class 내부에서 co_await 연산자를 오버로딩함으로써 해당 객체로 부터 Awaiter 객체를 얻어내면 되는데 시간은 코루틴 객체가 아니지만 co_await 할 수 있어야 하기 때문에 전역 co_await 연산자를 오버로딩한 것이다.

// Overloaded co_await operator for time duration - AsyncTimer. (e.g. co_await 3s;)
// Do you have a better way for AsyncTimer to be used along with coroutine?
// A thread for timer can be used, but if the coroutine is resumed all the left code resumed
//   before the timer expires - how to suspend again and return to the caller?
template <typename TR, typename TP>
inline auto operator co_await(const std::chrono::duration<TR, TP>& duration) noexcept
{
  struct TAwaiter {
    using TClock = std::chrono::high_resolution_clock;
    using TTime = decltype(TClock::now());
    std::chrono::duration<TR, TP> duration;
    TTime start;
    TAwaiter(const std::chrono::duration<TR, TP>& d) : duration(d), start(TClock::now()) {}
    bool await_ready() noexcept { return duration.count() < 1; } // for 0 or negative time
    auto await_suspend(coroutine_handle<>) noexcept {} // just suspend and return to caller
    auto await_resume() noexcept {                     // sleep for left time when resumed
      if(duration.count() < 1) return;
      auto te = std::chrono::duration_cast<std::chrono::microseconds>(TClock::now() - start);
      std::this_thread::sleep_for(duration - te);
    }
  };
  return TAwaiter{duration};
}

co_await <expr> 구문은 <expr>을 evaluation 한 후, Awaiter 객체를 얻어 아래의 pseudo-code에 보인 Awaitable Interface 로직에 따라 제어 흐름이 동작하도록 한다. 가령, 아래는 promise.initial_suspend()를 실행한 결과 값에 co_await 연산을 적용해서 Awaiter 객체를 얻은 후, 아래의 pusedo-code 로직에 따라 결과 값을 얻는다. 결과 값/type은 await_resume()이 반환하는 값/type이다.

co_await promise.initial_suspend(); 

앞의 SimpleTask class에서 이 함수는 suspend_never 객체를 return하고 있다. 이 놈은 suspend_always와 함께 <coroutine> 헤더에 정의된 가장 기본적인 Awaitable type이다. 아래의 pseudo-code 로직을 적용하면, 

• co_await suspend_never{};   => 코루틴을 중단시키지 않고 즉시 재개
• co_await suspend_always{}; => 코루틴을 중단시키고 caller에게 제어 흐름을 넘김

이라는 뜻이 된다.

마지막 키워드인 co_yield <expr>의 의미는 아래와 똑같다.

co_await promise.yield_value(<expr>);

yield_value(<expr>) 함수는 co_return <expr> 키워드가 사용하는  return_value(<expr>) 또는 return_void() 대신 사용해야 하는 Promise Interface 함수이다.

// Psuedo-code for "co_await <expr>;" statement.
// - source: https://blog.panicsoftware.com/co_awaiting-coroutines

Awaiter&& awaiter = get_awaiter(promise, <expr>);
if (!awaiter.await_ready()) {
  <suspend-coroutine>              // suspend 상태에서만 코루틴 resume() 및 destroy() 가능
  try { // for a <result type> of awaiter.await_suspend(coroutine_handle)
    if constexpr <void type> 
      awaiter.await_suspend(coroutine_handle);
    if constexpr <bool type> {
      bool await_suspend_result = awaiter.await_suspend(coroutine_handle);
      if(!await_suspend_result) goto <resume-point>;
    }
    if constexpr <coroutine_handle type> { // tail-call optimization 적용됨
      another_coro_handle = awaiter.await_suspend(coroutine_handle<promise_type> h);
      another_coro_handle.resume();
    }
    <return-to-caller-or-resumer>  // 여기에 닿지 않고 코루틴이 완료되면 handle이 자동 소멸됨
  } catch (...) {
    std::exception_ptr exception = std::current_exception();
    if(exception) std::rethrow_exception(exception);
  }
}

<resume-point> :
return awaiter.await_resume();     // co_await type을 여기서 결정

위의 로직을 컴파일러가 노래로 알려 주었다.

< 함께 기다려 (co_await something) > - c++20 컴파일러가 인간들에게.

무언가 함께 기다리는 것은              무언가 함께 기다리는 것은
그것을 핑계로                                 가슴이 아파도
잠깐 쉬게 하려는 것.                        홀로 보내야만 하는 것.

준비된 이에게는                              기약없이 떠나지만
선물 주어                                        언젠가는 함께
기꺼이 다시 시작하도록,                  기꺼이 다시 시작하도록,

아니면                                            시련은
잠시 그 자리에 멈춰 세워,                거세지만 내 의지로 맞서,

마음을 비우거나 진실한 이는            어둡고 거친 길에 지치고 외로워도  
사랑하는 이에 돌아 가도록,              잠시나마 쉴 수 있도록,
새 꿈을 가진 이엔                             끝없이 펼쳐진 갈래길을 헤매어도  
희망 찾아 떠나 가도록,                    가다 보면 만날 수 있도록,
거짓된 이도                                     또 다시는
선물 주어 다시 시작하도록.              그 누구도 기다리지 않도록.