遺伝的アルゴリズムでAIに自分の誕生日を祝ってもらう

突然ですが、本日7月25日は僕の誕生日です。

とはいえ、特に誰かが祝ってくれるわけでもないので「無いなら作る」というエンジニア精神で、誕生日を祝ってくれるプログラムを実装しました。

GitHub
github.com

システム要件
システムの実装
- [要件1] コマンドライン引数で名前を渡す
- [要件2] 遺伝的アルゴリズムの活用
デモンストレーション
- Gif
- 最終出力結果
終わりに

システム要件

コマンドライン引数で、祝ってもらう人（今回は自分）の名前を渡せるようにする
プログラムが「試行錯誤」しながら"Happy birthday"と誕生日を祝ってくれる

システムの実装

[要件1] コマンドライン引数で名前を渡す

まず要件1について、プログラムに出力してもらう文言をユーザがコマンドライン引数で設定できるようにします（参考 *1）。

例えば下記の test_argv.py を次のようにターミナルで実行します。

test_argv.py

import sys
 
args = sys.argv
 
print(args)
print('第１引数：' + args[1])

ターミナル

python test_argv.py 'upura'

すると、ターミナルのコマンドライン引数として渡した'upura'が sys.argv にリスト形式で格納されます。

ターミナルの出力

['test_argv.py', 'upura']
第１引数：upura

この仕組みを応用することで、コマンドライン引数で受け取った名前を含んだ文章を出力できるよう実装します。

今回は 'Happy Birthday, (コマンドライン引数)!' という文章を、目標の出力とします。以下の関数でコマンドライン引数を取得しました。

def get_objective_sentence():
    try:
        USER_NAME = sys.argv[1]
    except:
        USER_NAME = 'upura'

    objective_sentence = 'Happy birthday, ' + str(USER_NAME) + '!'
    return objective_sentence

この部分のunittestについては、別記事にまとめました。
upura.hatenablog.com

[要件2] 遺伝的アルゴリズムの活用

次いで要件2のため、今回は「遺伝的アルゴリズム」を用いて、目標の文章を出力する仕組みを作りたいと思います。

遺伝的アルゴリズムとは、生物界の進化の仕組みを模倣する解探索手法です*2。大雑把に言うと、ランダムに大量の解候補を生成し、たまたま「良くできた」候補を元に次なる候補を生成していくことで、目標の解にたどり着こうとする手法です。

今回の手順の概要を以下の図に示します。

f:id:upura:20180723200505p:plain

下記の手順で、目標の文章を出力する仕組みを実装しました。

「現世代」の $N$ 個の個体をランダムに生成する
「現世代」の各個体の「適応度」をそれぞれ計算する
ある確率で次のいずれかの遺伝子操作を実施し、結果を「次世代」に保存する
1. 個体を二つ選択して「交叉」
2. 個体を一つ選択して「突然変異」
3. 個体を一つ選択して「複製」
「次世代」の個体数が $N$ 個になるまで上記の動作を繰り返す
「次世代」の個体数が $N$ 個になったら「次世代」を「現世代」と見なす
2以降の動作を、目標の解を導出できる個体が出現するまで繰り返す

ただし $N=1000$ 、遺伝子操作の選択確率は $(交叉, 突然変異, 複製)=(0.1, 0.1, 0.8)$ としています。

以下では、各ステップについて説明していきます。

1. 「現世代」の $N$ 個の個体をランダムに生成する

ここでは、以下の関数で目標の文章と同じ長さの文章を生成します。単語の候補はアルファードの大文字・小文字に加え、半角スペース・半角カンマ・半角感嘆符です。

例えば`p!VGtdbirQedHyLtjaLfr!`のような文章を一つの個体として生成します。

def get_string_candidate():
    string_candidate = \
        [chr(i) for i in range(97, 97 + 26)] + [chr(i) for i in range(65, 65 + 26)]    
    string_candidate.append(' ')
    string_candidate.append(',')
    string_candidate.append('!')
    return string_candidate

def get_sentence(string_candidate, sentence_length):
    created_sentence = random.choices(string_candidate, k = sentence_length)
    return created_sentence

2. 「現世代」の各個体の「適応度」をそれぞれ計算する

ここでは、各個体の「適応度」を以下の関数で計算します。純粋に一文字単位で目標の文章との差異を調べています。

例えば'p!VGtdbirQedHyLtjaLfr!'の場合は、太字の部分が目標の文章と一致しているので、適応度は(一致した文字数)/(全文字数)として計算されます。

def get_fitness(objective_sentence, sentence):
    judgment = [i == j for i, j in zip(objective_sentence, sentence)]
    evaluation = sum(judgment) / len(judgment)
    return evaluation

3. ある確率で次のいずれかの遺伝子操作を実施し、結果を「次世代」に保存する

ここでは、以下のいずれかの遺伝子操作を実施します。

ただし以下の遺伝子操作における「選択」には「ルーレット選択」と呼ばれる手法を採用しました。ルーレット選択は個体 $i$ の適応度を $f_i$ としたときに、個体 $i$ を選ぶ確率 $p_i$ を下記のように計算する手法です。

$p_{i}={\frac {f_{i}}{\sum _{k=1}^{N}f_{k}}}$

def fitness_proportionate_selection(agents, evaluations):
    weight = np.array(evaluations) / sum(evaluations)
    index = np.arange(AGENT_NUM)
    return agents[np.random.choice(index, p = weight)]

個体を二つ選択して「交叉」

ここでは、「二点交叉」という手法を採用しました。交叉点をランダムで二つ選び、二つの交叉点に挟まれている部分を入れ換える方式です。

def crossover(agents, evaluations):
    father_agent = fitness_proportionate_selection(agents, evaluations)
    mother_agent = fitness_proportionate_selection(agents, evaluations)
    crossover_points = random.sample(list(np.arange(len(father_agent) - 1)), 2)
    next_agent = father_agent[:min(crossover_points)] \
        + mother_agent[min(crossover_points):max(crossover_points)] \
        + father_agent[max(crossover_points):]
    return next_agent

個体を一つ選択して「突然変異」

ここでは、個体の各要素を0.1の確率で別の単語に置き換えます。

def mutation(agents, evaluations, string_candidate):
    selectd_agent = fitness_proportionate_selection(agents, evaluations)
    next_agent = [i if random.random() > 0.1 else \
        get_sentence(string_candidate, 1)[0] for i in selectd_agent]
    return next_agent

個体を一つ選択して「複製」

ここでは、選択された個体をそのまま「次世代」に引き継ぎます。

def reproduction(agents, evaluations):
    return fitness_proportionate_selection(agents, evaluations)

4. 「次世代」の個体数が $N$ 個になるまで上記の動作を繰り返す

ここでは、3の操作を $N$ 回繰り返します。

5. 「次世代」の個体数が $N$ 個になったら「次世代」を「現世代」と見なす

ここでは、現時点での「次世代」を「現世代」と見なします。

6. 2以降の動作を、目標の解を導出できる個体が出現するまで繰り返す

ここでは、2以降の動作を繰り返し、目標の解を導出できる個体が出現するまで新たなる「次世代」を生成していきます。

デモンストレーション

以下は、各世代で一番適応度の高い個体を出力しています。徐々に目標の文章に近づいていっている様子が分かります。

Gif

f:id:upura:20180721165641g:plain

最終出力結果

最後には、目標の文章を出力できています。277世代までかかったので、約277000の個体を生成したことになります。

f:id:upura:20180721165800p:plain

終わりに

今回は、遺伝的アルゴリズムを用いて、自分の誕生日を祝ってくれるプログラムを実装しました。プログラムはGitHubで公開しており、簡単にですがREADMEやユニットテストも整備しています。気が向いたら自分の名前を入れて遊んでみてください。
github.com

誕生日のお祝いとして、はてなブックマークやSNS拡散も大歓迎です！！！

*1:www.python-izm.com

*2:Mitchell, Melanie (1996). An Introduction to Genetic Algorithms. Cambridge, MA: MIT Press. ISBN 9780585030944.