スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

PythonのDEAPが面白そう

Pythonはド素人だが、DEAPが面白そうなので勉強してみる。
DEAPは遺伝的アルゴリズムとか遺伝的プログラミングができるPythonのフレームワークです。
かなり柔軟に作っているようで、そのせいで少し難解です。

DEAP: http://code.google.com/p/deap/

プログラム例はhttp://deap.gel.ulaval.ca/doc/default/examples/index.htmlにいくつか載っています。

日本語の解説もありますね。
Pythonの進化計算ライブラリDeap
Pythonの進化計算ライブラリDeap(2)


遺伝的アルゴリズムの例としてOne Max Problemを取り上げます。
これは長さ100の0か1からなるリスト、たとえば(0,1,1,0,0,1,1,1,......)みたいなリストの中から、リスト内の総和を最大化する問題です。
答えは自明で、すべてが1になるものが最適解です。

最初はFirnessからFitnessMaxクラスを作っています。weightsが正ならfitnessを最大化させ、weightsが負ならfitnessを最小化するように最適化されます。
Individualクラスをlistから継承して作成しています。
creator.create("FitnessMax", base.Fitness, weights=(1.0,))
creator.create("Individual", list, fitness=creator.FitnessMax)


多目的最適化も扱え、複数の評価関数を使い、1つ目を最小化、2つ目を最大化ということもできます。
creator.create("FitnessMulti", base.Fitness, weights=(-1.0, 1.0))


以下は個体と個体群を定義しています。
tool.attr_boolをrandom.randint(0,1)のエイリアスとして登録しています。(0か1の乱数を返す)
"individual"ではそれを100回呼び出して初期化します。コンテナとしてcreator.Individualを指定しています。
"population"ではindividualの繰り返しで初期化しています。

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 = base.Toolbox()
toolbox.register("attr_float", random.random)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, 100)


評価関数を定義します。多目的最適化の場合は、重みの個数だけ値を返す必要があります。
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)


交叉方法は、
cxOnePoint():一点交叉
cxTwoPoint():二点交叉
cxUniform():一様交叉
などが用意されています。

突然変異は
mutGaussian()
mutFlipBit()
など。

選択方法は
selTournament():トーナメント選択
selRoulette():ルーレット選択
など。

詳細はhttp://deap.gel.ulaval.ca/doc/default/api/tools.htmlを参照

最初に個体群を作ります。ここでは300個の個体を作成。
def main():
pop = toolbox.population(n=300)


最初の個体群について適応度を計算。
    # Evaluate the entire population
fitnesses = list(map(toolbox.evaluate, pop))
for ind, fit in zip(pop, fitnesses):
ind.fitness.values = fit


各世代について以下のように進化させていく。
 
# 次の世代の個体を選択
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


最後に以下で最適な個体が取り出せます。
    best_ind = tools.selBest(pop, 1)[0]
print("Best individual is %s, %s" % (best_ind, best_ind.fitness.values))


プログラム全体はこちらに載ってます。
https://github.com/DEAP/deap/blob/master/examples/ga/onemax.py

実行結果はこちら。
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,)


ちゃんと最適な結果が得られています。



DEAPをダウンロードすると他にもサンプルが入っています。
ga/tspは巡回セールスマン問題です。
individualの型が異なったり、交叉・突然変異にcxPartialyMatched、mutShuffleIndexesが使われたりしていますが、それ以外はほぼ同じに書かれており、かなり統一的な書き方ができるようです。

ga/knapsackはナップサック問題です。
解説はこちらにあります。個体の定義にlistではなくsetを使っているため、交叉と突然変異を自分で書くサンプルになっています。
http://deap.gel.ulaval.ca/doc/default/examples/ga_knapsack.html
コメント
コメントの投稿
管理者にだけ表示を許可する

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。