巡回セールスマン問題を遺伝的アルゴリズムにより解く場合の致死遺伝子対策へのCプログラミングによる漸進的機能改善施策

概要

論文の詳細を見る
One of the problems when solving the traveling salesman problem through genetic algorithms(GA)is to get an approximation of the optimum and stable solution that is obtained with the least number of crossover operations without yielding lethal genes. Our experiments show that on early stage of generations an improved EX-operator that selects the nearest town from the current visiting town successively is available for selecting the last path with the minimum required distance,and that after generations the SXX-operator that generates individuals in the next generation by performing a crossover operation on a pair of the selected parents that have the local optimum sub-paths is available. In this paper,a changing crossover-operations method(CXO)which can flexibly substitute the current crossover operator for another suitable crossover operator at any time according to fitness values of individual strings that comprise the population is proposed. With this method we can obtain the optimum solution more efficiently rather than with another single operator. Validity of the CXO-method,which changes crossover operators from the improved-EX to the SXX in our experiment,is experimentally verified through C-programming by using data of 15 cities.
八戸工業大学の論文
2005-02-28