遺伝的アルゴリズムで誕生日を祝ってもらおう

#はじめに
今回は, 遺伝的アルゴリズムを用いて「お誕生日おめでとうございます」というメッセージを生成します. 
大学の授業の一環で遺伝的アルゴリズムを使用してなにか発表しろとの指示がありましたので, 少しおふざけまじりの内容となっています. 

#遺伝的アルゴリズム
遺伝的アルゴリズムの基本的な内容に関しては, 別記事を参照していただければ理解しやすいかと思います. 
[遺伝的アルゴリズムでOneMax問題を解いてみる](https://qiita.com/pontyo4/items/a986df2582f3d0aaaa40)

簡単なアルゴリズムの流れも貼っておきます. 
![スクリーンショット 2019-09-01 3.21.04.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/a9be54c4-4f2e-10e1-4246-ca488ceb5e5d.png)

##文字を整数値に変換
今回はひらがなのみを使用し, それぞれに整数値を振り分けます. 
濁点など含めて全部で86種類になります. 
![スクリーンショット 2019-09-01 3.26.40.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/1757f6e2-c789-8c03-e02e-2eb5c2f5a5c0.png)

以下のコードを実行することで, 生成したい文字列に対応する整数値リストが表示されます. 
文字列部分を変更すれば, 好きな文字列で遊ぶことができます. 


```python
print([ord(i)-12354 for i in "おたんじょうびおめでとうございます"])
#[8, 29, 81, 22, 69, 4, 49, 8, 63, 37, 38, 4, 18, 20, 2, 60, 23]
```

##個体表現
遺伝的アルゴリズムにおける個体は以下のように表現されます. 
![スクリーンショット 2019-09-01 3.36.17.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/c696119c-976a-9f59-4b6d-5e41a1328908.png)

##評価関数
生成した個体を評価するための関数を, 2パターン用意します. 
それぞれの評価関数を最大化することで探索していきます. 
1. ユークリッド距離を用いる. 
![スクリーンショット 2019-09-01 3.40.57.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/92a627c2-2f4d-54ed-8c5d-261305c9d24a.png)
2. ハミング距離を用いる. 
![スクリーンショット 2019-09-01 3.41.46.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/197f1f21-5a11-6395-4b09-40a10b0fd23e.png)

#実験設定
![スクリーンショット 2019-09-01 3.43.53.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/73cc5108-3f6e-3ab8-d441-1f9b1c88421c.png)

#コード

```python
# -*- coding: utf-8 -*-
import random
import time
import sys

# 各種パラメータ
pop = 100  # 親個体数
offspring_pop = 100    # 子個体数
generation_max = 100    # 世代数
# "おたんじょうびおめでとうございます"の正解番号
answer = [8, 29, 81, 22, 69, 4, 49, 8, 63, 37, 38, 4, 18, 20, 2, 60, 23]
length = len(answer)  # 遺伝子長
mutation_rate = 1.0/length    # 突然変異確率(1/遺伝子長)
interval = 0.1
random.seed(1)

# 初期個体群生成
def initialize():
    gene = [[random.randint(0,85) for i in range(length)] for j in range(pop)]
    return gene

# 個体評価(ユークリッド距離を使用)
def evaluate1(gene):
    fitness = []
    for i in range(pop):
        sum = 0
        for j in range(length):
            sum += (abs(answer[j] - gene[i][j]))
        fitness.append(-sum)
    return fitness

# 個体評価(ハミング距離を使用)
def evaluate2(gene):
    fitness = []
    for i in range(pop):
        sum = 0
        for j in range(length):
            if answer[j] == gene[i][j]:
                sum += 1
        fitness.append(sum)
    return fitness

# 親選択
def choice_parents(gene, fitness):
    father_index = random.randint(0,pop-1)
    mother_index = random.randint(0,pop-1)
    if fitness[father_index] > fitness[mother_index]:
        parents = gene[father_index]
    else:
        parents = gene[mother_index]
    return parents

# 交叉
def crossover(father, mother):
    offspring = []
    for i in range(length):
        p = random.random()
        if p < 0.5:
            offspring.append(father[i])
        else:
            offspring.append(mother[i])
    return offspring

# 突然変異
def mutation(offspring):
    for i in range(length):
        p = random.random()
        if p < mutation_rate:
            offspring[i] = random.randint(0, 83)
    return offspring

# 個体更新
def update(fitness, fitness2, gene, next_gene):
    fitness_all = fitness + fitness2
    gene_all = gene + next_gene
    count = 0
    fitness_new = []
    gene_new = []
    while True:
        index = fitness_all.index(max(fitness_all))
        fitness_new.append(fitness_all[index])
        gene_new.append(gene_all[index])
        del fitness_all[index]
        del gene_all[index]
        count += 1
        if count == pop:
            break
    return fitness_new, gene_new

# 文字列を表示
def show(gene, generation):
    print("generation:"+str(generation), end="   ")
    for i in range(length):
        print(chr(0x3042+gene[0][i]), end=" ")
    print("  ", end=" ")
    for i in range(length):
        print(chr(0x3042+gene[pop-1][i]), end=" ")
    print("")

# 評価にユークリッド距離を使用する
def main1():
    generation = 1
    next_gene = []

    # 初期個体群生成
    gene = initialize()
    # 初期個体評価
    fitness = evaluate1(gene)

    while generation <= generation_max:
        next_gene.clear()
        # 次世代個体群生成
        for i in range(offspring_pop):
            # 個体選択
            father = choice_parents(gene, fitness)
            mother = choice_parents(gene, fitness)
            # 交叉
            offspring = crossover(father, mother)
            # 突然変異
            offspring = mutation(offspring)
            next_gene.append(offspring)
        # 個体評価
        fitness2 = evaluate1(next_gene)
        # 個体更新
        fitness, gene = update(fitness, fitness2, gene, next_gene)

        #print("---------------------------------")
        #print("generation:", generation)
        #print(gene)
        #print(fitness)

        # インターバルごとに文字列表示
        show(gene, generation)
        time.sleep(interval)
        # ファイル出力
        average = sum(fitness)/len(fitness)
        f.write(str(generation) + " " + str(fitness[0]) + " " + str(fitness[-1]) + " " + str(average) + "\n")
        generation += 1
    f.close()

# 評価にハミング距離を使用する
def main2():
    generation = 1
    next_gene = []
    # file出力
    f = open('fitness.txt', 'w')

    # 初期個体群生成
    gene = initialize()
    # 初期個体評価
    fitness = evaluate2(gene)

    while generation <= generation_max:
        next_gene.clear()
        # 次世代個体群生成
        for i in range(offspring_pop):
            # 個体選択
            father = choice_parents(gene, fitness)
            mother = choice_parents(gene, fitness)
            # 交叉
            offspring = crossover(father, mother)
            # 突然変異
            offspring = mutation(offspring)
            next_gene.append(offspring)
        # 個体評価
        fitness2 = evaluate2(next_gene)
        # 個体更新
        fitness, gene = update(fitness, fitness2, gene, next_gene)

        #print("---------------------------------")
        #print("generation:", generation)
        #print(gene)
        #print(fitness)

        # インターバルごとに文字列表示
        show(gene, generation)

if __name__ == "__main__":
    print("ユークリッド距離の場合")
    main1()
    print("")
    print("ハミング距離の場合")
    main2()
```

#実行の様子
最初の方はよくわからない言葉が生成されているのがわかります. 
![スクリーンショット 2019-09-01 3.52.20.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/fbe8f839-733a-82e8-c7f2-dc2f55721ad2.png)

探索が進んでいくと徐々に正解ワードへと近づいていきます. 
![スクリーンショット 2019-09-01 3.52.42.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/319132/4d03e4ca-9cec-6391-14c9-6aca5622bc12.png)

評価関数にユークリッド距離を用いるよりも, ハミング距離を使用した方が収束が早かったです. 
今回のワードは簡単だったのですぐに正解ワードを見つけましたが, もっと長いワードを設定すると苦戦するかもしれませんね. 

なにはともあれ, コンピュータが試行錯誤しながらお誕生日をお祝いしれくれるプログラムができましたので, 1人寂しく過ごされる方はぜひ使ってみてください.