遺伝的アルゴリズム

－４．遺伝的アルゴリズム（ GA: Genetic Algorithm ）－

　　「生物は，交叉，突然変異，淘汰を繰り返しながら，環境に適合するように進化していく」と言われています．環境に適合する度合い（以後，適合度と呼びます）を数値で表せば，進化して生き残った個体の数値は徐々に高くなっていくことになります．

　　適合度を最適化問題の目的関数と考えると，目的関数の値が進化と共に徐々に大きくなっていくことになります．つまり，目的関数を最大にするという最適化問題の解に近づいていくことになります．

　　そこで，コンピュータ上に仮想生命を生成，かつ，その環境に対する適合度を最適化問題の目的関数に一致させ，進化の過程をシミュレーションすることによって，最適化問題を解くことが可能になります．これが，遺伝的アルゴリズム（ GA: Genetic Algorithm ）によって最適化問題を解く基本的考え方です．

４．１基本的用語

　　GA のアルゴリズムの説明に入る前に，GA で使用されている基本的な用語について説明しておきます．

個体（ Individual ）：　染色体によって特徴づけられた自律的な個
集団（ Population ）：個体の集まり
集団サイズ（ Popolation Size ）：集団内の個体数
遺伝子（ Gene ）：個体の形質を規定する基本構成要素
対立遺伝子（ Allele ）：遺伝子がとりうる値
染色体（ Chromosome ）：複数の遺伝子の集まり
遺伝子座（ Locus ）：染色体上の遺伝子の位置
遺伝子型（ Genotype ）：染色体の内部表現（文字列，木構造 or グラフ）
表現型（ Phenotype ）：染色体によって規定される形質の外部的表現．例えば，「染色体上のある位置の遺伝子の並びが 010 であるときは，羽の色が赤くなる」というような場合，「010」が遺伝子型に，また，「羽の色が赤くなる」ということが表現型に相当する．
適合度（ Fitness ）：各個体の環境に対する適合の度合い
コード化（ Coding ）：表現型から遺伝子型へ変換すること
デコード化（ Decoding ）：遺伝子型から表現型変換すること

４．２アルゴリズム

　　GA を使用して最適化問題を解く場合，「各個体をどのように表現するか」ということを決めてやる必要があります．遺伝子型を決めるためには，対立遺伝子や染色体の長さ（遺伝子長）を決める必要があります．一般的に，対立遺伝子として 0 と 1，遺伝子長を固定（例えば，n）する場合が多いようですが（この場合，染色体は，n 個の 0 と 1 の並びになる），問題によって様々です．必ずしも，実際の生物の表現方法にこだわる必要はありません．

　　また，表現型や適合度の計算方法も決めてやる必要があります．いずれにしろ，遺伝子型，表現型，適合度の計算方法等は，問題を解く効率に大きな影響を与えます．十分検討の上，決定する必要があります．

　　以上述べたことが決定されると，実際にプログラムを書くことになるわけですが，そのプログラムの基本的な流れは以下のようになります．

初期化

　　N 個の個体からなる初期集団を発生させ，各個体の適合度を計算しておきます．通常，各遺伝子の値はランダムに決定します．

　　ここで問題になるのは，集団サイズ N をどの程度にすべきかという点です．一般的に，遺伝子長が長ければ長いほど，大きな集団サイズが必要になります．また，同じ問題の場合，集団サイズを小さくすると，1 世代あたりの計算量は減りますが，収束するまでの世代数が大きくなると共に，局所的な最適解に陥る可能性が高くなります．集団サイズを大きくすると，収束するまでの世代数は小さくなりますが，1 世代あたりの計算量が増えます．
生物集団の評価

　　収束したか否かの判定を行います．判定方法としては，以下のようなものが考えられます．
1. 生物集団中の最大の適合度が，ある閾値より大きくなった場合
2. 生物集団全体の平均適合度が，ある閾値より大きくなった場合
3. 生物集団の適合度の増加率がある閾値以下の世代が一定期間続いた場合
4. 世代交代の回数が規定の回数を超えた場合
交叉

　　子供を生成する過程です．交叉方法に対しては，問題によって様々な方法が提案されていますが，一般的な方法として，以下に示すような方法が考えられています．

　　集団内よりランダムに M 個のペア（親）を選択し，設定された交叉確率 P_c （交叉が発生する確率）に従って， 2 * M 個の子供を生成します．ここで，M の値も，集団サイズ N と同様，GA の効率に大きな影響を与えます．各ペアから子供を生成する方法（交叉方法）には，例えば，以下に示すようなものが存在します．
1. 1 点交叉　　染色体の切断箇所をランダムに 1 カ所指定し，その箇所（下の例における赤線の部分）で親の遺伝子を交叉させる．
  01001|101 01001110 親 → 子供 01100|110 01100101
2. 多点交叉　　染色体の切断箇所をランダムに複数カ所（下の例では，2 カ所）指定し，それらの箇所で親の遺伝子を交叉させる．
  010|011|01 01000101 親 → 子供 011|001|10 01101110
3. 一様交叉　　染色体と同じ長さのマスクと呼ばれるビット列を，0 に対しては確率 p，また，1 に対しては確率 (1-p) で発生させ，マスクの値が 1 であるときは親 A の遺伝子を子 1（親 B の遺伝子を子 2）に，また，0 であるときは親 B の遺伝子を子 1（親 A の遺伝子を子 2）に継承させる．例えば，マスクが 00101011 となった場合は，以下のようになる．
  A 01001101 1 01000101 親 → 子供 B 01100110 2 01101110
　　個体の遺伝子型が連続値を表すときには，2 つの親の平均値を子の遺伝子とする平均化交叉等の方法も使用されます．平均化交叉では，2 つの親から 1 つの子供が生成されます．

　　今までの例に挙げた染色体では，対立遺伝子が 0 と 1 であり，染色体内に 0 や 1 が複数個現れています．しかし，問題によっては，染色体内に同じ対立遺伝子が現れないようにしたい場合があります．例えば，14352 という染色体は許されるが，12352 のように，同じ対立遺伝子が 2 回以上現れることは許したくない場合です．巡回セールスマン問題等を GA で扱いたい場合によく現れます．このような場合に対する交叉方法としては，以下のようなものがあります．
1. 循環交叉　　ランダムに 1 点を選択し，その位置にある遺伝子をそのまま各子供が選択する（青色の部分）．その位置にある親 2（ 1 ）の遺伝子を，その遺伝子の親 1（ 2 ）の場所に，子 1（ 2 ）が受け継ぐ（緑色の部分）．この手続きを，すでに受け継いだ遺伝子の位置が選択されるまで繰り返す．残りの遺伝子について，子 1（ 2 ）は，親 2（ 1 ）の遺伝子をその順番通りに受け継ぐ．
  1 2 4 1 3 6 5 + + 1 + + 5 1 3 2 1 4 6 5 親 * → → 子供 2 3 2 5 4 1 6 + + 5 + 1 + 2 2 4 5 3 1 6
2. 部分的交叉　　まず，各子供は，各親の遺伝子をそのまま受け継ぐ．ランダムに切れ目を選択し，切れ目の右側で，同じ位置にある子 1 と子 2 の遺伝子を取り出す（青色の部分）．次に，子 1 及び子 2 の染色体上で，この 2 つの遺伝子の位置を交換する（右図）．この操作を，切れ目の右側にあるすべての遺伝子対に対して実施する．
  2 4 1 | 3 6 5 2 3 5 4 1 6 → 3 2 5 | 4 1 6 4 2 6 3 5 1
3. 順序交叉　　ランダムに切れ目を決定し，子 1 に対し，切れ目の左側では，親 1 の遺伝子をそのまま受け継ぎ，右側では，親 1 の遺伝子を親 2 の遺伝子の出現順序に並べ替える．
  2 4 | 1 3 6 5 2 4 3 5 1 6 → 3 2 | 5 4 1 6 3 2 4 1 6 5
4. 一様順序交叉　　位置の集合をランダムに選択し，一方の親の選択された位置における遺伝子の順序に従って，他の親の遺伝子を並べ替える
  a b c d e f g h i j a i c d e b f h g j * * * * → e i b d f a j g c h b i c d f a j g e h
5. 一様位置交叉　　位置の集合をランダムに選択し，一方の親の選択された位置における遺伝子の位置に，他の親の同じ遺伝子を配置する．残りの遺伝子は，親と同じ順序に配置する．
  a b c d e f g h i j a i b c f d e g h j * * * * → * * * * e i b d f a j g c h i b c d e f a h j g
突然変異

　　ある与えられた確率 P_m（突然変異率）で，突然変異を起こさせます．一般的に，突然変異は，局所的最適解からの脱出に効果があります．しかし，突然変異率を大きくすると，ランダム探索に近い状態になりますので，通常，小さな値が使用されます．突然変異方法としては，以下のようなものがあります．
1. 一般的な方法　　各遺伝子をランダムに対立遺伝子に置き換える
2. 摂動　　染色体が連続値を表すときに使用され，値をランダムに与えられた幅だけ変更する
3. 逆位　　ランダムに選ばれた 2 点間の要素の順序を逆転する
4. スクランブル　　ランダムに選ばれた 2 点間の要素の順序をランダムに並べ替える
5. 転座　　ランダムに選ばれた 2 点間の要素を他の位置のものと入れ替える
6. 重複　　ランダムに選ばれた 2 点間の要素を他の位置にコピーする（遺伝子長が変化）
7. 位置移動　　ランダムに遺伝子を 2 個選択し，2 番目の遺伝子を 1 番目の遺伝子の前に移動する
8. 挿入　　ある長さの遺伝子を挿入する（遺伝子長が変化）
9. 欠失　　ある長さの遺伝子を消去する（遺伝子長が変化）
各個体の評価　　各個体の適合度を計算します．
淘汰　　ここまでの過程により，一般的に，個体数は N + 2 * M （交叉方法によっては，N + M ）となっているはずです．ここで，環境に適合しない個体を淘汰することによって，個体数を N に戻し，世代数 = 世代数 + 1 とし，2 に戻ります．淘汰方法としては，以下のようなものがあります．
1. エリート選択　　単純に，適合度が高い N 個の個体を残す方法です．この方法は簡単ですが，局所的最適解に陥りやすく，一般には，次に述べるルーレット選択と併用して使用します．つまり，ある数（< N）だけエリート選択で選択した後，残りをルーレット選択で選びます．
2. ルーレット選択　　適合度に基づいたルーレット版を作成し，そのルーレット版を使用してランダムに選択する方法です．例えば，現在の個体数が 5 で，かつ，各個体の適合度が，
  A　　40
  B　　20
  C　　20
  D　　10
  E　　10
  であったとします．適合度をそのまま利用してルーレット版を作成すれば，右図のようになります．集団サイズ N が 3 であれば，このルーレット版を 3 度回して，3 つの個体を選ぶことになります．確かに，個体 A が最も選ばれやすくなりますが，個体 D や E が選ばれる確率も 0 ではありません．
  
  　　ルーレット版を作成する際，適合度をそのまま利用する方法以外，適合度に順位をつけて，適当な減少率で線形化する方法，非線形変換を行う方法等，様々な方法が提案されています．

４．３スキーマ定理

　　この節では，スキーマ定理について説明します．スキーマとは，染色体と同じような文字列ですが，その中に don't care 記号「*」が含まれています．* は，任意の文字に対応する記号であり，例えば，スキーマ S が *1**10*** と表現されていると，2 番目，5 番目，及び，6 番目の文字が，0，1，及び，0 であるすべての文字列，例えば，

111110111, 111110110, ･･･

に相当します．ここで，以下の定義をしておきます．

O(S)： 次数（オーダー）．スキーマ中の定数の数である．上の例では，3 になる．
δ(S)： 定義長．スキーマ中の最初と最後の定数間の距離である．上の例では，4 になる．

　　ルーレット選択，1 点交叉，及び，一般的突然変異を使用した GA を，単純 GA と呼びますが，単純 GA のもとで，選択だけを考慮すると，以下の関係が成立します．

P(S, t+1) = P(S, t) * f(S) / f_m
	P(S, t)： 時刻 t において，スキーマ S を遺伝子型に含む個体の数
	f(S)： スキーマ S を遺伝子型に含む個体の平均適合度
	f_m： 集団内の全個体の平均適合度

また，1 点交叉によってスキーマＳが破壊される確率は，以下のようになります．

P_c * δ(S) / (L - 1)
	P_c： 交叉確率
	L： 遺伝子長

さらに，突然変異によってスキーマ S が破壊される確率は，以下のようになります．

P_m * O(S)
	P_m： 突然変異率

以上述べたスキーマの破壊を考慮すると，以下の式が成立します．

		P(S, t+1) = P(S, t) * f(S) / f_m * [1 - P_c * δ(S) / (L - 1) - P_m * O(S)]

　　この式は，「定義長 δ(S) が短く，次数 O(S) が低く，かつ，平均適合度 f_m より高い適合度をもつスキーマ S が次の世代で生き残れる確率が高い」ということを意味しています．つまり，「適合度が高く，短いスキーマが遺伝子型に存在する場合，そのスキーマは交叉や突然変異によって破壊されることなく，世代交代と共にその数を増やしていく」ということを意味しています．

４．４ＧＡの適用例

　　この節では，GA をいくつかの問題に適用した例を示します．必ずしも，GA を使用すべきであるような問題ではありませんが，単なる例として眺めてください．

４．４．１「1」の数

　　まず，簡単な問題によって，GA を体験してください．問題は，以下のような問題です．下に示される図（ JavaScript のプログラムによる表示）の指示に従って，GA を実行してみてください．なお，選択する場合，適合度が大きいものを意図的に選択するようなことはしないでください（そのようにしなくても，全体的に，適合度が大きくなっていくはずです）．

各個体の染色体： 0 と 1 の 10 個（10 が遺伝子長）の並び
適合度：染色体に現れる 1 の数
交叉方法： 1 点交叉（交叉の際，選択する親ペア数は 2）
突然変異：なし
淘汰方法：エリート選択
集団サイズ： 5

第 1 世代

(1) 0101010101　　適合度 5

(2) 0101010101　　適合度 5

(3) 0101010101　　適合度 5

(4) 0101010101　　適合度 5

(5) 0101010101　　適合度 5

親を 2 つ選んでください（ 1 ～ 5 ）

４．４．２巡回セールスマン問題

　　50 都市に対する巡回セールスマン問題を，以下のような設定で，GA で解いてみます．各個体は，都市番号の並びであり，その順番が都市を訪れる順序になります．　→　（ C/C++によるプログラム例　→　

，なお，他の言語（ PHP，Ruby，Python，C#，VB ）によるプログラム例に関しては，「プログラミング言語の落とし穴」第 9 章の「遺伝的アルゴリズム（ TSP，関数の最大値）」をご覧ください．）

遺伝子長： 50
集団サイズ： 200
交叉時の親のペア数： 250
交叉方法：順序交叉
突然変異方法：逆位（突然変異率： 0.03）
淘汰方法：ルーレット選択．ただし，上位 20 個はエリート選択で選ぶものとする．

　　結果は，例えば，以下のようになります（各世代における最も適合度が高いものを表示したもの）．

４．４．３関数の最大値

　　GA は，TSP のような組合せ最適化問題だけに利用できるわけではありません．この節では，先の節で使用した Species クラスを利用して，x が [0, 1]　のとき，次の関数の最大値を GA を使用して求めてみます．　→　（ C/C++によるプログラム例　→　

，なお，他の言語（ PHP，Ruby，Python，C#，VB ）によるプログラム例に関しては，巡回セールスマン問題の場合と同様，「プログラミング言語の落とし穴」第 9 章の「遺伝的アルゴリズム（ TSP，関数の最大値）」をご覧ください．）

f(x) = sin(3x) + 0.5sin(9x) + sin(15x + 50)

　　図からも明らかなように，この関数は多峰性です（山が 3 つある）．従って，非線形計画法の章で述べましたように，非線形計画法で述べたような方法を使用すると，初期値によって異なる最適解を得てしまう可能性があります．

　　例えば，黄金分割法を使用すると，初期値によって，得られる最適解は以下に示すように異なってきます．

初期値 0.0 1.0　（妥当な初期値の与え方ではない）
　　f(0.544158)=1.505713　（局所的最適解）
初期値 0.8 1.0
　　f(0.936235)=1.683352　（局所的最適解）
初期値 0.0 0.2
　　f(0.140792)=1.849314　（真の最適解）

　　しかし，GA を使用して解くと，この問題の場合，ほとんどすべての初期状態に対して，真の最適値に収束することが分かります．これは，GA においては，複数の初期値（複数の個体）から出発し，かつ，交叉や突然変異操作によって，局所的最適解に陥ることを防いでいるからです．

　　GA を適用するに当たり，まず，各個体の遺伝子型，表現型，適合度の計算方法等を決めてやる必要があります．遺伝子型は，0 と 1 の並びとし，変数 x の値に相当するものとします．実際の x の値（表現型）は，遺伝子長が n であれば，

x = （染色体を 2 進数とみなした値） / (2ⁿ - 1)

のようにして，計算できます．例えば，n = 5 で，かつ，ある個体の染色体が 01001 であれば，x = 9 / 31 = 0.29 となります．また，適合度は，得られた x を関数に代入した値とします．

　　その他，以下のような設定で GA を実行します．

遺伝子長： 20
集団サイズ： 20
交叉時の親のペア数： 10
交叉方法： 1 点交叉
突然変異方法：通常（突然変異率： 0.03）
淘汰方法：ルーレット選択．ただし，上位 2 つはエリート選択で選ぶものとする．

　　この結果，以下のような結果が得られます．各行の 2 番目が変数 x の値，最後が関数の値（適合度）です．第 1 世代（初期世代）では，x の値が区間 [0, 1] に散らばっていますが，世代を経る毎に，最適値の周りに集まっていくのが分かると思います（最も適合度が高い固体を緑色で示してあります）．

第 1 世代
　 1 0.664669    0.487323
　 2 0.449878    0.779902
　 3 0.421274    0.423158
　 4 0.0939523   1.56253
　 5 0.915608    1.63245
　 6 0.62815     0.921525
　 7 0.0661469   1.14195
　 8 0.248805    0.75209
　 9 0.905189    1.57068
　10 0.035594    0.529243
　11 0.349932   -0.10005
　12 0.536941    1.50067
　13 0.435383    0.596746
　14 0.00834561 -0.0772843
　15 0.16543     1.77348
　16 0.318222   -0.0260138
　17 0.941928    1.67931
　18 0.789944    0.233126
　19 0.467931    1.00069
　20 0.032279    0.456871

第 5 世代
　 1 0.916775   1.63794
　 2 0.945149   1.67341
　 3 0.0939523  1.56253
　 4 0.915608   1.63245
　 5 0.915554   1.63219
　 6 0.165365   1.77387
　 7 0.893734   1.47846
　 8 0.165431   1.77348
　 9 0.941928   1.67931
　10 0.91576    1.63318
　11 0.915429   1.63158
　12 0.168628   1.75312
　13 0.935384   1.68326
　14 0.943199   1.6773
　15 0.165608   1.77241
　16 0.165432   1.77347
　17 0.978233   1.45976
　18 0.165366   1.77387
　19 0.917806   1.64254
　20 0.035677   0.531044

第 10 世代
　 1 0.1639    1.78243
　 2 0.945149  1.67341
　 3 0.943196  1.6773
　 4 0.165758  1.7715
　 5 0.157613  1.81349
　 6 0.165731  1.77167
　 7 0.165431  1.77348
　 8 0.908102  1.59019
　 9 0.970421  1.53517
　10 0.133137  1.84168
　11 0.907919  1.58902
　12 0.918663  1.64618
　13 0.157947  1.81207
　14 0.165443  1.77341
　15 0.134053  1.8434
　16 0.168616  1.7532
　17 0.106131  1.69155
　18 0.111654  1.73778
　19 0.134542  1.84423
　20 0.106116  1.69142

第 15 世代
　 1 0.130696  1.83601
　 2 0.134681  1.84445
　 3 0.945149  1.67341
　 4 0.165758  1.7715
　 5 0.165761  1.77148
　 6 0.943987  1.67585
　 7 0.134543  1.84423
　 8 0.134542  1.84423
　 9 0.915759  1.63317
　10 0.181477  1.64957
　11 0.165667  1.77206
　12 0.134725  1.84452
　13 0.944008  1.6758
　14 0.107258  1.70162
　15 0.134602  1.84433
　16 0.195106  1.50613
　17 0.1061    1.69127
　18 0.169673  1.74597
　19 0.88456   1.38873
　20 0.111685  1.73801

第 20 世代
　 1 0.121695  1.80149
　 2 0.134681  1.84445
　 3 0.150306  1.83773
　 4 0.127601  1.82656
　 5 0.165914  1.77055
　 6 0.149603  1.83937
　 7 0.164312  1.78007
　 8 0.165762  1.77148
　 9 0.140982  1.84931
　10 0.149573  1.83944
　11 0.134673  1.84444
　12 0.126868  1.82395
　13 0.133169  1.84174
　14 0.944008  1.6758
　15 0.126364  1.82207
　16 0.165916  1.77054
　17 0.134528  1.84421
　18 0.121692  1.80148
　19 0.943991  1.67584
　20 0.140983  1.84931

　　次に，非線形計画法の中で対象とした 3 つの 2 変数関数の最小値を GA によって求めてみます．ただし，このプログラムは，今まで述べてきた例において使用した Species クラスの一部だけを利用しています．　→　（ C/C++ によるプログラム例　→　

）

システムの最適化

－ ４．遺伝的アルゴリズム（ GA: Genetic Algorithm ） －

－４．遺伝的アルゴリズム（ GA: Genetic Algorithm ）－