›› 2012, Vol. 27 ›› Issue (5): 937-949.doi: 10.1007/s11390-012-1275-3

Special Issue: Data Management and Data Mining

• Special Issue on Evolutionary Computation • Previous Articles     Next Articles

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

Pei-Chann Chang1 (张百栈), Wei-Hsiu Huang1 (黄伟修), and Zhen-Zhen Zhang2 (张真真)   

  1. 1. Department of Information Management, Yuan Ze University, Taoyuan 32026, Taiwan, China;
    2. Department of Computer Science, Xiamen University, Xiamen 361005, China
  • Received:2011-08-24 Revised:2012-01-05 Online:2012-09-05 Published:2012-09-05

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.

[1] Papadimitriou C H, Steglitz K. Combinatorial Optimization:Algorithms and Complexity. India: Dover Publications, 1998.
[2] Garey M R, Graham R L, Johnson D S. Some NP-completegeometric problems. In Proc. the 8th Annual ACM Sympo-sium on Theory of Computing, May 1976, pp.10-22.
[3] Ozcan E, Erenturk M. A brief review of memetic algorithmsfor solving Euclidean 2D traveling salesman problem. In Proc.the 13th Turkish Symposium on Artificial Intelligence andNeural Networks, June 2004, pp.99-108.
[4] Sankoff D, Zheng C, Mu~noz A, Yang Z, Adam Z, Warren R,Choi V, Zhu Q. Issues in the reconstruction of gene order evo-lution. Journal of Computer Science and Technology, 2010,25(1): 10-25.
[5] Black T, Fogel D B, Michalewicz Z. Handbook on Evolution-ary Computation. USA: Oxford University Press, 1997.
[6] Laporte G. The vehicle routing problem: An overview of ex-act and approximate algorithms. European Journal of Oper-ational Research, 1992, 59(3): 345-358.
[7] Onwubolu G C, Clerc M. Optimal path for automated drillingoperations by a new heuristic approach using particle swarmoptimization. International Journal of Production Research,2004, 42 (3): 473-491.
[8] Affenzeller M, Wanger S. A self-adaptive model for selectivepressure handling within the theory of genetic algorithms. InProc. the 9th EUROCAST, February 2003, pp.384-393.
[9] Budinich M. A self-organizing neural network for the trav-eling salesman problem that is competitive with simulatedannealing. Neural Computation, 1996, 8(2): 416-424.
[10] Liu G, He Y, Fang Y, Oiu Y. A novel adaptive search strat-egy of intensification and diversification in tabu search. InProc. International Conference on Neural Networks and Sig-nal Processing, December 2003, pp.428-431.
[11] Bianchi L, Knowles J, Bowler N. Local search for the proba-bilistic traveling salesman problem: Correction to the 2-p-optand 1-shift algorithms. European Journal of Operational Re-search, 2005, 162(1): 206-219.
[12] Chu S C, Roddick J F, Pan J S. Ant colony system with com-munication strategies. Information Sciences, 2004, 167 (1-4):63-76.
[13] Leung K S, Jin H D, Xu Z B. An expanding self-organizingneural network for the traveling salesman problem. Neuro-computing, 2004, 62: 267-292.
[14] Kirkpatrick S, Gelatt Jr. C D, Vecchi M P. Optimization bysimulated annealing. Science, 1983, 220(4598): 671-680.
[15] Grefenstette J, Gopal R, Rosimaita B, Gucht D V. Geneticalgorithms for the traveling salesman problem. In Proc. Int.Conf. Genetics Algorithms and Their Applications, October1985, pp.160-168.
[16] Braun H. On solving traveling salesman problems by geneticalgorithm. In Lecture Notes in Computer Science 496, Schwe-fel H P, Männer R (eds.), Springer-Verlag, pp.129-133.
[17] Michalewicz Z. Genetic Algorithms + Data Structures = Evo-lution Programs (3rd edition). Berlin, Germany: Springer-Verlag, 1996.
[18] Fan J, Li D. An overview of data mining and knowledge dis-covery. Journal of Computer Science and Technology, 1998,13(4): 348-368.
[19] Moscato P, Norman M G. A memetic approach for the trav-eling salesman problem implementation of a computationalecology for combinatorial optimization on message-passingsystems. In Proc. International Conference on Parallel Com-puting and Transputer Application, Sept. 1992, pp.177-186.
[20] Oliver I M, Smith D J, Holland J R C. A study of permutationcrossovers on the TSP. In Proc. the 2nd International Con-ference on Genetic Algorithm and Their Applications, July1987, pp.224-230.
[21] Whitely L D, Starkweather T, Fuquay D'A. Scheduling prob-lems and traveling salesman: The genetic edge recombinationoperator. In Proc. the 3rd International Conference on Ge-netic Algorithms, June 1988, pp.133-140.
[22] Mühlenbein H, Gorges-Schleuter M, Krämer O. Evolution al-gorithms in combinatorial optimization. Parallel Computing,1988, 7(1): pp.65-85.
[23] Nagata Y, Kobayashi S. Edge assembly crossover: A high-power genetic algorithm for the travelling salesman problem.In Proc. the 7th International Conference on Genetic Algo-rithms, July 1997, pp.450-457.
[24] Tao G, Michalewicz Z. Inver-over operator for the TSP. InProc. the 5th Int. Conf. Parallel Problem Solving from Na-ture, September 1998, pp.803-812.
[25] Johnson D S, McGeoch L A. The traveling salesman problem:A case study in local optimization. In Local Search in Com-binatorial Optimization, Aarts E, Lenstra J K (eds.), JohnWiley and Sons, Ltd., 1997, pp.215-310.
[26] Zou P, Zhou Z,Wan Y Y, Chen G L, Gu J. New meta-heuristicfor combinatorial optimization problems: Intersection basedscaling. Journal of Computer Science and Technology, 2004,19(6): 740-751.
[27] Merz P. A comparison of memetic recombination operatorsfor the traveling salesman problem. In Proc. the Genetic andEvolutionary Computation Conference, July 2002, pp.472-479.
[28] Baraglia R, Hidalgo J I, Perego R. A hybrid heuristic for thetraveling salesman problem. IEEE Transactions on Evolu-tionary Computation, 2001, 5(6): 613-622.
[29] Tsai H K, Yang J M, Tsai Y F, Kao C Y. Some issues ofdesigning genetic algorithms for traveling salesman problems.Soft Computing, 2004, 8(10): 689-697.
[30] Goldberg D E, Korb B, Deb K. Messy genetic algorithms:Motivation, analysis, and first results. Complex Syst., 1989,3(5): 493-530.
[31] Goldberg D E, Deb K, Kargupta H, Hank G. Rapid accurateoptimization of difficult problems using fast messy genetic al-gorithms. In Proc. the 5th Int. Conf. Genetic Algorithms,June 1993, pp.56-64.
[32] Kujazew D, Golberg D E. OMEGA-ordering messy GA: Solv-ing permutation problems with the fast messy genetic algo-rithm and random keys. In Proc. Genetic Evolutionary Com-putation Conf., July 2000, pp.181-188.
[33] Zaritsky A, Sipper M. The preservation of favored build-ing blocks in the struggle for fitness: The Puzzle Algo-rithm. IEEE Transactions on Evolutionary Computation,2004, 8(5): 443-455.
[34] Chang P C, Chen S H, Fan C Y. Mining gene structures toinject artificial chromosomes for genetic algorithm in singlemachine scheduling problems. Applied Soft Computing, 2008,8(1): 767-777.
[35] Chang P C, Chen S H, Fan C Y, Chan C L. Genetic al-gorithm with artificial chromosomes for multi-objective flowshop scheduling problems. Applied Mathematics and Compu-tation, 2008, 205(2): 550-561.
[36] Chang P C, Chen S H, Fan C Y, Mani V. Generating ar-tificial chromosomes with probability control in genetic algo-rithm for machine scheduling problems. Annals of Operations Research, 2010, 180(1): 197-211.
[37] Kantardzic M. Data Mining: Concepts, Models, Methods,and Algorithms. Totowa, USA, Wiley-IEEE Press, 2003.
[38] Sangkavichitr C, Chongstitvatana P. Fragment as a smallevidence of the building blocks existence. In Exploitationof Linkage Learning in Evolutionary Algorithms, Chen YP (ed.), Adaptation, Learning, and Optimization, Springer-Verlag Berlin Heidelberg, 2010, pp.5-44.
[39] Dorigo M, Gambardella L M. Ant colony system: A coop-erative learning approach to the traveling salesman prob-lem. IEEE Transactions on Evolutionary Computation, 1997,1(1): 53-66.
[40] Narendra P M, Fukunaga K. A branch and bound algorithmfor feature subset selection. IEEE Transactions on Comput-ers, 1977, C-26(9): 917-922.
[41] Skellam J G. Studies in statistical ecology: I. Spatial pattern.Biometrica, 1952, 39(3/4): 346-362.
[42] Pasti R, de Castro L N. A Neuro-immune network for solvingthe traveling salesman problem. In Proc. International JointConference on Neural Networks, July 2006, 6: 3760-3766.
[43] Somhom S, Modares A, Enkawa T. A self-organizing modelfor the travelling salesman problem. Journal of the Opera-tional Research Society, 1997, 48: 919-928.
[44] Smith J, Fogarty T C. Recombination strategy adaptation viaevolution of gene linkage. In Proc. the IEEE Conference onEvolutionary Computation, USA, May 1996, pp.826-831.
[45] Hahsler M, Hornik K. TSP-Infrastructure for the travelingsalesperson problem. Journal of Statistical Software, 2007,23(2): 1-21.
[46] Yao X. An empirical study of genetic operators in geneticalgorithms. Microprocessing and Microprogramming, 1993,38(1-5): 707-714.
[47] Dai H W, Yang Y, Li C, Shi J, Gao S, Tang Z. Quantum in-terference crossover-based clonal selection algorithm and itsapplication to travelling salesman problem. IEICE Trans.Inf. & Syst., 2009, E92.D(1): 78-85.
[48] Chang P C, Huang W H, Ting C J. Developing a varietal GAwith ESMA strategy for solving the pick and place problemin printed circuit board assembly line. Journal of IntelligentManufacturing, 2010, DOI: 10.1007/s10845-010-0461-9.
No related articles found!
Full text



[1] Wang Hui; Liu Dayou; Wang Yafei;. Sequential Back-Propagation[J]. , 1994, 9(3): 252 -260 .
[2] Wang Shijun; Wang Shulin;. Research and Design of a Fuzzy Neural Expert System[J]. , 1995, 10(2): 112 -123 .
[3] XIAO Limin; ZHU Mingfa;. Exploiting the Capabilities of the Interconnection Network on Dawning-1000[J]. , 1999, 14(1): 49 -55 .
[4] Imad Jawhar and Jie Wu. QoS Support in TDMA-Based Mobile Ad Hoc Networks[J]. , 2005, 20(6): 797 -810 .
[5] Cliff Reader. AVS Intellectual Property Rights (IPR) Policy[J]. , 2006, 21(3): 306 -309 .
[6] Chiou-Yng Lee, Jenn-Shyong Horng, and I-Chang Jou. Low-Complexity Bit-Parallel Multiplier over GF(2$^m$) Using Dual Basis Representation[J]. , 2006, 21(6): 887 -892 .
[7] Yong Xi, Ke-Wei Sha, Wei-Song Shi, Loren Schwiebert, and Tao Zhang. Probabilistic Adaptive Anonymous Authentication in Vehicular Networks[J]. , 2008, 23(6 ): 916 -928 .
[8] Varun Gupta and Jitender Kumar Chhabra. Package Coupling Measurement in Object-Oriented Software[J]. , 2009, 24(2): 273 -283 .
[9] Maryam Zarezadeh, Hamid Mala, Homa Khajeh. Preserving Privacy of Software-Defined Networking Policies by Secure Multi-Party Computation[J]. Journal of Computer Science and Technology, 2020, 35(4): 863 -874 .
[10] Jun-Wei Cao, (曹军威), Member, CCF, ACM, Senior Member, IEEE, Fan Zhang (张帆), Student Member, IEEE, Ke Xu (许可), Lian-Chen Liu (刘连臣) and Cheng Wu (吴澄). Formal Verification of Temporal Properties for Reduced Overhead in Grid Scientific Workflows[J]. , 2011, 26(6): 1017 -1030 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved