Title : Math::Evol
|
Location : Home > Languages > Perl > Package Title : Math::Evol |
|
Math::Evol - 進化探索による最適化
use Math::Evol; (\@xb,\@sm,$fb,$lf) = &evol(\@xb,\@sm,\&function,\&constrain,$tm); # または (\@xb, \@sm) = &select_evol(\@xb, \@sm, \&choose_best, \&constrain); # または $new_text = &text_evol($text, \&choose_best_text, $nchoices );
本モジュールは進化探索戦略を実装している。目的関数の微分は必要ない。制限条件を組み込むことができる。呼び出す側は変数の初期値と初期ステップサイズを指定する必要がある。
この進化戦略はランダム戦略であり、特に頑強であり、変数の数が多い場合や起伏の激しい目的関数にも適用することができる。
Evol.pm は自動で目的関数を最小化することも（evol）、対話形式で（多少煩雑であるが）人間が各段階で２つの可能性から選択していくことも（select_evol）できる。他のサブルーチン（text_evol）では特別なコメントによりテキストで指定されたパラメータを記述したテキストファイル内で数値パラメータを進化させることもできる。人間が判断するファインチューニングを利用したスクリプト ps_evol は PostScript で描かれている。
evol(\@xb, \@sm, \&minimise, \&constrain, $tm);
引数は以下の通りである。
ステップサイズ及び最小化対象の関数 &function ・&constrain は以下に記す。
$tm のデフォルト値は 10 秒である。
evol は以下の４つの値のリストを返す。
\@xb：変数の最良値
\@sm：ステップサイズの最終値
$fb：目的関数の最良値
$lf：成功したパラメータ
$lf はＣＰＵ時間を使い切れば false が設定される。
select_evol(\@xb, \@sm, \&choose_best, \&constrain, $nchoices);
引数は以下の通りである。
ステップサイズ及び最小化対象の関数 &function ・&constrain は以下に記す。
$nchoices は、現在の最良の値の配列に追加してユーザに提示される選択肢の数である。$nchoices のデフォルト値は 1 で、この場合にはユーザには現在の最良値ともう１つ選択肢を提示する。
evol は以下の２つの値のリストを返す。
\@xb：変数の最良値
\@sm：ステップサイズの最終値
text_evol( $text, \&choose_best_text, $nchoices );
$text は初期値、オプションで最大値・最小値を指定するために合言葉でマークされた数値パラメータを含むことを想定している。
例えば
$x = -2.3456; # evol step .1 /x 3.4567 def % evol step .2 /gray_sky .87 def % evol step 0.05 min 0.0 max 1.0
コメントのマジックビット（The magic bit）は evol step で、同じ行の過去の数値は変化した値として採られる。
関数参照 \&choose_best_text は以下に記す。
text_evol により渡される $nchoices は直接 select_evol に渡す。
&text_evol は最適化された $text を返す。
&text_evol は PostScript のファインチューニング用・特殊な GUI・HTML レイアウト・スタイルシート・または MIDI であることを意図している。これらは人間の判断による。
例として、ファインチューニングされた A4 PostScript の図用に呼び出された ps_evol が本パッケージには含まれている。その例では $nchoices = 8 で、最良のものを選択するために Ghostview で見ることのできるA4ページの上に9つの選択肢を示している。
呼び出す側ではステップサイズの初期値を指定しなければならない。
Rechenberg 及び Schwefel の業績に従い、evol はこれらのステップサイズを約 0.2 の成功率で修正していく。しかしステップサイズが生き残る比率が一定であるため、微妙な値に収束するのに役立つ。
大まかに言って、最適値から期待値までの差は変数の値の平方根である。
ステップサイズを大きくするほうが、極小値に陥らず最大値を探索する可能性を高める。ただし収束の速度は遅くなる。
minimise( @x );
evol は目的関数を最小化する。関数は変数のリストを受け取り、数値のスカラの結果を返す。例えば以下の通りである。
sub minimise { # 最小化されるべき目的関数
my $sum; foreach (@_) { $sum += $_*$_; } # Σ x**2
return $sum;
}
\@x = &evol (\@xb, \@sm, \&minimise);
constrain( @x );
変数に対し値を制限して与えるサブルーチン constrain(@x) を利用することができる。変数に制限を与えたくなければ代わりに 0 を与えればよい。constrain(@x) は値のリストを返す。例えば以下の通りである。
sub constrain { # 受付可能な範囲に値を設定する。
if ($_[0]>1.0) { $_[0]=1.0; # これは確率
} elsif ($_[0]<0.0) { $_[0]=0.0;
}
my $cost = 3.45*$_[1] + 4.56*$_[2] + 5.67*$_[3];
if ($cost > 1000.0) { # 最大費用を 1000 ドルに設定
$_[1]*=1000/$cost; $_[2]*=1000/$cost; $_[3]*=1000/$cost;
}
if ($_[4]<0.0) { $_[4]=0.0; } # 人口密度
$_[5] = int ($_[5] + 0.5); # 整数
return @_;
}
\@x = &evol (\@xb, \@sm, \&minimise, \&constrain);
choose_best( \@a, \@b, \@c ... );
参照が select_evol に渡される関数はmust accept a list of array_refs のリストを受け取らねばならない。最初の参照は値の現在の配列を参照し、残りは他の配列を参照する。
ユーザはどの配列が最適かを choose_best で選択しなければならない。$preference が array_ref (0, 1, etc) で参照された場合は ($preference, $continue) を返す。
ユーザが既に最適値に到達したと判断した場合はこれが select_evol の唯一の収束値となり他の引数 ($continue) は false に設定される。
例えば
use Term::Clui;
sub choose_best { my ($aref, $bref) = @_;
&inform("Array 0 is @$aref");
&inform("Array 1 is @$bref");
my $preference = 0 + &choose('Do you prefer 0 or 1 ?','0','1');
my $continue = &confirm('Continue ?');
return ($preference, $continue);
}
\@x = &evol(\@xb, \@sm, \&choose_best);
choose_best_text( $text1, $text2, $text3 ... );
参照が text_evol に渡される関数はテキスト文字列を受け付けなければならない。最初は現在の値であり、残りは他の値である。
ユーザはどの文字列が最適な結果を生み出すかを選択しなければならない。
choose_best_text は$preference が array_ref (0, 1, etc) で参照された場合は ($preference, $continue) を返す。
ユーザが既に最適値に到達したと判断した場合はこれが text_evol の唯一の収束値となり他の引数 ($continue) は false に設定される。
例としてファインチューニングされた A4 PostScript の図用に呼び出された ps_evol が本パッケージには含まれている。
Peter J Billam, http://www.pjb.com.au/comp/contact.html
ステップサイズを調整する戦略として成功率を 0.2 とするのは I. Rechenberg の業績である Optimisation of Technical Systems in Accordance with the Principles of Biological Evolution（Problemata Series, Vol. 15, Verlag Fromman-Holzboog, Stuttgart 1973） による。
evol のコードは Numerische Optimierung von Computer-Modellen mittels der Evolutionsstrategie から M.W. Finnis により英訳された（Interdiscipliniary Systems Research, Vol. 26）, Birkhaeuser Verlag, Basel 1977. における Hans-Paul Schwefel の業績である、Numerical Optimisation of Computer Models のフォートランバージョン（Wiley 1981, pp 104-117, 330-337）に基づく。
呼び出しインタフェースは大幅に Perl 用に修正されており、変数の制限は単純化されている。
滑らかな関数における小規模な問題（変数が50から60以下）に対する決定論的最適化戦略としてはもっと高速の方法はある。Nelder と Mead のシンプレックス戦略を実装した John A.R. Williams の CPAN モジュール Math::Amoeba を見よ。他のよいアルゴリズムとしては、まだ Perl に移植されていないが、Davidon, Fletcher, Powell and Stewart によるものがあり、これについては Algorithm 46 and notes, in Comp J. 13, 1 (Feb 1970), pp 111-113; Comp J. 14, 1 (Feb 1971), p 106 and Comp J. 14, 2 (May 1971), pp 214-215 を見よ。
http://www.pjb.com.au/・perl(1) も参照のこと。
|
|
Updated : 2008/10/07 |