遺伝的アルゴリズム(Genetic Algorithm:GA)

自然界において個体を特徴づけているものは，遺伝子が一定の順序で配列してい る染色体である．この染色体の変異と環境による選択淘汰によって種の進化が実 現されている．Hollandの研究に始まるGAは，上述のような遺伝子情報に基づく 生物の環境適応的な進化過程を模擬した最適化手法である．GAを最適化問題に適 用する方法について以下に述べる．

まず最適化問題の決定変数ベクトル$x$を $N$個の記号 $X_i(i=1,\cdots,N)$の列で表すこととし，これを $N$個の遺伝子座からなる染色体とみなす． $X_i$は遺伝子であり，これの取り得る値が対立遺伝子である．対立遺伝子としては，通常， 0と1の2値，ある整数の組，ある範囲の実数値，単なる記号などが用いられる． このような記号化された染色体を個体の遺伝子型と呼び，染色体に対応して定ま る変数$X$の値を表現型と呼ぶ．次に，進化の過程の実現方法について述べる．

上述の記号化された染色体を用いて表現される$N_{\mbox{p}}$個の個体からなる集合(集 合 群)を考え，世代$t$における個体群に対して，以下のような遺伝的操作(遺伝演算子) を適用し，次の世代$t+1$の個体群を生成する．

(1)選択
世代$t$の個体集合中の各個体$i$について，その適応度$g_i$に応じ て，次世代に残す子の数を増減させる．代表的な選択方法として， 適応度比例選択(ルーレット選択)，期待値選択，ランキング選択な どが挙げられる．さらに，評価回数の低減の観点から， Steady State，Minimal Generation Gap(MGG)等が提案されている．
(2)交叉
個体集合内の個体をランダムに２個ずつ組み合わせ，ある確率(交叉率)で， 2つの個体の遺伝子列を部分的に交換する．代表的な交叉方法として，単純交叉， 複数交叉，一様交叉などが挙げられる.
(3)突然変異
各個体について，ある確率(突然変異率)で，各遺伝子座の遺伝子を 他の対立遺伝子と入れ替える．

このような遺伝的操作により世代更新を繰り返し，更新のたびにより良い個体 (より最適解に近い解$x$)が選択されて，増殖するようにすれば，やがて最適解 $x^0$が得られるであろうというのがGAの考え方である．


GAの全体的な流れを以下に示す．
$1^{\circ}$
ランダムに$M$個の個体を生成して初期個体集合$P(0)$を作り, 世代$t=0$ とする．繰り返し回数(最終世代)$T$を設定する.
$2^{\circ}$
個体集合$P(t)$内の個体に付いて，その適応度$g$を計算する.
$3^{\circ}$
個体集合$P(t)$に選択演算子を適用し，$P'(t)$を生成する．
$4^{\circ}$
$P'(t)$に交叉演算子を適用し，$P''(t)$を生成する.
$5^{\circ}$
$P''(t)$に突然変異演算子を適用し，次世代の個体集合 $P(t+1)$を生成する．
$6^{\circ}$
$t \leq T$ならば，$t=t+1$として$1^{\circ}$へ．そうで なければ計算終了．これまでに得られた最大適応度の個体 を準最適解とする．