Bi-distinctive-population co-evolutionary genetic algorithm for traveling salesman problem

This paper introduces a new co-evolutionary strategy for genetic algorithm based on bi-distinctive populations. One of the two populations adopts permutation encoding; the other one adopts edge encoding. Each of two populations evolutes separately, and exchange critical information after evolution. Population with permutation encoding could avoid premature convergence by stochastically selecting reference optimization edge set from original edge set or edge sets established by individuals from population with edge encoding. The analyses and experimental results show that new genetic algorithm could converge to global optimal solution of arbitrary traveling salesman problems, whose scales are less than 1,500, from TSPLIB95 with shorter time than congeneric algorithms.