Location : Home > Languages > Perl > Package
Title : Algorithm::Evolve
 		Toolbox Logo

名称

　Algorithm::Evolve - 進化アルゴリズム実行に関する拡張可能な一般的枠組み

概要

#!/usr/bin/perl -w
use Algorithm::Evolve;
use MyCritters;     ## 適切なメソッドによるクラス

sub callback {
    my $p = shift;  ## population オブジェクトに戻る

    ## 10 世代ごとに統計量を出力
    print $p->avg_fitness, $/ unless $p->generations % 10;

    ## 2000 世代で停止
    $p->suspend if $p->generations >= 2000;
}

my $p = Algorithm::Evolve->new(
   critter_class    => MyCritters,
   selection        => rank,
   size             => 400,
   callback         => \&callback,
);

$p->start;

## 最終的な結果を出力

説明

　本モジュールは進化アルゴリズムの迅速で容易な実装のための有用なツールとなることを意図して開発された。柔軟でありながら簡単であることを目指している。このため、全ての可能な進化アルゴリズムを網羅しているわけではない。Perl の柔軟性により、単純な文字列・配列・配列のハッシュといった深い構造や他の CPAN モジュールで作成されたグラフオブジェクトのような複雑なものなど、考えうるいかなるタイプの進化も対象とできる。
　進化アルゴリズムは一般に CPU-集約的であることに言及することには意味がある。非常に多数回 rand() を呼び出し、多数回浮動小数点の計算を行う。もし電光石火の速度の枠組みを求めているなら、CPAN はおそらく探し始めるにはまずいところである。しかしこれは私が効率を追求していないということではない。適合関数（fitness function）が最大のボトルネックなのである。

枠組みの概観

　進化アルゴリズムの設定可能な箇所は次の２つに分類される。

進化させる遺伝子の内部表現に依存するもの

　これらには適合関数・交叉（crossover）及び突然変異（mutation）演算子が含まれる。例えば文字列の遺伝子を進化させるには配列遺伝子を進化させるのとは異なった突然変異演算子が必要である。

表現が独したもの

　これらには選択（selection）・置換（replacement）メソッド、population の数・事象数などが含まれる。

　Algorithm::Evolve ではオプションの最初のグループは最大限の柔軟性をもってユーザにより実装されることになる。これらの関数は進化可能なクラス（本ドキュメントでは Critter クラス）に抽出されている。モジュール自体は設定スィッチやメソッドを用いてアルゴリズムの表現独立性を扱っている。

使用方法

　あなたがとにかく動くものを手にしてみたいという人種ならここで止めてまずは examples フォルダにある中身を見たほうがいいだろう。

Critter オブジェクトクラス（インタフェース仕様）の設計

　Algorithm::Evolve は進化させるべき Critter オブジェクトの population を管理している。以下のメソッドで提供されているクラスを用いて望むオブジェクトのタイプを進化させることができる。

Class->new()

　本メソッドは引数なしでクラスメソッドとして呼び出される。祝福された critter オブジェクトを返す。 It is recommended that the 返された critter の遺伝子は無作為に初期化することを勧める。

Class->crossover( $critter1, $critter2 )

　本メソッドは２つの Critter クラスを引数としてクラスメソッドとして呼び出される。渡されたオブジェクトの遺伝子に基づく２つの新しい Critter クラスのリストを返す。

$critter->mutate()

　本メソッドは引数なしでインスタンスメソッドとして呼び出される。Critter の遺伝子は無作為に修正される。返り値は無視される。

$critter->fitness()

　本メソッドは引数なしでインスタンスメソッドとして呼び出される。問題内で定義された、通常非負の数値で示される適合度を返す。本メソッドは Algorithm::Evolve により Critter ごとに一度呼び出されるだけなので記録する必要はない。
　本メソッドは選択／置換を行ったときにのみ無視される（後述）。

Class->compare( $critter1, $critter2 )

　本メソッドは選択メソッドとともに Co_Evolution|co-evolution に利用される。 $critter1 のほうが「よい」場合には負の値が、同じ値である場合には 0 が、$critter2 のほうが「よい」場合は正の値が返される。

　population から Critter が削除されたかを検出するために DESTROY メソッドを用いることもできる。
　Critter クラスのサンプルを見るには examples フォルダを見よ。また Critter クラスを実装するのに有用なユーティリティを提供している Algorithm::Evolve::Util も参照のこと。

Algorithm::Evolve population interface

$p = Algorithm::Evolve->new( option => value, ... )

　引数としてハッシュを取り、population オブジェクトを返す。関連するオプションは以下の通り。

critter_class：進化されるべきオブジェクトの Critter クラスの名称。このクラスはコード内で use または require で宣言されているものとする。
selection 及び replacement：selection 及び replacement メソッドを用いるタイプ。使用可能なメソッドは現在では以下の通り。

  • tournament：指定したサイズのトーナメントグループを生成する。（後述））
    　適合度が高いほうの２つのグループのメンバーが育てられ、適合度の低いほうの２つが置換される（これは単純トーナメント選択と呼ばれる）。selection 及び replacement が指定されている必要がある。
  • gladitorial：後述の共進化（Co_Evolution|co-evolution）を見よ。selection 及び replacement が指定されている必要がある。
  • random：Critter を完全に無作為に選択する。
  • roulette：Critter を適合度に基づいた確率で重み付けして選択する。selection の際には各 Critter の重みは適合度が用いられる。replacement の際には Critter の重みには 1/(fitness + 1) が用いられる。
  • rank：Critter をランクに基づく確率で選択する。selection の際には最高の Critter の重みは $p->size が用いられ、最低のものには 1 が与えられる。replacement に際しては逆順が用いられる。
  • absolute：Selection には N 番目に適合度の高い Critter までが用いられ、Replacement には N 番目に低い Critter までが用いられる。

　異なる種類の selection や replacement メソッドを混合したり連続して用いたりしてもよい。例外は tournament と gladitorial である。selection 及び replacement メソッドの両方を用いるからである。メソッドが同じであれば引数のリストから一方を省いてもよい。

tournament_size：, only required if you choose tournament selection/replacement を選択した時にのみ必要で、少なくとも４以上でなければならない。
max_gladitorial_attempts：gladitorial selection における比較で育成を行う間、無作為に Critter を選択する際に引き分けを許す回数。最初に起こったときモジュールは文句を言う。
parents_per_gen 及び children_per_gen： 各世代における育成の数を制御する。children_per_gen は parents_per_gen の倍数でなければならない。parents_per_gen は偶数でなければならない。各世代で選択された親の各対は同じ数の子どもを生み、必要な回数 critter クラスにおいて交差メソッドを呼び出す。選択された親は children_per_gen/parents_per_gen だけの遺伝子複写の数を取得する。children_per_gen を指定しないと parents_per_gen と同じ値に設定される。両方指定しないとデフォルトの２に設定される。tournament 及び gladitorial selection では、children_per_gen は parents_per_gen と同じでなければならない。各世代におけるトーナメントの数は parents_per_gen/2.でなければならない。
size：population における Critter の数。
callback：オプションではあるが推奨される、関数への参照。引数は１つで population オブジェクトである。世代ごとに呼び出される。現在の統計情報を出力する際には有用である。ある世代数実行後（または他の目的で）停止させたいのであれば用いる必要がある。
random_seed：アルゴリズム実行前に srand を実行するために必要な種となるオプションの値。過去の値を再生産する際に用いる。もし指定しなければ Algorithm::Evolve は種を無作為に生成する。

$p->size()

　上で与えられた population の大きさを返す。進化アルゴリズム実行中は変更することができない。

$p->run()

　アルゴリズムを実行し、population が suspend されたときの結果を返す。

$p->suspend()

　アルゴリズムの繰り返しを停止し run メソッドから返るためにコールバック関数内部から本メソッドを呼び出す。

$p->resume()

　suspend された状態からアルゴリズムを再開する。

$p->generations()
$p->avg_fitness()
$p->best_fit()

　これらは population の現在の状態に関する基本的な情報を返す。おそらくはコールバックサブルーチン内部で利用する。best_fit メソッドは population で最良の Critter を返す。

$p->critters()

　population 内の Critter を適合度の昇順でソートした結果を含む配列への参照を返す。全 Population に対し繰り返しこれを用いることはできるが、配列を修正してはならない。

$p->fitnesses()

　population の適合度（昇順で）を含む配列への参照を返す。配列の順序は critter の配列に対応している。これは独自の seleciton / replacement メソッドを用いる際に有用である。配列は修正しないこと、

$p->random_seed()

　無作為な乱数の種を生成する。

$p->selection( [ $new_method ] )
$p->replacement( [ $new_method ] )

　実行中に selection/replacement メソッドを変更する。

$p->parents_children_per_gen($parents, $children)

　アルゴリズム実行中に Population の parents_per_gen 及び children_per_gen 属性を変更する。後者は前者の倍数でなければならないので変更する際は同時である。

共進化

　問題に絶対的な適合度が与えられていない場合、critter の適合度は他の population のメンバーに依存する。これは共進化（co-evolution）と呼ばれる。いい例がじゃんけんである。このゲームの進化戦略を求めようとすると、戦略の成功は population の残りの振る舞いにかかっている。
　このような進化アルゴリズムを実行するには、critter クラスに compare メソッドを実装し、gladitorial selection 及び replacement を実装しておく必要がある。
　Gladitorial selection/replacement は Critter の対を無作為に選択し、これらを比較する。結果が引き分けでなければ勝者は再生産する権利を得、敗者は置換される。この操作が全ての親の数を網羅するか時間切れになるまで行われる。

Selection/Replacement メソッドの追加

　ユーザが独自の selection 及び replacement メソッドを追加するには、Algorithm::Evolve::selection または Algorithm::Evolve::replacement の名前空間で宣言すればよい。最初の引数は population オブジェクトで２つめの引数は selection/replacement の対象となる Critter の数でなければならない。ユーザが選択した indices のリストに返るべきである。

use Algorithm::Evolve;

sub Algorithm::Evolve::selection::reverse_absolute {
    my ($p, $num) = @_;

    ## 適合度が低いほうから $num 個の critter のインデクスを選択する。
    ## 適合度の降順に並び替えられていることを思い出すこと。
    return (0 .. $num-1);
}

sub Algorithm::Evolve::replacement::reverse_absolute {
    my ($p, $num) = @_;

    ## 適合度の高いほうから $num 個の critters のインデクスを選択する。
    return ($p->size - $num .. $p->size - 1);
}

## これらは全体的な selection/replacement のようであるが、逆で、
## 進化アルゴリズムは適合関数を＊最小化する＊ものである。

my $p = Algorithm::Evolve->new(
    selection => reverse_absolute,
    replacement => reverse_absolute,
    ...
);

　様々な selection/replacement メソッドがどのように実装されているかを見るためには本モジュールのソースを見よ。
　selection/replacement メソッドを追加する機構については将来のバージョンで変更するかも知れない。

参考資料

　example フォルダにある Algorithm::Evolve::Util|Algorithm::Evolve::Util

著者

　Algorithm::Evolve は Mike Rosulek <mike@mikero.com> により開発された。コメント・質問・パッチ・その他もろもろは私までコンタクトを。

著作権

　Copyright (c) 2003 Mike Rosulek. All rights reserved.

　本モジュールはフリーソフトウェアであり、Perl 本体と同等の条件で修正／再配布してもよい。

［訳注］

　文中でよく出てくる critter だが、creature と同類の言葉で「生き物」とか「やつ」とかの意味がある。対象にしているのが「進化」なのでクラスの名前に「生き物」という意味の言葉が使われているのが英語的にはすごくうまい表現なのだが、これを日本語では適切に表せず、そのままにしているのがとても残念。orz

Toolbox Logo
 Updated : 2008/04/10