A Puzzle-Based Genetic Algorithm with Block Mining and Recombination Heuristic for the Traveling Salesman Problem  

作　　者：张百栈 黄伟修 张真真 

机构地区：[1]Department of Information Management,Yuan Ze University,Taoyuan 32026,Taiwan,China [2]Department of Computer Science,Xiamen University,Xiamen 361005,China

出　　处：《Journal of Computer Science & Technology》2012年第5期937-949,共13页计算机科学技术学报（英文版）

摘　　要：In this research, we introduce a new heuristic approach using the concept of ant colony optimization （ACO） to extract patterns from the chromosomes generated by previous generations for solving the generalized traveling salesman problem. The proposed heuristic is composed of two phases. In the first phase the ACO technique is adopted to establish an archive consisting of a set of non-overlapping blocks and of a set of remaining cities （nodes） to be visited. The second phase is a block recombination phase where the set of blocks and the rest of cities are combined to form an artificial chromosome. The generated artificial chromosomes （ACs） will then be injected into a standard genetic algorithm （SGA） to speed up the convergence. The proposed method is called ＂Puzzle-Based Genetic Algorithm＂ or ＂p-ACGA＂. We demonstrate that p-ACGA performs very well on all TSPLIB problems, which have been solved to optimality by other researchers. The proposed approach can prevent the early convergence of the genetic algorithm （GA） and lead the algorithm to explore and exploit the search space by taking advantage of the artificial chromosomes.In this research, we introduce a new heuristic approach using the concept of ant colony optimization （ACO） to extract patterns from the chromosomes generated by previous generations for solving the generalized traveling salesman problem. The proposed heuristic is composed of two phases. In the first phase the ACO technique is adopted to establish an archive consisting of a set of non-overlapping blocks and of a set of remaining cities （nodes） to be visited. The second phase is a block recombination phase where the set of blocks and the rest of cities are combined to form an artificial chromosome. The generated artificial chromosomes （ACs） will then be injected into a standard genetic algorithm （SGA） to speed up the convergence. The proposed method is called ＂Puzzle-Based Genetic Algorithm＂ or ＂p-ACGA＂. We demonstrate that p-ACGA performs very well on all TSPLIB problems, which have been solved to optimality by other researchers. The proposed approach can prevent the early convergence of the genetic algorithm （GA） and lead the algorithm to explore and exploit the search space by taking advantage of the artificial chromosomes.

关 键 词：artificial chromosome blocks mining block recombination traveling salesman problem 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] O224[自动化与计算机技术—控制科学与工程]