How to implement Genetic Algorithm with python / 遺伝的アルゴリズムをPythonで実装する
モチベーション
以前子供たちと一緒にめんぼうで遺伝的アルゴリズムを実装しました。その内容をPythonプログラムとして実装することでより一層理解を深めたいと思い始めました。
そもそも遺伝的アルゴリズムとは？
以下の書籍が非常に参考となります。今回の実装もこちらに基づいております。
ソースコード
実際の実装は以下リンク先から参照してください。
サンプルコード
3つの3択問題についての解答を試行するGAになります。
import numpy as np
from lib import crossover, evaluate, gen_population, select, mutation
if __name__ == '__main__':
answer = [1, 2, 3]
num_question = len(answer)
num_survive = 3
num_population = 5
population = gen_population(num_population, num_question, (min(answer), max(answer)))
score_dict = {idx:sum(evaluate(answer, result)) for idx, result in population.items()}
score_list_sorted = sorted(score_dict.items(), reverse=True, key=lambda x: x[1])
print(score_list_sorted[0])
cnt = 0
while score_list_sorted[0][1] != 3:
score_list_selected = select(score_list_sorted, num_survive)
idx_selected = [t[0] for t in score_list_selected]
population_selected = [population[idx] for idx in idx_selected]
pop01 = population[score_list_sorted[0][0]]
pop02 = population[score_list_sorted[1][0]]
crv_point = np.random.randint(1, num_question-1)
new01, new02 = crossover(pop01, pop02, crv_point)
new01 = mutation(new01, (1, 4))
new02 = mutation(new02, (1, 4))
population_selected.append(new01)
population_selected.append(new02)
population = population_selected[:]
population = {i:pop for i, pop in enumerate(population)}
score_dict = {idx:sum(evaluate(answer, result)) for idx, result in population.items()}
score_list_sorted = sorted(score_dict.items(), reverse=True, key=lambda x: x[1])
print(score_list_sorted[0])
cnt += 1
if cnt > 100:
print(population)
break</code></pre></div>
設計コンセプト
遺伝的アルゴリズムは大まかに以下の4つの処理を繰り返していきます。
- 解候補の生成
- 各解候補の評価
- 優秀な解候補の選別
- 新規解候補の生成（交叉・変異）
以下に各処理に関連するメソッドを載せておきます。
解候補の生成
generateでは単一の候補が決められた範囲内（range_ans）からint型の解を生成します。次にgen_populationでは解候補を指定数生成して各候補ごとにgenerateで解を生成します。
def generate(number_question, range_ans):
"""Generate answer array for questions
Args:
number_question(int):
range_ans(tuple):
Returns:
(np.array):
"""
return np.random.randint(range_ans[0], range_ans[1], number_question)
def gen_population(num_population, num_question, range_ans):
"""Generate population
Args:
num_population(int): number of population
num_question(int): number of question
range_ans(tuple): range of answers, only supported int
Returns:
(dict):{index: answer_array}
"""
return {i:list(generate(num_question, range_ans)) for i in range(num_population)}
各解候補の評価
各候補の解と生成した解を比較して候補ごとの評価を下します。
def evaluate(answer, generated):
"""Evaluate answer array
Args:
answer(list): answer array
generated(list): generated array
"""
result = []
for a, b in zip(answer, generated):
if a == b:
match = 1
else:
match = 0
result.append(match)
return result</code></pre></div>
優秀な解候補の選別
evaluateを使って候補ごとにスコアが出たので次の世代に残したい候補数（num_survive）を上位から順に確保しておきます。
def select(score_list, num_survive):
"""Selection method
Args:
score_list(list):
num_survive(int): number of survival candidate
Returns:
(list)
"""
return score_list[:num_survive]</code></pre></div>
新規解候補の生成（交叉・変異）
交叉と変異の実装です。簡易的なものなのでここは工夫のしがいがあります。今後の伸び代としてとっておきます。
def mutation(arr, range_mut):
"""Mutation
Args:
arr(list): array for mutation
range_mut(tuple/list): range value for mutation
"""
idx_max_mut = len(arr)
idx_mut = np.random.randint(0, idx_max_mut)
arr[idx_mut] = np.random.randint(range_mut[0], range_mut[1])
return arr
def crossover(arr_01, arr_02, crv_point):
"""Cross over
Args:
arr(list):
crv_point(int): cross over point
Returns:
(tuple)
"""
arr_01_left = arr_01[:crv_point]
arr_01_right = arr_01[crv_point:]
arr_02_left = arr_02[:crv_point]
arr_02_right = arr_02[crv_point:]
arr_01_new = arr_01_left + arr_02_right
arr_02_new = arr_02_left + arr_01_right
return arr_01_new, arr_02_new</code></pre></div>
最後に
実は以前にの簡単なGAの実装に試みたことがあったのですがうまくいきませんでした。前回との違いはアソビワークショップで綿棒実装したことでかなり理解が深まっていたものと思います。今後の課題としては適用可能な問題が整数型の選択問題に限ったものなのでその適用範囲を広げるといった試みは必要かと思います。
そういえば変異を実装せずに一度サンプルスクリプトを動かしてみるとなかなか解が収束しない状況に陥りました。やはり候補の多様性というのが遺伝子の生き残りにおいては重要な要素なのだと改めて実感した次第です。