PythonでL-SystemをGAさせてみました。
流行りのプログラミング言語Pythonを用いて人工生命モデルのL-Systemを選択式遺伝的アルゴリズム（GA）を用いて進化させるプログラムを書いてみました。
できたもの：
https://colab.research.google.com/drive/1DKnFdlqc3hgfg6X3S7ZbLSqS-AnDmd3B?usp=sharing
Google Colaboratoryを用いて、クラウド上でPythonを動かし、L-Systemを作りました。L-Systemの描画ルールであるgenerator文字列を遺伝子に見立て、遺伝的アルゴリズム(GA)の手法で進化させていきます。
#PythonでL-SystemをGAする。 bbd
#昔どこかで見たようなシミュレーションを作りたくなりました。
#思い付きだけでなんとかなる時代にITの進化を実感しました。
#参考にした記事
#PythonエンジニアによるPython3学習サイト
#https://www.python.ambitious-engineer.com/
#E.V.ジュニアさん
#PythonでL-Systemsを作る(5) 植物の成長システム
#https://note.com/evjunior/n/nab0229b23b40
import numpy as np
import matplotlib.pyplot as plt
import random
#後で使用する変数
drawcolor = 'green'
repeat = 4
distance = 2 * (1 / 2) ** repeat
#スコープ不明の変数。とりあえず作成
state = [[0, 0], 0]
initiator = ""
generator = {"":"", "":""}
angle = 0
stack = []
com = initiator
def forward(st, axis):
th = st[1]
x1 = st[0][0]
y1 = st[0][1]
x2 = x1 + distance * np.cos(th)
y2 = y1 + distance * np.sin(th)
axis.plot([x1, x2], [y1, y2], lw = 1, color = drawcolor)
return [[x2, y2], th]
def rotate(coef, st):
th = st[1]
th = th + coef * angle
return [st[0], th]
def turtle(command, st, axis):
if command == "A" or command == "F":
st = forward(st, axis)
if command == "+":
st = rotate(1, st)
if command == "-":
st = rotate(-1, st)
if command == "[":
stack.append(st)
if command == "]":
#スタックアンダーフローに備える。
if (len(stack) > 0):
st = stack.pop()
return st
def drawOne(coms, st, axis):
#ひとつ描く
for i in range(repeat):
coms = coms.translate(str.maketrans(generator))
for command in coms:
st = turtle(command, st, axis)
def sRandom():
#ランダムでgeneratorの文字を与える。
#頻度を考慮している。
return random.choice(('A', 'A', 'A', 'F', '+', '-', '[', ']'))
def genRandomStr(n):
#n文字のgenerator文字列を作成する。
s = ''
for i in range(n):
s = s + sRandom()
return s
def mutation(s, n):
#n回突然変異を起こす。
p = random.randint(0, len(s) - 1)
for i in range(n):
s = s[:p] + sRandom() + s[p + 1:]
return s
def crossover(pa):
#2組のリストpaをランダムな位置pで交叉する。
p = random.randint(1, len(pa[0]) - 2)
res = ["", ""]
res[0] = pa[0][:p] + pa[1][p:]
res[1] = pa[1][:p] + pa[0][p:]
return res
#初期値は既知のパターン
parents = [ "FA[+F[+FA][-F]][-FA[+F][-F]]", "F-[[A]+A]+F[+FA]-A" ]
nRows, nCols = 2, 5
#メインループ
nGen = 1
while True:
#作図領域の初期化を行う。
fig, ax = plt.subplots(nRows, nCols, figsize = (12, 6))
i = 0
for r in range(nRows):
for c in range(nCols):
ax[r, c].axis([0, 8, 0, 8])
ax[r, c].axis("off")
ax[r, c].text(0.1, 0.1, hex(i)[2:])
i = i + 1
#parentよりchildrenを得る。
children = []
while True:
#遺伝子は任意の位置で交叉する。
cv = crossover(parents)
cv0 = cv[0]
#一定確率で突然変異する。
if random.randint(0, 9) == 0:
cv0 = mutation(cv0, 1)
#リストに追加する。
children.append(cv0)
#childrenを整理し重複をなくす。
children = list(set(children))
#遺伝子が一定数増えるまで繰り返す。
if len(children) >= nRows * nCols:
break
#作図を行う。
i = 0
for curRow in range(nRows):
for curCol in range(nCols):
state = [[4, 1], np.pi / 2]
initiator = "A"
generator = {"F":"FF", "A":children[i]}
angle = 22.5 / 180 * np.pi
stack = []
com = initiator
drawOne(com, state, ax[curRow, curCol])
i = i + 1
fig.suptitle("Gen:" + str(nGen) + " parents[0]:" + parents[0] + " parents[1]:" + parents[1])
plt.show()
#次の世代へ残す個体を選択する。例:"01"、"00"など。”?"で現世代のgeneratorを表示する。
sel = ""
while True:
sel = input("選択:")
if sel == "?":
for j in range(len(children)):
print(str(j) + ":" + children[j])
else:
break
#選択された個体を親にする。
parents[0] = children[int(sel[0])]
parents[1] = children[int(sel[1])]
nGen = nGen + 1処理の流れ：
1.親となる遺伝子をリストにします。
2.両親の遺伝子を任意の場所で「交叉」させ、たまに「突然変異」させます。
3.５＊２＝１０通りの遺伝子を作り、その遺伝子を元に、L-Systemのルールに従い、展開した表現型を得ます。
4.作図を行います。
5.プロンプトを表示し、ユーザーに次の世代の親を決めてもらいます。
6.最初に戻ります。
荒削りながら、プロトタイプとなるプログラムができました。こんなに短時間で、作りたいものを描き出せるPythonの実力を知ることができました。
きっかけ：
私の友人がFacebookでGeneticAlgorithmについての話をしていたことがきっかけでした。
私も久しぶりにGeneticAlgorithmを使って遊んでみたくなりました。かといって、新しいアイデアがあるわけではなく、昔どこかで見たことがあるようなシミュレーションを勉強を兼ねて取り組んでみたいと思いました。
私は学生時代にニューラルネットワークに関する研究をしていて、入社後も人工知能や人工生命について個人的に興味を持っていました。趣味者としての取り組みであまり実用的な活用法は考えず、シミュレーションを見て楽しむ程度でした。その当時は計算速度も遅く、今のような視覚化ライブラリも乏しかったため、書籍で勉強してもそれを試せなかったり、貧弱な出力を見て自己満足するレベルでした。
それから二十数年。。。ニューラルネットワークはディープラーニングの発展により再び脚光を浴び、また画像処理を中心にAIが活躍できる領域が生まれてきました。なにより、オープンソース化でこれらの技術がひろく共有され、簡単に利用できる環境が用意されていることに驚いています。
かねてよりPythonはIT業界の一員としてどこかで絡んでおかないとまずい。と感じていました。最近よく面接で「Pythonやってます。」と言われることが多くなってきています。「最近流行ってますものね。」程度しか返せていませんでした。これはちょっと残念なことです。もっと気の利いた突っ込んだ話がしたいと思ってました。
L-Systemは人工生命が流行ったころに少しかじっていました。LOGOのタートルグラフィックスに与える命令を工夫しルールを展開することで様々な図形を作図することができます。シンメトリーな幾何学模様だけでなく、アシンメトリーな自然樹形のような形状も作図できるため、ゲームの背景に使う樹木をこの方法で作成されることもあるようです。
行動命令を文字列で記述します。例えば「F-[[A]+A]+F[+FA]-A」のように表現します。
意味は次のとおりです。
F、A：前へ進む。
＋：左へある角度回転する。
ー：右へある角度回転する。
［：現在の位置と向きを保存棚に積む。
］：保存棚から位置と向きを得る。
次のターンでは、F→FF、A→F-[[A]+A]+F[+FA]-Aのように展開します。これを所定の回数繰り返します。このような比較的単純なルールで自然の植物に似た形状が描画できるのです。
ただ、元となる「F-[[A]+A]+F[+FA]-A」のような遺伝子を考えるのは非常に難しいことです。そこで、遺伝的アルゴリズム（GA）の出番です。
遺伝子を「交叉」「突然変異」させながら、その評価を行い、進化させていくことができます。パターンを自ら考える必要はなく、良いものを選択するだけです。
これは育種家の仕事に似ています。掛け合わせを繰り返し新しい品種を作るような作業です。
実はこの作業は非常に粗削りな手法です。L-Systemのルールの中には「［」、「］」があります。これは本来は対になって使用されなければならず、括弧の数が合っていないとダメなものです。
トマス・レイ博士の作った「Tierra」というシステムがあります。これは、架空のコンピュータ内にアセンブラで書かれたプログラムを並列で実行しながら、自己複製、交叉、突然変異を繰り返し、進化する様子を垣間見るものです。架空のマシン語が突然変異でつじつまが合わなくなったとき、「NOP」（No OPration）として処理をしていました。
これを真似て、今回作ったシステムもできた遺伝子に厳格な構文チェックを行わず、スタックアンダーフローの対策を施しています。
Amazonプライムで「スタートレック・ピカード」を観ました。ここでも人工生命（アンドロイド）がテーマになっていました。やはりここらでもう一度人工生命をやっといた方がよいのか？と思い始めました。
まずはPythonの勉強から始めました。
本屋で立ち読みしたり、ネットで情報を収集しながら勉強の方法を探っておりました。
私の場合、下記のサイトがとても役立ちました。
PythonエンジニアによるPython3学習サイト
https://www.python.ambitious-engineer.com/
初心者向けの俯瞰を一通り読むと、Pythonのコードのおおよその感じが掴めてきました。
・for文
・タプル
・配列のマイナスインデックス
・関数の複数戻り値
など、新鮮な概念がたくさんありました。
また、Pythonの動作環境を模索しているうち、VSCodeではなく、Google Colaboratoryを用いる手段を学びました。
googleのアカウントがあるだけで、クラウド上で開発環境が手に入るなんて驚きです。
次にL-Systemについて探しました。
E.V.ジュニアさん
PythonでL-Systemsを作る(5) 植物の成長システム
ドンピシャな記事が見つかり驚きました。タートルグラフィックスからL-Systemへ至るまでを学びました。今回のプログラムはこの記事で紹介されていたものをベースにしています。
最後に遺伝的アルゴリズムを組み込みました。
昔どこかで見たことがある、選択型の遺伝的アルゴリズムです。ここからは自力でプログラミングしていきます。
・画面を分割して描画する。
・描画ルーチンを関数化する。
・遺伝子の「交叉」、「突然変異」を実装する。
・次の遺伝子を選択する。
などの処理が必要になります。
・画面を分割して描画する。
matplotlibを用いて、グラフをたくさん書きました。細かい部分でやりたいことはたくさんあるものの、ほぼほぼ満足のいく出来栄えです。
・描画ルーチンを関数化する。
これには少してこずりました。drawOne()という関数にまとめたところ、エラーが頻発しました。「local variable 'com' referenced before assignment」といった感じです。
ローカル、グローバル 変数のスコープがまだよくわかっていません。Cプログラマーの悲しい性、変数の宣言が欲しくなりました。
・遺伝子の「交叉」、「突然変異」を実装する。
def sRandom():
#ランダムでgeneratorの文字を与える。
#頻度を考慮している。
return random.choice(('A', 'A', 'A', 'F', '+', '-', '[', ']'))
def genRandomStr(n):
#n文字のgenerator文字列を作成する。
s = ''
for i in range(n):
s = s + sRandom()
return s
def mutation(s, n):
#n回突然変異を起こす。
p = random.randint(0, len(s) - 1)
for i in range(n):
s = s[:p] + sRandom() + s[p + 1:]
return s
def crossover(pa):
#2組のリストpaをランダムな位置pで交叉する。
p = random.randint(1, len(pa[0]) - 2)
res = ["", ""]
res[0] = pa[0][:p] + pa[1][p:]
res[1] = pa[1][:p] + pa[0][p:]
return ressRandom()関数のこだわりポイントは、「A」の出現回数をほかより多くしたかったため、数を増やしています。
mutation()関数は突然変異させるため、乱数で変化させる文字数を得て、そこに乱数で得た文字を当てはめています。Pythonのクセの強いリストへのアクセス方法を学ぶことができました。
crossover()関数はリストを返す関数です。ポインタとかハンドルとかややこしいことを考えずとにかく直球勝負で組んでいきます。
・次の遺伝子を選択する。
matplotlibで図形を表示させた後、input()関数を用いて、文字列の入力をしています。実行の仕方によっては、うまくinput()関数が表示されないことがあります。原因はまだよくわかっていませんが、とにかく動くので、今は良しとします。「01」、「00」など、0から9までの数字を2つ入力します。
しばらく遊んでいると、とても良いパターンへ進化することがあります。この時のために「?」というコマンドを作成しました。
0:FA[+F[+FA][[+FA]-A
1:FA[[A[+A]+F[+FA]-A
2:FA[+F[+FA][-FFA]-A
3:FA[+F[+A]+F[+FA]-A
4:FA[+F[+FA][-F]A]-A
5:FA[+F[+FA][-F]][-FA[
6:FA[+F[+F]+F[+FA]-A
7:FA[[A]+A]+F[+FA]-A
8:FA[+F[+FA][-F]][-FA[+F]
9:FA[+F[+FA][-+FA]-Aのように遺伝子を表示できます。
さいごに
とにかく、あまり難しく考えずコーディングができるところが面白いです。リストのアクセスは少し癖がありますが、その他はとてもシンプルに記述できるのでとても気に入りました。
あと、ネット上での情報量が豊富すぎます。ヘルプを見るよりググった方が早いという不思議な体験をしました。ググると欲しい情報がピンポイントで見つかり、今組んでいるコードにそのまま組み込めてしまいます。Google Colaboratoryだと、別のセルへ開発中の関数を抜き出して、テストがドンドンできます。ネットから探してきてコピペして、ちょっといじってのくり返しです。良いとか悪いとかではなく、こんな世の中なのかと感じ入りました。これは、ネットがなくなったら大変なことになるなと恐ろしくなりました。
また、私にとっては、変数の宣言がないのはとても気持ち悪いです。確かに私が最初に覚えたBASIC言語は変数宣言しても、しなくてもよい言語でした。プログラミングスキルが上がるにつれ、変数宣言をきちんとする習慣が身につきました。これは慣れの問題なのでしょうか。しばらく時間が必要です。
これを作って、ちょっと乗ってきました。次なるステップは野鳥動画の解析に機械学習を利用することです。なんだかできそうな気がしてきました。
#Python #L-System #GA 人工生命 #遺伝的アルゴリズム
この記事が気に入ったらサポートをしてみませんか？