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

CORC > 厦门大学 > 信息技术－已发表论文

	A Puzzle-Based Genetic Algorithm with Block Mining and Recombination Heuristic for the Traveling Salesman Problem
	Chang, Pei-Chann ; Huang, Wei-Hsiu ; Zhang, Zhen-Zhen ; Zhang ZZ(张真真)
刊名	http://dx.doi.org/10.1007/s11390-012-1275-3
	2012-09
关键词	ORGANIZING NEURAL-NETWORK COMBINATORIAL OPTIMIZATION ARTIFICIAL CHROMOSOMES SCHEDULING PROBLEMS EVOLUTION SELECTION ISSUES MODEL TSP
英文摘要	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.
语种	英语
出版者	J COMPUT SCI TECH-CH
内容类型	期刊论文
源URL	[http://dspace.xmu.edu.cn/handle/2288/92379]
专题	信息技术－已发表论文
推荐引用方式 GB/T 7714	Chang, Pei-Chann,Huang, Wei-Hsiu,Zhang, Zhen-Zhen,et al. A Puzzle-Based Genetic Algorithm with Block Mining and Recombination Heuristic for the Traveling Salesman Problem[J]. http://dx.doi.org/10.1007/s11390-012-1275-3,2012.
APA	Chang, Pei-Chann,Huang, Wei-Hsiu,Zhang, Zhen-Zhen,&张真真.(2012).A Puzzle-Based Genetic Algorithm with Block Mining and Recombination Heuristic for the Traveling Salesman Problem.http://dx.doi.org/10.1007/s11390-012-1275-3.
MLA	Chang, Pei-Chann,et al."A Puzzle-Based Genetic Algorithm with Block Mining and Recombination Heuristic for the Traveling Salesman Problem".http://dx.doi.org/10.1007/s11390-012-1275-3 (2012).