2020/12/20

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

 

뜬금없이 먼가 떠올랐을때 해봐야 직성이 풀리는 못된 버릇이 있다. 세살 버릇 여든 간다. 오늘은 코로나 뉴스를 보다가, 소시적 원서를 질러 독학했던 유전 알고리즘(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분 내에 답을 찾을 것이다.


댓글 없음:

댓글 쓰기