遺伝的アルゴリズムGAの基本的な実装を行って文章を生成する。”Hello, where are you?”を作るようにする。
全体のコードは以下になる。突然変異mutateで作りたい文章を求めている。
import random
target_sentence = "Hello, where are you?"
gene_pool = " ,!?abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
population_size = 10
def generate_chromosome(length):
genes = []
while len(genes) < length:
genes.append(gene_pool[random.randrange(0, len(gene_pool))])
return ''.join(genes)
def calculate_fitness(chromosome):
fitness = 0
ctr = 0
for i in chromosome:
if i == target_sentence[ctr]:
fitness += 1
ctr += 1
return fitness
def mutate(chromosome):
index_to_mutate = random.randrange(0, len(chromosome))
gene = list(chromosome)
mutated_gene = gene_pool[random.randrange(0, len(gene_pool))]
gene[index_to_mutate] = mutated_gene
return ''.join(gene)
population = []
for i in range(population_size):
population.append(generate_chromosome(len(target_sentence)))
#print(population)
population_fitness = []
for chromosome in population:
population_fitness.append(calculate_fitness(chromosome))
for generation in range(5000):
parent_index = population_fitness.index(max(population_fitness))
parent = population[parent_index]
child = mutate(parent)
#print('Parent: ', parent)
#print('Child : ', child)
child_fitness = calculate_fitness(child)
#print('Child Fitness: ', child_fitness)
index_to_delete = population_fitness.index(min(population_fitness))
del population[index_to_delete]
del population_fitness[index_to_delete]
population.append(child)
population_fitness.append(child_fitness)
#print('Current Population: ', population)
#print('Current Fitness : ', population_fitness)
if child == target_sentence:
print('Solution found at Generation: ', generation)
print('Current Population: ', population)
break
# 出力
Solution found at Generation: 4197
Current Population: ['Hello, wherw are you?', 'Hello, wherP are you?', 'Hello, wherJ are you?', 'Hello, wheru are you?', 'Hello, wherM are you?', 'Hello, wherw are you?', 'Hello, wherh are you?', 'Hello, wherg are you?', 'Hello, wherN are you?', 'Hello, where are you?']
['Hello, wherw are you?', 'Hello, wherP are you?', 'Hello, wherJ are you?', 'Hello, wheru are you?', 'Hello, wherM are you?', 'Hello, wherw are you?', 'Hello, wherh are you?', 'Hello, wherg are you?', 'Hello, wherN are you?', 'Hello, where are you?']4197ループ目で目的の”Hello, where are you?”の文字列が生成された。
他にも選択淘汰などの機能があり、使いたい場合は追加で関数を定義して実装する必要がある。
以下で世代のpopulationを生成する。populationのサイズは10としている。
population_size = 10
def generate_chromosome(length):
genes = []
while len(genes) < length:
genes.append(gene_pool[random.randrange(0, len(gene_pool))])
return ''.join(genes)
population = []
for i in range(population_size):
population.append(generate_chromosome(len(target_sentence)))
print(population)
# 出力
['OQzZrHKYeEWNiluQoWdJF', 'QxxCj!nKKNWuybbSxSglu', 'iCkb,UEBAVOSJEjAqjmdS', ' mTamYPXGQKZajvFTfZwK', 'c ?UeZOeiNnXKxltIJvyB', 'dhfVQIYAKu?qFWXRYCE!J', 'h?TNsYBfANeYVfGXPYe!!', 'FzEkGxYTDOBkxQUxxEU C', 'kLtip,rlYrzXvcquGZtRm', 'daidulVdI?RHuEOb?Rjxm']以下で適合度を求める。目的の文章と比べてスペルが何文字合っているか数える。
def calculate_fitness(chromosome):
fitness = 0
ctr = 0
for i in chromosome:
if i == target_sentence[ctr]:
fitness += 1
ctr += 1
return fitness
population_fitness = []
for chromosome in population:
population_fitness.append(calculate_fitness(chromosome))
print(population)
print(population_fitness)
# 出力
['OQzZrHKYeEWNiluQoWdJF', 'QxxCj!nKKNWuybbSxSglu', 'iCkb,UEBAVOSJEjAqjmdS', ' mTamYPXGQKZajvFTfZwK', 'c ?UeZOeiNnXKxltIJvyB', 'dhfVQIYAKu?qFWXRYCE!J', 'h?TNsYBfANeYVfGXPYe!!', 'FzEkGxYTDOBkxQUxxEU C', 'kLtip,rlYrzXvcquGZtRm', 'daidulVdI?RHuEOb?Rjxm']
[0, 0, 0, 0, 0, 0, 0, 0, 1, 0]以下で変異を定義している。ランダムに１文字を変化させる。変異の方法は他にも何種類かある。
def mutate(chromosome):
index_to_mutate = random.randrange(0, len(chromosome))
gene = list(chromosome)
mutated_gene = gene_pool[random.randrange(0, len(gene_pool))]
gene[index_to_mutate] = mutated_gene
return ''.join(gene)