8.2. 遺伝的アルゴリズム (GA)

GAは発見的な最適化手法で、限定 された無作為の検索の中で働きます。最適化の問題に対する一式の解は 個体人口と呼ばれます。 個体の環境への採用は適合度によって指定されます。

探策空間の中で個体の座標は、染色体によって表されます。 これは本質的には一式の文字列です。遺伝子は染色体の 一部であり、最適化をしようとしているパラメータの値をコード化します。 遺伝子のコード化の典型的な例としてはバイナリ整数があります。

進化論の過程のシミュレーションである、組換え突然変異、そして選択を 通して、祖先よりも 適合度の平均が高い新世代の探策点が見つけられます。

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

GAの構造図:

---------------------------


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

+=========================================+
|>>>>>>>>>>>  Algorithm GA  <<<<<<<<<<<<<<|
+=========================================+
| INITIALIZE t := 0                       |
+=========================================+
| INITIALIZE P(t)                         |
+=========================================+
| evalute 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)}  |
|   +-------------------------------------+
|   | evalute FITNESS of P''(t)           |
|   +-------------------------------------+
|   | t := t + 1                          |
+===+=====================================+