無料スクリプト配布のPHP.TO   PHPの実用的なtips PHPマニュアル MySQLマニュアル Apacheマニュアル PostgreSQLマニュアル マニュアル検索    

53.2. 遺伝的アルゴリズム

遺伝的アルゴリズム( GA )は発見的な最適化手法で、無作為の検索として働きます。 最適化の問題に対する解の集合は 個体 とみなされます。 個体の環境への順応の度合は 適応度 によって指定されます。

検索空間の中で個体の同格性は、その実体が文字列の集合である 染色体 によって表現されます。 遺伝子 は最適化をしようとしている1つのパラメータの値を符号化する染色体の一部分です。 遺伝子の符号化の典型的な例として バイナリ もしくは 整数 が挙げられます。

進化の過程のシミュレーションである、 再組合せ 突然変異 淘汰 を通して、祖先よりも適応度の平均が高い新世代の検索点が見つけられます。

comp.ai.genetic FAQ によると、 GA が問題に対する純粋な無作為検索ではないことをどんなに強調してもし過ぎということはありません。 GA は確率的なプロセスを使いますが、結果は明らかに(無作為よりもより良い)非無作為です。

図 53-1. 遺伝的アルゴリズムの構造図

P(t) 時間tにおける先祖の世代
P''(t) 時間tにおける子孫の世代

+=========================================+
|>>>>>>>>>>>  Algorithm GA  <<<<<<<<<<<<<<|
+=========================================+
| INITIALIZE t := 0                       |
+=========================================+
| INITIALIZE P(t)                         |
+=========================================+
| evaluate FITNESS of P(t)                |
+=========================================+
| while not STOPPING CRITERION do         |
|   +-------------------------------------+
|   | P'(t)  := RECOMBINATION{P(t)}       |
|   +-------------------------------------+
|   | P''(t) := MUTATION{P'(t)}           |
|   +-------------------------------------+
|   | P(t+1) := SELECTION{P''(t) + P(t)}  |
|   +-------------------------------------+
|   | evaluate FITNESS of P''(t)          |
|   +-------------------------------------+
|   | t := t + 1                          |
+===+=====================================+

powered by SEO.CUG.NET