Chapter.2 巡回セールスマン問題に対するGAの応用 - 田中雅博監修・日高正博製作補助 知能情報Web教材巡回セールスマン問題(TSP)とは？ 巡回セールスマン問題 (the Traveling Salesman Problem) は，N個の都市すべてを1度ずつ訪問した後に最初の都市に戻る巡回路のうち、 最小の距離のものを求める問題である。 この巡回セールスマン問題に対してGAの応用を考えよう。 Partially Matched Crossover [PMX] 通常の交叉では、都市の重複が考えられるため、工夫する必要がある。ここでは連続した組の遺伝子対に着目し、交叉するPMXの手順を簡単に説明する。 一対の親染色体が以下のように与えられているとき、ある連続した部分列の組（この例では(3,7),(6,2),(1,5)の３組）に注目する。
