はじめに

DEAPという進化計算フレームワークをご存じでしょうか。
え？DEAP以前に進化計算何それという状態ですか？
まあ進化計算の前提知識はこの記事ではあまり関係ありません。この記事の主目的は進化計算を実装するためにDEAPがどれだけPythonをうまく使っているかを説明し、Python力向上の助けになればいいなということですので。

進化計算特に遺伝的アルゴリズムについて

前提知識がなくてもOKと言ってもこの後に出てくる単語がわからないといけないので進化計算、特に説明に使用する遺伝的アルゴリズム（Genetic Algorithm : GA)について簡単に説明します。

GAは「遺伝的」とあるように、生物の進化をヒントに考えられたアルゴリズムです。
今いる生物が生き残っているのは何故か？いろいろな理由はありますがGAでは以下の3つが主要な要素になります。

選択（selection）: 弱い生物は死に、強い生物は生き残ります。強い弱いとはどういうことかということについてはこの後で説明します。
交叉（crossover）: 生き残った生物は子孫を残すために交配します。子供には両親の遺伝子が受け継がれます。
突然変異（mutation）: 今いる生物はもちろん地球ができたころからいるわけではありません。徐々に進化していったわけですがそれには親からの性質を受け継ぐ以外にちょっと違う部分を持つ子が必要になります。それが積もり積もると全く違う生物にもなるわけです。

さて、選択で強い生物が生き残ると書きましたが「強い」とは「適合度（fitness）が高い」という意味です。次に「じゃあ適合度って何？」となりますが、GAにおいては「解きたい目的関数の値」となります。$f(\vec{x})$です。お次は$\vec{x}$の話。

遺伝子表現と操作

やっと遺伝的アルゴリズムの「遺伝」のところに来ました。「遺伝」とは遺伝子のことです。この遺伝子が数式的に書いた場合の$\vec{x}$です。
遺伝子の表現は大きく分けて二つ、0/1のバイナリ列で表し$f(\vec{x})$を計算するときは0/1から目的関数の定義域に変換して計算する方法、数値をそのまま「遺伝子」として使う実数値GAと呼ばれる方法です。

交叉では両親の遺伝子が受け継がれると書きましたが、以下のように遺伝子を切り貼りして子供を作ります。どこで切るかは通常乱数で決めます。

父 ：01101101  母 ：11000011
真ん中で切って貼り付け（子1は父の左半分＋母の右半分、子1は母の左半分＋父の右半分）
子1：01100011  子2：11001101

突然変異は一定確率でビットを反転させます。

交叉後、子1突然変異（左端が0→1になった）
子1：11100011

このようにしてできた子が生き残れるかは子の適合度（目的関数値）によります。これが選択です。
この選択、交叉、突然変異をぐるぐる回します。するとそのうち適合度の高い（目的関数値の高い）個体が生き残っており求めたい$\vec{x}$（設計変数値）が得られているというのがGAの発想です。

どのように交叉させる（交叉手法を用いる）か、突然変異させるか、選択するのがよいかは対象問題の性質にもよります。もちろん対象問題の性質は既知でないことの方が多いため、「いろいろ試してみる」ということになります。

さて簡単にと言いつつだいぶ長くなってしまいましたが、そろそろDEAPの萌えポイントについて説明することにしましょう。

DEAPでの個体表現

Overviewに沿って見ていきましょう。まずは個体表現です。
「個体表現」という場合に考慮が必要なのは「遺伝子をどう実装するか」と「適合度をどう実装するか」です。

適合度（Fitness）の実装

DEAPでは先に適合度を表すクラスを定義します。ここからすでにおもしろい。

from deap import base, creator
creator.create("FitnessMin", base.Fitness, weights=(-1.0,))

Overviewには「これでFitnessMinクラスが作られます」と書かれています。
いや待て「クラスが作成される」ってどういうことだよ関数呼び出しじゃねえのかよこれと思いませんか。次にcreator.createのリファレンスを見てみましょう（リンク先は英語です）

deap.creator.create(name, base[, attribute[, ...]])
creatorモジュールにbaseを継承したnameという名前のクラスを作成します。そのクラスには第3引数以降のキーワード引数で指定された属性を定義できます。引数がクラスの場合、作成するクラスのオブジェクトを作るときに引数で渡されたクラスのオブジェクトが作られ属性に設定されます。引数がクラスでない場合は、作成クラスの静的属性として設定されます。

リファレンスではFooクラスについてcreator.createを書いたものと等価なクラス定義が示されていますが先のcreator.create("FitnessMin", base.Fitness, weights=(-1.0,))を同じように当てはめてみると以下となります。

creatorモジュール内で実行されることになる

class FitnessMin(base.Fitness):
    weights = (-1.0,)

どう動くかはわかった。だがどうやってるんだ？というところで出てくるのがPythonではクラスも第一級オブジェクト¹という概念です。WIkipediaの第一級オブジェクトの項でその性質が挙げられていますがその中で今特に重要なのはこちら。

実行時に構築可能である。

そうPythonは実行時にクラスを定義できるのです。
普通にプログラム作るときは必要なことはまずありませんが、フレームワーク作るときにはこれができると便利です。次にPythonリファレンスのtype関数を見てみましょう。

class type(name, bases, dict)
引数が 3 つの場合、新しい型オブジェクトを返します。本質的には class 文の動的な形式です。 name 文字列はクラス名で、 name 属性になります。 bases タプルは基底クラスの羅列で、 bases 属性になります。 dict 辞書はクラス本体の定義を含む名前空間で、標準の辞書にコピーされて dict 属性になります。

creator.createはこのtype関数を利用し、クラスの動的定義を行っています。なお、globals関数は「モジュール内のグローバル変数」の辞書を返します。これを利用し、代入することでクラスが定義されます（type関数で作成するだけではまだ他から参照することはできません）
普通にクラス定義させればいいのでは？とか、提供モジュール内にクラスができるのどうなん？とかいろいろ突っ込みたくもなりますが、おもしろいのでOK(笑)

なお継承元のbase.Fitnessもおもしろいことをしていますがそれについてはもう少し後で萌えポイントを説明します。

個体（Individual）の実装

Overviewでは次に個体クラスを定義しています。

creator.create("Individual", list, fitness=creator.FitnessMin)

上で説明したcreator.createの動作により以下のクラスがcreatorモジュールに定義されることになります。

class Individual(list):
    def __init__(self):
        self.fitness = FitnessMin()

ここで大事なのは「個体はリストである²。リストに何を入れるかはこの時点では決まっていない」という点です。

個体の初期化

GAでは選択、交叉、突然変異のループの開始点となる初期個体を通常ランダムに発生させます。それに該当する定義を行っているのが以下の部分です。なお正確にはこの時点では定義だけで実際の個体は生成されていません。

import random
from deap import tools

IND_SIZE = 10

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

新しい要素が出てきました。Toolboxクラスです。道具箱の名の通りこれに登録を行うようです。とりあえずToolbox.registerのリファレンスを見てみましょう。

register(alias, method[, argument[, ...]])
関数（method引数）をaliasという名前で登録する。登録される関数に渡すデフォルト引数を設定できる。関数呼び出し時に上書きも可能である。

individualという名前で登録しているコードを改めて確認します。

toolbox.register("individual", tools.initRepeat, creator.Individual,
                 toolbox.attribute, n=IND_SIZE)

これが何をしているのかを確認するにはtools.initRepeatのリファレンスを見る必要があります。

deap.tools.initRepeat(container, func, n)
funcの関数をn回呼び出して、それを引数にcontainerの関数を呼び出す。

containerの位置に対応するのはIndividualです。これはリスト（を継承したクラス）でした。
funcはtoolbox.attribute。これはただのrandom.randomの別名です。
このことから、Toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attribute, n=IND_SIZE)の呼び出しで以下のようなメソッドが定義されることになります。

def individual():
    return tools.initRepeat(creator.Individual, random.random, n=IND_SIZE)
    """
    initRepeatの処理をさらに展開すると以下のようになる
    return Individual([random.random() for _ in range(IND_SIZE)])
    """

つまり、individual()と呼び出すことで[0, 1)の乱数を10個発生させ個体に詰め込むメソッドを定義するということを行っています。
これで、先ほど書いた「リストに何を入れるかはこの時点では決まっていない」に対応して「リストに入れる要素は何か」が定義されてたことになります。バイナリ遺伝子のGAを行うか、実数値GAを行うかで結構プログラム構造に影響を与えるのですが、DEAPでは比較的気軽に「リストに実際入るもの」を定義できるのも萌えポイントの一つです。

部分適用

さておもしろいのはここからです。Toolbox.registerでは「渡された関数にデフォルト引数を設定して別名を付ける」ということが行われますが何故このようなことができるのでしょうか。ここで出てくるのが部分適用という考え方です。とりあえずToolbox.registerのコードを見てみましょう。大事なところだけ抜き出したものを貼ります。

deap/py

    def register(self, alias, function, *args, **kargs):
        pfunc = partial(function, *args, **kargs)
        setattr(self, alias, pfunc)

partialはfunctoolsモジュールで提供されている関数です。

functools.partial(func, /, *args, **keywords)
新しい partial オブジェクトを返します。このオブジェクトは呼び出されると位置引数 args とキーワード引数 keywords 付きで呼び出された func のように振る舞います。

部分適用の何が楽しいかを説明するために個体群を生成するpopulationの定義を見てみましょう。比較のためにindividualの定義も再掲します。

toolbox.register("individual", tools.initRepeat, creator.Individual,
                 toolbox.attribute, n=IND_SIZE)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

individualではinitRepeatの「全引数を指定しています」が、populationでは「nを指定していません」。そのため、populationを呼び出す際にはnを指定する必要があります。

pop = toolbox.population(n=50)

GAで問題を解く場合、対象問題に対する遺伝子の表現（遺伝子長）を決めればそれは普通変えません。一方、個体数は少ない場合、多い場合、その中間と「色々変えてみるパラメータ」となります。そのため、nは都度指定するものなります。部分適用があることにより、汎用の関数を用いてより特化した関数を作成、それを使って処理が記述できるということになります。

DEAPでの手法の設定

ここまでの説明でOverviewの残りの部分も何をやっているのかわかるようになったと思いますが一応説明します。

GAでは選択、交叉、突然変異の手法を色々試してみると説明しました。各手法には手法特有のパラメータというものがあります。
一方、交叉であれば「2匹の個体を引数に取り、2匹の子個体を返す」、突然変異であれば「1匹の個体を引数に取り、1匹の突然変異した個体を返す」、選択であれば「個体群と生き残らせる数を引数に取り、生存個体を返す」のような、「操作の一般的な入出力」というものが決まっています。
これらについても部分適用を利用し、用意されている各手法に対して手法独自のパラメータを部分適用しておいたメソッドを作り出します。

def evaluate(individual):
    return sum(individual),

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

この際、mate, mutate, select, evaluateという名前を付けるのは「GAを回す全体のアルゴリズム」を使う際に重要です。「全体のアルゴリズム」の一つであるeaSimpleには以下のように書かれています。

deap.algorithms.eaSimple(population, toolbox, cxpb, mutpb, ngen[, stats, halloffame, verbose])
この関数はtoolboxにmate, mutate, select, evaluateが登録されていることを想定している。

枠組み（フレームワーク）側が想定する名前を付けておくことで適切に呼び出される、ということです。

再計算の抑止

長々と書いてしまい自分でも忘れかけていましたが最後にbase.Fitnessの萌えポイントです。Tutorials: Part 2を見るとおもしろいことが書いてあります。

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

何故valuesに代入するとvalidがTrueになるのでしょうか。これはプロパティで実現されています。
さらにvalues自体も実はプロパティです。こちらは代入が行われると初めに定義したweightsが掛けられたものが保持されるというカラクリになっています。³

validの実装
 valuesの実装

何故このようにvalidというものがあるのか。
それは交叉や突然変異ではそれぞれ交叉率、突然変異率というものが設定され、実際には「交叉も突然変異も起こらなかった遺伝子できる」ことがあるためです。同じ遺伝子なので当然目的関数値も同じになります。その場合に再計算をするのは無駄でありそれを回避するためです⁴。

まとめ

以上、DEAPのdeepな裏側について見てきました。普段あまりお目にかからない、知ってるとどこかで使えるかもしれないPython奥義としては以下のものがありました。

type関数を用いたクラスの動的定義
functiontools.partialを用いた部分適用

私は言語の機能を使い倒しているフレームワークが大好きなのですが、DEAPもまさにPythonを駆使しているといった感じでいいですね。

ファーストクラスオブジェクトとも呼ばれますが、オブジェクト指向的「クラス」とは違うのでこの記事では「級」という言葉を使います。 ↩
リスト以外をスーパークラスにすることもできて、ドキュメントでは集合（set）を継承する例も挙げられています。 ↩
符号反転することで最小化問題も最大化問題も統一的に扱えるようにするため。 ↩
テスト問題はともかく実問題だと計算自体が数分かかるというものもあるらしいです。私が昔聞いたころの計算機能力での話ですが。 ↩

DEAPに学ぶdeepなPython