A Puzzle-Based Artificial Chromosome Genetic Algorithm for the Traveling Salesman Problem

The standard Genetic Algorithm has suffered from the early convergence and trapped into a local optimum when dealing with combinatorial optimization problems. 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 blocks mining phase, the ACO technique has been adopted to establish a set of non-overlap block archive and the remaining cities (nodes) to be visited in set S. 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 (AC) then will be injected into the SGA process to speed up the convergence. The proposed method is called "Puzzle-based Artificial Chromosome 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 GA and lead the algorithm to explore and exploit the searching space via taking advantage of Artificial Chromosomes which are produced by recombination of the mined blocks.