Location : Home > Languages > Perl > Package Title : AI::Genetic

名称

　AI::Genetic - ジェネティックアルゴリズムの pure Perl 実装

概要

use AI::Genetic;

my $ga = new AI::Genetic(
   -fitness    => sub { rand },
   -type       => 'bitvector',
   -population => 500,
   -crossover  => 0.9,
   -mutation   => 0.01,
  -terminate  => sub { rand > 0.5 },
);

$ga->init(10);
$ga->evolve('rouletteTwoPoint', 100);

print "Best score = ", $ga->getFittest->score, ".\n";

説明

　本モジュールは遺伝アルゴリズム（GA; Genetic Algorithm）を純粋な Perl で実装している。
　他の Perl モジュールでも同じ目的を達成しているものもあるだろうから、CPAN をチェックしてほしい。私は本モジュールを自分の必要のためにと、GAを勉強しようとして書いたものである。
　注意：これは v0.02 である。AI::Genetic はモジュール的にかつ拡張可能なように書き直した。これを達成するために API を書き換える羽目になり、v0.01 とは互換性がない。つまりは私は v0.01 をサポートするつもりはない。
　ここでは GA について詳細には触れないが、基礎的なことには触れておく。多くの情報がウェブ上で確認できるだろうから。

　GA では、多くの個体が生存をめぐって競争する。各個体はその振る舞いを定義する遺伝子の集合で規定される。よい個体（適合度関数により定義）は他の個体と組になる可能性が高くなる。２つの個体が組になればいくつかの遺伝子を交換し、「親」の属性を引き継ぐ個体ができる。時々遺伝子の値がランダムに変化する突然変異が発生し異なった個体をもたらす。全てがうまく行けば少ない世代で十分によい結果に到達する。

　GA 実装では世代（generations）で表現される離散の時間刻みで実行される。各世代間で起こることは戦略に依存する（戦略を参照のこと）。典型的には以下のようなことが起こる。

1. 選択（Selection）

　各個体は特定の適合度値を持っており、全ての個体の能力が適合度関数に基づいて評価される。 値が大きければ交差を通じて次の世代に生き残る可能性が高くなる。

2. 交差（Crossover）

　交差（性的再生産）のために個体がランダムに組み合わされる。双方の親からどれだけ遺伝子を受け継ぐかに関する比率は指定されている。新しい個体は現在の集団に組み込まれる。

3. 突然変異（Mutation）

　このステップでは突然変異率に従って各個体が変異を起こす。ある個体が変異すれば遺伝子は他の状態にランダムに変更される。

クラスメソッド

　以下にパブロックメソッドを記す。

$ga->new(options)

　これはコンストラクタである。ハッシュ−値の対をオプションで受けとる。

• -population
  population の大きさ、すなわち各世代で同時に存在する個体の数をを定義する。デフォルトは 100。
• -crossover
  交差率を定義する。デフォルトは 0.95。
• -mutation
  突然変異率を定義する。デフォルトは 0.05。
• -fitness
  適合度関数を定義する。サブルーチンへの参照であることを想定する。詳しくは適合度関数を見よ。
• -type
  遺伝子の型を定義する。今のところ AI::Genetic では３つの型をサポートしている。
  
  • bitvector
    遺伝子がビットであるような個体。各遺伝子は２つのうち１つの可能な状態を指す。on または off など。
  • listvector
    各遺伝子が可能な文字列値の特定のリストから選んだ１文字列であるようなものを指す。
  • rangevector
    各遺伝子が可能な整数の範囲内のある整数であるようなものを指す。整数だけがサポートされていることに留意すること。ユーザは適切な10のべきを掛けたり割ったりして望む分数値などの変換することができる。
  デフォルトは bitvector である。
• -terminate
  このオプションにより終了サブルーチンを定義できる。サブルーチン参照であることが想定されている。このサブルーチンは１つの引数 AI::Genetic オブジェクトを受け取り、各世代の最後に呼び出される。サブルーチンが true を返すと進化が終了する。

$ga->createStrategy(strategy_name, sub_ref)

　このメソッドは進化の間に用いるユーザ定義の戦略を生成する。ユニークな戦略名とサブルーチンを引数とする。サブルーチンは AI::Genetic オブジェクトの１引数をとる。各世代で集団を変換する。詳しくは戦略を参照のこと。

$ga->init(initArgs)

　このメソッドは集団をランダムな個体で初期化する。evolve() または inject().が呼び出される前に呼び出されなければならない。副次的効果既に集団内に存在している個体は削除される。個体の型に依存して１つの引数をとる。

• bitvectors に対しては、引数は bitvector の長さである。
  

  $ga->init(10);
  

  これは10遺伝子を持つ集団を初期化する。
  
• listvectors に対しては、引数はリストの匿名リストである。サブリストの数は個々の個体の遺伝子の数に等しい。各サブリストは対応する遺伝子が想定する可能な文字列の値を指定する。
  

  $ga->init([
            [qw/red blue green/],
            [qw/big medium small/],
            [qw/very_fat fat fit thin very_thin/],
            ]);
  

  これは各個体が３遺伝子を持ち、それぞれが所与の値を持つ集団を初期化する。
  
• rangevectors に対しては、引数はリストの匿名リストである。サブリストの数は個々の個体の遺伝子の数に等しい。各サブリストは遺伝子が想定する整数の最小値と最大値を指定する。
  

  $ga->init([
            [1, 5],
            [0, 20],
            [4, 9],
           ]);
  

  これは各個体が３遺伝子を持ち、それぞれが指定された範囲内の整数を取る集団を初期化する。
  

$ga->inject(N, args)

　このメソッドは集団に新しい個体を追加する。新しい個体はランダムに生成されるかまたは明示的に指定される。最初の引数は追加すべき個体数 N を指定する。この後に、追加する個体を表す遺伝子を指定する最大 N 個の引数をとる。指定された遺伝子の数 n が N よりも小さければ N - n 個の個体をランダムに生成する。ランダムな個体は init() メソッドに同じ引数を渡して生成される。

例：

$ga->inject(5,
            [qw/red big thin/],
            [qw/blue small fat/],
           );

　これは５つの新しい個体が追加され、２つが指定されたもの、３つがランダムに生成されたものである。

$ga->evolve(strategy, num_generations)

　このメソッドは指定の戦略により集団を進化させて解く。
　戦略名は第１引数で指定される。第２引数はオプションで進化させる世代の数を指定する。デフォルトは 1 である。デフォルトの戦略に関するさらんる情報は戦略を参照のこと。
　書く世代は以下の段階からなる。

• population を個体の適合度順にソートする。
• 命名された戦略に対応するサブルーチンが AI::Genetic オブジェクト１引数とともに呼び出され、そのオブジェクト自身を変換する。
• 終了サブルーチンが指定されていれば実行されて返り値を確認 true を返せば終了。

$ga->getFittest(N)

　これは適合度の高い順に N 個の個体を返す。もし指定されなければ N のデフォルトは 1 である。副次的効果として適合度により集団がソートされる。AI::Genetic::Individual オブジェクトが返される。
　個体の遺伝子または値が取得したければ genes() 及び score() メソッドを用いる。詳しくは AI::Genetic::Individual をチェックすること。

$ga->sortPopulation

　このメソッドは適合度に従い集団をソートする。速度を優先して結果はキャッシュされる。

$ga->sortIndividuals([ListOfIndividuals])

　所与の個体の匿名リストに対し、このメソッドは適合度によりソートし、ソートされた個体の匿名リストを返す。

$ga->people()

　現在の集団の個体のリストを返す。
　重要：AI::Genetic オブジェクトにより使われる配列参照が返される。そのため $ga には多くの変動がある。

$ga->size(newSize)

　このメソッドは集団の大きさを取得／設定する。

$ga->crossProb(newProb)

　このメソッドは交差率（crossover rate）を取得／設定する。

$ga->mutProb(newProb)

　このメソッドは突然変異率（mutation rate）を取得／設定する。

$ga->indType()

　このメソッドは個体の型 bitvector, listvector, rangevector を返す。

$ga->generation()

　このメソッドは現在の世代を返す。

適合度関数

　適合度関数を適切に定義することがＧＡにおける最重要の局面である。遺伝アルゴリズムの計算において最も時間を費やすのは個体を分離してそれぞれの適合度を計算するところである。AI::Genetic では適合度をキャッシュすることで時間の最小化を図っているが、実行時間を短縮するには、適合度関数の最適化に多大な時間を費やさなければならない。
　適合度関数は引数が１つであることが想定されており、それは解析される対象の遺伝子のリストである。返り値はその個体に対する適合度である。値が大きければ大きいほど個体に適合度があり、交差で選択される機会が多くなる。

戦略

　AI::Genetic には 9 種類の戦略が準備してある。

rouletteSinglePoint

　この戦略はルーレット選択と単一点交差を実装している。

rouletteTwoPoint

　この戦略はルーレット選択と２箇所交差を実装している。

rouletteUniform

　この戦略はルーレット選択と均一交差を実装している。

tournamentSinglePoint

　この戦略はトーナメント選択と単一点交差を実装している。

tournamentTwoPoint

　この戦略はトーナメント選択と２箇所交差を実装している。

tournamentUniform

　この戦略はトーナメント選択と均一交差を実装している。

randomSinglePoint

　この戦略はランダム選択と単一点交差を実装している。

randomTwoPoint

　この戦略はランダム選択と２箇所交差を実装している。

randomUniform

　この戦略はランダム選択と均一交差を実装している。

　これらの戦略の詳細やどのようにユーザの固有の戦略に組み込むかについては AI::Genetic::OpSelection, AI::Genetic::OpCrossover, AI::Genetic::OpMutation を参照のこと。
　ユーザは上記モジュールで定義された関数を用いて独自の戦略を作成することができる。詳しくはマニュアルページを見よ。
　独自の戦略は strategy() メソッドを用いて定義することができ、各世代の最初に呼び出される。唯一の引数は AI::Genetic オブジェクト自身である。この点における集団は各個体の適合度順にソートされていることに注意すること。戦略サブルーチンは AI::Genetic オブジェクトに格納されている集団を修正することが想定されている。ここにコードもどきがある。

for (1 .. num_generations) {
   sort population;
   call strategy_sub;
   if (termination_sub exists) {
      call termination_sub;
      last if returned true value;
   }
}

速度／効率

　遺伝アルゴリズムは本質的に遅い。
　Perl は極めて処理が速いが、最適化された C コードの速度には敵わない（少なくとも私の Perl コーディングではそうだ）。私は AI::Genetic を主に自分の学習経験に基づいて書いたので、可能な限り柔軟性を保ったままで最適化を試みているところだ。
　このために、長いリストを渡す代わりにリストへの参照を渡したり（例えば適合度関数を呼び出す際に遺伝子のリストを渡す）、適合度をキャッシュしたり（同じ個体についての適合度が計算され、適合度関数が呼び出されないなら、キャッシュ結果を返す）などのよく知られた技を使おうとしている。
　実行時の速度を上げるためには、各世代において個体を呼び出すために適合度の計算に特別な注意を払う必要がある。そこで少しでも時間が節約できるなら、全体として大きな時間を節約できることになる。

バグ

　私はそれほど本モジュールをテストしたというわけではないが、問題を解く分にはエラーがない程度には確認した。しかしもしバグを見つけたら教えてほしい。それを必ず見るから。
　また、要望やコメント・示唆があるなら自由にメールしてほしい。

インストール

　よくやるように

perl Makefile.PL make make install

　と打つか、Perl が実行時に検索できるどこかに置いておき @INC で読み込むかである。これは純粋な Perl なんだから。

著者とクレジット説明

　Written by Ala Qumsieh, <aqumsieh@cpan.org>
　John D. Porter と Oliver Smith にはシミュレーションに関する議論をしてくれ、大きな示唆をくれたことに感謝している。 Daniel Martin と Ivan Tubert-Brohman はバグを指摘してくれて助かった。

著作権

　(c) 2003-2005 Ala Qumsieh. All rights reserved.

　本モジュールは Perl 本体と同等の条件で配布される。

Updated : 2008/05/08