遺伝的アルゴリズムの練習で迷路を解かせてみた

機会学習を触ってみようと思い立ち、
個人的に最もとっつきやすかった「遺伝的アルゴリズム」で、とりあえず何か作ってみようと試みました。

そんな事情から、この記事は、pythonも機会学習も初心者な筆者が、
ほぼ備忘のために記載していきます。
(誤ったことを書いていたらご指摘くださると大変ありがたいです)

ちなみに、今回ご紹介するプログラムは、下記githubにコミットしてあります。
もしご興味があれば、ご覧ください。
https://github.com/holothuria/Genetic_labyrinth

##そもそも遺伝的アルゴリズムとは
遺伝的アルゴリズムとは、生物の遺伝子を模したアルゴリズムです。
まるで進化していくかのように学習させ、解法を導くアルゴリズムです。

ちなみに。生物を模しているためか、遺伝的アルゴリズムには、色々と用語がありますが、
ほとんど生物学の用語そのままです。生物系出身の人はとっつきやすいかと思います。

####・導入(生物なお話)
遺伝的アルゴリズムは、「遺伝的」という名が表す通り、生物と遺伝子を模しています。
折角なので、少し導入として、生物のお話をします。

生物のいる自然界では、優れた個体が生き残り、劣っていれば数は減っていきます。
あまりにも環境に適応できていなければ、そのまま滅んでしまうこともあるでしょう。

例えば、キリンは、皆さんご存知の通り、首が長いです。
しかしながら、キリンも、ご先祖からして元から首が長かったわけではありません。
キリンの住む環境では、首が長いほど有利だったからこそ、首が長い個体の方が生き残り、子孫を残し、集団全体として、段々と首が長くなっていったのです。

そんな、有利なものほど生き残る、という過程を、プログラムで再現したのが、遺伝的アルゴリズムです。

####・とてもざっくりと書くと
プログラムとしてやることは以下のような感じです。

1.優秀さを数値として判定する
2.優秀なものだけ残し、後は切り捨てる
3.優秀なものから多少変えて、たくさん複製する
4.たくさん複製した中でも、優秀なものを選び出す

で、後は「2.」～「4.」を繰り返すようなイメージです。
そうすると、段々と優秀なものが残り、全体の優秀さが上がっていきます。

####・少し詳細にざっくりと書くと
以下のような感じです。
・「遺伝子」を持つ「個体」がいます。
　※ここでいう「遺伝子」は、例えば、「迷路の経路」等に当たります。
・「個体」の集合は「個体群」と呼ばれます。
・「遺伝子」は「個体」同士で交わったり(「交叉」)、「突然変異」したりし、変化していきます。
・成績が良い(「適応度」が高い)「遺伝子」を持つ「個体」だけが生き残り、次の個体群となります(「淘汰」)。
　※成績の付け方はプログラミング次第。ここが一番重要そう。
・上記の「交叉・突然変異」と「淘汰」を繰り返す(「世代」を重ねる)事で、徐々に正解に近づいていきます。

この辺りは、もっと詳しく正しいことが書いてある記事がたくさんありますので、
そちらを参照いただければと思います。

今回解く迷路の条件

###サイズ
10*10マス

###終了条件
外に出る、壁に触れる、ゴールする

###イメージ
白い四角が壁で、「・」と「◎」が経路、「S」「G」がスタートとゴールです。

今回用いた迷路用遺伝的アルゴリズムの設定

####・遺伝子
　迷路の経路を保持します。
　x軸とy軸で、[x,y]の形で1つとし、この連なりが遺伝子となります。
　例)「[1,3][2,3][2,4][2,5]」であれば、「[1,3]から右下下に移動し[2,5]にいる」ことを表します。

####・個体群
　個体が100保持されています。

####・交叉
　2つの個体の内、同じ座標を通っている遺伝子で2点を選択し、その2点間を入れ替えます。
　イメージ)
　　個体1：◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆◆
　　個体2：◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇
　　　↓
　　個体1：◆◆◆◆◆◆◆◆◇◇◇◇◇◇◇◆◆◆◆◆◆◆◆◆
　　個体2：◇◇◇◇◇◇◇◇◆◆◆◆◆◆◆◇◇◇◇◇◇◇◇◇

####・突然変異
　挿入：経路の最後の位置に、上下左右の内ランダムな方向へ進む遺伝子を追加します。
　欠損：ランダムな位置の経路を消失させます。

####・適応度
　ゴールしていない場合：壁を無視した、ゴールまでの最短距離が短いほど優秀とします。
　ゴールしている場合：ゴールまでにかかった経路が短いほど優秀とします。

実際に作成したプログラム

ここからは、実際にどのようなプログラムを作成したか綴っていきます。
大枠の部分しか載せていません。
細かい部分まで気になる方は、どうかgithubの方のソースでお願いします。

###・遺伝子(gene)
開始時に、遺伝子をランダムに生成します。
遺伝子の0番目はスタート位置で固定で、それ以降は、ランダムな座標を作製し、遺伝子の末尾に付与しています。
長さは20~70までで、ランダムに決定されます。

初期の遺伝子作成コード

individual.py

	# ランダムに初期遺伝子を決定するメソッド
	def gene_creater(self, start_position):
		self.gene = [start_position]
		for i in range(random.randint(20,70)):
			self.end_insertion()
	

末尾にランダムな移動先座標を付与するメソッドの中身は、下記の通りです。
その時遺伝子に存在している、最後尾の座標を取得します。
その後、その最後尾の座標から、上下左右に移動に移動した際の座標を、遺伝子に追加しています。

遺伝子追加メソッド

individual.py

	# 遺伝子の最後に遺伝子を追加するメソッド
	def end_insertion(self):
		# 最後の座標を取得
		add_gene = copy.copy(self.gene[len(self.gene) - 1])
		
		# 取得した座標から、ランダムに上下左右に移動
		direction = random.randint(0,3)
		if direction == 0:
			add_gene[0] = add_gene[0] - 1
			
		elif direction == 1:
			add_gene[0] = add_gene[0] + 1
			
		elif direction == 2:
			add_gene[1] = add_gene[1] - 1
			
		elif direction == 3:
			add_gene[1] = add_gene[1] + 1
			
		# 移動した座標を遺伝子に追加
		self.gene.append(add_gene)

###・突然変異
突然変異では、挿入と欠損を行います。
挿入は、上記の初期生成時と同じメソッドを使用しています。
挿入、欠損回数は、どちらもランダムです。
回数のランダムさは、遺伝子の長さが影響し、挿入は短いほど、欠損は長いほど、回数が増えるように設定しています。

ga_main.py

	# 突然変異メソッド
	def mutation(self, individual):
		
		# 挿入
		while True:
			if random.randint(0, 99) <= 80:
				break
			individual.end_insertion()
		
		# 欠損
		while True:
			if len(individual.get_gene()) <= random.randint(15, 99):
				break
			individual.missing()

######欠損
欠損は、遺伝子のランダムな1ヵ所を削除し、その地点よりも後ろをずらします。
例えば、遺伝子が「[1,2][1,3][2,3][3,3]」とあったとして、2番目の[1,3]が欠損した場合、
[1,2]から下に行った事実が消滅し、「[1,2][2,2][3,2]」となります。

individual.py

	# 遺伝子のどこかを欠損させるメソッド
	def missing(self):
		
		# 欠損位置をランダムに決定
		missing_gene_id = random.randint(1, (len(self.gene) - 1))
		
		# 指定位置の遺伝子を欠損させる
		missing_gene = self.gene.pop(missing_gene_id)
		
		# 差分の取得
		diff_x = self.gene[missing_gene_id - 1][0] - missing_gene[0]
		diff_y = self.gene[missing_gene_id - 1][1] - missing_gene[1]
		
		# 欠損位置より後ろの遺伝子を、差分の量だけずらす
		for i in range(missing_gene_id, len(self.gene)):
			self.gene[i][0] += diff_x
			self.gene[i][1] += diff_y

###・交叉
交叉は、2個体の遺伝子を、2点間で交換します。
同じ座標を通る場所を起点とします。

例えば、[8,7]と[1,3]の2つをどちらも通る2つの個体がいたとします。
[8,7]以前と[1,3]以後の遺伝子は元のまま、[8,7]と[1,3]の間の部分のみ、2つの遺伝子で入れ替えます。

ga_main.py

	# 交叉メソッド
	def crossover(self, individual_pair):
		
		# それぞれを暫定的に雄雌として格納
		gene_male = individual_pair[0].get_gene()
		gene_female = individual_pair[1].get_gene()
		
		# 交叉
		for i in range(5):
			# 雄側の1つ目の交叉起点の確認
			male_cross_pos_1 = random.randint(1, len(gene_male) - 1)
			
			try:
				# 雄側と一致する、雌側の1つ目の交叉起点の確認
				female_cross_pos_1 = gene_female.index(gene_male[male_cross_pos_1])
				
			except ValueError as e:
				# 交叉起点が一致しなかった場合は再検索
				continue
			
			# 2つ目の交差点検索
			for j in range(10):
				
				# 雄側の2つ目の交叉起点の確認
				male_cross_pos_2 = random.randint(1, len(gene_male) - 1)
				
				try:
					# 雄側と一致する、雌側の2つ目の交叉起点の確認
					female_cross_pos_2 = gene_female.index(gene_male[male_cross_pos_2])
					
				except ValueError as e:
					# 交叉起点が一致しなかった場合は再検索
					continue
					
				# 交差点の位置関係が正しいか確認し、位置関係が逆であれば再検索
				if male_cross_pos_1 <= male_cross_pos_2:
					if female_cross_pos_2 <= female_cross_pos_1:
						continue
				if male_cross_pos_2 <= male_cross_pos_1:
					if female_cross_pos_1 <= female_cross_pos_2:
						continue
				
				
				# 1つ目の座標の方が小さくなるように変更
				if male_cross_pos_2 <= male_cross_pos_1:
					tmp = male_cross_pos_2
					male_cross_pos_2 = male_cross_pos_1
					male_cross_pos_1 = tmp
				if female_cross_pos_2 <= female_cross_pos_1:
					tmp = female_cross_pos_2
					female_cross_pos_2 = female_cross_pos_1
					female_cross_pos_1 = tmp
				
					
				# 位置関係が正しければ、交叉を行う
				male_gene_lead = gene_male[:male_cross_pos_1]
				male_gene_middle = gene_male[male_cross_pos_1:male_cross_pos_2]
				male_gene_end = gene_male[male_cross_pos_2:]
				female_gene_lead = gene_female[:female_cross_pos_1]
				female_gene_middle = gene_female[female_cross_pos_1:female_cross_pos_2]
				female_gene_end = gene_female[female_cross_pos_2:]
				
				# 中央部のみ雌雄を入れ替えて格納
				new_male_gene = male_gene_lead + female_gene_middle + male_gene_end
				new_female_gene = female_gene_lead + male_gene_middle + female_gene_end
				
				# 交叉した雌雄を格納
				individual_pair[0].set_gene(new_male_gene)
				individual_pair[1].set_gene(new_female_gene)
				
				# 交叉した個体ペアを返却
				return individual_pair
		
		
		# 交叉せず個体ペアを返却
		return individual_pair

###・淘汰
適応度の高い個体を厳選します。
個体群の中から10個体を選び、最も適応度の高い個体を個体群プールに保持します。
個体群プールがいっぱいになったら、その中から2個体を選出します。
選出後、交叉と突然変異を行い、適応度を計測します。
最も高い適応度の遺伝子は登録しておきます。

ga_main.py

	# 選出メソッド
	def selection(self):
		
		# 個体群プールの生成
		population_ark = []
		
		# 最優秀個体のセットとリセット
		population_ark.append(self.top_individual)
		self.top_individual = None
		
		# 優秀な個体の選出
		for i in range(len(self.population) - 1):
			individualList = []
			
			# 個体群からランダムに10個体を選択する
			for j in range(10):
				individualList.append(self.population[random.randint(0, len(self.population) - 1)])
				
			population_ark.append(self.tournament(individualList).clone())
		
		next_population = []
		
		# 遺伝子の変異
		for i in range(len(population_ark) // 2):
			
			individual_pair = []
			# 個体プールから順に2個体を選出する(直前に順番含めランダムのため、こちらで再度ランダムにする必要はない)
			for j in range(2):
				individual_pair.append(population_ark.pop(len(population_ark) - 1))
				
			# 個体ペアを交叉及び突然変異させる
			for individual in self.crossover(individual_pair):
				# 突然変異させる
				self.mutation(individual)
				
				# 適応度の再計算
				self.fitness_calc(individual)
				
				# 次世代個体群に追加
				next_population.append(individual)
		
		# 確定した次世代個体群を新たな個体群として設定
		self.population = next_population
		
		
	
	
	# 最優秀を決めるメソッド
	def tournament(self, individualList):
		
		now_top_individual = None
		
		for individual in individualList:
			
			# 現在の最優秀個体と適応度を比較し、上回っていれば入れ替える
			if (now_top_individual is None) or (now_top_individual.get_fitness() < individual.get_fitness()):
				now_top_individual = individual
		return now_top_individual

##交叉や突然変異の重要性
突然変異はともかく、交叉は実際なんの役に立つのか、分かりにくい気がします。
そこで、実際に交叉と突然変異を抜いてみて、何世代でゴールできるのか試してみました。
迷路は、上の方でイメージとして添付している迷路です。

	突然変異 +交叉	突然変異 のみ	交叉のみ
平均世代数	42.1 (n=30)	209 (n=21)	- (ほぼゴールできないため 算出不可)

「交叉のみ」は論外としても、「突然変異のみ」と「突然変異+交叉」でも、予想以上に明らかに大きな差がありました。

「交叉のみ」でも値が算出できるように、もっと単純な迷路で比較した方が良かったかもしれません。

##最後に
まず、ここまで読んでくださりありがとうございます。(たぶんここから読み始めた方はいないでしょう。)
ここまで読んでくださった方は重々承知かと思いますが、改めて。この投稿は、初心者のほぼ備忘です。鵜呑みにしないようお願いいたします。
そもそも、pythonの知識が足りていないせいで、非効率・pythonにふさわしくない書き方になっている部分も多々あると思います。
また、今回のモジュールに関しても、良くできているとはとても言えません。あまり複雑な迷路では、ゴールにとても長い時間がかかってしまいます。
適応度の算出方法など、見直すべき点は多そうです。