改进的遗传算法求解旅行商问题

提出一种解决旅行商问题的改进遗传算法.在传统遗传算法的基础上,引入贪婪算法进行种群初始化;从遗传进化代数和个体适应函数值两个方面实现遗传参数自适应调节,在加快寻优速度的同时防止寻优陷入局部最优;采用基于贪婪方法的启发式交叉算子优化交叉结果;对交叉前后的种群分别实施精英个体保留策略,保证最优基因结构得以延续.实验结果分析表明,改进的遗传算法可以在种群规模较小的情况下具有更可靠的寻优能力.

Improved genetic algorithm for solving TSP

An improved genetic algorithm for solving traveling salesman problem(TSP) is proposed. Based on the traditional genetic algorithm, the proposed algorithm introduces the greedy method into species initialization. In order to improve the optimization speed and prevent the local minimum, the improved algorithm updates the crossover probability and mutation probability adaptively according to the evolution stages and the fitness value of individuals. The heuristic crossover operator based on greedy method is used to optimize the crossover results. The strategy of keeping the best individuals to propagate the optimal gene structure is introduced. The results of TSP example show that the improved algorithm can find the global optimal solution with high performance.