2Q-8
Voronoi手法による巡回セールスマン問題(TSP)の解法の性能改善
○木村 翼,髙橋良英(八戸工大)
巡回セールスマン問題(TSP: Traveling Salesman Problem)の解法としてVoronoi手法が着目を浴びている。Voronoi手法とは,巡回路を構成する都市のボロノイ分割を遺伝的アルゴリズム(GA: Genetic Algorithm)の遺伝子交叉に応用した手法である。そこでは,両親の有効な枝情報をボロノイ分割した単位で子供に引き継ぐ。そしてボロノイ分割した領域境界の都市をその間の距離が最短になるようにつなぎあわせ,更に経路長の短い子供を生成する。
SeoとMoonが提案したVoronoi分割を応用したGAは,突然変異手段としてダブルブリッジ,ローカルサーチとしてLin-Kernighan法を使用したハイブリッド手法である。本検討では初期ツアー生成や突然変異手段とし蟻の餌採取活動を模したアントコロニー最適化法ACO,ローカルサーチとして親Aと親Bの同数の枝を交換し新たな巡回路を生成する枝組み立て交叉(EAX: Edge Assembly Crossover)を使用した,Voronoi based遺伝的アルゴリズムの有効性を検証する。