2. 유전자 알고리즘

Posted on by

집단지성 프로그래밍 이란 책을 보며 알게된 알고리즘이다. 그냥 여기저기 이야기만 들었지 실질적으로 정체를 파악하고 구현을 해보게 된건 이번이 처음이다.

유전자 알고리즘에 대한 자세한 설명은 엔하위키-유전자 알고리즘(http://ko.wikipedia.org/wiki/%EC%9C%A0%EC%A0%84_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98)에 아주 자세히 잘 나와있다.

그냥 내식대로 간단히 정리하자면 무수히 많은 경우의 수 중 일부의 경우들을 샘플링하여 1세대 데이터군을 만들고 이 데이터들중 최적을 선택하여 교배하고 돌연변이 발생 시켜 더 나은 다음 세대군을 만드는 과정을 여러번 반복하여 최적의 결과를 찾아가는 알고리즘이다. (나 왜이리 글을 못쓰지?)

알고리즘 순서를 대충 요약하면 다음과 같다.

  1. 무수히 많은 경우의 수 중 일부의 경우를 랜덤하게 샘플링하여 하나의 데이터 세트를 구성한다. 이런 한 세트를 세대라고 부른다. 최초 샘플링에 의해서 만들어진 세대를 1세대 라고 한다.
  2. 한 세대가 구성이 되었으면 이중 최적에 가까운 일정 수를 선택한다. 이 선택된 데이터들을 엘리트라고 한다. 엘리트 선택 비율은 딱히 정해져있진 않은거 같다. 난 10% 정도를 엘리트로 선택하기로 했다.
  3. 선택된 엘리트들을 교배(교차)시키거나 돌연변이를 일으켜 이전 세대와 동일한 구성원 수를 갖는 다음 세대를 구성한다.
  4. 새로운 세대로 2~3과정을 여러번 반복한다.
  5. 더 이상 좋은 결과가 나오지 않거나 일정 횟수 이상 반복한 결과를 취한다.

연습삼아 만들어 본 것은 난수로 이루어진 정수들로 부터 0에 근접한 수를 만들어 내는 프로그램이다. 프로그램 돌아가는 과정은 다음과 같다.

  1. 랜덤함수를 이용하여 일정수 이상의 난수를 생성하여 1세대를 구성한다.
  2. 구성된 세대를 오름차순으로 정렬한다. 정렬할때는 절대값을 사용하여 음수도 0보다 큰 수로 정렬되게 한다.
  3. 정렬된 수중에서 0에 가까운 10%의 수를 선택한다.
  4. 버려진 90%의 구성원을 대치할 새로운 구성원을 만든다. 일정한 확률을 정하여 구성원 수가 모두 찰때까지 교차(교배) 혹은 돌연변이를 일으킨다.
    1. 교차(교배) : 선택된 가장 작은 10%수중 랜덤으로 두개를 선택하여 교배(교차)시킨다. 첫번째 수의 앞 16bit, 두번째 수의 뒤 16bit를 취한 값을 합하여 새로운 수를 만든다.
    2. 돌연변이 : 선택된 가장 작은 10% 수중 랜덤을 하나를 선택해서 돌연변이를 일으킨다. 랜덤하게 몇개의 비트를 선택하여 inverse 시킨다.
  5. 2~4를 계속 반복한다.
  6. 최종 결과를 확인한다.

실험 결과는 아래 처럼 나왔다.

  1. 실험 1
    1. 조건 : 세대구성수 100, 세대교체 횟수 100, 엘리트 비율 10%, 돌연변이 발생 확률 10%, 총 시도 횟수 5회
    2. 결과 : -1, 43, 10, 515, -2
  2. 실험 2
    1. 조건 : 세대구성수 1000, 세대교체 횟수 10, 엘리트 비율 10%, 돌연변이 발생 확률 10%, 총 시도 횟수 5회
    2. 결과 : 344, -81, -3588, -1045, 109
  3. 실험 3
    1. 조건 : 세대구성수 10, 세대교체 횟수 1000, 엘리트 비율 10%, 돌연변이 발생 확률 10%, 총 시도 횟수 5회
    2. 결과 : 2, 16, 16, -1, 0
  4. 실험 4
    1. 조건 : 세대구성수 1000, 세대교체 횟수 1000, 엘리트 비율 10%, 돌연변이 발생 확률 10%, 총 시도 횟수 5회
    2. 결과 : 1, 1, 1, 0, 1
  5. 실험 5
    1. 조건 : 세대구성수 10000, 세대교체 횟수 100, 엘리트 비율 10%, 돌연변이 발생 확률 10%, 총 시대 횟수 5회
    2. 결과 : -1, -1, -1, 0, 1
  6. 실험 6
    1. 조건 : 세대구성수 100, 세대교체 횟수 10000, 엘리트 비율 10%, 돌연변이 발생 확률 10%, 총 시대 횟수 5회
    2. 결과 : 1, 0, 1, -1, -1

 

예전에 페북에 끄적거렸던과 달리 실험2와 실험3을 비교해 보면 세대수가 많아도 세대 교체횟수가 적절하지 않으면 그 반대의 경우보다 결과가 좋지 않게 나오는거 같다. 오히려 적은 구성수도 돌연변이가 적절히 발생하면서 세대교체가 많이 이루어지면 자연히 좋은 결과를 내는것 같다. 그리고 실험 4~6을 보면 전체 경우수의 일정 비율 이상을 샘플링 한다면 구성원수와 교체횟수를 극단적으로 치우치게 하지만 않는다면 다 좋은 결과를 도출해 내는것 같다.

실험1 기준으로 32bit 정수 표현의 모든 경우의 수를 비교하는것( O(2^32) )로 반드시 0을 찾을 수 있다.)에 대비하여 100개의 원소를 100번 정렬하는 것( O(100*log(100) * 100) )으로 거의 근사치(2~16)를 구한것을 보면 완벽한 최적값을 요구하는 조건이 아니라면 상당히 유용한 알고리즘인것 같다.

특이한 점은 1과 같이 어느정도 최적치에 근접한 이후부터는 변화가 거의 없다. 아마 세대의 모든 엘리트들의 값이 1로 통일된 상태에서는 교배도 더이상 의미가 없고 돌연변이만을 통해서 0에 도달해야하는데 돌연변이 같은 우연발생으로 최적에 도달하려는 시도는 논리적으로 성공을 보장할 수는 없는 부분이니 운에 맡기는 방법밖에 없기 때문에 그런 것이 아닐까 한다.

결과적으로 유전자 알고리즘은 경우의 수를 모두 따지기 어려운 매우 큰 집단에 대해서 일정 수준의 최적치를 얻기에는 좋은 방법인것 같다. 다만, 완벽한 최적값을 기대한다면 실망할 여지가 크다.

아래는 토비 세가란의 집단지성프로그래밍 책을 참고하여 만든 코드다. net.abh0518.genetic 패키지가 유전자 알고리즘 구현 부분이다.
https://github.com/abh0518/ProgrammingCollectiveIntelligence

3766 Total Views 1 Views Today

Leave a Reply