最初に

DEAPのドキュメントを直訳して言っています。　　
今までにOverviewとCreating Typesチュートリアルを見て来ました。今回はOperators and Algorithmsについて見ていきます。

いつも通り、ただの直訳もどきなので意味が分からないところもあるかと思います。(そういう所は私も意味が分かっていません...)

Operators and Algorithms

complex algorithmsを始める前に、いくつかDEAPの基本を見て見ましょう。まず、Creating Typesチュートリアルで見たように、個体を作成し、異なる演算子を使用して相互作用させます。その後の、他のアルゴリズムやツールの使い方を学んでいきましょう。

A First Individual(最初の個体)

最初に要求されるモジュールをインポートし、目的関数の値を最小化していくということを示すとともに、Floatのリストである個体を作成していくための異なる関数を登録していきます。

import random

from deap import base
from deap import creator
from deap import tools

IND_SIZE = 5

creator.create("FitnessMin", base.Fitness, weights=(-1.0, -1.0))
creator.create("Individual", list, fitness=creator.FitnessMin)

toolbox = base.Toolbox()
toolbox.register("attr_float", random.random)
toolbox.register("individual", tools.initRepeat, creator.Individual,
                 toolbox.attr_float, n=IND_SIZE)

これで、以下のスクリプトを追加することで最初の個体を作成することができます。

ind1 = toolbox.individual()

また、下記のように個体ind1をプリントしたり適応度が有効かどうか見ることができます。

print ind1               # [0.86..., 0.27..., 0.70..., 0.03..., 0.87...]
print ind1.fitness.valid # False

個体はベースクラスの形(今回の場合はList)でプリントされ、また、適応度を計算していないため無効であることが確認できました。

Evaluation(評価)

このパートは進化的アルゴリズムにおいて一番個人に寄る所だと思います。ここがライブラリの中で唯一自分自身で書かないといけない所でしょう。典型的な評価関数は引数として一つの個体をとり、その適応度をタプルとして返します。コアセクションで見ていく通り、適応度はFloatの値であり、再評価するべきかを知るためのプロパティvalidを持っています。適応度はタプルとしてvalueがセットされます。例として、先程作ったind1の適応度を計算してみます。

def evaluate(individual):
    # Do some hard computing on the individual
    a = sum(individual)
    b = len(individual)
    return a, 1. / b

ind1.fitness.values = evaluate(ind1)
print ind1.fitness.valid    # True
print ind1.fitness          # (2.73, 0.2)

目的関数が一つの場合も同様です。目的が一つの場合でも、複数目的の場合の特別な場合と考えられるので、必ずタプルでかえさなくてはいけません。

Mutation(突然変異)

次に紹介するのは突然変異演算子です。deap.toolsモジュール中に様々な突然変異演算子があります。それぞれの突然変異は様々な特徴があり、違うタイプの個体に使用されることがあります。望まない振る舞いをしてしまうのを防ぐために、選んだ演算子のドキュメントを気をつけて読みましょう。　

突然変異演算子の一般的なルールは、突然変異だけをするというものです。これが意味することは、元々の個体を変化させたくない場合や、他の個体から参照されている場合は、突然変異させる前にコピーを作成しておかないといけないということです。

個体ind1に突然変異(今回はgaussian mutation)を適用するためには、単純に、適した関数を適用していきます。

mutant = toolbox.clone(ind1)
ind2, = tools.mutGaussian(mutant, mu=0.0, sigma=0.2, indpb=0.2)
del mutant.fitness.values

突然変異が起こると個体は元の個体とは関係がなくなるので、今までの適応度は消去します。上記のように突然変異は個体を突然変異をさせるだけで、適応度の無効化などに責任を追うものではありません。下の例ではind1とmutantは同じ個体であることを示しています。

print ind2 is mutant    # True
print mutant is ind1    # False

Crossover(交叉)

2つ目に紹介するのは交叉演算子です。こちらもdeap.toolsモジュール中に様々な交叉演算子があります。それぞれの交叉は様々な特徴があり、違うタイプの個体に使用されることがあります。望まない振る舞いをしてしまうのを防ぐために、選んだ演算子のドキュメントを気をつけて読みましょう。　

交叉演算子の一般的なルールは、交叉だけをするというものです。これが意味することは、元々の個体を変化させたくない場合や、他の個体から参照されている場合は、個体同士を噛み合わせる前にコピーを作成しておかないといけないということです。

それでは、既にクローンが作成されている二つの子供に交叉演算子を適用してみましょう。

child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)]
tools.cxBlend(child1, child2, 0.5)
del child1.fitness.values
del child2.fitness.values

Note
この言語の注意点としてtoolbox.clone([ind1, ind2])という形式は使用できません。もし、ind1とind2がメモリの同じ場所を参照していた場合、独立しているコピーは一つしかなく、二つ目のコピーも独立した一つ目のコピーを参照することになります。これは再帰的ループを防ぐためのメカニズムに由来します。最初に個体が現れた時に"memo"辞書におかれます。2回目に現れる時、そのオブジェクトの深いコピーは中止され前に作成されたコピーへの参照がおかれます。深いコピーをする際は気をつけてください。

Selection(選択)

選択はdeap.toolsモジュール中の選択演算子によって集団中で行われます。選択演算子は通常一つ目の引数として反復可能な個体を、また、選択する個体の数をとります。これは選択された個体のリストを返します。選択は下記のようにします。

selected = tools.selBest([child1, child2], 2)
print child1 in selected    # True

注意!
ここでは、選択オペレータが選択プロセス中に個体を複製しないことに注意することが非常に重要です。もし、個体が二度選択され、そのうちの片方が変更された時、もう片方も変更されます。個体への参照のみコピーされます。他の演算子と同様に選択のみ行います。

通常、集団全体の複製は選択の後か変更前に行われます。

selected = toolbox.select(population, LAMBDA)
offspring = [toolbox.clone(ind) for ind in selected]

Using the Toolbox

toolboxは初期化の演算子から評価演算子までの、全てのtoolを含むことを目指しています。各アルゴリズムを簡単に設定できます。toolboxは基本的に二つのメソッドを持ちます。register()とunregister()です。それぞれ、toolboxにツールを加えるとき、外すときに使用します。

このパートでは初期化のツールを登録するよりも、進化的ツールを登録する事についてみていきたいと思います。通常の進化的ツールの名前は、mate()、mutate()、evaluate()とselect()になります。
ただし、一意の名前であれば任意の名前を登録することができます。下の例がtoolboxへの登録の仕方です。

from deap import base
from deap import tools

toolbox = base.Toolbox()

def evaluateInd(individual):
    # 何かの計算する
    return result,

toolbox.register("mate", tools.cxTwoPoint)
toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.2)
toolbox.register("select", tools.selTournament, tournsize=3)
toolbox.register("evaluate", evaluateInd)

ツールの登録にtoolboxを使用すると、残りのアルゴリズムを残りのオペレーターセットから独立させておくのに役立ちます。このスキームによってtoolboxのツールを設置したり変えたりするのを簡単になります。

Using the Tools

進化的アルゴリズムを構築するときに、toolboxは演算子を含めるために使用され、一般名で呼び出されます。例えば、これはとても単純な世代進化アルゴリズムです。

for g in range(NGEN):
    # 次の世代の個体を選択する
    offspring = toolbox.select(pop, len(pop))
    # 選んだ個体のクローンを作成する
    offspring = 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 = toolbox.map(toolbox.evaluate, invalid_ind)
    for ind, fit in zip(invalid_ind, fitnesses):
        ind.fitness.values = fit

    # 世代が子集団に置き換わる
    pop[:] = offspring

これは完璧なアルゴリズムです。選んだ個体の型に適している限り、あらゆる種類の個体、演算子を受け入れるために十分に汎用性があります。先ほどの例に示すように、toolboxの使用により、可能な限り疑似コードに近いアルゴリズムを書くことができます。今、書いて経験するのはあなた次第です。

Algorithms

algorithmsモジュールにいくつかのアルゴリズムが実装されています。それらは非常に単純で文献にある基本的な進化的アルゴリズムを反映しています。前のセクションで述べたようにこれらのアルゴリズムはToolboxを使用します。toolboxをアルゴリズムのためにセットアップするために、必要な演算子を特定の名前で登録する必要があります。詳細については選んだアルゴリズムのドキュメントを参照してください。一度toolboxの準備ができたら、アルゴリズムを動かす時です。基本的な進化的アルゴリズムは5つの引数をとります。集団、toolbox、各世代で各個体を交配させる確率(cxpb)、各世代で各個体を突然変異させる確率(mutpb)、そして実行する世代の回数(ngen)になります。

from deap import algorithms

algorithms.eaSimple(pop, toolbox, cxpb=0.5, mutpb=0.2, ngen=50)

単純な進化的アルゴリズムがどのように動いているのか理解するために、ドキュメントを見たり、ソースコードを眺めてみるのが良いでしょう。

これでもう、Pythonで自分の進化的アルゴリズムを作成可能になりました。

終わりに

とりあえず、ここまで見ればわかるのかなという気がします。途中ちょっと省略しています。次回、サンプルコードを見て終わりたいと思います。
　　
　　

進化的計算フレームワークDEAP (1) Overview
進化的計算フレームワークDEAP (2) Creating Types
進化的計算フレームワークDEAP (4) One Max Problem