摘要
为了克服传统算法求解有约束TSP的早熟收敛缺陷,提出混合启发式算法。采用基于遍历城市顺序的染色体编码,结合随机法与贪心法生成较优初始种群,执行优先保留交叉和平移变异操作,引入局部邻域及混沌搜索,设计特定的适应度函数,给出最优解判据,最后证实该算法的有效性。
A hybrid heuristic algorithm is proposed to overcome premature convergence of the tradi- tional algorithm used for solving constrained Travelling Salesman Problem (TSP). The algorithm adopted the chromosome encoding scheme based on solutions to the travelling salesman problem, combined with the stochastic method and the greedy method ways of producing superior initial pop ulations. Precedence Preservation, Crossover and Shift Change Mutation operations were executed, and chaos searching and local neighborhood searching were introduced. Furthermore, by means of setting a specific fitness function, the criteria were used to extract an optimal solution. Finally, the effectiveness of the new algorithm is demonstrated.
出处
《西安邮电学院学报》
2013年第1期86-89,共4页
Journal of Xi'an Institute of Posts and Telecommunications
基金
国家自然科学基金青年科学基金资助项目(71102149)
教育部人文社会科学研究青年基金资助项目(12YJC790084)
陕西省教育厅专项科学研究计划资助项目(12JK0056)
西安邮电学院青年教师科研基金资助项目(ZL2011-22)
陕西省体育局常规课题资助项目(12092)
关键词
约束
TSP
混合启发式算法
交叉变异
constraint, travelling salesman problem (TSP), hybrid heuristic algorithm, crossover and mutation