TSPを遺伝的アルゴリズム(GA)で解く際，訪問する都市の順番を何らかの方法で表さなくてはなりませんが，その際の解の表現について調べたので，まとめておきます．
パス表現 (Path Representation)
最も直感的なやり方です．
都市0, 3, 2, 1, 4の順番で巡回する場合，[0, 3, 2, 1, 4]というリストで表します．わかりやすいですが，適当に交叉を行うと，同じ都市を二度訪問する致死遺伝子が生じるという欠点があります．致死遺伝子を回避しながら交叉を行う方法が以下のページで紹介されています．（以下のページでは順序表現という名前で紹介されています．）
隣接表現 (Adjacent Representation)
都市$i$から都市$j$に移動するとき，リストの$i$番目に都市$j$を配置する方法です．
この時，都市0から都市3に移動するなら，リストの0番目に3と記録されることになります．
0, 3, 2, 1, 4の順番で巡回する場合，[3, 4, 1, 2, 0]となります．
やはり適当な交雑によって致死遺伝子が発生するという問題があります．
順序表現 (Ordinal Representation)
順序表現では，未訪問の都市リストを持ち，次に訪問する都市が未訪問の都市リストの何番目かで表現します．
最初に未訪問リスト[0, 1, 2, 3, 4]があったとして，0, 3, 2, 1, 4の順番で巡回する場合，[0, 2, 1, 0, 0]という表現になります．
適当に交叉をおこなっても致死遺伝子が発生しないというメリットがありますが，交叉点より後半の遺伝子の意味は前半の遺伝子の並びに依存するため，交叉点が染色体の前であるほど，子の巡回路は親とは似ても似つかぬものとなってしまう欠点を持ちます．
このため，順序表現を用いるGAでは，突然変異のみからなるランダムサーチ程度の性能しか示さず，特に，コストとしてユークリッド距離を用いる TSPでは交差する経路を持つ解は明らかに劣りますが，順序表現ではこれを解消できないことが知られています．
参考文献