遺伝子交叉オペレータ交代法による巡回セールスマン問題の解法

スポンサーリンク

概要

• 論文の詳細を見る

• In order to solve the Traveling Salesman Problem (TSP) through Genetic Algorithms (GAs), a method of changing crossover operators (CXO), which can flexibly substitute the current crossover operator for another suitable crossover operator at any time, is proposed. We examined seven crossover operators. Our experiments using data of the famous Eilon's 75-city problem show that CXO which uses an improved EX in early generation and uses SXX after several generations can efficiently provide with a best approximate solution of TSP, where improved EX, whose idea comes from greedy algorithm, selects the nearest town from the current visiting city selected out of adjacent cities in parents to create local optimum sub-paths and our SXX efficiently generates cyclic paths in the next generation by performing a crossover operation on a pair of the selected parents that have the local optimum sub-paths. In our case study, a CXO can find an approximate solution of the optimum cyclic paths on the 77-th generation after exchanging improved EX for SXX on the 40-th generation, and it takes about 21.9 seconds to select the best solution with the length (≒544.81). Our experiments have shown that CXO can improve path's length as well as computer execution time which the improved EX and SXX have. This experimental result suggests that changing crossover operators at arbitrary time according to city data is available to improve both the functionality and the performance of GAs.

• 八戸工業大学の論文
• 2006-02-28

著者

• 高橋 良英

  八戸工業大学大学院工学研究科電子電気・情報工学専攻・教授

• 高橋 良英

  八戸工業大学

• 出貝 賢一

  大学院工学研究科電気電子工学専攻博士前期課程・2年

• 高橋 良英

  八戸工業大学システム情報工学科・教授

関連論文

• 拡張遺伝子交叉オペレータ交代法の有効性の検証
• 巡回セールスマン問題を解く拡張遺伝子交叉オペレータ交代法
• 拡張遺伝子交叉オペレータ交代法による巡回セールスマン問題の解法
• 巡回セールスマン問題を解く枝組み立て交叉(Edge Assembl Crossover)の拡張遺伝子交叉オペレータ交代法による性能改善
• 遺伝的アルゴリズムと蟻協調行動モデルによる巡回セールスマン問題の解法
• 遺伝子交叉オペレータ交代法による巡回セールスマン問題の解法
• 巡回セールスマン問題を遺伝的アルゴリズムにより解く場合の致死遺伝子対策へのCプログラミングによる漸進的機能改善施策
• 最適概念形成への遺伝的アルゴリズムの適用可能性の検討
• 6V-8 ACO突然変異方式による枝組立交叉(EAX)の性能改善 : 巡回セールスマン問題(TSP)の解法(遺伝的アルゴリズム(2),学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
• 6V-7 フェロモン量の動的増減制御によるACOの性能改善(遺伝的アルゴリズム(2),学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
• ハイブリット手法による巡回セールスマン問題の解法
• 再帰的拡張遺伝子交叉オペレータ交代法による巡回セールスマン問題の解法

もっと見る 閉じる

スポンサーリンク