유전알고리즘 ( Evolution Algorithms )

유전알고리즘.
내가 소속한 연구실에서 유전알고리즘을 학습하면서
정리도 할 겸 유전알고리즘에 대해서 포스팅하게 되었다.

보통 알고리즘이라하면, 주어진 문제를 제한된 자원하에 풀 수 있는 일련의 절차"를 생각하기 쉽지만,
유전알고리즘은 지금까지와의 알고리즘과는 살짝 성격을 달리하는 알고리즘이다.

유전알고리즘은 그 이름에서도 알 수 있듯이 주어진문제에 대한 '답'을 진화시켜서 찾아낸다.
그래서 항상 최적해를 찾는다는 보장은 없지만, 준최적해를 구하는 뛰어난 알고리즘이다.
일반적으로 유전알고리즘이 다루는 문제는 일반 알고리즘으로 풀 수 있는 그런 문제를 대상으로 하지 않는다.
예를들어 정렬이라던가, 다익스트라알고리즘, 선형계획알고리즘 등 다항시간내에 풀 수 있는 문제는 유전알고리즘의 대상이 아니다.
유전알고리즘은 주로 다항시간내에 풀기 곤란한 문제라던가, 답이 존재하는지 존재하지 않는지 모르는 문제에 적용된다.

예를들면, 다목적순회판매원문제를 생각해볼수가 있겠다.
다목적순회판매원문제는 유명한 NP완전문제이다.
다항시간내에 풀기가 매우 곤란한 문제이다.
이런 문제에 유전알고리즘을 적용시켜서 준최적해를 구하기는 '비교적간단'하다.

구체적으로 유전알고리즘을 알아보기전에, 유전알고리즘의 특징에 대해서 좀 살펴보자.
유전알고리즘은 뛰어난 유전자를 가진 개체가 다음 세대에도 살아남는다는 아이디어를 이용한다.
그렇다. 다윈의 '진화론'과 매우 비슷하다.
매우 많은 세대교체가 이루어지고 난 다음의 개체들중 가장 뛰어난 개체을 답으로 제시하는 방법, 그것이 유전알고리즘의 개요이다.

유전알고리즘에서 파생된 여러 알고리즘중 진화알고리즘은 유전알고리즘의 성질을 가장 솔직하게 적용시키는 알고리즘 중 하나이다.
물론, 진화알고리즘(Genetic Algorithms)에도 여러 갈래가 있지만 그 중에서 가장 간단한 Simple Genetic Algorithms 을 살펴보자.
문제마다 파라미터를 변경시켜서 가장 성능을 좋게 만드는 작업이 필요하다는 것이 여느 알고리즘과는 달라서 생소할것이다.
이른바, Do And Fix 를 다소 필요로한다.

문제를 설정해 보자. 
실수함수 f(x, y) 가 주어졌다고 할 때, 이 실수함수의 최소값이 존재하는지, 존재하면 그 값은 얼마인지를 찾는다.
어떻게 풀것인가? 잠시 생각해보길바란다.

이 문제에 유전알고리즘을 적용시켜서 준최적해를 찾아보도록하자 ( 찾은해가 최적해이지 않을 수 있다는것을 전제로 한다. )


1. 개체수는 3000 개 정도로 설정해보자.  ( 이 값을 높게 설정할수록 성능은 좋아진다. ==  해의 정밀도가 높아진다 )
2. 1세대부터 1000 세대까지 진화시켜보자. ( 이 값을 높게 설정할수록 성능은 좋아진다. ==  해의 정밀도가 높아진다 )
3. 하나의 개체가 가지는 유전자를 설정하자.
   >> 이 문제같은 경우, 유전자를 double gene[2] ( x, y 값 ) 로 설정한다. 즉, gene[0] 이 x 값, gene[1] 이 y 값이 되는것이다.
4. (중요) 하나의 개체가 문제에 대해서 얼마나 적합한지를 판단하는 적응도함수를 설정하자.
   >> y=x^2 과 같은 함수라면, 문제를 풀기전에 이미 최대값은 없고, 최소값은 0 이라는 사실을 알기에 0 에 가까울수록 높은 적응도를 주는 함수로 설정하면 된다. 하지만, 최소값의 존재여부를 모르기에 이 함수를 어떻게 작성하는가에 따라서 준최적해의 정밀도가 달라진다. 이 적응도 함수의 작성법에는 여러가지가 있겠지만, 여기서는 충분히작은수를 미리 정의하여놓고 이값에 얼마나 가까운지에 따라서 적응도를 리턴하는 함수를 작성한다. 예를들어 -10000000 에 가까울수록 높은 적응도를 리턴한다고 하자.
===============================================================================================================
5. 첫 세대는 랜덤하게 생성한다.
6. n 번째 세대의 모든 개체에 대하여 적응도 함수를 적용시켜 적응도를 구한 후, 적응도에 대해여 내림차순으로 정렬한다.
7. 엘리트(적응도가 높은 개체)들은 다음세대에 그대로 남긴다.
8. 엘리트 개체들을 부모로 하여 자식을 생성한다.
   >> 엘리트개체에서 랜덤하게 2개의 개체를 선택하여 유전자를 랜덤하게 섞어서 자식을 생성한다. 쌍방교환이 아니라 유전자를 섞는것임에 주의.
9. 엘리트가 아닌 개체들에 대해서 돌연변이를 일으킨다.
  >> 엘리트가 아닌 개체들중 낮은 확률로 개체의 유전자를 재할당한다.
10. n+1 세대로 세대를 교체한다.
  >> 6번으로 돌아간다. 루프를 돌며 세대를 교체한다.


이것이 가장간단한 진화알고리즘이다.
코드를 작성하는것도 매우 간단하다. 직접 아무 함수를 정의하여서 적용시켜보길바란다.
연속함수에대해서 매우 높은 정밀도로 준최적해를 구할 수 있음이 알려져있지만,
불연속함수에대해서는 조금 더 개선된 진화알고리즘을 쓴다.