关键词: 旅行商问题 遗传算法 群体间竞争与协作 免疫选择

Abstract:

The classic travding salesman problem is one of the NP-hard combinatorial optimization problems, and a fast and effective solution to TSP has the impo  rtant theoretical and practical significance. Enlighted by the mutual contacts between the nature species groups, the paper proposes the inter-group com petition and collaboration of genetic algorithms to solve the traveling salesman problem. In the iterative process, we only choose a competitive group to execute the evolutionary process each time. Meanwhile in order to maintain the balance between all the groups, the populations have a cyclical exchang e, so as to promote good gene patterns to come into being in the process of olution. This algorithm is not only effective for maintaining the diversity of the population, and will increase the speed of convergence. Simulation results show that the algorithm is feasible and effective.

Key words: TSP;genetic algorithm;intergroup competition and collaboration;immune choice