読者です 読者をやめる 読者になる 読者になる

DEAPのメモ

概要

  • 拡張性を最も意識している。データ構造もアルゴリズムもほとんどがカスタマイズ可能。
  • 問題や遺伝子の型を扱う、creator, 遺伝子操作を扱うtoolboxが中心モジュール。
  • インストール
    • 描画用にvpythonも入れておく(pipでコケる場合は面倒なのでaptで入れてしまう.)
  $ pip install deap 
  $ pip install vpython

使い方のメモ

  1. 大枠
    まず,問題表現(個体表現)と適応度を定義する.次に,個体と集団の初期化方法を登録.突然変異,交叉,適応度評価方法,淘汰方法を登録.ここまでできたらGAフレームワークを回すだけ.

  2. 個体表現,適応度の定義

    • Deapでは個体表現,適応度をそれぞれ型(クラス)として定義する.自分で決められるところがDeapのいいところだけど,全部自分でやるのは大変だ.そこで使うのがCreator.Creatorは型定義を簡単にしてくれるクラス製造機みたいなものだ.
    • createの使い方はcreate('type-name', base-type, optional)。optionalは作る型に応じて付ける。つまり,最低限型の名前とそのベースクラスが必要ということだ.オプショナル引数はたぶんインスタンス変数が追加されているんだと思う。
    • 問題の型:creator.create("FitnessMin", base.Fitness, weights=(-1.0,)).weightは単目的であってもタプルで渡すこと.最小化の場合は-1.0, 最大化の場合は1.0にする.多目的の場合はそれぞれの重みを与える.
    • 遺伝子の型:creator.create("Individual", list, fitness=creator.FitnessMin)
    • これをやっておいて、initRepeatコンストラクタなどを活用して別途個体や集団の初期化方法を定義する。initRepeatはinitRepeat(container, constructor, n=num)とすると、containerにnum個のconstructorで生成するオブジェクトを格納する。つまり、コンストラクタを繰り返すもので、遺伝子の初期化などに使えるんだ。
    • initIterate(container, generator).generatorが生成するオブジェクトをcontainerに代入して返す
    • 木のコンストラクタは3種ある
      • genFull:左右の葉の高さが等しい
      • genGrow:左右の葉の高さが等しくはないことも許す
      • genHalfAndHalf:genFullとgenGrowが半々で発生する。
  3. ToolboxにGAで使用するお決まりの関数の登録

    • toolbox.register("mutate", tools.mutGaussian, mu=0, sigma=1, indpb=0.1).などとして、mutate, crossoverとかの中身を割り当てる。こうすることで、アルゴリズムインターフェイスを統一的にしようって狙いだと思われる.統一した名前で突然変異,交叉を定義しておけば,それを回す上位ルーチンはフレームワーク化できる.
    • 突然変異や交叉だけでなく,個体の生成方法,集団の生成方法も定義する.この際に,initRepeatが活躍する.
  4. fitnessのEvaluationを書く

    • これだけは絶対に自分で書く部分
  5. アルゴリズムを書く

    • mutate, crossoverとか、決められた名前で関数をtooboxに定義しておけば algorithm.eaSimpleとかで定形ループは回してくれる。
    • 定形でないことをやりたいなら、ループを自分で書く。
    • 突然変異はtoolの中にいろいろある。注意点は、コピーしないと元のものが変化する。 mutant = toolbox.clone(ind1) ind2, = tools.mutGaussian(mutant, mu=0.0, sigma=0.2, indpb=0.2) del mutant.fitness.values child1, child2 = [toolbox.clone(ind) for ind in (ind1, ind2)] tools.cxBlend(child1, child2, 0.5) del child1.fitness.values del child2.fitness.values

主要モジュール

  • Creator
    • fitnessや遺伝子などはすべてcreatorを使って、’ある型’として生成する。
    • APIはcreator.create('name-of-type', base-class, optional-args)
    • Fitnessを定義する時は、weightを渡す。特に、weightは多目的な場合のためにタプルで渡す。 最大化の時は正、最小化の時は負の値。 ie) creator.create('FitnessMin', baseFitness, weight=(-1,))
    • 遺伝子(Indivisual)を定義する時は上で定義したfitnessをfitness属性として渡す。 ie) creator.create("Individual", list, fitness=creator.FitnessMin)
  • Toolbox
    • registerで関数と、そのエイリアスを登録する。3つ目以降の引数は登録する関数のパラメタ として渡される。
    • APIは register('alias-name', function, function-args)
  • initRepeat
    • 3 argな関数。arg1はデータを入れるコンテナ,arg2は個々の生成関数,arg3は個数

GPについて

  • DEAPはGAだけでなくGPも対応している.
  • 終端記号と原始記号を定義する。終端記号は特に、引数(変数)と定数に分類する。
  • トップ関数名や引数の数はgp.PrimitiveSet('top-name', num-of-args)で設定。
  • 引数はデフォルトはARG0, ARG1,..になっている.必要ならrenameArgumentsで名前を付ける。
  • 定数はすべてを指定する必要はなく、例えばこの範囲の整数、とかはEphemeralConstantとして 定義する。下の例は,-1,0,1のどれかの定数が入る。
pset = gp.PrimitiveSet("MAIN", 1)  
pset.renameArguments(ARG0='x')
pset.addPrimitive(operator.add, 2)
pset.addEphemeralConstant("rand101", lambda: random.randint(-1,1))
  • 木のパースのときにスタックが溢れるので、90以上の木の高さは扱えない
  • 木の描画
    • networkxとgraphvizの例があるけど、networkxも結局graphvizで描画するっぽい。 ならばgraphvizを入れようということで、
      • sudo pip install pygraphviz だとimportErrorでコケる。
      • pip install pygraphviz --install-option="--include-path=/usr/include/graphviz" --install-option="--library-path=/usr/lib/graphviz/"
    • sudo apt-get install libgraphviz-dev を先に入れておく。

サンプル

DEAPはマルチプロセッシング含めて,たくさんのサンプルが提供されている.それを見ながら理解するのが一番分かりやすいと思う.そこで,OneMaxはドキュメントにも説明があるので,ナップザック問題のサンプルを例題にコメントを追加する.元のサンプルには最大アイテム数の制約があるがそれは無くしている.また,ナップザックの大きさを明に与えずに多目的関数として定義している.

import random
import numpy

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

IND_INIT_SIZE = 5 
MAX_WEIGHT = 50
NBR_ITEMS = 20

# 決まった乱数を出すために種は指定しておく
random.seed(64)

# 問題の入力(アイテムの重さと価値)定義
# ここでは乱数でアイテムを生成する.
items = {}
for i in range(NBR_ITEMS):
    items[i] = (random.randint(1, 10), random.uniform(0, 100))

# 問題定義(適応度と個体)
creator.create("Fitness", base.Fitness, weights=(-1.0, 1.0))
creator.create("Individual", set, fitness=creator.Fitness)

toolbox = base.Toolbox()

# 遺伝子生成ルーチン登録(サンプルでは遺伝子をアトリビュートと呼んでいる)
# 一つの個体は複数の遺伝子から構成される.つまり個体の各ビットのこと.
toolbox.register("attr_item", random.randrange, NBR_ITEMS)

# 個体の生成ルーチン登録
# 個体はナップザックに含まれるアイテムの集合として定義している.
toolbox.register("individual", tools.initRepeat, creator.Individual, 
    toolbox.attr_item, IND_INIT_SIZE)

# 集団の生成ルーチン登録
# 何個生成するのかの引数は明に与えない.
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

# 適応度の計算ルーチン定義
def evalKnapsack(individual):
    weight = 0.0
    value = 0.0
    for item in individual:
        weight += items[item][0]
        value += items[item][1]
    return weight, value

# 交叉ルーチン定義
def cxSet(ind1, ind2):
    .... # 省略
    return ind1, ind2
    
def mutSet(individual):
    ... # 省略
    return individual,

# GA基本オペレータの登録(適応度計算,交叉,変異,選択)
toolbox.register("evaluate", evalKnapsack)
toolbox.register("mate", cxSet)
toolbox.register("mutate", mutSet)
toolbox.register("select", tools.selNSGA2)

def main():
    random.seed(64)
    NGEN = 50
    MU = 50
    LAMBDA = 100
    CXPB = 0.7
    MUTPB = 0.2
    
    pop = toolbox.population(n=MU)
    hof = tools.ParetoFront()   # 多目的最適化としているから

    # ログ関数の登録
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", numpy.mean, axis=0)
    stats.register("std", numpy.std, axis=0)
    stats.register("min", numpy.min, axis=0)
    stats.register("max", numpy.max, axis=0)
    
    algorithms.eaMuPlusLambda(pop, toolbox, MU, LAMBDA, CXPB, MUTPB, NGEN, stats,
                              halloffame=hof)
    
    return pop, stats, hof
                 
if __name__ == "__main__":
    main()