A Genetic Algorithm for the Treveling Salesman Problem

"巡回セールスマン問題とは,いわゆるNP完全問題の一つで,与えられたすべての都市をそれぞれ一度ずつ訪れる経路の中で最短の経路を求めるという問題である。都市の数が増えると,道順の組合せが爆発的に増えるので,手に負えない問題とされている。一方,遺伝的アルゴリズムは,生物の進化にヒントを得たアルゴリズムで,確率的探索・最適化の一手法として最近注目をあつめている。本文では,巡回セールスマン問題について,遺伝的アルゴリズムを用いた効率的解決法を提案する。また,行なった比較検証実験の結果から,その有効性を示す。