Title : Math::ES
|
Location : Home > Languages > Perl > Package Title : Math::ES |
|
Math::ES - 進化戦略最適化
use Math::ES;
# 新規 ES オブジェクト
my $es new Math::ES (
'genes' => [ -100,-50, 5, 200],
'gene_deviations' => [ 1,1,1,1],
'max_gene_values' => [ 500, 500, 500, 500],
'min_gene_values' => [-500,-500,-500,-500],
'rating_function' => \&function,
);
my ($value1, $ra_genes1) = $es->start(); # ES を開始
# ... 他の処理 ...
$es->run(); # 再度 ES を実行
my @best_genes2 = $es->return_best_genes();
my $best_value2 = $es->return_best_value();
sub function {
my $sum;
foreach my $x (@_) {$sum += $x**2};
return ($sum);
}
パッケージ Math::ES は関数最小化のためのオブジェクト指向進化戦略（ES; Evolution Strategy）を提供する。複数の集団（multiple populations）・世代交代（elitism）・移住（migration）・隔離（isolation）・２つの選択スキーム・自己変化幅調整（self-adapting step widths）をサポートする。
進化プログラム（Evolution Programs）は1960年台に、別々の意図ではあるが、ドイツと合衆国で同時に考案された。John Holland は自然の最適化の形態を研究しようとし、生物学・生化学からの新たな知見を導入しようとし、進化アルゴリズム（GA; Genetic Algorithm）を考案した。他方、ドイツ人エンジニアである Ingo Rechenberg は実用的な問題解決に興味があり、彼の考案した進化戦略（Evolution Strategies）を現実の世界の問題に適用して成功を収めていた。
長い間、２つのアルゴリズムは互いに離反したままであった。今では多くのアイデアが混合され、単に進化プログラム（Evolution Programs）と呼ばれている。
しかしながら、最適化問題を扱うほとんどの人がGAをツールとみなしているが ES はあまり知られていない。GAでは伝統的に変数表現としてビット列を用いている（伝統的な２進数の欠点を克服するための特別なコーディングを開発した）のに対し、ESでは人が本当に望むであろう実数を利用しているのだから、奇妙なことである。
初期化
ES オブジェクトの初期化。入力遺伝子から複写された個体からなる集団が生成される。
ループ開始
進化過程の開始。主要な世代ループが始まる。
子の生成・交差・変異
定められた数の子が生成される。各子はランダムに選択された親から生成される。各子の遺伝子はそれぞれの親の遺伝子の値から（分散パラメータに基づき）ランダムに決定される。その後、各遺伝子の分散は variance_mutator パラメータの影響で変化させられる。
Be the variance at generation $i$ $\sigma_i$ then the updated
variance $\sigma_{i+1}$ is determined via
\begin{equation}
\sigma_{i+1} = \sigma_i * \exp({\cal N}(0,\Delta))
\end{equation}
with ${\cal N}(0, \Delta)$ being a random number from a
standard normal distribution with variance $\Delta$, the variance\_mutator parameter.
最後に、新しい遺伝子の値が stepwidth_const 及び stepwidth_var パラメータも従い0の周りの標準分布に従う乱数を加えることにより生成される。
The gene $x_i$ in generation $i$ is mutated to $x_{i+1}$ according to
\begin{equation}
x_{i+1} = x_i + s {\cal N}(0,\sigma_{i+1})
\end{equation}
with $s$ being the stepwidth defined by
\begin{equation}
s = a \cdot b
\end{equation}
Thereby $a$ is a constant stepwidth parameter (normally $1$)
and $b$ is the variable stepwidth parameter that is either $b$ or $1/b$
(decided randomly).
レート・ランク・子の選択
与えられた関数が全ての子に対して計算され、関数値の昇順に並べられる。最良の n または n-1 の個体の選択が行われる。もし世代交代が行われるなら残される個体は選択の対象ではなく、次の世代に保存される。
移住・集団の混合
移住を認めるならば定義された数の移住者が集団間で循環的に交換される。すなわち３つの集団があれば、まず集団１から集団２に移住し、集団２から集団３へ移住があり、空いている集団１の数を集団３からの移住で埋める。
最後に、混合が可能であれば、指定された隔離世代の間は何もせず、その後は全集団間で収集され、再配分される。
ループ終了
指定された数の世代が終了後、最適化が終了し、結果の探索が行われる。パラメータを更新するために同じコントロールパラメータで再度実行するかも知れない（概要を見よ）。
基本的な用法は概要に記述しており、自己説明的である。しかし以下のデフォルトパラメータはその意味の詳細な記述とともに表している。
ユーザが定義しなければならない genes, gene_deviations, max_gene_values, min_gene_values, rating_function を除けば、以下のコンストラクタリストはデフォルト値を指定することができる。
my $es = new Math::ES ( 'debug' => 0, 'log' => 1, 'log_file' => 'es-xx.log', 'dbg_file' => 'es-xx.dbg', 'individuals' => 5, 'parents' => 2, 'children' => 10, 'populations' => 2, 'selection_scheme' => 1, 'elite' => 1, 'generations' => 50, 'stepwidth_const' => 1, 'stepwidth_var' => 1.5, 'variance_mutator' => 0.5, 'migrators' => 1, 'isolation' => 25, 'genes' => [], 'max_gene_values' => [], 'min_gene_values' => [], 'gene_deviations' => [], 'max_gene_deviations' => [], 'min_gene_deviations' => [], 'rating_function' => '', );
debug
デバッグ出力をするか否かのフラグ。最初の ES オブジェクトについてはファイル es-1.dbg に出力される。
log
値が true であれば ES は各集団・各世代ごとで最良の遺伝子と関数の値を出力する。最初の ES オブジェクトについてはファイル es-1.log に出力される。
log_file
ログファイルの名称。ユーザにより上書きされない限り自動的に es-xx.log に設定される。ただし xx は全体で生成された ES オブジェクトの数の内部カウンタである。
dbg_file
デバッグファイルの名称。ログファイルと同様。
individuals
集団の中の個体の数を決定する。すなわち初期値と生存する子どもの数である。
parents
交差を用いて生成する子どもの数。parents = 1 ならば交差は行わず、遺伝子は親から複写される。そうでなければ各遺伝子とその変化はそれぞれの親からランダムに決定される。
children
各世代において生成された集団における子の数。子に対する個体の比率が少ないほど進化圧力は高まる。
populations
生成される（独立した）集団の数。
selection_scheme
適用される選択スキーム。２つのスキームが定義されている。
elite
選択から逃れられる最良の個体の数。
例えば elite = 1 であれば、次の世代に残されるのは最良の親と子の組のみであることを意味する。
generations
最適化を実行する回数。これのみがシミュレーションの終了条件であることに注意すること。
stepwidth_const
変異決定のための s_c パラメータ（詳しくは前セクションを見よ）。
stepwidth_var
変異決定のための s_v パラメータ（詳しくは前セクションを見よ）。
variance_mutator
遺伝子変化の変異のためのパラメータ。
migrators
各世代において（変異と選択の後に）隔離した集団との交換される個体（移住者）の数。
isolation
集団を隔離したままにしておく世代の数。０よりも大きければそれぞれの数の世代の後に全ての個体が集められ集団の間でランダムに分配される。
rating_function
これは遺伝子の配列を引数としてとるレイト付け関数への参照でなければならない。関数の値をスカラとして返す。ES はこの関数を最小化しようとする。
genes
最小化されるべきパラメータの配列。
gene_deviations
変異のために利用されるパラメータの分散の配列。
max_gene_values, min_gene_values
パラメータ境界の配列。
max_gene_deviations, min_gene_deviations
遺伝子変化の境界を示す配列。設定されなければ意図しない大きさまで大きくなる。
ES オブジェクトでは以下のメソッドが利用可能である。
start()
本メソッドは集団を構成し、計算を行う。初期化をし、ES を実行する。最良の関数値と最終の世代における最良の変数の値の配列への参照を返す。誤った入力の場合はエラーメッセージを返す。
run()
（同じパラメータで）ES を再実行する際に用いられる。更新に有用である(test.pl 内のサブルーチン test3 を見よ）。start() と同じ出力を返す。誤った入力に対してはエラーメッセージを返す。
return_best_genes()
最後の世代における最良の変数の組の配列を返す。
return_best_value()
最後の世代における最良の関数値を返す。
set_values()
今のところ、１つのオプションに対し実際の追加メソッドはない。
繰り返し後に ES オブジェクトのオプションを変更したければ値を直接に変更するしかない。
$es->set_values( 'generations' => 100 );
しかしながら、コントロール変数は変更することができる。中核のパラメータ（genes, gene_deviations, max_gene_values, min_gene_values, individuals の数；rating_function）は新たに初期化された ES オブジェクトが必要である。
validate()
ES を開始する前に実行する。全てがOKであれば空の文字列を返し、そうでなければエラーメッセージを文字列として返す。もしエラーがあれば start() または run() が実行された際に最初に validate() が内部で呼び出される。エラーがあればエラー文字列を返す。
現在のモジュールは CPAN の Math::Random に依存している。これがモジュールから検索できるところになければならない。
Anselm H. C. Horn, Computer Chemie Centrum, Friedrich-Alexander-Universitaet Erlangen-Nuernberg, Anselm.Horn@chemie.uni-erlangen.de, http://www.ccc.uni-erlangen.de/clark/horn
本ソフトウェアに対しては 'Artistic License' が適用される。詳細は Math::ES 内の LICENSE ファイルを見るか、http://www.opensource.org/licenses/artistic-license.php を訪問してほしい。
また、科学文献で本作品を引用するには以下のように表記して欲しい。
Anselm H. C. Horn, 'ES - Evolution Strategy Optimizer', Version x.xx Erlangen 2003; http://www.cpan.org/authors/id/A/AH/AHCHORN/Math/ES/
文献リストも含めて私に送ってくれることも検討して欲しい。
メインバージョンナンバーは 0.08 である。
perl(1).
更なる参照としては
本ソフトウェアは無保証である。詳細は著作権を見よ。
|
|
Updated : 2007/11/14 |