인공지능 수업에서 유전자 알고리즘에 대한 과제를 하게 되었다.
다윈의 진화론에 의하면, 지구가 처음 생성되고 지금까지 환경에 적응한 생물만이 살아남고, 또한 진화했다. 유전 알고리즘은 생물체가 환경에 적응하며 진화하는 모습을 모방하여, 최적해를 찾아내는 검색 방법이다. 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 |
정답과 같은 길이의 염색체를 10개정도 생성하여, 리스트에 저장한다. 이때 유전자의 배열은 0부터 9까지 사이 숫자의 랜덤 값이다.
| 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 |
숫자와 그 위치까지 동일하다면 스트라이크이므로 5점, 만약 위치는 같지 않고 숫자만 같다면 볼이므로 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 | 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) # --- 생략 --- |
선택한 염색체 중 랜덤으로 선택하여 유전자를 교배 시킨다. Single Point Crossover 방식으로, 유전자, 즉 숫자의 일부를 두 유전자끼리 교환시킨다. Crossover Point는 임의로 지정하였다.
| 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() |
주관적인 생각이 많이 들어간 포스트입니다. 지적은 언제나 환영입니다!