遺伝的アルゴリズムによるOneMax問題の最適化
OneMax問題とは、[1,0,0,1,0,1,1,1,1,0]のように0/1からなる数列の和を最大化する問題のこと。 答えはすべて1の数列と自明だが、これを最適化アルゴリズムの１つである遺伝的アルゴリズムで解く。 遺伝的アルゴリズムとは、このような数列を遺伝子と見立て複数生成し、 数世代に渡り交叉と突然変異を繰り返すことにより、優秀な遺伝子を生み出すアルゴリズムのこと。 ここでの優秀の定義は「数列の和が大きい」となる。
PythonではDEAPという 遺伝的アルゴリズムのライブラリーがあるが、個人的に拡張性が低くて使いにくかったのと、 実装がそれほど難しくはないので、Pythonでスクラッチから書くことにした。
アルゴリズムの流れ
- 第１世代の個体群の生成
- エリートの選択
- エリートの交叉／突然変異
- 次世代の個体群の生成
- 2〜4の操作を繰り返し、適応度の最も高い個体を解として出力
簡単な流れは上記の通り。 各世代の個体群の数は固定で、現世代のエリートと、彼らの子供の和となる。
1. 第１世代の個体群の生成
第２世代以降の個体群の生成は、基本的に交叉か突然変異になる。 そのため、この操作は第１世代だけ必要になる。 ランダム選択した0/1がN_PARAM個並ぶ数列を、 N_POP個生成する。
def get_population(self):
population = []
for i in range(N_POP):
arr = [random.randint(0,1) for j in range(N_PARAM)]
population.append(arr)
return population
各個体は後ほど適応度を計算するが、まず-1で初期化しておく。
>>> pop = [(-1, p) for p in self.get_population()]
>>> pop
[
(-1, [0, 0, 0, 0, 1, 1, 1, 1, 0, 0]),
(-1, [1, 0, 1, 0, 1, 0, 0, 1, 0, 0]),
(-1, [1, 0, 0, 0, 1, 0, 0, 0, 0, 1]),
...
]
2. エリートの選択
evaluateメソッドで、個体の適応度（fitness）を計算している。 OneMaxにおける適応度はリストの和とシンプルだが、今後の拡張を考えてメソッド化（clac_score）しておく。
def clac_score(self, x): return sum(x) def evaluate(self, pop): fitness = [] for p in pop: if p[0] == -1: fitness.append((self.clac_score(p[1]), p[1])) else: fitness.append(p) fitness.sort() fitness.reverse() return fitness
全個体の適応度を計算してソートしたら、ELITE_RATEの割合でエリートとして選択する。
>>> fitness = self.evaluate(pop) >>> elites = fitness[:int(len(pop)*ELITE_RATE)]
3. エリートの交叉／突然変異
突然変異mutate()では、個体の数列からパラメーターを１つだけ反転させる。
交叉crossover()では、片親の遺伝子の一部を切り取り、もう片親の同じ位置にペーストする。
これを２点交叉というが、場合によっては１点交叉にもなり得る。
def mutate(self, parent): r = int(math.floor(random.random()*len(parent))) child = copy.deepcopy(parent) child[r] = (parent[r]+1) % 2 return child def crossover(self, parent1, parent2): length = len(parent1) r1 = int(math.floor(random.random()*length)) r2 = r1 + int(math.floor(random.random()*(length-r1))) child = copy.deepcopy(parent1) child[r1:r2] = parent2[r1:r2] return child
突然変異はMUTATE_BROPの確率で起こり、それ以外は交叉となる。 これを全ての個体に対して行う。個体の組合せはランダムである。
pop = elites[:] while len(pop) < N_POP: if random.random() < MUTATE_PROB: m = random.randint(0, len(elites)-1) child = self.mutate(elites[m][1]) else: c1 = random.randint(0, len(elites)-1) c2 = random.randint(0, len(elites)-1) child = self.crossover(elites[c1][1], elites[c2][1]) pop.append((-1, child))
4. 次世代の個体群の生成
現世代のエリートを選択し、彼らを交叉／突然変異させた個体群を生成した。 これらの適応度を計算することで、次世代の個体群が生成される。
fitness = self.evaluate(pop) pop = fitness[:]
結果
10個の0/1の数列のOneMax問題を解かせたところ、第４世代で最適解が得られた。
Generation: 0 (8, [1, 1, 1, 1, 1, 1, 1, 0, 0, 1]) Generation: 1 (9, [1, 1, 1, 1, 1, 1, 1, 1, 0, 1]) Generation: 2 (9, [1, 1, 1, 1, 1, 1, 1, 1, 0, 1]) Generation: 3 (10, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) ... Generation: 24 (10, [1, 1, 1, 1, 1, 1, 1, 1, 1, 1])
ソースコード
全ソースコードを以下に載せておく。１ファイルにまとまっている。$ python ga.pyで実行可能。
# coding: utf-8 import random import math import copy N_PARAM = 10 N_POP = 20 N_GEN = 25 MUTATE_PROB = 0.1 ELITE_RATE = 0.2 class GA: def __init__(self): pass def main(self): pop = [(-1, p) for p in self.get_population()] for g in range(N_GEN): print 'Generation: ' + str(g) # Get elites fitness = self.evaluate(pop) elites = fitness[:int(len(pop)*ELITE_RATE)] # Cross and mutate pop = elites[:] while len(pop) < N_POP: if random.random() < MUTATE_PROB: m = random.randint(0, len(elites)-1) child = self.mutate(elites[m][1]) else: c1 = random.randint(0, len(elites)-1) c2 = random.randint(0, len(elites)-1) child = self.crossover(elites[c1][1], elites[c2][1]) pop.append((-1, child)) # Evaluate indivisual fitness = self.evaluate(pop) pop = fitness[:] print pop[0] print def get_population(self): population = [] for i in range(N_POP): arr = [random.randint(0,1) for j in range(N_PARAM)] population.append(arr) return population def clac_score(self, x): return sum(x) def evaluate(self, pop): fitness = [] for p in pop: if p[0] == -1: fitness.append((self.clac_score(p[1]), p[1])) else: fitness.append(p) fitness.sort() fitness.reverse() return fitness def mutate(self, parent): r = int(math.floor(random.random()*len(parent))) child = copy.deepcopy(parent) child[r] = (parent[r]+1) % 2 return child def crossover(self, parent1, parent2): length = len(parent1) r1 = int(math.floor(random.random()*length)) r2 = r1 + int(math.floor(random.random()*(length-r1))) child = copy.deepcopy(parent1) child[r1:r2] = parent2[r1:r2] return child if __name__ == "__main__": GA().main()
