ここではセールスマン巡回問題(TSP)に代表される順序問題に対するGAの適用方法について述べる． 例えば100都市のTSPの場合に問題になるのは最小の巡回距離になる100都市の巡回順序で あるので，この問題の常識的な表現方法は1から100までの整数の順列ということになる．従って，遺伝子の表現方法は１から１００までの長さ100の整数列ということになる． もちろん，これとは異なった方法も考えられる．いずれにしても，これらの表現方法では交叉や突然変異などの遺伝子操作はバイナリビットストリングの場合とは異なってくる．実際問題を考えてみると，このような順列表現に適した問題が意外に多いことがわかる．これら遺伝子操作法は遺伝子の表現方法によっても変わってくるので，表現方法との 関連を考えながら，現在用いられている各種の方法につい述べる． 特に大きく影響を受けるのは交叉方法であるので，これを中心に述べ，併せて突然変異の方法にも触れる．
交叉においては子が親のそれぞれの形質，この場合では巡回経路，をどの程度受け継ぐことができるかが重要となる．TSPでは巡回経路の順番が問題であり，どこから開始するかは関係がない．しかし，問題によっては順番のみならず，その位置が重要となる場合が あるので，各方式の評価においてTSPとその他では異なってくることもあり得る． なお，説明は主として文献[1]および[2]を参考にして行う． またTSP を対象に説明しているが，以下に述べることは他の順序・組合せ問題に も多くの場合にそのまま適用できる． 順序問題に対する遺伝子の表現方法としてはパス表現，隣接表現，順序表現の3種と 別に行列による表現があるが，ここでは前3者を対象とする． これら方式により交叉の方式が変わってくるので，各表現別に交叉方法及び突然変異の 方法について説明する．
以下に示す表は遺伝子表現法とそれに用いられる交叉方法とを一覧表にまとめた ものである．
また突然変異についてはパス表現用突然変異について 説明しているが，他の表現についても同様の考えを適用できる．
1. パス表現(Path Representation )
パス表現は巡回する都市の番号を巡回する順序に並べた表現方法であり，最も自然な表現法といえる．この表現法では，経路:
5 - 1 - 7 -8 - 9 - 4 - 6 - 2 - 3
を次のようなリストで表す．
( 5 1 7 8 9 4 6 2 3 )
パス表現法には以下に述べる３種の交叉法が考えられている．1.1 部分写像交叉(PMX: Partially-mapped crossover)
部分写像交叉はGoldberg らにより提案された方法である．親の一方からはその部分経路をそのまま受け継ぎ，他の親からも残りの都市について，できるだけ多く親の順番を受け継ぐことを 目的にしている． そのために，２つのランダムに選んだ切断点間の部分経路を選び，以下に示す交叉を 行う．To top of page
例えばつぎに示す２つの親の経路の交叉を考える．
p1=(1 2 3 | 4 5 6 7 | 8 9)
p2=(4 5 2 | 1 8 7 6 | 9 3)
まず縦棒 | にて示した２点で挟まれた部分を交叉するとつぎに示す子が得られる． ここで * は今のところ未決定であることを示す．
c1=(* * * | 1 8 7 6 | * *)
c2=(* * * | 4 5 6 7 | * *)
このことは次の入れ替えを定義していることにもなる． 1 <-> 4, 8 <-> 5, 7 <-> 6, 6 <-> 7
残りの未決定の部分について，既定のものと衝突を起こさないもの （即ち，既定のものに含まれないもの）はそのまま入れると，つぎの経路が得られる．
c1=(* 2 3 | 1 8 7 6 | * 9)
c2=(* * 2 | 4 5 6 7 | 9 3)
最後に残った部分には前記の入れ替えの定義を参照して衝突を起こさないように入れる．即ち，c1 については１番目の * には1の代わりに4を入れ， ８番目の * には8 の代わりに 5 を入れる．同様の操作を c2 についても 行うと次の経路が得られる．
o1=(4 2 3 | 1 8 7 6 | 5 9)
o2=(1 8 2 | 4 5 6 7 | 9 3)
この方法は類似性と順序を保存している点に特徴がある．1.2 順序交叉(OX:Order crossover)
順序交叉は Davis により提案されたものである． 片方の親からは一部をそのままに受け継ぎ，残りの部分については相対的な順番は保存しつつ受け継ぐ方法である． 例として次の２つの親からの交叉を考える．To top of page
p1=(1 2 3 | 4 5 6 7 | 8 9)
p2=(4 5 2 | 1 8 7 6 | 9 3)
先ず２切断点間はそのままコピーする．
c1=(* * * | 4 5 6 7 | * *)
c2=(* * * | 1 8 7 6 | * *)
次に第２切断点から開始して右回りに順序を保ちながら他の親をコピーする． その際に既定のものと衝突するものがあれば除く．
例えば，子 c1について見てみると，第２の親 p2 の順序は
9 - 3 - 4 - 5 - 2 - 1 - 8 - 7 - 6
となるが子 c1 と衝突するもの（4, 5, 6, 7）を除くと
9 - 3 - 2 - 1 - 8
となるので，これを c1 に挿入するとつぎのとおりになる．
c1=(2 1 8 | 4 5 6 7 | 9 3)
同様にして， c2 がつぎのように得られる．
c2=(3 4 5 | 1 8 7 6 | 9 2)
この方法はパス表現法の特質である都市の順番の重要性，即ち
9 - 3 - 4 - 5 - 2 - 1 - 8 - 7 - 6
4 - 5 - 2 - 1 - 8 - 7 - 6 - 9 - 3
は同じ巡回経路であることを利用している．1.3 順序交叉(OX)の修正方式
Syswerda は順序交叉(OX)につぎの２つの修正案を提案している．To top of page
- 修正案１：順序に基づく交叉(Order-based crossover)
つぎの例をもとに説明する．
p1=(1 2 3 4 5 6 7 8 9)
p2=(4 1 2 8 7 6 9 3 5)
- まず親 p2 より任意の位置にある都市を選ぶ． 例えば3,4,6,9 番目にある 2,8,6,5 を選ぶ．つぎに p1 のこれらの数値に 相当する位置（即ち2,8,6,5番目）以外にある要素をそのまま子c1 に受け継ぐ． 従って
c1=(1 * 3 4 * * 7 * 9)
- 残りの場所には p2 の 2,8,6,5 をこの順序に入れる．従って最終的に
c1=(1 2 3 4 8 6 7 5 9)
となる．同様に c2 については次のようになる．
c2=(3 1 2 8 7 4 6 9 5)
- 修正案２：位置に基づく交叉(Position-based crossover)
原案と殆ど同じであり，違いは複写する都市を順番ではなくランダムに選ぶことである．1.4 循環交叉(CX: Cyclic crossover)
循環交叉はOliver により提案された方式である． 次の親の場合を例に説明する．To top of page
p1=(1 2 3 4 5 6 7 8 9)
p2=(4 1 2 8 7 6 9 3 5)
まず，順番に残すものを決める．第1の子 c1 について，親 p1 の最初の 都市の1より開始し，つぎは親 p2 の1番目の都市は4 であるので 親 p1 の 4 を取り出す．つぎは p1 の 4 の位置に相当する p2 の都市は 8 で あるので，p1 の 8 を取り出す．この結果つぎの子ができる．
c1=(1 * * 4 * * * 8 *)
この様にして c1 を作って行くと次のリストが得られる．
c1=(1 2 3 4 * * * 8 *)
このリストで最後に入れられたのは 2 であるが，この位置の p2 の要素は 1 であり最初に戻り，これ以上は進めない．従って残りの都市は反対側の親 p2 の ものをそのまま入れると，つぎのリストが得られる．
c1=(1 2 3 4 7 6 9 8 5)
他の親も同様の方法を用いると，つぎのリストが得られる．
c2=(4 1 2 8 5 6 7 3 9)
この方法では各要素は親の位置をそのまま受け継いでいる．1.5 サブツア交換交叉(Subtour exchanging crossover)
アブツア交換交叉は山村 ら[2}により提案された交叉法である． ２つの親の間で交換されるサブツアに含まれる都市集合が一致するときのみ交叉 する．例えば次の親の場合で２点交叉を考える．To top of page
p1=(1 2 | 3 4 5 | 6 7 8 9)
p2=(2 7 6 9 | 4 3 5 | 1 8)
両親の | で囲まれた範囲をみると都市集合がいずれも同じである，交叉を行うと つぎの子が得られる．
c1=(1 2 4 3 5 6 7 8 9)
c2=(2 7 6 9 3 4 5 1 8)
これに右回り，左回りを考えてさらに２つの子が作られる．1.6 辺再組合せ交叉（ER : Edge recombination crossover）
辺再組合せ交叉はWhitleyにより提案された方式であり，基本的には親の保有する辺を子に受け継ぐことにある．この方式では親の95% の辺を子に移している． この操作では辺に関する情報を扱う．例えば経路To top of page
(3 1 2 8 7 4 6 9 5)
では辺は
(3 1),(1 2),(2 8),(8 7),(7 4),(4 6),(6 9),(9 5),( 5 3)
となり，各辺は距離の情報を持つことになる．TSPでは正しい経路を構成する辺の 距離の合計を最小にすることが目的である．従って都市間の距離が問題であり， 都市の位置や辺の方向などは重要ではない． 辺 (3 1) と (1 3) とはただ都市1と都市3 が直接接続していることを示しているに 過ぎない．
辺再組合せ交叉の基本的な考えは”子は親の両方に存在する辺から構成すべきである” であり，このために両方の親の経路から作られた辺リストを利用する． 各都市は少なくとも２つ，最大４つの都市と接続している． いま親の辺リストがつぎのとおりであったとする．
p1=(1 2 3 4 5 6 7 8 9)
p2=(4 1 2 8 7 6 9 3 5)
従って辺リストはつぎのとおりになる．
都市1:辺で接続している都市: 9 2 4
都市2:辺で接続している都市: 1 3 8
都市3:辺で接続している都市: 2 4 9 5
都市4:辺で接続している都市: 3 5 1
都市5:辺で接続している都市: 4 6 3
都市6:辺で接続している都市: 5 7 9
都市7:辺で接続している都市: 6 8
都市8:辺で接続している都市: 7 9 2
都市9:辺で接続している都市: 8 1 6 3
この親の辺リストから子の構成を次のように行う．
このようにして次の子の辺リストが得られる．
- 子の最初の都市を親のひとつより選ぶ．いま都市1を選んだとする．
- 辺リストより都市1に接続する都市は 9,2,4 であるので，この中から最小 の辺の数を持つ都市を選ぶ．都市2,4 が３つの都市，9 が４つの都市と接続しているの で2,4 よりランダムに選んで都市4とする．
- 今度は都市4について同じ操作を繰り返す．以下同じ．
(1 4 5 6 7 8 2 3 9)
実験によると辺の失敗は非常に少なかったといわれている（1-1.5%）．
その後，辺再組合せはさらに改善された．その考えは共通部分経路である．辺リストの 中に繰り返し現れる辺がある．例えば，前の例で述べると辺 (4 5) がこれに相当する． 都市4に接続する都市は都市3,5,1 であり，辺リストで見ると辺 (4 5) は２回 現れている．これを表すために辺リストで都市4に接続する都市のうち都市5には 記号" - "を付ける．即ち都市4では
都市4:辺で接続している都市: 3 -5 1
となる．同様の操作を全ての辺リストに対して行う．
そして辺リストからつぎの都市を選ぶ際に，こうした記号を与えた都市には優先権を 与えるようにした．これにより性能が改善したといわれている．
辺再組合せ交叉法をみると，パス表現法が経路の重要な性質の表現力に乏しいのを 辺リストで補っていることが分かる．1.7 辺に着目したヒュリスティック操作
これまで論じて来た方式では都市（その位置と順序）を考えてきたが重要なのは 経路の中の都市の位置ではなくむしろ都市間の接続関係である． 従って巡回問題のビルディングブロックとして都市の位置表現ではなく辺（Edge） 表現を用いることが考えられる． Grefenstette は辺に着目したヒューリスティック操作を開発した． この操作はつぎのように動作する．To top of page報告によるとこのような操作は親の辺の60%を伝えている．即ち残り40% は任意に 選ばれていることになる．
- 子の都市として任意の都市１つを選ぶ．
- この都市に接続する辺を４つ（各親より２つずつ）選ぶ．
- 上記各辺のコストに基づき確率分布を定義する．以前訪問した都市に関連した 辺には零を割り振る．
- １つの辺を選択する．少なくとも１つの辺が非零確率なら上記分布に基づき， そうでない場合は未訪問都市よりランダムに選ぶ．
- 選定した辺の他端の都市がつぎの都市になる．
- 経路が完成なら停止．そうでない場合はステップ２に戻る．
1.7 突然変異
突然変異の方式は順序問題では一般の方式と異なった方式が必要となる．すなわち 順序を突然変異で変更することになる．その方式としては以下のものが用いられている． いずれの方式がよいかは一概に言えないので，シミュレーションの結果などを 参考に決めることになる．To top of page
- 交換 ランダムに選んだ２つの都市を互いに入れ換える方式である．
- 挿入 ランダムに選んだ１つの都市を取り出してその位置を詰め， 同じくランダムに選んだ１つの都市の所に挿入し，それ以降をずらす方式である．
2. 隣接表現(Adjacent Representation)
隣接表現は巡回経路をリストで表し，i都市からj都市へ進む場合にリストのi番目に jとして表す方法である．例えばTo top of page
(2 4 8 3 9 7 1 5 6)
は次の巡回路を表している．
1-2-4-3-8-5-9-6-7
この方法の場合，正しくない経路を表す場合がある．例えば
(2 4 8 1 9 3 5 7 6)
は次の様にループを作ってしまう．
1-2-4-1
また通常の交叉演算子がそのままの形では使用できないので，次の３種の 修正アルゴリズムが考えられている．隣接表示の特徴はセマータ解析が可能なことである．例えばスキーマ (* * * 3 * 7 * * *)
- 交互辺交叉(Alternating-edge crossover)：
先ず第１の親からランダムに １つの辺を選び，つぎに第２の親からこれに続く辺を選び，再び第１の親から これに続く辺を選ぶ，というように両方の親から交互に辺を選んで交叉を行う． もし途中でループを作る場合は残りの辺から（ランダムに）１つを選んだ後， 再び上記の方法を続ける．例えば
p1= (2 3 8 7 9 1 4 5 6)
p2= (7 5 1 6 9 2 8 4 3)
に対して，つぎの様に選ぶ．
c1= (2 5 8 7 9 1 6 4 3)
この場合，辺 (7 8) がループを作ったので，代わりに (7 6) を選んだのが 唯一のランダム選択である．- 部分経路交叉(Subtour-chunks crossover)：
最初に第１の親からランダムな 長さの部分経路を選び，つぎに第２の親からこれに続くランダムな長さの部分経路を 選ぶという方法で交叉を行う．もしある辺がループを作る場合には 残り部分より新しくランダムに辺を選ぶ．- ヒューリスティック交叉(Heuristic crossover)：
先ず開始都市を任意に選ぶ． つぎに両方の親のこの同じ都市を出発する辺のうち短い方を選ぶ． この辺の到達都市をつぎの出発都市として上記を繰り返す． もし途中でループを生じる場合は残りの都市よりランダムに選ぶ．
このヒューリスティック交叉の効果は親の経路の短い部分経路をつなぎ合わせる ことにある．しかし望ましくない辺の交わりを作ることもあるのでローカル経路の 最終調整の段階で使用することは望ましくない．
は辺 (4 3) 及び (6 7) を持つ全ての経路を表している．しかし， この方法の欠点は全ての操作に対して比較的貧しい結果となっていることである． 交互辺交叉ではよい経路を壊すことがしばしば起こる．部分辺交叉では交互辺交叉 に比べて壊す割合は低いが性能はまだよくない．ヒューリスティック交叉が最もよい 性能を示しているといわれている．3. 順序表現(Ordinal Repesentation)
順序表現は n 都市のリストという形で表す，即ちリストの i 番目の要素は i から n-i+1 の範囲の数字のひとつである．この表し方を具体的な例で示す． 先ず基準となる順序リストを定める．これがつぎの通りであるとする．参考文献
c=(1 2 3 4 5 6 7 8 9 )
これを用いて，巡回経路
1 - 2 - 4 - 3 - 8 - 5 - 9 - 6 - 7
をつぎのリスト q で表す．
q = ( 1 1 2 1 4 1 3 1 1)
このリストの表す巡回経路は以下のようにして求めることができる．この方法の特長は通常の交叉が使えることである． 例えば二つの親がつぎのとおりであったとする：
- リスト q の最初の数値は 1 であるので，巡回経路の最初の都市として リスト c より1番目の1（即ち都市1）を採用する．同時にリストcより 1 を除く．
- リスト q の次の数値もまた 1 であるので，リスト c の１番目の 2（即ち都市2）を採用して巡回経路は 1 - 2 となる．同時に2をリスト c より除く．
- リスト q の次の数値は 2 であるので，リストc の2番目の4 を 採用して巡回経路 1 - 2 - 4 となる．同時に 4 をリストc より除く．
- リスト q の次の数値は 1 であるので，リストc の1番目の要素 3 を 採用して巡回経路は 1 - 2 - 4 - 3 となる． この 3 をリスト c より除く．
- 以下これを繰り返す．
p1=(1 1 2 1 | 4 1 3 1 1)
p2=(5 1 5 5 | 5 3 3 2 1)
これはそれぞれ次の経路を表している．
1 - 2 - 4 - 3 - 8 - 5 - 9 - 6 - 7
5 - 1 - 7 - 8 - 9 - 4 - 6 - 3 - 2
縦棒 | で示した点で交叉すると次のリストが得られる．
c1=(1 1 2 1 | 5 3 3 2 1)
c2=(5 1 5 5 | 4 1 3 1 1)
これはつぎの経路を表している．
1 - 2 - 4 - 3 - 9 - 7 - 8 - 6 - 5
5 - 1 - 7 - 8 - 6 - 2 - 9 - 3 - 4
これをみると交叉点の左側の経路は親のものが保存されているが， 右側の経路では壊されており，親の一部しか継承されない． この方式も結果はよくないといわれている．
[1] Michalewicz, Z. : Genetic Algorithms + Data Structures = Evolution Programs, Second, Extended Edition, Springer-Verlag, 340p, 1994.
[2] 山村, 小野, 小林 : 形質の遺伝を重視した遺伝的アルゴリズムに 基づく巡回セールスマン問題の解法,人工知能学会誌,Vol.7,No.6,1049/1059,1992.
To top of page
小野 俊彦 (Toshihiko Ono)