摘要
巡回旅行商问题(TSP)是一个组合优化方面的问题,已经成为测试组合优化新算法的标准问题。应用遗传算法解决TSP问题,首先对访问城市序列进行排列组合的方法编码,这保证了每个城市经过且只经过一次。接着生成初始种群,并计算适应度函数,即计算遍历所有城市的距离。然后用最优保存法确定选择算子,以保证优秀个体直接复制到下一代。采用有序交叉和倒置变异法确定交叉算子和变异算子。最后用MATLAB来实现算法,仿真后,观察路径,得出最终结果。
TSP（Traveling Salesman Problem） is a problem of combination optimization with simple definition but difficult to be solved.Using Genetic Algorithm（GA） to solve TSP,we should encode the visited cities according to the method of permutation and combination this can guarantee every city to be visited only once.Then generate the initial population,and calculate the fitness function,that is the distance of all the cities.Next,use the method of optimal preservation to determine the selection operator to ensure those excellent individuals can being reproduced to the next generation.Use the method of orderly cross and inversion mutation to determine the crossover operator and the mutation operator.Using MATLAB to carry out the algorithm,after simulation,we observe the route and obtain the result in the end.
出处
《安阳师范学院学报》
2012年第2期38-40,共3页
Journal of Anyang Normal University
