はじめに
最近Youtubeで遺伝的アルゴリズムに関する動画をよく見ます。
段々とプログラムが成功に近づいていく様子が大変面白いです。
で、自分でもやってみたくなったので、今回遺伝的アルゴリズムを用いて迷路を解かせてみようと思います。
※今回コーディングがぐちゃぐちゃのぐちゃですが許してください
準備
まず、今回解かせる迷路を用意します。
クソ雑魚迷路
白色or黄色が通路です。灰色の箇所は壁で通れません。
左上の1がスタートで、右下の31がゴールです。
各マスの数字はスタートからの距離を表しており、より遠くまで(最終的にはゴール)移動することを目標とします。
迷路を解かせる個体を用意します。
個体は0～3までの整数31個からなる遺伝子を持っています。
[2, 3, 1, 1, 0, 2, 2, 0, 0, 2, 2, 3, 2, 1, 1, 1, 1, 2, 0, 0, 1, 0, 3, 1, 0, 1, 2, 2, 2, 2, 2]
各数字は移動する方向を表しています。
個体は遺伝子の左から、その数字が示す方向に移動しようとします。
ただし、移動先が壁の場合は移動せず、次の数字を読み込みます(つまり足踏みする)
こうやって遺伝子に従い移動/足踏みをすることでゴールになんとか近づいてくわけです。
おわかりかと思いますが、ゴールまでの距離が31、遺伝子の長さも31のため、
ゴールに辿り着くためには一度も足踏みすることなく、また道に迷わずに一直線でゴールに行く必要があります。
Youtubeの動画でもだいたいなんとかなってたからなんとかなるやろ！！
遺伝的なところ
世代ごとに10個の個体を用意して迷路を解かせます。
また、世代を交代するときに以下の操作を行い、次世代の10個体を生成します。
- 前世代で最も優秀な個体と2番目に優秀な個体を選出する
- 優秀な個体と2番目に優秀な個体を交叉させて、子供の個体を作る
- 各個体を生成後に突然変異を起こさせる(確率で突然変異するようにプログラムする)
次世代の10個体は以下のように生成します。
生成後に突然変異のプロセスを走らせて、突然変異させます。
個体1：前世代の最優秀個体
個体2：前世代の2番目に優秀な個体
個体3：個体1と個体2の交叉個体
個体4：個体1と個体2の交叉個体
個体5：個体1と個体2の交叉個体
個体6：個体1と個体2の交叉個体
個体7：個体1と個体2の交叉個体
個体8：個体1と個体2の交叉個体
個体9：ランダムに生成した個体
個体10：ランダムに生成した個体
※交叉や突然変異については下記の記事を参考にさせていただきました
【初心者向け】Re:ゼロから始める遺伝的アルゴリズム【人工知能】
実装
とりあえず書いてみた結果。
import numpy as np
import random
generation_length = 100 #世代の数
genom_length = 31 #遺伝子の長さ
seed_num = 10 #1世代ごとの個体
seeds = {} #個体の入れ物
seeds_score_all = {} #各個体のスコアの入れ物
best_seeds = {} #各世代のベスト個体
direction = {0 : [0, -1], 1 : [1, 0], 2 : [0, 1], 3 : [-1, 0]} #上下左右
mutant_ratio = 0.01 #突然変異率
generation = 0 #世代管理
top_second = [] #上位2位の個体のindexを収納
maze = np.array([[0,0,0,0,0,0,0,0,0,0,0,0], #迷路(1 = 通路 0 = 壁)
[0,1,1,1,0,0,1,1,0,0,1,0],
[0,0,0,1,1,1,1,0,1,1,1,0],
[0,1,1,1,0,1,0,0,1,0,0,0],
[0,0,0,1,0,0,1,1,1,1,1,0],
[0,1,1,1,0,1,1,0,0,1,0,0],
[0,1,0,0,0,0,1,0,1,1,1,0],
[0,1,1,1,1,1,1,0,1,0,1,0],
[0,0,0,1,0,0,0,0,1,1,0,0],
[0,1,0,1,1,1,1,1,0,1,1,0],
[0,1,1,1,0,1,0,1,0,0,1,0],
[0,0,0,0,0,0,0,0,0,0,0,0]])
distance = np.array([[0,0,0,0,0,0,0,0,0,0,0,0],#距離(1,1からの距離)=スコア
[0,1,2,3,0,0,8,9,0,0,26,0],
[0,0,0,4,5,6,7,0,23,24,25,0],
[0,7,6,5,0,7,0,0,22,0,0,0],
[0,0,0,6,0,0,19,20,21,22,23,0],
[0,9,8,7,0,19,18,0,0,23,0,0],
[0,10,0,0,0,0,17,0,25,24,25,0],
[0,11,12,13,14,15,16,0,26,0,26,0],
[0,0,0,14,0,0,0,0,27,28,0,0],
[0,19,0,15,16,17,18,19,0,29,30,0],
[0,18,17,16,0,18,0,20,0,0,31,0],
[0,0,0,0,0,0,0,0,0,0,0,0]])
def init_seed():#第0世代の個体の遺伝子を生成
for i in range(seed_num):
seeds[i] = []
for j in range(genom_length):
seeds[i].append(random.randint(0,3))#0-3の整数をランダムに生成
def score(seed):#個体のスコア
position = [1,1]
for i in range(genom_length):#遺伝子の順番に移動できるかを判定
if maze[position[0]+direction[seed[i]][0], position[1]+direction[seed[i]][1]] == 0:#移動先が壁の場合
continue
else:#移動先が通路の場合
position[0] = position[0] + direction[seed[i]][0]
position[1] = position[1] + direction[seed[i]][1]
return distance[position[0], position[1]]
def scoring():#個体のスコアを格納
seeds_score_all[generation] = []
for i in range(seed_num):
seeds_score_all[generation].append(score(seeds[i]))
def top_second_seed_choice():#世代ごとの優秀個体のindexを取得(1位2位)
global top_second
top_second.clear()
if len([i for i, v in enumerate(seeds_score_all[generation]) if v == max(seeds_score_all[generation])]) > 1: #1位が2つ以上ある場合はランダムに2つ選ぶ
top_second = random.sample([i for i, v in enumerate(seeds_score_all[generation]) if v == max(seeds_score_all[generation])], k=2)
else:
top_second.append(seeds_score_all[generation].index(max(seeds_score_all[generation])))
if len([i for i, v in enumerate(seeds_score_all[generation]) if v == sorted(set(seeds_score_all[generation]))[-2]]) > 1:#2位が2つ以上ある場合はランダムに2つ選ぶ
a = random.randint(0,len([i for i, v in enumerate(seeds_score_all[generation]) if v == sorted(set(seeds_score_all[generation]))[-2]])-1)
top_second.append([i for i, v in enumerate(seeds_score_all[generation]) if v == sorted(set(seeds_score_all[generation]))[-2]][a])
else:
top_second.append([i for i, v in enumerate(seeds_score_all[generation]) if v == sorted(set(seeds_score_all[generation]))[-2]][0])
def best_seed_choice():#世代ごとの最優秀個体の遺伝子を格納
best_seeds[generation] = seeds[top_second[0]]
def crossing_genom(seed1, seed2):#交叉
new_genom1 = []
new_genom2 = []
a = random.randint(0, genom_length)
b = random.randint(a, 31)
new_genom1 = seed1[:a] + seed2[a:b] + seed1[b:]
new_genom2 = seed2[:a] + seed1[a:b] + seed2[b:]
return new_genom1, new_genom2
def mutant():#突然変異
for i in range(0,seed_num):
for j in range(genom_length):
m = random.random()
if m <= mutant_ratio:
new_direction = random.randint(0,3)
while new_direction == seeds[i][j]:
new_direction = random.randint(0,3)
seeds[i][j] = new_direction
else:
continue
def make_seed():#次の世代の個体を生成する
global generation
new_seed = {}
new_seed[0] = seeds[top_second[0]]#前世代の1位
new_seed[1] = seeds[top_second[1]]#前世代の位
m1 = crossing_genom(seeds[top_second[0]], seeds[top_second[1]])
new_seed[2] = m1[0]#1位と2位の交叉
new_seed[3] = m1[1]#1位と2位の交叉
m2 = crossing_genom(seeds[top_second[0]], seeds[top_second[1]])
new_seed[4] = m2[0]#1位と2位の交叉
new_seed[5] = m2[1]#1位と2位の交叉
m3 = crossing_genom(seeds[top_second[0]], seeds[top_second[1]])
new_seed[6] = m3[0]#1位と2位の交叉
new_seed[7] = m3[1]#1位と2位の交叉
new_seed[8] = [random.randint(0,3) for i in range(genom_length)]#ランダム個体
new_seed[9] = [random.randint(0,3) for i in range(genom_length)]#ランダム個体
seeds.clear()
for i in range(seed_num):
seeds[i] = []
seeds[i] = new_seed[i]
def next_generation():#世代をすすめる
global generation
generation += 1
init_seed()
while generation < generation_length:
scoring()
top_second_seed_choice()
best_seed_choice()
if generation == generation_length - 1:
next_generation()
else:
make_seed()
mutant()
next_generation()
print(best_seeds[generation - 1]) #最終世代の最優秀個体
for i in range(0, generation - 1): #全世代全個体のスコア
print(seeds_score_all[i])
とりあえず100世代でやってみた結果。
[2, 3, 1, 1, 0, 2, 2, 0, 0, 2, 2, 3, 2, 1, 1, 1, 1, 2, 0, 0, 1, 0, 3, 1, 0, 1, 2, 2, 2, 2, 2]
[6, 1, 1, 4, 8, 4, 8, 9, 2, 6]
[9, 8, 1, 6, 6, 6, 9, 5, 4, 7]
[9, 9, 9, 9, 9, 9, 9, 9, 2, 3]
[9, 9, 9, 9, 7, 9, 9, 9, 7, 7]
[9, 9, 9, 9, 9, 9, 9, 9, 1, 5]
[9, 9, 9, 9, 9, 9, 9, 9, 7, 7]
[6, 9, 5, 9, 9, 6, 9, 9, 1, 7]
[9, 9, 1, 9, 9, 9, 9, 9, 2, 2]
[9, 9, 7, 9, 9, 9, 9, 9, 1, 6]
[7, 4, 1, 9, 9, 9, 9, 9, 5, 3]
[9, 9, 9, 9, 9, 9, 9, 9, 6, 2]
[9, 9, 9, 11, 9, 9, 9, 9, 7, 3]
[11, 9, 9, 1, 9, 1, 11, 9, 2, 6]
[11, 11, 11, 11, 11, 11, 10, 11, 2, 7]
[7, 11, 11, 11, 11, 11, 11, 11, 3, 7]
[11, 11, 11, 11, 11, 12, 11, 11, 1, 3]
[12, 11, 12, 11, 12, 11, 12, 11, 6, 6]
[12, 12, 12, 12, 12, 12, 12, 12, 7, 9]
[7, 12, 12, 12, 12, 12, 12, 3, 6, 5]
[12, 12, 12, 12, 2, 12, 12, 2, 2, 8]
[8, 12, 12, 12, 12, 12, 12, 12, 2, 3]
[6, 12, 12, 2, 12, 12, 12, 12, 3, 4]
[12, 7, 12, 12, 12, 13, 12, 12, 1, 6]
[13, 12, 7, 12, 13, 12, 13, 12, 4, 2]
[13, 13, 13, 13, 13, 13, 3, 13, 9, 6]
[13, 7, 12, 12, 3, 13, 13, 13, 3, 3]
[13, 13, 13, 13, 13, 13, 13, 13, 5, 4]
[13, 13, 13, 13, 13, 13, 13, 13, 4, 2]
[13, 6, 12, 13, 13, 13, 13, 13, 6, 2]
[13, 13, 13, 13, 13, 13, 13, 13, 7, 8]
[12, 13, 13, 13, 12, 13, 7, 13, 5, 4]
[12, 15, 13, 13, 13, 13, 12, 13, 7, 3]
[15, 12, 15, 13, 5, 12, 15, 13, 1, 1]
[15, 15, 15, 15, 3, 15, 15, 15, 5, 5]
[14, 15, 15, 15, 7, 15, 16, 15, 5, 1]
[16, 7, 16, 14, 10, 15, 14, 15, 7, 4]
[16, 16, 16, 16, 16, 16, 16, 16, 8, 1]
[16, 16, 16, 10, 16, 7, 16, 3, 1, 7]
[16, 16, 16, 16, 16, 16, 7, 16, 1, 7]
[16, 16, 16, 16, 7, 16, 16, 16, 1, 7]
[16, 16, 16, 16, 16, 16, 16, 16, 7, 3]
[16, 16, 16, 10, 16, 7, 16, 16, 6, 7]
[16, 16, 16, 16, 16, 16, 16, 16, 9, 7]
[16, 16, 5, 7, 16, 16, 15, 15, 5, 3]
[16, 16, 16, 16, 16, 16, 16, 16, 1, 9]
[16, 16, 16, 7, 16, 7, 16, 16, 6, 5]
[16, 16, 16, 16, 16, 16, 16, 16, 2, 5]
[16, 16, 16, 16, 16, 16, 16, 16, 6, 1]
[16, 16, 14, 16, 16, 16, 16, 16, 9, 8]
[7, 16, 16, 16, 16, 16, 16, 10, 7, 1]
[16, 16, 16, 16, 16, 16, 16, 16, 2, 1]
[16, 16, 16, 16, 16, 16, 16, 16, 5, 2]
[16, 10, 16, 7, 16, 16, 16, 10, 7, 6]
[7, 16, 16, 16, 16, 16, 16, 16, 5, 6]
[3, 16, 16, 16, 10, 16, 16, 16, 6, 4]
[16, 16, 3, 16, 3, 16, 16, 16, 3, 4]
[16, 16, 16, 3, 16, 16, 10, 16, 5, 2]
[16, 16, 16, 10, 16, 16, 16, 16, 5, 2]
[10, 16, 7, 16, 16, 16, 16, 16, 1, 2]
[16, 16, 16, 16, 14, 16, 16, 16, 7, 7]
[15, 16, 16, 16, 16, 16, 16, 16, 2, 1]
[16, 16, 16, 16, 16, 16, 16, 16, 2, 7]
[7, 14, 16, 16, 16, 16, 16, 16, 5, 7]
[16, 16, 16, 16, 16, 16, 3, 16, 5, 4]
[16, 16, 16, 16, 16, 16, 15, 16, 4, 6]
[16, 16, 16, 16, 16, 16, 16, 16, 3, 4]
[16, 16, 16, 16, 16, 16, 16, 16, 2, 3]
[16, 16, 16, 10, 16, 5, 10, 5, 1, 2]
[16, 16, 16, 16, 16, 16, 16, 15, 4, 2]
[16, 16, 5, 16, 16, 16, 16, 16, 6, 1]
[16, 16, 10, 16, 16, 16, 15, 5, 6, 7]
[7, 15, 16, 16, 16, 16, 16, 15, 2, 5]
[16, 16, 16, 16, 16, 16, 16, 16, 8, 9]
[16, 16, 16, 16, 5, 14, 16, 16, 7, 7]
[16, 16, 5, 16, 5, 16, 16, 16, 3, 10]
[5, 16, 10, 16, 7, 16, 16, 10, 1, 3]
[16, 16, 16, 16, 16, 5, 16, 16, 2, 1]
[16, 7, 16, 16, 16, 15, 16, 16, 5, 1]
[10, 16, 16, 16, 16, 16, 16, 16, 6, 2]
[16, 16, 16, 16, 16, 10, 16, 16, 3, 2]
[16, 16, 16, 16, 6, 16, 16, 16, 3, 2]
[16, 16, 16, 16, 10, 16, 16, 16, 5, 7]
[16, 16, 16, 16, 16, 16, 14, 16, 8, 1]
[16, 16, 16, 16, 16, 16, 16, 16, 7, 7]
[16, 16, 16, 16, 16, 16, 16, 16, 3, 5]
[16, 16, 16, 16, 16, 16, 16, 16, 8, 2]
[16, 10, 16, 16, 16, 16, 16, 16, 4, 7]
[16, 16, 16, 16, 16, 16, 16, 15, 5, 2]
[16, 16, 16, 16, 16, 16, 16, 16, 3, 1]
[16, 15, 16, 16, 16, 16, 16, 14, 4, 7]
[16, 16, 16, 16, 16, 16, 16, 16, 5, 5]
[10, 16, 16, 16, 16, 16, 16, 16, 1, 3]
[16, 16, 16, 16, 16, 16, 14, 14, 6, 7]
[16, 16, 16, 16, 16, 16, 16, 16, 5, 5]
[16, 16, 16, 16, 16, 16, 16, 16, 7, 7]
[16, 16, 16, 16, 16, 5, 16, 16, 5, 3]
[16, 16, 16, 16, 16, 16, 16, 16, 5, 4]
[16, 15, 10, 16, 15, 16, 16, 16, 3, 1]
[16, 16, 16, 16, 10, 16, 16, 5, 8, 8]
最終スコア16で想像以上に迷路攻略が進んでません。
というか、30世代くらいからずっとスコア16やんけ！！！
ならば1000世代くらいやればなんとかなるんやろか。
くっそ長いのでスコアの最後の方だけ抜粋
[18, 18, 16, 18, 18, 18, 18, 18, 4, 3]
[18, 18, 18, 18, 18, 18, 18, 18, 1, 4]
[18, 18, 18, 18, 18, 18, 5, 18, 3, 7]
[18, 17, 18, 18, 18, 18, 18, 18, 6, 7]
[18, 18, 18, 15, 18, 18, 18, 18, 4, 1]
[18, 18, 18, 18, 18, 17, 5, 18, 1, 2]
[5, 18, 18, 18, 18, 18, 18, 18, 2, 4]
[18, 18, 18, 18, 18, 16, 16, 18, 3, 1]
[18, 16, 18, 18, 18, 16, 7, 18, 1, 8]
[18, 16, 18, 18, 18, 18, 18, 18, 1, 1]
[16, 18, 18, 18, 18, 18, 18, 18, 7, 4]
[18, 18, 18, 18, 18, 18, 18, 18, 3, 3]
[18, 18, 18, 18, 16, 18, 18, 5, 3, 10]
[7, 18, 18, 18, 18, 18, 18, 18, 7, 4]
[18, 18, 18, 18, 18, 18, 18, 18, 1, 6]
[18, 18, 18, 16, 18, 14, 16, 18, 3, 4]
[14, 14, 18, 14, 18, 18, 14, 18, 5, 5]
[18, 18, 18, 18, 18, 18, 16, 5, 2, 10]
[18, 18, 18, 14, 18, 18, 18, 18, 6, 4]
[14, 18, 5, 18, 16, 18, 18, 14, 4, 2]
[18, 18, 16, 14, 18, 7, 18, 18, 8, 1]
[18, 18, 18, 18, 18, 18, 18, 18, 8, 6]
[18, 18, 18, 5, 18, 18, 18, 18, 1, 5]
[18, 18, 14, 18, 18, 18, 18, 18, 3, 6]
[18, 18, 18, 18, 18, 18, 16, 18, 5, 1]
[18, 18, 18, 14, 18, 18, 5, 14, 4, 3]
[18, 16, 13, 18, 18, 18, 18, 18, 5, 3]
[16, 18, 18, 18, 16, 14, 5, 18, 3, 7]
[18, 18, 18, 14, 18, 7, 18, 7, 3, 9]
[14, 18, 18, 18, 18, 18, 18, 18, 2, 3]
[18, 18, 18, 18, 18, 18, 16, 18, 8, 1]
[18, 18, 6, 16, 18, 18, 18, 17, 5, 11]
[18, 18, 18, 18, 18, 18, 5, 16, 7, 8]
[18, 7, 18, 18, 7, 18, 18, 18, 7, 1]
[14, 18, 18, 18, 18, 18, 16, 14, 4, 3]
[16, 18, 18, 18, 18, 18, 18, 16, 7, 2]
んースコア18ぃ？？？？
このあと何度か試してみましたが、スコアが高くても22程度で、ゴールには到達しませんでした。
また、世代数が多いと学習が進むかというとそうでもなく、大体14～20の間で推移してました。
気になるのは、世代が進むと同スコアの個体が多くなるということです。
これはどういうことなんやと、最終世代の各個体の遺伝子を調べてみます。
[19, 19, 19, 19, 19, 19, 19, 19, 7, 5]
[1, 1, 2, 2, 1, 1, 1, 0, 3, 2, 1, 2, 0, 2, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 3, 1, 3]
[1, 1, 2, 2, 1, 1, 1, 0, 3, 2, 1, 2, 0, 2, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3]
[1, 1, 2, 2, 1, 1, 1, 0, 3, 2, 1, 2, 0, 2, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3]
[1, 1, 2, 2, 1, 1, 1, 0, 3, 2, 1, 2, 2, 2, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3]
[1, 1, 2, 2, 1, 0, 1, 0, 3, 2, 1, 2, 0, 2, 1, 1, 2, 2, 0, 0, 3, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3]
[1, 1, 2, 2, 1, 1, 1, 0, 3, 2, 1, 2, 0, 2, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3]
[1, 1, 2, 2, 1, 1, 1, 0, 3, 2, 1, 2, 0, 2, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3]
[1, 1, 2, 2, 1, 1, 1, 0, 3, 2, 1, 2, 0, 2, 1, 1, 2, 2, 0, 0, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3]
[1, 2, 3, 0, 3, 3, 1, 3, 3, 0, 0, 0, 0, 0, 2, 1, 2, 3, 2, 0, 0, 1, 1, 1, 3, 0, 1, 1, 1, 0, 0]
[0, 3, 3, 1, 0, 0, 3, 3, 1, 3, 3, 3, 0, 1, 2, 2, 0, 1, 2, 1, 2, 0, 2, 1, 0, 1, 0, 1, 2, 2, 1]
100世代後の個体10個の遺伝子です。
1行目が最終世代のスコアで下10行が個体ごとの遺伝子です。
見て分かる通り、個体1～個体8までがほとんど一緒の遺伝子になってます！！！！
考察ですが、個体3～個体8を最優秀個体と2番目に優秀な個体との交叉で生成し続けたため、
近親交配状態となり、遺伝子がほとんど変化しなくなってしまったためかと思われます。
そのため、より優秀な個体となるためには突然変異か、個体9と個体10のランダム個体に頼らざるを得なくなってしまい、
多様性が失われてしまったんですね。
まとめ
軽い気持ちでコーディングしてみましたが、生物にとって多様性が重要ということがよくわかりました。