ムダにエボリューショナルな"hello, world"の出力方法(Python)


# ムダにエボリューショナルな"hello, world"の出力方法(Python)

## 概要

**<内容>**

- [遺伝的アルゴリズム](https://ja.wikipedia.org/wiki/%E9%81%BA%E4%BC%9D%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0)を用いて、"hello, world"を出力します。出力する文字列は、[K&R](https://ja.wikipedia.org/wiki/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E8%A8%80%E8%AA%9EC)に敬意を表し、大文字なし、感嘆符なしの"hello, world"とします。

**<経緯>**

- トレンド入りしていた、[ムダにクリエイティブな"Hello World"の出力方法一覧(Java)](https://qiita.com/KMim/items/dfa1cde772f67ef50618)を見て、心に火がつきました。
- [『機械学習と深層学習《Pythonによるシミュレーション》』](https://ndlonline.ndl.go.jp/#!/detail/R300000001-I028959772-00)を読んで、遺伝的アルゴリズムを試してみたいと思っていました。

**<結論>**

- 出力に成功しました。

![hello, world](https://github.com/tanuk1647/evolutional-hello-world/raw/master/figures/evolutional-hello-world-0000.png)

- 実行の様子は、以下をクリックすると、YouTubeの動画でご覧頂けます。

[![実行の様子](https://github.com/tanuk1647/evolutional-hello-world/raw/master/figures/evolutional-hello-world-0005.png)](http://www.youtube.com/watch?v=a2DOI-hMyVc)


## hello, world

"hello, world"は意外と易しく、比較的早く最適解に到達します。

    1 : e,rwo
    2 : nn l?,vwld
    3 : nn l?,vwld
    4 : nn l?,vwld
    5 : e?l,qrud
    6 : hebrs gor 
    7 : hebrs gor 
    8 : bel?o or
    9 : bel?o or
    10 : hellm rq
    11 : hellm rq
    12 : helloznyk,?w,rd
    13 : helloznyk,?w,rd
    14 : helloznyk,?w,rd
    15 : helloznyk,?w,rd
    16 : heklo, ml
    17 : hel!o, zweb!d
    18 : heplo. zw,rnd
    19 : heplo. zw,rnd
    20 : heplo, !omlr
    21 : heplo, !omlr
    22 : hello, voslp
    23 : hello, voslp
    24 : hmllo, wo?xh
    25 : hmllo, wo?xh
    26 : heplo, !omlr
    27 : hello, onrm
    28 : hello, ngr ,d
    29 : hello, ngr ,d
    30 : hello, olll
    31 : hello, ngr ,d
    32 : hello, ngr ,d
    33 : hello, eoxr??
    34 : hello, eoxr??
    35 : hello, rxd
    36 : hello, rxd
    37 : hello, wkwd
    38 : hello, wo
    39 : hello, wprqsd
    40 : hello, wprqsd
    41 : hello, wo@.d
    42 : hello, wo@.d
    43 : hello, wo@.d
    44 : hello, voroo
    45 : hello, wo
    46 : dello, woul
    47 : hello, wosr
    48 : hello,,wrld
    49 : hello,,wrld
    50 : hello,,wrld
    51 : helko, worlw
    52 : hello, wolc
    53 : hello, wwld
    54 : hello,,wrld
    55 : hello,kwoald
    56 : hello, worlo
    57 : hello, wov,d
    58 : hello, w?ld
    59 : hello, work
    60 : hello, word
    61 : hello, word
    62 : hello, word
    63 : hello, word
    64 : hello, wordd
    65 : hello, worl
    66 : hello, worl
    67 : hello, worl
    68 : hello, worl
    69 : hello, word
    70 : hello, world

![hello, world](https://github.com/tanuk1647/evolutional-hello-world/raw/master/figures/evolutional-hello-world-0001.png)

## i love you

他の文字列、具体的には、"i love you"についても試してみましたが、意外と難しく、局所的最適解への収束を三回経て、四回目でようやく大域的最適解に到達しました。グラフに三つの崖があるのを確認して頂けるかと思います。

    1 : frkyox@eyobju
    2 : ilyo
    3 : wi l!xeheosb
    4 : wi l!xeheosb
    5 : l vo,,pyoru
    6 : i .koqrp lyo!
    7 : .!,c xoce yodu@
    8 : i .koqrp lyo!
    9 : i o? ys
    10 : i lomyu
    11 : i lomyu
    12 : ialobefyolf
    13 : ialobefyolf
    14 : i le yx 
    15 : i leqyoj
    16 : i le yx 
    17 : i le yx 
    18 : i lauemz  you
    19 : i lauemz  you
    20 : i lauemz  you
    21 : i lo y
    22 : i lve,o
    23 : i lavyu
    24 : i loeu
    25 : i loeyow
    26 : i lovyzu
    27 : i lovcyu
    28 : i lo yoq
    29 : i loeyop
    30 : i lveyo
    31 : i loeyku
    32 : i lo yoz
    33 : i loeyou
    34 : i loeyou
    35 : i loeyou
    36 : i loeyou
    37 : i loeyou
    38 : i loeyou
    39 : i loeyou
    40 : i loeyou
    41 : i loeyou
    42 : i loeyou
    43 : i loeyou
    44 : i loeyou
    45 : i loeyou
    46 : i loeyou
    47 : i loeyou
    48 : i loeyou
    49 : i loeyou
    50 : i loeyou
    51 : i loeyou
    52 : i loeyou
    53 : i lovyou
    54 : i loeyou
    55 : i loeyou
    56 : i loeyou
    57 : i loeyou
    58 : i loeyou
    59 : i loeyou
    60 : i loeyou
    61 : i loeyou
    62 : i loeyou
    catastrophe occured!
    63 : i koeyou
    64 : i koeyou
    65 : i loezou
    66 : i koeyou
    67 : i koeyou
    68 : i koeyou
    69 : i koeyou
    70 : i koeyou
    71 : i obe ou
    72 : i obe ou
    73 : i obe ou
    74 : i lovexy
    75 : i lovexy
    76 : i lovexy
    77 : i lbeyou
    78 : i loeyos
    79 : i lovyou
    80 : i lovyou
    81 : i loeyou
    82 : i loeyou
    83 : i lovyou
    84 : i lovyou
    85 : i loeyou
    86 : i lovyou
    87 : i loeyou
    88 : i loeyou
    89 : i loeyou
    90 : i loeyou
    91 : i loeyou
    92 : i loeyou
    93 : i lovyou
    94 : i lovyou
    95 : i lovyou
    96 : i loeyou
    97 : i lovyou
    98 : i loeyou
    99 : i loeyou
    100 : i loeyou
    101 : i loeyou
    102 : i loeyou
    103 : i loeyou
    104 : i loeyou
    105 : i loeyou
    106 : i loeyou
    107 : i loeyou
    108 : i loeyou
    catastrophe occured!
    109 : i loeyou
    catastrophe occured!
    110 : r vysu
    111 : iroo?eycx
    112 : iroo?eycx
    113 : tloge o
    114 : i ve r k
    115 : i ve r k
    116 : i lyou
    117 : i xo@ ou
    118 : i xo@ ou
    119 : i xo@ ou
    120 : i xo@ ou
    121 : i ls rou
    122 : i lwveo
    123 : i lovy
    124 : i lsvw u
    125 : gklova ou
    126 : i love j
    127 : i love j
    128 : i love j
    129 : i loveo
    130 : i loveku
    131 : i loveo
    132 : i lovysu
    133 : i lovyo
    134 : i loveo
    135 : y love u
    136 : i lovyou
    137 : i lovyou
    138 : i lovyou
    139 : i loveou
    140 : i loveou
    141 : i loveou
    142 : i loveou
    143 : i loveyu
    144 : i love y
    145 : i love y
    146 : i love y
    147 : i love u
    148 : i loveou
    149 : i loveou
    150 : i love u
    151 : i love u
    152 : i loveou
    153 : i love y
    154 : i lov ou
    155 : i loveou
    156 : i loveou
    157 : i loveou
    158 : i loveou
    159 : i love u
    160 : i love y
    161 : i loveou
    162 : i loveou
    163 : i love y
    164 : i loveou
    165 : i love u
    catastrophe occured!
    166 : i love y
    catastrophe occured!
    167 : u oyom
    168 : ilieyo
    169 : ilieyo
    170 : ilieyo
    171 : ilieyo
    172 : i !oey z
    173 : i !oey z
    174 : i !oey z
    175 : klon yu
    176 : ,hlovpgyqu
    177 : i lom. yay
    178 : i lom. yay
    179 : q lovu yu
    180 : q lovu yu
    181 : i lom. yay
    182 : i lovedyy
    183 : ealofe you
    184 : i lovedyy
    185 : i lovedyy
    186 : i love xo
    187 : i love xo
    188 : i love xo
    189 : i lose ynu
    190 : i love yo
    191 : i love yo
    192 : i love yo
    193 : i love yoqu
    194 : i love hou
    195 : i love yo
    196 : i love you

![i love you](https://github.com/tanuk1647/evolutional-hello-world/raw/master/figures/evolutional-hello-world-0002.png)

## 設計概要

設計は、以下のとおりとしました。

- 遺伝情報は長さ84のビット列で表現する。内訳は、１）文字列長（1~16）を表す4ビット、２）a-zや簡単な記号を含む32種類の文字を表す5ビット×16=80、である。
    - なお、"hello, world"となるパターンは、「0b\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*0100110001101111010011100000000001010100100011000101010011011011」である。

- 個体は文字【 !,.?@abcdefghijklmnopqrstuvwxyz】からなる、長さ1~16の文字列である。個体の環境への適応度（fitness）は、指定された文字列との[編集距離](https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2)で測られる。

- 繁殖時、子供はビットごとに、両親いずれかの遺伝子を引き継ぐものとする。遺伝子の引き継ぎ後、突然変異が発生するものとする。突然変異は、子供の各ビットごとに一定確率で値を反転させるものである。

- 個体の集団は、適応度が上位20%のエリートと、残り80%の非エリートに分かれるものとする。エリート全員に繁殖の機会が与えられるが、その相手は非エリートである。これは、多様性を保つため、あるいは、近親相姦のタブーを表現するためである。なお、雌雄の区別はないものとする。エリート一体が複数体の子供を残すものとする。

- 次世代に残る候補は、１）エリートのうち12/16の確率でランダムに選ばれた個体、２）子供、３）非エリートのうち3/16の確率でランダムに選ばれた個体の３グループをまとめた中から、適応度の高い順に集団の上限サイズまで選ばれるものとする。

- 集団にはカタストロフィ（破局）が発生するものとする。破局発生時は、現世代のごく一部が生き残り、現世代の遺伝情報を引き継がない新個体群と共に、次世代を構成するものとする。これは、隕石の衝突などの大惨事を模したものである。

- 進化をつかさどる何かが状況を監視しており、集団の進化が停滞した際には、破局を引き起こし、さらなる進化を促すものとする。

遺伝的アルゴリズム、と言える内容だと思います。[パレートの法則](https://ja.wikipedia.org/wiki/%E3%83%91%E3%83%AC%E3%83%BC%E3%83%88%E3%81%AE%E6%B3%95%E5%89%87)を取り入れたところや、局所的最適解からの脱出を図る**破局**の仕組みを取り入れたところが、特徴と言えるでしょうか。もちろん、遺伝的アルゴリズムは様々なバリエーションがあるわけですが、本記事では以上のアルゴリズムを採用したということです。

## プログラム概要

プログラムの概要は、以下のとおりです。

- クラス「EvolutionController」。進化をつかさどる何か。初期化時に、ターゲット文字列、集団の上限サイズ、世代交代の上限回数、破局を引き起こすまでの許容回数、出力の冗長性、ログの記録（グラフの表示）有無を指定できるようにする。進化する集団を監視し、その過程や結果を画面表示する。また、進化の停滞時——集団の最良個体の適応度が一定以上の世代に渡り変化しなかったとき——には、集団に破局を引き起こすものとする。

- クラス「Population」。集団を表すクラス。「EvolutionController」の管理下で、世代交代を繰り返す。適応度の高い順にソートされた個体群を保持しており、カップリングと、次世代に生存する個体の選択に責任を持つ。世代についての情報——最良の個体の文字列表現、および、適応度の最小値、最大値、平均値、中央値——を、「EvolutionController」に提供するものとする。また、「EvolutionController」が破局の引き金を引いた際には、現世代からランダムに選択した個体以外を抹消。現世代の遺伝情報を引き継がない新個体群を発生させ、世代を一新する処理を行うものとする。

- クラス「Individual」。個体を表すクラス。「Population」の管理下で、発生と繁殖を行う。ランダムに得た、あるいは、両親から引き継いだ遺伝情報を元に発現し、1~16の長さの文字列からなる身体と適応度を持つ。適応度は、ターゲット文字列との編集距離で測られる。遺伝情報はビット列なので、ビット演算を行い、遺伝情報を読み解くものとする。\_\_gt\_\_等のオペレータを実装し、「Population」が正しく個体の選択やソートを行えるようにする。繁殖を行う際には、やはりビット演算により、自身とパートナーの遺伝情報の引き継ぎ、および、子供の突然変異を行うものとする。


## 利用した技法や考え方

本プログラムの作成にあたっては、以下の技法や考え方を利用しました。

- ビット演算
    - 下位から取得したいビットのみを1としたマスクを用意し、対象ビット列とand演算を行う。実施後は、取得した分だけ右シフトし、次の取得ができるようにする。
    - ランダムに発生させたビット列で親1とand演算を行い、親1の遺伝情報の一部を収集する。また、反転したマスクと親2のand演算を行い、親2の遺伝情報の残りを収集する。収集した遺伝情報をor演算で合成し、子供の遺伝情報とする。
    - マスクの各ビットに一定の確率で1を立てる。マスクと子供のxor演算を行うことで、1を立てた箇所のビットを反転させ、突然変異とする。

- 拡張比較メソッドの実装
    - クラス「Individual」に[拡張比較メソッド](https://docs.python.jp/3/reference/datamodel.html#richcmpfuncs)を実装し、適応度による比較やソートを可能にする。

- [パレートの法則](https://ja.wikipedia.org/wiki/%E3%83%91%E3%83%AC%E3%83%BC%E3%83%88%E3%81%AE%E6%B3%95%E5%89%87)
    - 全体の数値の大部分は、全体を構成するうちの一部の要素が生み出しているという理論。80:20の法則、ばらつきの法則とも呼ばれる。繁殖の際、集団を20:80に分けている。また、次世代への生存確率も、エリートと非エリートでは比が80:20になるようにしている。

- [編集距離](https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2)
    - レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される。個体の適応度を測る評価関数として利用している。詳細は、参考記事の[二番目](https://qiita.com/tanuk1647/items/5a591da10e2ea5bedef6)を参照。

- コンソール出力の上書き
    - キャリッジリターン(`\r`)を出力することで、カーソルが行頭に復帰するため、コンソール出力を上書きすることができる。また、Jupyter Notebookではうまく動作しないが、CSIという仕組みを利用することもできる。詳細は、参考記事の[三番目](https://qiita.com/airtoxin/items/bb445529c94d3cd871f3)、[四番目](https://qiita.com/exy81/items/99e99ab8c184343948cc)を参照。


**<参考記事>**

- [Python ビット演算 超入門](https://qiita.com/7shi/items/41d262ca11ea16d85abc)
- [編集距離（レーベンシュタイン距離）を理解し、実装する](https://qiita.com/tanuk1647/items/5a591da10e2ea5bedef6)
- [コンソールへの出力を上書きしてゆく方法](https://qiita.com/airtoxin/items/bb445529c94d3cd871f3)
- [Pythonで出力した文字を消す方法](https://qiita.com/exy81/items/99e99ab8c184343948cc)


## 感想

本プログラムを作成し、機械学習との共通点を感じました。

- ハイパーパラメータによる調整が必要
    - 集団あたりの個体数
    - 一体の親が何体の子供を生むか
    - 突然変異の発生率
    - 破局の際、現行世代をどの程度残すか

- 局所的最適解を避ける工夫が必要
    - あえてエリートと非エリートをカップリングさせる
    - 突然変異
    - 破局

- 評価関数の定義が必要
    - 編集距離

また、本来「準最適解を短時間で見つける」のが遺伝的アルゴリズムの特徴だと思いますが、本記事で作成したプログラムは、破局の効果もあり、ほぼ確実に最適解の「hello, world」を見つけてくれますので、そこは達成感、満足感がありました。

一つ謎なのは、同程度の長さの文字列でも、なかなか最適解に到達しないものがあります。例えば、"john lennon"は、"hello, world"より一文字少ないのに、最適解への到達に苦労します。なぜでしょうね。

![john lennon1](https://github.com/tanuk1647/evolutional-hello-world/raw/master/figures/evolutional-hello-world-0003.png)

![john lennon2](https://github.com/tanuk1647/evolutional-hello-world/raw/master/figures/evolutional-hello-world-0004.png)


## 作成したプログラム

最後に、作成したプログラムを以下に示します。ご興味があれば、[Google Colaboratory](https://colab.research.google.com/notebooks/welcome.ipynb)などで、お試しあれ。モジュールは、[GitHub](https://github.com/tanuk1647/evolutional-hello-world/blob/master/evolutional_hello_world.py)にもあります。


```python
import sys
import random
from functools import lru_cache
from statistics import mean
import matplotlib.pyplot as plt
import matplotlib.ticker as ticker
from collections import deque


class Individual():
    '''個体
    
    ・遺伝情報
      ・長さ84のビット列で表現する
      ・それぞれ以下に発現する
        ・length(4bit)：文字列長（0~15）
        ・string(5bit * 16)：以下文字を16個
          ・スペース
          ・記号（@!,.?）
          ・小文字アルファベット（a-z）
    '''
    
    _max_len_str = 16
    _gene_size = 84
    _expression = ' !,.?@abcdefghijklmnopqrstuvwxyz'
    
    _mask_uint4 = 0b1111
    _shift_uint4 = 4
    
    _mask_char5 = 0b11111
    _shift_char5 = 5
    
    _mutate_probability = 0.05
    
    def __init__(self, target, gene=None):
        self._target = target
        
        if gene is None:
            self.gene = random.getrandbits(self._gene_size)
        else:
            assert 0 <= gene < 2 ** self._gene_size
            self.gene = gene
        
        # 遺伝情報を読み解く
        gene = self.gene
        
        info_length = (gene & self._mask_uint4) + 1
        gene = gene >> self._shift_uint4
        
        info_string = [0] * self._max_len_str
        for i in range(self._max_len_str):
            info_string[i] = (gene & self._mask_char5)
            gene = gene >> self._shift_char5
        
        # 遺伝子から個体へと発現する
        self.body = [0] * info_length
        
        for i in range(info_length):
            self.body[i] = self._expression[info_string[i]]
        
        self.body = ''.join(self.body)
        
        # 適応度を計算する
        self.fitness = lss(self.body, self._target)
    
    def _is_valid_operand(self, other):
        return hasattr(other, 'fitness')
    
    def __eq__(self, other):
        if not self._is_valid_operand(other):
            return NotImplemented
        return self.fitness == other.fitness
    
    def __ne__(self, other):
        if not self._is_valid_operand(other):
            return NotImplemented
        return self.fitness != other.fitness
    
    def __lt__(self, other):
        if not self._is_valid_operand(other):
            return NotImplemented
        return self.fitness < other.fitness
    
    def __le__(self, other):
        if not self._is_valid_operand(other):
            return NotImplemented
        return self.fitness <= other.fitness
    
    def __gt__(self, other):
        if not self._is_valid_operand(other):
            return NotImplemented
        return self.fitness > other.fitness
    
    def __ge__(self, other):
        if not self._is_valid_operand(other):
            return NotImplemented
        return self.fitness >= other.fitness
    
    def __hash__(self):
        return hash(self.fitness)
    
    def __repr__(self):
        return f"Individual('{self._target}', {self.gene})"
    
    def __str__(self):
        return self.body
    
    def __format__(self, format_spec):
        return self.body
    
    def __bool__(self):
        return True if self.fitness == 1.0 else False
    
    def mate(self, other, target):
        '''子供を作る'''
        assert isinstance(other, Individual)
        
        child_gene = 0
        self_gene = self.gene
        other_gene = other.gene
        
        # 両親の遺伝子を受け継ぐ
        mask_mate = random.getrandbits(self._gene_size)
        self_gene = self_gene & mask_mate
        other_gene = other_gene & ~mask_mate
        child_gene = self_gene | other_gene
        
        # 突然変異
        mask_mutation = 0
        for _ in range(self._gene_size):
            mask_mutation = mask_mutation << 1
            if random.random() <= self._mutate_probability:
                mask_mutation = mask_mutation | 0b1
        child_gene = child_gene ^ mask_mutation
        
        return Individual(target, child_gene)


class Population():
    '''集団'''
    _fertility_rate = 10
    _catastrophe_damage = 100
    
    def __init__(self, target, population_size):
        self._target = target
        self._population_size = population_size
        self.generation = [Individual(target) for _ in range(self._population_size)]
        self.generation.sort(reverse=True)
        self.generation_number = 0
    
    def next_generation(self):
        '''次世代を生み出す'''
        self.generation_number += 1
        
        # エリートと非エリートに分ける
        pareto = self._population_size // 5
        elites = self.generation[: pareto]
        non_elites = self.generation[pareto :]
        
        # エリートが非エリートと繁殖する
        children = []
        for parent1 in elites:
            while True:
                parent2 = random.choice(non_elites)
                if parent1 is parent2:
                    continue
                else:
                    break
            
            for _ in range(self._fertility_rate):
                children.append(parent1.mate(parent2, self._target))
        
        # 次世代に生存する個体を選択
        elites = random.sample(elites, 12 * len(elites) // 16)
        non_elites = random.sample(non_elites, 3 * len(non_elites) // 16)
        self.generation = elites + children + non_elites
        self.generation.sort(reverse=True)
        self.generation = self.generation[: self._population_size]
        
        # 世代の記録を残す
        max_one = self.generation[0]
        max_body = max_one.body
        max_fitness = max_one.fitness
        
        min_fitness = self.generation[-1].fitness
        mean_fitness = mean(i.fitness for i in self.generation)
        median_fitness = self.generation[self._population_size // 2].fitness
        
        return max_body, min_fitness, max_fitness, mean_fitness, median_fitness
    
    def catastrophe(self):
        '''破局の発生'''
        survivor = random.sample(self.generation, self._population_size // self._catastrophe_damage)
        newcomer = [Individual(self._target) for _ in range(self._population_size)]
        self.generation = survivor + newcomer
        self.generation.sort(reverse=True)
        self.generation = self.generation[: self._population_size]


@lru_cache(maxsize=4096)
def ld(s, t):
    '''編集距離（レーベンシュタイン距離）を計算する'''
    if not s: return len(t)
    if not t: return len(s)
    if s[0] == t[0]: return ld(s[1:], t[1:])
    l1 = ld(s, t[1:])
    l2 = ld(s[1:], t)
    l3 = ld(s[1:], t[1:])
    return 1 + min(l1, l2, l3)


def lss(s, t):
    '''類似度を計算する（編集距離を標準化し線形変換する）'''
    return -(ld(s, t) / max(len(s), len(t))) + 1


class History():
    '''履歴を管理するクラス'''
    def __init__(self):
        self.min = []
        self.max = []
        self.mean = []
        self.median = []
    
    def append(self, history):
        '''履歴を追加する'''
        assert len(history) == 4
        self.min.append(history[0])
        self.max.append(history[1])
        self.mean.append(history[2])
        self.median.append(history[3])


def visualize(title, history):
    '''履歴をグラフ化する'''
    assert isinstance(history, History)
    x = range(1, len(history.min) + 1)
    plt.figure()
    plt.plot(x, history.min, marker='.', label='min_fitness')
    plt.plot(x, history.max, marker='.', label='max_fitness')
    plt.plot(x, history.mean, marker='.', label='mean_fitness')
    plt.plot(x, history.median, marker='.', label='median_fitness')
    plt.legend(bbox_to_anchor=(0, 1), loc='upper left', fontsize=10)
    plt.grid()
    plt.xlabel('generation')
    plt.ylabel('fitness')
    plt.title(title)
    plt.gca().get_xaxis().set_major_locator(ticker.MaxNLocator(integer=True))
    plt.show()


class EvolutionController():
    '''進化をつかさどる何か'''
    def __init__(self, target, population_size=1000, epochs=1000,
                 patience=60, verbose=0, log=False):
        
        self._target = target
        self._population = Population(self._target, population_size)
        self._epochs = epochs
        self._patience = patience 
        self._memory = deque([], patience)
        self._verbose = verbose
        self._log = log
        
        if self._log:
            self._history = History()
    
    def start(self):
        '''進化を開始する'''
        try:
            get_ipython()
        except:
            is_ipython = False
        else:
            is_ipython = True
        
        for i in range(1, self._epochs + 1):
            max_body, *history = self._population.next_generation()
            
            if self._verbose == 0:
                if is_ipython:
                    r = i % 4
                    
                    if r == 0:
                        s = '\r↑'
                    elif r == 1:
                        s = '\r→'
                    elif r == 2:
                        s = '\r↓'
                    else:
                        s = '\r←'
                else:
                    s = f'\033[2K\033[G{max_body}'
                
                sys.stdout.write(s)
                sys.stdout.flush()
            
            elif self._verbose > 0:
                print(f'{self._population.generation_number} : {max_body}')
            
            if self._log:
                self._history.append(history)
            
            if history[1] == 1.0:
                if self._verbose == 0:
                    if not is_ipython:
                        sys.stdout.write('\033[2K\033[G')
                        sys.stdout.flush()
                    print(f'\r{max_body}')
                
                elif self._verbose > 0:
                    print([self._population.generation[0]])
                
                if self._log:
                    visualize(max_body, self._history)
                
                break
            
            self._memory.append(history[1])
            if self._memory.count(self._memory[-1]) == self._patience:
                if self._verbose == 0:
                    if is_ipython:
                        s = '\r※'
                    else:
                        s = '\033[2K\033[GCATASTROPHE OCCURED!'
                    sys.stdout.write(s)
                    sys.stdout.flush()
                elif self._verbose > 0:
                    print('CATASTROPHE OCCURED!')
                self._population.catastrophe()
        
        else:
            if self._verbose == 0:
                if not is_ipython:
                    sys.stdout.write('\033[2K\033[G')
                    sys.stdout.flush()
                print(f'\r{max_body}')
            
            if self._log:
                visualize(max_body, self._history)


def hello_world_with_ga():
    '''遺伝的アルゴリズムでhello, world'''
    ec = EvolutionController('hello, world', epochs=1000, patience=30, verbose=1, log=True)
    ec.start()


if __name__ == '__main__':
    ec = EvolutionController('hello, world', epochs=1000, patience=30, verbose=0, log=False)
    ec.start()

```