The Efficiency of a Genetic Algorithm with a SHC Mutation

スポンサーリンク

概要

• 論文の詳細を見る

• Recently, Genetic Algorithms (GAs) have been investigated as a technique for solving combinatorial optimization problems and have been shown to be effective at searching solutions among a large and complex space in an adaptable way, guided by the equivalent biological evolutionary mechanisms of reproduction, crossover and mutation. In this paper, we propose an efficient Genetic Algorithm (GA) for solving the traveling salesman problem (TSP) as a combinatorial optimization problem. In our computational model, we propose a complete subtour exchange crossover that breaks as few good subtours as possible, because good subtours are worth preserving for descendants. Generally speaking, global search GAs are considered to be better approaches than local searches. However, it is necessary to strengthen local searches as well as global ones in order to increase a GAs total efficiency. In this study, we propose a new GA which applies a stochastic hill climbing (SHC) procedure in the mutation process of the GA. Experimental results have shown an efficiency convergence as high as 99 percent even for 500 cities TSP.

• 岡山理科大学の論文

著者

• 成久 洋之

  Faculty of Engineering, Okayama University of Science

• 坂本 浩之

  Graduate School Of Engineering Okayama University Of Science

• 片山 謙吾

  Graduate School of Engineering, Okayama University of Science

関連論文

• バイナリー2次計画問題における遺伝的局所探索法での突然変異の効果
• ナップザック問題に対する効率的 GA の適用
• TSP の GA 解法における配置パターンの影響について
• The Efficiency of a Genetic Algorithm with a SHC Mutation

スポンサーリンク