一种基于模拟退火的遗传算法在受约束旅行商问题中的应用

Applied research on genetic algorithm based on simulated annealing of constrained traveling salesman problem

旅行商路径问题已被证明是高维非线性完全问题,现实情况中还会增加非流通图约束.鉴于现有遗传算法在求解过程中容易出现早熟及冗余迭代的缺陷,设计了一种基于模拟退火的优化算法.该算法以旅行商途径地点次序作为编码,初始化过程中混合了贪心方法以实现局部优化,避免出现大量非可行染色体,增大了后续的进化效率.并且依据约束满足条件推导出特定的适值函数,选择了当前较为高效的交叉变异操作,在执行过程中融入了基于模拟退火算法的子体接纳判据.最后引用国内若干城市的信息用于算法检验,结果显示新算法显著优于现有算法.

Traveling salesman problem（TSP） was demonstrated to be non-deterministic polynomial complete problem, let alone unconnected graph constraint. In consideration of premature convergence and redundant iteration of the existing genetic algorithm,a new genetic algorithm based on simulated annealing was designed as an optimization algorithm. It employed order of places where traveling salesman went by as codes. Greedy transformation was mixed during initialization to realize local optimization, prevent a great quantity of inferior individuals emerging and increase evolution productiveness during the follow-up process. The specific fitness function was also deduced based on conditions of unconnected graph constraint. After that, the new genetic algorithm chose currently high- efficiency crossover and variation arithmetic, blending in new daughter adoption criterion based on simulated annealing algorithm. Lastly, information of some cities in our country was quoted to examine the new genetic algorithm. It was found that the new genetic algorithm was notably superior to the existing GA.