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

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

作　　者：孔令夷[1] 

机构地区：[1]西安邮电大学管理工程学院,陕西西安710061

出　　处：《东北师大学报（自然科学版）》2014年第1期55-59,共5页Journal of Northeast Normal University(Natural Science Edition)

基　　金：国家自然科学基金资助项目(71102149);教育部人文社会科学研究项目(12YJC790084);陕西省教育厅科研计划项目(12JK0056);西安邮电大学青年教师科研基金资助项目(ZL2011-22);陕西省体育局常规课题项目(12092)

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

关 键 词：旅行商问题 模拟退火 遗传算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]