유전 알고리즘 파이썬 구현 - yujeon algolijeum paisseon guhyeon

인공지능 수업에서 유전자 알고리즘에 대한 과제를 하게 되었다.

다윈의 진화론에 의하면, 지구가 처음 생성되고 지금까지 환경에 적응한 생물만이 살아남고, 또한 진화했다. 유전 알고리즘은 생물체가 환경에 적응하며 진화하는 모습을 모방하여, 최적해를 찾아내는 검색 방법이다. GA는 수학적으로 명확하게 이해 혹은 풀기 힘든 문제에도 적용이 가능하기 때문에, 이 경우 매우 유용하게 사용된다.
염색체(Chromosome) 는 생물학적으로 유전자들이 뭉쳐져 포장된 것이다. GA에서의 염색체는 하나의 개체 값을 의미한다.
유전자(gene) 는 생물학적으로나 GA적으로나 염색체의 요소로, 유전 정보를 나타낸다.
자손(offspring, child) 는 부모(Parent) 유전자로부터 생성된 자식 유전자이며, 이전 세대와 비슷한 (완전히 동일하지는 않은) 유전 정보를 갖게 된다.
적합도(fitness) 어떤 염색체가 최적해에 얼마나 가까운지 나타내는 고유 값으로, 적합도의 값으로 염색체의 개체선별을 하게 된다.

어떤 문제에 유전 알고리즘을 적용하기 위해서는 그 문제에 대해 아래와 같이 5개의 연산을 정의해야 한다.

보통 1번 연산 후, 2~5번 연산을 반복하는 식으로 진행된다. 각 연산에 대한 설명은 실습과 함께 진행하겠다.

저번 다층 퍼셉트론 실습에서, C/C++ 로 제로코드부터 시작하여 코딩하였었는데, 그 당시의 고통이 너무 커서… 이번엔 비교적 간단한 예제를 파이썬으로 실습을 진행할 계획이다.
해결할 문제는 숫자야구 게임이다. 숫자야구 게임 규칙은 다음과 같다.

실습에서는 N은 6, 즉 임의의 6자리 숫자를 가지고 실험하였으며, 염색체를 10개를 두고 실험하였다.
fitness 함수는 스트라이크를 5점, 볼을 1점으로 환산하여 적합도를 계산하였다. 선택 방식은 룰렛방식으로, 각 염색체 중 적합도가 가장 높은 염색체를 선택하여 유전자를 교환하였다.

1
2
3
4
5
6
7
8
9
10

def _generate_parent(length, geneSet, get_fitness):
chromosome_list = []
for i in range(0, 10):
    genes = []
    while len(genes) < length:
        sampleSize = min(length - len(genes), len(geneSet))
        genes.extend(random.sample(geneSet, sampleSize))
    fitness = get_fitness(genes)
    chromosome_list.append(Chromosome(genes, fitness))
return chromosome_list

1
2
3
4
5
6
7
8
9

 def get_fitness(guess, target):
fitness = 0
for expected, actual in zip(target, guess):
    if expected == actual:
        fitness += 5
    elif actual in target:
        fitness += 1

return fitness

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

 def _generate_child(parent_list, geneSet, get_fitness):
child_list = []
fitness_percent_list = []
fitness_accum_list = []
fitness_sum = 0
for parent in parent_list:
    fitness_sum += parent.Fitness

for parent in parent_list:
    fitness_percent_list.append(parent.Fitness / fitness_sum)

fitness_sum = 0
for fitness_percent in fitness_percent_list:
    fitness_sum += fitness_percent
    fitness_accum_list.append(fitness_sum)

# Selection
for i in range(0, 10):
    rand = random.random()
    before = 0
    for j in range(0, len(fitness_accum_list)):
        if rand > before and rand <= fitness_accum_list[j]:
            child_list.append(copy.deepcopy(parent_list[j]))
            break
        before = fitness_accum_list[j]

# --- 생략 ---

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

 def _generate_child(parent_list, geneSet, get_fitness):
# --- 생략 ---

# Crossover
crossover_rate = 0.20
selected = None
for i in range(0, len(child_list)):
    rand = random.random()
    if rand < crossover_rate:
        if selected is None:
            selected = i
        else:
            child_list[selected].Genes[2:], child_list[i].Genes[2:] = \
                child_list[i].Genes[2:], child_list[selected].Genes[2:]
            selected = None

    # update
    child_list[i].Fitness = get_fitness(child_list[i].Genes)

# --- 생략 ---

1
2
3
4
5
6
7
8
9
10
11
12

 def _generate_child(parent_list, geneSet, get_fitness):
# --- 생략 ---

# mutate
mutate_rate = 0.2
for i in range(0, len(child_list)):
    rand = random.random()
    if rand < mutate_rate:
        child = _mutate(child_list[i], geneSet, get_fitness)
        del child_list[i]
        child_list.append(child)
return child_list

결과는 다음과 같다.

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

 target : 841532
820653	1/3	8	0:00:00.000997
491670	1/1	6	0:00:00.000997
763810	0/3	3	0:00:00.000997
642183	1/4	9	0:00:00.000997
702563	1/2	7	0:00:00.000997
721048	1/3	8	0:00:00.000997
978064	0/2	2	0:00:00.000997
543081	1/4	9	0:00:00.000997
841530	5/0	25	0:00:00.000997
493157	0/4	4	0:00:00.000997
average fitness : 8.1
new maximum fitness : 9.1
new maximum fitness : 13.6
new maximum fitness : 17.2
...중략...
new maximum fitness : 29.2
new maximum fitness : 29.6
new maximum fitness : 30.0
841532	6/0	30	0:00:00.038933
841532	6/0	30	0:00:00.038933
841532	6/0	30	0:00:00.038933
841532	6/0	30	0:00:00.038933
841532	6/0	30	0:00:00.038933
841532	6/0	30	0:00:00.038933
841532	6/0	30	0:00:00.038933
841532	6/0	30	0:00:00.038933
841532	6/0	30	0:00:00.038933
841532	6/0	30	0:00:00.038933
average fitness : 30.0

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

 target : 495367
450791	1/3	8	0:00:00
315478	1/3	8	0:00:00
068147	1/2	7	0:00:00
598437	2/3	13	0:00:00
385704	1/3	8	0:00:00
623759	0/5	5	0:00:00
253147	1/3	8	0:00:00
548967	2/3	13	0:00:00
067142	0/3	3	0:00:00
431768	2/2	12	0:00:00
average fitness : 8.5
new maximum fitness : 9.5
new maximum fitness : 11.0
...중략...
new maximum fitness : 29.1
new maximum fitness : 30.0
495367	6/0	30	0:00:00.025973
495367	6/0	30	0:00:00.025973
495367	6/0	30	0:00:00.025973
495367	6/0	30	0:00:00.025973
495367	6/0	30	0:00:00.025973
495367	6/0	30	0:00:00.025973
495367	6/0	30	0:00:00.025973
495367	6/0	30	0:00:00.025973
495367	6/0	30	0:00:00.025973
495367	6/0	30	0:00:00.025973
average fitness : 30.0

위와 같이 원하는 결과가 잘 나오는 것을 확인할 수 있었다.

저번 다층 퍼셉트론 구현할 때 사실 엄청난 좌절감을 느꼈었다. 이번에도 혹시나 실패하여 좌절감이 더해지지는 않을 까 걱정 했었는데, 다행히도 난이도가 그렇게 어렵지 않은 실습이었고, 오픈소스를 참고할 수가 있어 오히려 자신감이 붙은 느낌이다. 이 교육용 오픈소스가 보기 쉽게 되어있어서, 유전자 알고리즘을 이해하는 데 많은 도움이 되었다. 하지만 Crossover 없이 Mutate로만 구현되어 있었고, 염색체도 하나밖에 쓰지 않아서, 해당 부분은 내가 직접 구현했다. 덕분에 유전자 알고리즘을 한층 더 이해하기 수월했던 것 같다.

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192

import datetime
import random
import unittest
import copy

def _generate_parent(length, geneSet, get_fitness):
    chromosome_list = []
    for i in range(0, 10):
        genes = []
        while len(genes) < length:
            sampleSize = min(length - len(genes), len(geneSet))
            genes.extend(random.sample(geneSet, sampleSize))
        fitness = get_fitness(genes)
        chromosome_list.append(Chromosome(genes, fitness))
    return chromosome_list

def _mutate(parent, geneSet, get_fitness):
    childGenes = parent.Genes[:]
    index = random.randrange(0, len(parent.Genes))
    newGene, alternate = random.sample(geneSet, 2)
    childGenes[index] = alternate if newGene == childGenes[index] else newGene
    fitness = get_fitness(childGenes)
    return Chromosome(childGenes, fitness)

def _generate_child(parent_list, geneSet, get_fitness):
    child_list = []
    fitness_percent_list = []
    fitness_accum_list = []
    fitness_sum = 0
    for parent in parent_list:
        fitness_sum += parent.Fitness

    for parent in parent_list:
        fitness_percent_list.append(parent.Fitness / fitness_sum)

    fitness_sum = 0
    for fitness_percent in fitness_percent_list:
        fitness_sum += fitness_percent
        fitness_accum_list.append(fitness_sum)

    # Selection
    for i in range(0, 10):
        rand = random.random()
        before = 0
        for j in range(0, len(fitness_accum_list)):
            if rand > before and rand <= fitness_accum_list[j]:
                child_list.append(copy.deepcopy(parent_list[j]))
                break
            before = fitness_accum_list[j]

    # Crossover
    crossover_rate = 0.20
    selected = None
    for i in range(0, len(child_list)):
        rand = random.random()
        if rand < crossover_rate:
            if selected is None:
                selected = i
            else:
                child_list[selected].Genes[2:], child_list[i].Genes[2:] = \
                    child_list[i].Genes[2:], child_list[selected].Genes[2:]
                selected = None

        # update
        child_list[i].Fitness = get_fitness(child_list[i].Genes)

    # mutate
    mutate_rate = 0.2
    for i in range(0, len(child_list)):
        rand = random.random()
        if rand < mutate_rate:
            child = _mutate(child_list[i], geneSet, get_fitness)
            del child_list[i]
            child_list.append(child)
    return child_list


def get_best(get_fitness, targetLen, optimalFitness, geneSet, display):
    random.seed()

    # 1. Generate Parent
    bestParentList = _generate_parent(targetLen, geneSet, get_fitness)
    display(bestParentList)

    gen_count = 0
    maximum_average = 0
    while True:
        gen_count += 1
        #print("generation : {}".format(gen_count))
        child_list = _generate_child(bestParentList, geneSet, get_fitness)

        fitness_sum = 0
        for child in child_list:
            fitness_sum += child.Fitness

        average = fitness_sum / 10
        if average > maximum_average:
            print("new maximum fitness : {}".format(average))
            bestParentList = child_list
            maximum_average = average

        if average >= optimalFitness:
            return child_list

class Chromosome:
    def __init__(self, genes, fitness):
        self.Genes = genes
        self.Fitness = fitness

def get_fitness(guess, target):
    fitness = 0
    for expected, actual in zip(target, guess):
        if expected == actual:
            fitness += 5
        elif actual in target:
            fitness += 1

    return fitness

def display(candidate, target, startTime):
    timeDiff = datetime.datetime.now() - startTime
    strike = 0
    ball = 0
    for expected, actual in zip(target, candidate.Genes):
        if expected == actual:
            strike += 1
        elif actual in target:
            ball += 1

    if strike == 0 and ball == 0:
        result = "out"
    else:
        result = "{}/{}".format(strike, ball)

    print("{}\t{}\t{}\t{}".format(
        ''.join(candidate.Genes),
        result,
        candidate.Fitness,
        timeDiff))

def display_list(candidate_list, target, startTime):
    fitness_sum = 0
    for candidate in candidate_list:
        display(candidate, target, startTime)
        fitness_sum += candidate.Fitness
    print("average fitness : {}".format(fitness_sum / len(candidate_list)))

def pick_baseball_num(length, is_duplicate_allowed):
    if is_duplicate_allowed is True or length > 10:
        return ''.join(random.choice("0123456789")
                       for _ in range(length))

    baseball_list = []
    num = random.randrange(0, 10)

    for i in range(length):
        while str(num) in baseball_list:
            num = random.randrange(0, 10)
        baseball_list.append(str(num))

    return ''.join(baseball_list)


class BaseballGames(unittest.TestCase):
    geneset = "0123456789"

    def test_Baseball(self):
        length = 6

        target = pick_baseball_num(length, False)
        print("target : {}".format(target))
        self.guess_baseball(target)

    def guess_baseball(self, target):
        startTime = datetime.datetime.now()

        def fnGetFitness(genes):
            return get_fitness(genes, target)

        def fnDisplay(candidate_list):
            display_list(candidate_list, target, startTime)

        optimalFitness = len(target) * 5
        child_list = get_best(fnGetFitness, len(target), optimalFitness,
                                self.geneset, fnDisplay)

        fnDisplay(child_list)


if __name__ == '__main__':
    unittest.main()

주관적인 생각이 많이 들어간 포스트입니다. 지적은 언제나 환영입니다!