Multiprogramming genetic algorithm for optimization problems with permutation property

Permutation property has been recognized as a common but challenging feature in combinatorial problems. Because of their complexity, recent research has turned to genetic algorithms to address such problems. Although genetic algorithms have been proven to facilitate the entire space search, but they lack in fine-tuning capability for obtaining the global optimum. Therefore, in this study a multiprogramming genetic algorithm (MGA) was developed for permutation optimization. Both the global exploration (through crossover operation and mutation operation) among the population and the local exploitation (through selection operation) around chromosomes are integrated to MGA. In order to improve the performance of MGA, the authors establish some regulations (replacement regulation, local optimization regulation and global optimization regulation) to help the evolvement of MGA. Computational experiments are conducted on most of ATSP instances available in the TSPLIB, and on a set of larger asymmetric instances with known optimal solutions. The comparisons show that the results obtained by our method compare favorably with those obtained by several other algorithms recently proposed for the ATSP.