ムダにエボリューショナルな"hello, world"の出力方法(Python)
概要
<内容>
<経緯>
- トレンド入りしていた、ムダにクリエイティブな"Hello World"の出力方法一覧(Java)を見て、心に火がつきました。
- 『機械学習と深層学習《Pythonによるシミュレーション》』を読んで、遺伝的アルゴリズムを試してみたいと思っていました。
<結論>
- 出力に成功しました。
- 実行の様子は、以下をクリックすると、YouTubeの動画でご覧頂けます。
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
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
設計概要
設計は、以下のとおりとしました。
-
遺伝情報は長さ84のビット列で表現する。内訳は、１）文字列長（1~16）を表す4ビット、２）a-zや簡単な記号を含む32種類の文字を表す5ビット×16=80、である。
- なお、"hello, world"となるパターンは、「0b*****************0100110001101111010011100000000001010100100011000101010011011011」である。
-
個体は文字【 !,.?@abcdefghijklmnopqrstuvwxyz】からなる、長さ1~16の文字列である。個体の環境への適応度（fitness）は、指定された文字列との編集距離で測られる。
-
繁殖時、子供はビットごとに、両親いずれかの遺伝子を引き継ぐものとする。遺伝子の引き継ぎ後、突然変異が発生するものとする。突然変異は、子供の各ビットごとに一定確率で値を反転させるものである。
-
個体の集団は、適応度が上位20%のエリートと、残り80%の非エリートに分かれるものとする。エリート全員に繁殖の機会が与えられるが、その相手は非エリートである。これは、多様性を保つため、あるいは、近親相姦のタブーを表現するためである。なお、雌雄の区別はないものとする。エリート一体が複数体の子供を残すものとする。
-
次世代に残る候補は、１）エリートのうち12/16の確率でランダムに選ばれた個体、２）子供、３）非エリートのうち3/16の確率でランダムに選ばれた個体の３グループをまとめた中から、適応度の高い順に集団の上限サイズまで選ばれるものとする。
-
集団にはカタストロフィ（破局）が発生するものとする。破局発生時は、現世代のごく一部が生き残り、現世代の遺伝情報を引き継がない新個体群と共に、次世代を構成するものとする。これは、隕石の衝突などの大惨事を模したものである。
-
進化をつかさどる何かが状況を監視しており、集団の進化が停滞した際には、破局を引き起こし、さらなる進化を促すものとする。
遺伝的アルゴリズム、と言える内容だと思います。パレートの法則を取り入れたところや、局所的最適解からの脱出を図る破局の仕組みを取り入れたところが、特徴と言えるでしょうか。もちろん、遺伝的アルゴリズムは様々なバリエーションがあるわけですが、本記事では以上のアルゴリズムを採用したということです。
プログラム概要
プログラムの概要は、以下のとおりです。
-
クラス「EvolutionController」。進化をつかさどる何か。初期化時に、ターゲット文字列、集団の上限サイズ、世代交代の上限回数、破局を引き起こすまでの許容回数、出力の冗長性、ログの記録（グラフの表示）有無を指定できるようにする。進化する集団を監視し、その過程や結果を画面表示する。また、進化の停滞時——集団の最良個体の適応度が一定以上の世代に渡り変化しなかったとき——には、集団に破局を引き起こすものとする。
-
クラス「Population」。集団を表すクラス。「EvolutionController」の管理下で、世代交代を繰り返す。適応度の高い順にソートされた個体群を保持しており、カップリングと、次世代に生存する個体の選択に責任を持つ。世代についての情報——最良の個体の文字列表現、および、適応度の最小値、最大値、平均値、中央値——を、「EvolutionController」に提供するものとする。また、「EvolutionController」が破局の引き金を引いた際には、現世代からランダムに選択した個体以外を抹消。現世代の遺伝情報を引き継がない新個体群を発生させ、世代を一新する処理を行うものとする。
-
クラス「Individual」。個体を表すクラス。「Population」の管理下で、発生と繁殖を行う。ランダムに得た、あるいは、両親から引き継いだ遺伝情報を元に発現し、1~16の長さの文字列からなる身体と適応度を持つ。適応度は、ターゲット文字列との編集距離で測られる。遺伝情報はビット列なので、ビット演算を行い、遺伝情報を読み解くものとする。__gt__等のオペレータを実装し、「Population」が正しく個体の選択やソートを行えるようにする。繁殖を行う際には、やはりビット演算により、自身とパートナーの遺伝情報の引き継ぎ、および、子供の突然変異を行うものとする。
利用した技法や考え方
本プログラムの作成にあたっては、以下の技法や考え方を利用しました。
-
ビット演算
- 下位から取得したいビットのみを1としたマスクを用意し、対象ビット列とand演算を行う。実施後は、取得した分だけ右シフトし、次の取得ができるようにする。
- ランダムに発生させたビット列で親1とand演算を行い、親1の遺伝情報の一部を収集する。また、反転したマスクと親2のand演算を行い、親2の遺伝情報の残りを収集する。収集した遺伝情報をor演算で合成し、子供の遺伝情報とする。
- マスクの各ビットに一定の確率で1を立てる。マスクと子供のxor演算を行うことで、1を立てた箇所のビットを反転させ、突然変異とする。
-
拡張比較メソッドの実装
- クラス「Individual」に拡張比較メソッドを実装し、適応度による比較やソートを可能にする。
-
- 全体の数値の大部分は、全体を構成するうちの一部の要素が生み出しているという理論。80:20の法則、ばらつきの法則とも呼ばれる。繁殖の際、集団を20:80に分けている。また、次世代への生存確率も、エリートと非エリートでは比が80:20になるようにしている。
-
- レーベンシュタイン距離（レーベンシュタインきょり、英: Levenshtein distance）は、二つの文字列がどの程度異なっているかを示す距離の一種である。編集距離（へんしゅうきょり、英: edit distance）とも呼ばれる。具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される。個体の適応度を測る評価関数として利用している。詳細は、参考記事の二番目を参照。
-
コンソール出力の上書き
<参考記事>
感想
本プログラムを作成し、機械学習との共通点を感じました。
-
ハイパーパラメータによる調整が必要
- 集団あたりの個体数
- 一体の親が何体の子供を生むか
- 突然変異の発生率
- 破局の際、現行世代をどの程度残すか
-
局所的最適解を避ける工夫が必要
- あえてエリートと非エリートをカップリングさせる
- 突然変異
- 破局
-
評価関数の定義が必要
- 編集距離
また、本来「準最適解を短時間で見つける」のが遺伝的アルゴリズムの特徴だと思いますが、本記事で作成したプログラムは、破局の効果もあり、ほぼ確実に最適解の「hello, world」を見つけてくれますので、そこは達成感、満足感がありました。
一つ謎なのは、同程度の長さの文字列でも、なかなか最適解に到達しないものがあります。例えば、"john lennon"は、"hello, world"より一文字少ないのに、最適解への到達に苦労します。なぜでしょうね。
作成したプログラム
最後に、作成したプログラムを以下に示します。ご興味があれば、Google Colaboratoryなどで、お試しあれ。モジュールは、GitHubにもあります。
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()