最初に
deapを使用したOne Max Problemについて見ていきます。参考にしたサイトはこちらになります。また、元のコードも公式のgitからいただいています。ワンマックス問題以外にも色々例が乗っているので参考になると思います。今回は直訳という形ではなく、コードを読んでく形です。
One Max Problem
最初にランダムにint型の0または1で埋められた個体で作られる集団を作成します。最終的に、要素が全て1になるように進化させていきます。とりあえず、最終的なコードはこちら。
import random
from deap import base
from deap import creator
from deap import tools
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)
toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat, creator.Individual,
toolbox.attr_bool, 100)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
def evalOneMax(individual):
return sum(individual),
toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
def main():
random.seed(64)
pop = toolbox.population(n=300)
CXPB, MUTPB = 0.5, 0.2
print("Start of evolution")
fitnesses = list(map(toolbox.evaluate, pop))
for ind, fit in zip(pop, fitnesses):
ind.fitness.values = fit
print(" Evaluated %i individuals" % len(pop))
fits = [ind.fitness.values[0] for ind in pop]
g = 0
while max(fits) < 100 and g < 1000:
g = g + 1
print("-- Generation %i --" % g)
offspring = toolbox.select(pop, len(pop))
offspring = list(map(toolbox.clone, offspring))
for child1, child2 in zip(offspring[::2], offspring[1::2]):
if random.random() < CXPB:
toolbox.mate(child1, child2)
del child1.fitness.values
del child2.fitness.values
for mutant in offspring:
if random.random() < MUTPB:
toolbox.mutate(mutant)
del mutant.fitness.values
invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
ind.fitness.values = fit
print(" Evaluated %i individuals" % len(invalid_ind))
pop[:] = offspring
fits = [ind.fitness.values[0] for ind in pop]
length = len(pop)
mean = sum(fits) / length
sum2 = sum(x*x for x in fits)
std = abs(sum2 / length - mean**2)**0.5
print(" Min %s" % min(fits))
print(" Max %s" % max(fits))
print(" Avg %s" % mean)
print(" Std %s" % std)
print("-- End of (successful) evolution --")
best_ind = tools.selBest(pop, 1)[0]
print("Best individual is %s, %s" % (best_ind, best_ind.fitness.values))
if __name__ == "__main__":
main()
実行してみると、
...
...
...
-- Generation 35 --
Evaluated 177 individuals
Min 86.0
Max 100.0
Avg 97.04333333333334
Std 2.325536975028139
-- End of (successful) evolution --
Best individual is [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], (100.0,)
と、確かに最後に全ての要素が1になっていることがわかります。
とりあえず、少しずつコードを見ていきたいと思います。
設定する
とりあえず、最初に必要なモジュールをインポートします。
import random
from deap import base
from deap import creator
from deap import tools
Creator
deap.creatorを使用することで簡単に個体を作成することができる。
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)
最初にFitnessMaxというクラスを定義している。これはdeap.baseモジュールのFitnessクラスを継承している。また、weightsという属性を持っており、これは必ずタプルでないといけないので注意する必要がある。また、1.0というのは目的関数の値を最大化させることを表しており、負の値の場合は最小化させることを表す。また、必ずしも1.0である必要でなく、この値を変更することによって目的関数の重みを変更することができる。
二行目でIndividualクラスを作成している。これはlistを継承したものであり、先ほど定義したFitnessMaxをfitness属性として持つ。
Toolbox
Toolboxに関数を登録していく。
toolbox = base.Toolbox()
toolbox.register("attr_bool", random.randint, 0, 1)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_bool, 100)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)
ここでは、世代を作成する関数toolbox.attr_bool()と2つの初期化関数、individual()とpopulation()を作成している。toolbox.attr_bool()が呼ばれると、int型の0か1をランダムで返す。これはramdom.randint(0, 1)と同等である。
individual()とpopulation()はそれぞれ個体と集団を初期化する関数である。これらはinitRepeat()という関数を使用している。この関数の最初の引数はコンテナクラスとなる。3行目の例では、indivisual()がtools.initRepeat(creator.Individual, toolbox.attr_bool, 100)と同等になる。1つ目の引数として先ほど作成したIndividualが使用されており、これはcreator.IndividualというListを継承しているクラスがattr_bool()メソッドを使用して要素が埋めらることになる。また、3つ目の引数に100が入っていることから100個のint型の0か1を持つことになる。
population()についても同様で、Listがtoolbox.individual()を使用して埋められる事となる。だが、集団を構成する個体の数は固定されていない。また後で指定していく。
評価関数
この例で評価関数は非常に簡単である。なぜなら、含まれる1の個数を数えれば良いだけだからだ。
def evalOneMax(individual):
return sum(individual),
ただ、必ず目的の数と同じだけの値をイテレート可能な形で返さないといけない事に注意する。今回は目的関数が１つなので１つの値を返すだけで良い。
遺伝子操作
4つの関数を登録する。
toolbox.register("evaluate", evalOneMax)
toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutFlipBit, indpb=0.05)
toolbox.register("select", tools.selTournament, tournsize=3)
評価はevaluateとエイリアスされた関数が実行される。ここで、引数を固定しないのが大事になってくる。なぜなら、集団中の各個体に対して評価を行っていく必要があるからだ。
これまでで、下準備はだいたい終了。
進化のサイクル
集団を作成する
先ほど作成したpopulation()を使用して集団を作成する。
def main():
pop = toolbox.population(n=300)
先ほど、個体の数を固定しなかったのでここで指定している。つまり、この集団は個体300個から作成されるものとなる。また、先ほど引数を固定した通りpopはList型となる。
また、ここで交叉をする確率(CXPB)、突然変異(MUTPB)をする確率を定義しておく。
CXPB, MUTPB = 0.5, 0.2
次にそれぞれの個体を評価していく。
fitnesses = list(map(toolbox.evaluate, pop))
for ind, fit in zip(pop, fitnesses):
ind.fitness.values = fit
1行目でmap()を使用し、各個体にtoolbox.evaluate()を適用して評価していく。fitnessesとpopの並び順は同じになるので次のfor文で適応度を個体にセットしていく。
進化させる
集団は準備できたので、進化させていく。今、各個体はint型の0か1を100個持っていて最終的に全て1にしたいというのが今回の目的であった。つまり、最終的に評価関数の値が100になれば良いという事である。まず、各個体の評価関数の値を得る必要がある。
fits = [ind.fitness.values[0] for ind in pop]
そして、どれかの個体の評価関数の値が100になるか、1000回世代交代するまで繰り返していく。
# 世代回数を覚えておくために変数を用意する。
g = 0
# 進化開始
while max(fits) < 100 and g < 1000:
# 新しい世代
g = g + 1
print("-- Generation %i --" % g)
進化は、選択、交叉、突然変異と進んでいく。
まず最初に次の世代のために選択をしていく。
offspring = toolbox.select(pop, len(pop))
offspring = list(map(toolbox.clone, offspring))
2行目でクローンを作成している。1行目では参照だったため、2行目で深いコピーをして独立した個体を作成している。
次に交叉と突然変異をしていく。先ほど定義したCXPBとMUTPBでそれぞれの確率を決めている。
# 交叉。それぞれ偶数のもの、奇数のものを交叉させようとしている。
for child1, child2 in zip(offspring[::2], offspring[1::2]):
if random.random() < CXPB:
toolbox.mate(child1, child2)
del child1.fitness.values
del child2.fitness.values
# 突然変異
for mutant in offspring:
if random.random() < MUTPB:
toolbox.mutate(mutant)
del mutant.fitness.values
また、それぞれ適応した後に適応度を無効化している。
先ほどの段階で適応度が変化した個体があるので、無効化されているものを再度計算してく。
invalid_ind = [ind for ind in offspring if not ind.fitness.valid]
fitnesses = map(toolbox.evaluate, invalid_ind)
for ind, fit in zip(invalid_ind, fitnesses):
ind.fitness.values = fit
これで新たな世代が作成されたので、置き換える。
pop[:] = offspring
進化がどんな感じで進んでいるか確かめるためにプリントしていく。
fits = [ind.fitness.values[0] for ind in pop]
length = len(pop)
mean = sum(fits) / length
sum2 = sum(x*x for x in fits)
std = abs(sum2 / length - mean**2)**0.5
print(" Min %s" % min(fits))
print(" Max %s" % max(fits))
print(" Avg %s" % mean)
print(" Std %s" % std)
値を取り出す
進化が十分行われたら、解を取り出す。
best_ind = tools.selBest(pop, 1)[0]
この関数はpopの中からよかったものを1つとりだすという物である。ちなみに1を2にすればよかったものを2つ取り出せる。返り値はリストになっているので[0]でさらに取り出している。
終わりに
なんか、途中から口調が変わりましたね。とりあえず、わたし的に、簡単な例までは理解することができるようになったと思いますー！色々できそうなのでいじってみたいと思います。個人的にNSGA-IIを実装したいので、もうちょい勉強しないといけないなとは思いますが。ドキュメントがしっかりしているって素敵ですね。基本的な使い方まではわかったのでこれにて終わりたいと思います。
進化的計算フレームワークDEAP (1) Overview
進化的計算フレームワークDEAP (2) Creating Types
進化的計算フレームワークDEAP (3) Operators and Algorithms