파이썬(Python) - 유전 알고리즘

파이썬(Python) - 유전 알고리즘

Author : Jino Bae / Send Mail

이 블로그에서 이론을 참고했다. 책에 나와있는 것과 유사한 내용인데 좀 더 정리가 잘 된 내용인 것 같다. 간단하게 정리하면 이렇다.

용어

  • 염색체 : 유전 정보를 담은 문자열
  • 유전자 : 문자열의 유전 정보
  • 교차 : 두 개의 염색체를 조합
  • 돌연변이 : 확률적으로 유전자의 정보가 바뀜
  • 자손 : 교차와 돌연변이로 생성된 염색체

알고리즘

  1. 최초 염색체 생성
  2. 세대 적합도 평가
  3. 세대 교차 및 돌연변이
  4. 다음 세대 적합도 평가
    • 목표 적합도 미달성(2번으로)
    • 목표 적합도 달성(종료)

단, 어려운 문제는 목표치를 선정하기 어려우므로 반복횟수를 제한하는게 일반적

일단 유전 알고리즘의 이론은 알겠는데 솔직히 이걸 어떻게 적용해야할까 싶은 생각이 든다. 그래서 일단 할 수 있는 일부터 해보기로 했다. 최초 목표는 0-9까지의 유전자가 존재하는 염색체에서 단지 1 유전자만을 가진 염색체를 생성하는 것을 목표로 하였다.

알고리즘 기록

최초 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import random
import numpy

chromo = [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0]]
new_chromo = [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0]]

# 각 염색체의 적합도 평가
evalution = [0,0,0,0,0]
# 우성 유전자
dominant = 1
# 선택된 우성 염색체
select = [0,0] 
# 세대
gene = 0

# 최초의 세대 생성
for i in range(5) :
    for j in range(10) :
        chromo[i][j] = random.randint(0,9)

print(gene,"Gen : ",chromo)
gene+=1

# 완전체가 나올때까지 반복
while(1) :
    # 적합도 평가
    for i in range(5) :
        m_sum = 0
        for j in range(10) :
            if chromo[i][j] > dominant :
                m_sum += chromo[i][j] - dominant
            else :
                m_sum += dominant - chromo[i][j]
        evalution[i] = m_sum

    # 목표 적합도가 있으면 종료
    for i in range(5) :
        if evalution[i] == 0 :
            break

    # 우성 염색체 2쌍 선택
    for i in range(2) :
        select[i] = numpy.argsort(evalution)[i]

    # 염색체 교차
    for i in range(5) :
        for j in range(10) :
            new_chromo[i][j] = chromo[select[random.randint(0,1)]][j]

    chromo = new_chromo
    print(gene,"Gen : ",chromo)
    gene+=1

    # 1000세대 넘으면 종료
    if gene > 1000 :
        break

먼저 위처럼 작성했더니 초기에는 정상적으로 동작했다. 하지만 5세대가 지나면 비슷한 염색체끼리 합쳐져 나중에는 똑같은 염색체만 남아 계속해서 똑같은 염색체만 만들어진다. 지역최적화라는 용어가 떠올랐는데 내가 한가지 간과하고 있던건 돌연변이에 대한 설정이다.

1
2
3
4
5
6
7
8
9
mutation = 0.01 
...
    for i in range(5) :
        for j in range(10) :
            if random.random() < mutation :
                new_chromo[i][j] = random.randint(0,9)
            else :
                new_chromo[i][j] = chromo[select[random.randint(0,1)]][j]
...

돌연변이를 추가했다. 0.01로 설정하니 아까처럼 비슷한 염색체가 남았을때 좀 더 괜찮은 염색체가 생성되면 그 염색체처럼 변화했다. 좀 더 급격하게 변할 수 있도록 0.1로 설정했더니 염색체가 너무 과도하게 변하여 결국 랜덤으로 숫자가 생성되는 수준이었다.

단, 여기서 확률은 실제 알고리즘에서 사용되는 확률과 상이할 수 있다.

1
2
3
4
(0, 'Gen : ', [[7, 1, 3, 0, 7, 9, 1, 8, 8, 1], [1, 4, 8, 4, 5, 9, 0, 4, 6, 0], [7, 7, 7, 5, 5, 7, 3, 2, 7, 2], [7, 1, 2, 1, 9, 4, 9, 8, 4, 9], [3, 1, 3, 5, 4, 9, 7, 0, 3, 5, 0]])
(1, 'Gen : ', [[1, 4, 8, 4, 4, 9, 0, 0, 3, 0], [1, 4, 3, 4, 5, 9, 7, 0, 6, 0], [3, 4, 8, 4, 4, 9, 0, 4, 3, 5], [1, 1, 3, 4, 4, 9, 7, 4, 6, 0], [1, 1, 3, 4, 5, 9, 0, 4, 3, 5]])
(100, 'Gen : ', [[0, 2, 1, 1, 1, 0, 2, 2, 2, 2], [0, 2, 1, 1, 1, 0, 2, 2, 2, 2], [0, 2, 1, 1, 1, 0, 2, 2, 2, 2], [0, 2, 1, 1, 1, 0, 2, 2, 2, 2], [0, 2, 1, 1, 1, 0, 2, 2, 2, 2]])
(1000, 'Gen : ', [[1, 0, 1, 1, 2, 1, 1, 2, 1, 1], [7, 0, 1, 1, 2, 1, 1, 2, 1, 1], [7, 0, 1, 1, 2, 1, 1, 2, 1, 1], [7, 0, 1, 1, 2, 1, 1, 2, 1, 1], [7, 0, 1, 1, 2, 1, 1, 2, 1, 1]])

1에는 근접하고 있지만 절대 1만 나오는 경우가 없다. 갑자기 이상하게 적합도가 깡충 올라가기도하고… 10000세대까지 돌리면 어떻게든 나올 것 같지만 그건 결국 랜덤으로 때려맞추는 수준이다. 뭐가 문제일까…


알고리즘엔 문제가 없었으나 가장 큰 문제가 되었던건 파이썬 대한 이해 부족이다. 파이썬에는 메모리를 참조하여 같은 값을 가지는 얇은 복사와 다른 메모리를 참조하는 깊은 복사가 있는데, 나는 얇은 복사를 사용하여 변이가 일어났을 경우 그게 다음 세대에게 큰 영향을 주고 있었다.

따라서 copy 라이브러리를 이용하여 염색체 복사를 깊은 복사로 변경하였더니 성공적으로 동작하였다.

최종 소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import random
import numpy
import copy

chromo = [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0,0]]
new_chromo = [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0]]

# 각 염색체의 적합도 평가
evalution = [0,0,0,0,0]
# 우성 유전자
dominant = 1
# 돌연변이가 나타날 확률
mutation = 0.01
# 선택된 우성 염색체
select = [0,0] 
# 세대
gene = 0

# 최초 새대 생성
for i in range(5) :
    for j in range(10) :
        chromo[i][j] = random.randint(0,9)

print(gene,"Gen : ",chromo)
gene+=1

# 완전체가 나올때까지 반복
while(1) :
    # 적합도 평가
    for i in range(5) :
        m_sum = 0
        for j in range(10) :
            if chromo[i][j] > dominant :
                m_sum += chromo[i][j] - dominant
            else :
                m_sum += dominant - chromo[i][j]
        evalution[i] = m_sum

    # 목표 적합도가 있으면 종료
    done = False
    for i in range(5) :
        if evalution[i] == 0 :
            done = True
            break
    if done == True :
        break
    
    # 적합도 출력
    print evalution

    # 우성 염색체 2쌍 선택
    for i in range(2) :
        select[i] = numpy.argsort(evalution)[i]

    # 우성 염색체 출력
    print select

    # 염색체 교차 및 돌연변이
    for i in range(5) :
        for j in range(10) :
            # 돌연변이 발생
            if random.random() < mutation :
                new_chromo[i][j] = random.randint(0,9)
            else :
                new_chromo[i][j] = chromo[select[random.randint(0,1)]][j]

    # 리스트 깊은 복사
    chromo = copy.deepcopy(new_chromo)
    print(gene,"Gen : ",chromo)
    gene+=1

    if gene > 1000 :
        break
    
print("Done!!!")
1
2
(750, 'Gen : ', [[1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 2, 2], [1, 1, 1, 1, 1, 1, 1, 1, 1, 2]])
Done!!!

750세대에서 목표한 염색체가 생성되었다. 변이율을 0.05로 증가시켰더니 좀 더 빠르게 완전체(?)가 등장하는 듯 하다. 소스코드 원문


Jino Bae
WRITTEN BY

Jino Bae

Digital is a purely man-made playground. That's why I like.
im@baejino.com


comments powered by Disqus