静岡理工科大学 情報学部 菅沼ホーム 目次 索引

システムの最適化

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

  1. 4.1 基本的用語
  2. 4.2 アルゴリズム
  3. 4.3 スキーマ定理
  4. 4.4 GAの適用例
    1. 4.4.1 「1」の数
    2. 4.4.2 関数の最大値
    3. 4.4.3 巡回セールスマン問題
  「生物は,交叉,突然変異,淘汰を繰り返しながら,環境に適合するように進化していく」と言われています.環境に適合する度合い(以後,適合度と呼びます)を数値で表せば,進化して生き残った個体の数値は徐々に高くなっていくことになります.

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

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

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

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

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

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

  1. 初期化

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

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

  2. 生物集団の評価

      収束したか否かの判定を行います.判定方法としては,以下のようなものが考えられます.

    1. 生物集団中の最大の適応度が,ある閾値より大きくなった場合
    2. 生物集団全体の平均適応度が,ある閾値より大きくなった場合
    3. 生物集団の適応度の増加率がある閾値以下の世代が一定期間続いた場合
    4. 世代交代の回数が規定の回数を超えた場合

  3. 交叉

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

      集団内よりランダムに M 個のペア(親)を選択し,設定された交叉確率 Pc (交叉が発生する確率)に従って, 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
      				

  4. 突然変異

      ある与えられた確率 Pm(突然変異率)で,突然変異を起こさせます.一般的に,突然変異は,局所的最適解からの脱出に効果があります.しかし,突然変異率を大きくすると,ランダム探索に近い状態になりますので,通常,小さな値が使用されます.突然変異方法としては,以下のようなものがあります.

    1. 一般的な方法  各遺伝子をランダムに対立遺伝子に置き換える

    2. 摂動  染色体が連続値を表すときに使用され,値をランダムに与えられた幅だけ変更する

    3. 逆位  ランダムに選ばれた 2 点間の要素の順序を逆転する

    4. スクランブル  ランダムに選ばれた 2 点間の要素の順序をランダムに並べ替える

    5. 転座  ランダムに選ばれた 2 点間の要素を他の位置のものと入れ替える

    6. 重複  ランダムに選ばれた 2 点間の要素を他の位置にコピーする(遺伝子長が変化)

    7. 位置移動  ランダムに遺伝子を 2 個選択し,2 番目の遺伝子を 1 番目の遺伝子の前に移動する

    8. 挿入  ある長さの遺伝子を挿入する(遺伝子長が変化)

    9. 欠失  ある長さの遺伝子を消去する(遺伝子長が変化)

  5. 各個体の評価  各個体の適応度を計算します.

  6. 淘汰  ここまでの過程により,一般的に,個体数は N + 2 * M となっているはずです.ここで,環境に適合しない個体を淘汰することによって,個体数を N に戻し,世代数 = 世代数 + 1 とし,1 に戻ります.淘汰方法としては,以下のようなものがあります.

    1. エリート選択  単純に,適応度が高い N 個の個体を残す方法です.この方法は簡単ですが,局所的最適解に陥りやすく,一般には,次に述べるルーレット選択と併用して使用します.つまり,ある数(< N)だけエリート選択で選択した後,残りをルーレット選択で選びます.

    2. ルーレット選択  適応度に基づいたルーレット版を作成し,そのルーレット版を使用してランダムに選択する方法です.例えば,現在の個体数が 5 で,かつ,各個体の適応度が,
      A  40
      B  20
      C  20
      D  10
      E  10
      であったとします.適応度をそのまま利用してルーレット版を作成すれば,右図のようになります.集団サイズ N が 3 であれば,このルーレット版を 3 度回して,3 つの個体を選ぶことになります.確かに,個体 A が最も選ばれやすくなりますが,個体 D や E が選ばれる確率も 0 ではありません.

        ルーレット版を作成する際,適応度をそのまま利用する方法以外,適応度に順位をつけて,適当な減少率で線形化する方法,非線形変換を行う方法等,様々な方法が提案されています.
4.3 スキーマ定理

  この節では,スキーマ定理について説明します.スキーマとは,染色体と同じような文字列ですが,その中に 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) / fm
P(S, t): 時刻 t において,スキーマ S を遺伝子型に含む個体の数
f(S): スキーマ S を遺伝子型に含む個体の平均適応度
fm: 集団内の全個体の平均適応度

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

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

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

Pm * O(S)
Pm: 突然変異率

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

P(S, t+1) = P(S, t) * f(S) / fm * [1 - Pc * δ(S) / (L - 1) - Pm * O(S)]

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

4.4 GAの適用例

  この節では,GA をいくつかの問題に適用した例を示します.必ずしも,GA を使用すべきであるような問題ではありませんが,単なる例として眺めてください.なお,4.4.2 節及び 4.4.3 節の例は,「C/C++ 及び Java による GA のプログラム例」を使用して解いています.

4.4.1 「1」の数

  まず,簡単な問題によって,GA を体験してください.問題は,以下のような問題です.下に示されるアプレットの指示に従って,GA を実行してみてください.なお,選択する場合,適応度が大きいものを意図的に選択するようなことはしないでください(そのようにしなくても,全体的に,適応度が大きくなっていくはずです). → このアプレットのソースコード

4.4.2 関数の最大値

  この節では,x が [0, 1] のとき,次の関数の最大値を GA を使用して求めてみます.

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 進数とみなした値) / (2n - 1)

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

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

  この結果,以下のような結果が得られます.各行の 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
		
  より複雑な問題に対しては,「GA により 2 変数関数の最小値を求める」を参考にしてください.

4.4.3 巡回セールスマン問題

  50 都市に対する巡回セールスマン問題を,以下のような設定で,GA で解いてみます.各個体は,都市番号の並びであり,その順番が都市を訪れる順序になります.

  結果は,例えば,以下のようになります.

静岡理工科大学 情報学部 菅沼ホーム 目次 索引