目录
1 引言 ............................................................................................................................................ 1 2 问题描述 .................................................................................................................................... 2 3 基于遗传算法TSP算法 ........................................................................................................... 2
3.1 基于遗传算法的TSP算法总体框架 ............................................................................ 2 3.2 算法的详细设计 ............................................................................................................. 3
3.2.1 解空间的表示方式 ................................................................................................ 3 3.2.2 种群初始化 ............................................................................................................ 4 3.2.3 适应度函数 .......................................................................................................... 4 3.2.4 选择操作 .............................................................................................................. 4 3.2.5 交叉操作 .............................................................................................................. 5 3.2.6 变异操作 .............................................................................................................. 6 3.2.7进化逆转操作 ......................................................................................................... 6 3.3 实验结果分析 ................................................................................................................... 7 4 基于模拟退火算法的TSP算法 ............................................................................................... 10
4.1 SA算法的实现过程 ........................................................................................................ 10 4.2 算法流程图 ................................................................................................................... 10 4.3模拟退火算法的实现过程 .............................................................................................. 10 4.4实验结果 .......................................................................................................................... 11 5 对两种算法的评价 .................................................................................................................... 14
5.1遗传算法优缺点 .............................................................................................................. 14 5.2 模拟退火算法的优缺点 ................................................................................................. 15 6结语 ............................................................................................................................................. 15 参考文献......................................................................................................................................... 17 附录： ............................................................................................................ 错误！未定义书签。
廊坊师范学院本科生毕业论文
论文题目：基于遗传算法与模拟退火算法的TSP算法求解10大城市最短旅途
论文摘要：TSP问题为组合优化中的经典的NP完全问题.本论文以某旅行社为中
关键词：国十大旅游城市--珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海制定最短旅途为例，分别利用基于遗传算法的TSP算法与基于模拟退火算法的TSP算法求解10大城市旅游路线问题. 本论文给出了遗传算法与模拟退火算法中各算子的实现方法，并展示出求解系统的结构和求解系统基于MATLAB的实现机制． 利用MATLAB软件编程，运行出结果，并对基于遗传算法的TSP算法结果与基于模拟退火算法的TSP算法的结果进行比较，描述其优缺点，并选择最为恰当的TSP算法，实现最短旅途的最优解.
遗传算法；模拟退火算法；TSP；最短路径；
Title： TSP Algorithm Based on Genetic Algorithm or Simulated Annealing
Algorithm for Solving the Shortest Journey of 10 Cities
Abstract：TSP problem is a classic NP problem about combinatorial
optimization． This article takes a travel agency looking for the shortest trip of ten tourist cities in China－Zhuhai， Xi'an， Hangzhou， Lhasa， Beijing， Lijiang， Kunming， Chengdu， Luoyang and Weihai for instance，and solves this problem by TSP algorithm based on genetic algorithm and simulated annealing algorithm． The article gives the implementations of every operator of genetic algorithm and simulated annealing algorithm and demonstrates the architecture and the implementation mechanism of the solving system based on MATLAB． I program and operate the results by MATLAB software，and compare the results based on genetic algorithm and simulated annealing algorithm．And describe their advantages and disadvantages so that choose the most appropriate TSP algorithm to achieve the optimal solution for the shortest path．
Keywords：genetic algorithm；simulated annealing algorithm；TSP；the shortest path