| As one kind of the most important optimization algorithms, evolutionary algorithms are random search algorithms that are inspired by the principles of the nature evolution. Without requiring the differentiability of the functions and with implicit parallelism, evolutionary algorithms are often used to solve some difficult problems which the classical algorithms can't.The TSP is a class of NP-hard combinatorial optimization problems. Many practical problems can be transformed into the TSP. So evolutionary algorithms with the global convergence become one of the most important algorithms to solve the TSP. In this paper, a novel hybrid globally convergent evolutionary algorithm for the TSP is proposed. A new and simple integer-encoding scheme is designed, and each integer is corresponding to a unique valid tour, and vice versa. The advantages of the proposed algorithm are that it always generates feasible solution, uses less computation, and is easy to design genetic operators.Quantum-Inspired genetic algorithm (QIGA) has been successfully applied to some difficult optimization problems due to its effective search ability, and ability of keeping proper population diversity. It is necessary to study the QIGA. The traditional QIGA is improved by introducing a new controllable rotation gate and a new terminate criterion for global optimization problems. The improved QIGA can effectively escape from the local optimal solutions and keep the balance between the solution quality and running time; Moreover, based on this, a new QIGA for the TSP is proposed. Due to adopting pairs of amplitudes to encode, the population size needed is only1/10 ~ 1/5 that of standard genetic algorithm. At the same time, the two-phase local search for edge evolving is integrated into QIGA to accelerate its convergent speed.Moreover, the global convergence of the two proposed new algorithms is analyzed, and numerical experiments are made. The results show the effectiveness of both proposed algorithms.
|
PDF Full Text Request