유전 알고리즘 가지고 놀기

예제 링크: https://github.com/Kcrong/Simple-Genetic-Algorithm

유전 알고리즘이란,

"유전 알고리즘(Genetic Algorithm)은 자연세계의 진화과정에 기초한 계산 모델로서 존 홀랜드(John Holland)에 의해서 1975년에 개발된 전역 최적화 기법으로, 최적화 문제를 해결하는 기법의 하나이다. 생물의 진화를 모방한 진화 연산의 대표적인 기법으로, 실제 진화의 과정에서 많은 부분을 차용하였으며, 변이(돌연변이), 교배 연산 등이 존재한다. 또한 세대, 인구 등의 용어도 문제 풀이 과정에서 사용된다." - 위키피디아

유전 알고리즘은 부모의 유전 정보들이 자식들에게 골고루 분포 됨으로써, 문제에 대한 해를 찾아가는 알고리즘이다.

자식 해는 부모 해와 비슷한 형질을 가지며, 우월한 유전자들은 다시 자식해를 만들며 우수 유전자를 널리 퍼트리는 특징이 있다.

소스 설명 전, 사용할 용어에 대한 설명은 아래와 같다.

1. 유전자

예시 소스에서는 integer list 로 정의했다. 하지만 그 형태와 값의 크기는 무엇이든지 될 수 있으며, 제한이 없다. (구현이 어려울 뿐..)

2. 세대

유전자들의 생성과 소멸을 아우르는 하나의 주기를 말한다.

보통 생성 -> 번식 -> 소멸 의 주기를 가진다.

3. 적합도 (Fitness)

유전자가 얼마나 우월한지 보여주는 지수.

이 지수가 높을 수록 우월한 유전자임을 뜻한다.

전체적인 알고리즘은 3가지로 이루어져있다.

1. 부모 유전자 선택

2. 번식 

3. 돌연변이

부모 유전자 선택

부모 유전자를 선택하는 부분에서는, 룰렛 휠 선택 방식을 이용했다.

# 부모를 select_list를 이용해 정함.
# 부모로 선출될 확률은 fitness 과 비례한다.
parents = tuple(self.select_list[rand(0, len(self.select_list))] for i in range(2))

룰렛 휠 방식

이미지 출처: http://blog.secmem.org/category/IT%20%EB%86%80%EC%9D%B4%ED%84%B0/Elite%20Member%20Tech%20%26%20Talk?page=37

룰렛 휠 방식이란, 적합도가 높을 수록 부모 해로 선택될 확률이 높아지도록 하는 방식이다.

위 그림처럼, 적합도가 100인 C는 룰렛에서 보듯이 선택될 확률이 높다. 하지만 적합도가 40인 D는 C와 달리 선택될 확률이 적다.

이처럼 우월한 유전자를 가질 수록 부모 해로 선택될 확률을 높이는 것을 룰렛 휠 방식이라고 한다.

번식 (교차)

자식 유전자를 만들 때는, 2점 교차 라는 방식을 이용했다.

# 각 교차 포인트를 정한다.
# rand 함수의 반환이 float 형이므로, 소수점을 버리기 위해 int() 형변한을 해준다.
switch_point = (rand(1, gene_len // 2), rand(gene_len // 2, gene_len))
 
# 처음 자식이 받는 유전자는 parent1
# 다만 교차 포인트에 다다르면, 다른 parent 유전자 정보를 받아오기 시작한다. (parent = parent2)
parent = parents[0]
 
for i in range(gene_len):
    # 자식 유전자 정보는 부모 유전자에서 받아온다
    gene_data.append(parent.gene_data[i])
 
    if i in switch_point:
        # 유전자를 받아오는 부모 변경
        try:
            parent = parents[parents.index(parent) + 1]
        except IndexError:
            parent = parents[0]
 
        """
        a = parents.index(parent) --> 현재 부모의 index 값
        parents[a+1] --> 부모 리스트에서, 현재 부모 인덱스값보다 +1 된 값 가져옴
        IndexError --> 만약 1이 넘어가면
        parent = parents[0] 다시 0으로 돌아옴
        """

2점 교차는 두 점을 임의로 선택하여, 그 점을 기준으로 각 부모 유전자에서 번갈아 유전자를 받아오는 방법이다.

물론 점의 위치에 따라 부모1과 부모2의 유전 정보 비율은 달라질 수 있지만 교차의 경우 섞이는 복잡도를 정하는 단계이므로 신경쓰지 않는다.

--> Mutation (돌연변이) 

# 돌연변이 확률은 fitness 와 반비례 한다.
# fitness 가 높을 수록, 돌연변이 확률이 적어진다.
if rand(0, self.fitness * 100) == 0:
    return DNA([rand(min(WE_WANT), max(WE_WANT)) for i in range(len(WE_WANT))])

돌연변이 확률은 적합도와 반비례 하도록 구현했으며, 돌연변이는 기존 부모와 상관없는 전혀 새로운 유전자를 갖는다.

돌연변이는 그 확률 설정에 따라 다른 결과가 나온다. 자세한 내용은 아래 결과 분석에서 살펴보자.

결과분석

우선 목표값을
0 과 1로 이루어진 8자리 list 로 잡았다.

결과는 다음 이미지와 같다. X축이 세대, Y축이 적합도 수치를 나타낸다.

[그림1] 목표 값 [0,1,0,1,0,1,0,1]

목표 값이 단순한 관계로 얼마 지나지 않아 40번째 세대 쯤에서 최대 적합도에 수렴하는 것을 볼 수 있다.

목표 값을 조금 복잡하게 해보자.

0~9의 값을 가지도록 조정해봤다.

[그림2] 목표 값 [3,1,2,9,7,4,3,6]

조금 더 흥미로운 결과가 나왔다.

목표 값의 범위를 늘리자 최대 적합도에 도달하는 세대가 늘어난 것이다.

위 1차 결과와는 달리 80 ~ 100 번째 세대에서 최대 적합도에 가까이 수렴하는 결과가 나왔다.

조금 더 복잡하게 해보자. 이번엔 목표 값의 길이를 바꿔볼 것이다.

[그림3-1] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9]

100 세대로는 최대 적합도에 도달하기에 한참 부족한 듯 싶다. 진화 횟수를 조금 늘려보았다.

[그림3-2] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가

비록 최대 적합도에는 도달하지 못했지만, 근사한 값을 얻었다.

그럼 보다 더 최대 적합도에 가까운 값을 얻기 위해서는 어떻게 해보는 것이 좋을까?

돌연변이의 확률을 늘리고, 세대에서 가장 좋은 유전자 (Fitness 수치가 가장 높은) 1개를 다음 세대에도 보존 시켜보았다.

[그림3-3] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 _돌연변이 확률 증가, 우월 유전자 보존

최대 적합도에 도달하는데 성공했다!!!

하지만 필요 세대가 너무 많다는 문제점이 있다...

또한 돌연변이 확률을 늘렸더니 중간중간 생기는 뾰족한 부분 (내려오는 부분)이 늘어났다.

위 문제^[각주:1]를 조금 개선시켜보자.

우월한 유전자를 자식 세대에 포함시키는 과정에서, 1개가 아닌 5개를 포함시켜보았다.

[그림3-4] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 _돌연변이 확률 증가, 우월 유전자 보존 _보존 유전자 갯수 증가

약 1100 - 850 = 250 세대가 감소했다!!~!

우월 유전자의 보존 비율 조금 더 늘려보자.

이번엔 5개 대신 10개를 포함시켜 보았다.

더욱 개선된 결과가 나오리라 생각했다.

[그림3-5] 목표 값 [3,1,2,9,7,4,3,6,5,2,6,9] _진화 횟수 증가 _돌연변이 확률 증가, 우월 유전자 보존 _보존 유전자 갯수 증가 _ 10개 보존

예상과는 달리, 이전 결과 보다 더욱 못한 결과가 나왔다.

이유를 살펴보았더니, 우월 유전자의 보존 비율이 증가하면 우월 유전자에 가까운 자식 유전자들이 많이 생기지만,

우월 유전자의 잘못된 부분도 같이 유지되는 문제가 있었다.

우월 유전자의 보존 비율이 높다고 진화의 방향이 좋은 것은 아니라는 것이다.

이번 실험 결과 중, 우리의 실생활과 매우 흡사한 부분이 아닐까 싶다. :)

P.s 

질문이나 기타 문제점은 GitHub 이슈로 달아주세요

풀리퀘 받는 것도 좋아합니다.

1. 필요 세대가 너무 많다는 문제점 [본문으로]