遗传算法毕业论文
目录
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
1 引言
TSP问题为组合优化中的经典问题，已经证明为一NP完全问题[1]，即其最坏情况下的时间复杂性随着问题规模的扩大，按指数方式增长[2]，到目前为止不能找到一个多项式时间的有效算法.TSP问题可描述为:已知n个城市相互之间的距离，某一旅行商从某个城市出发访问每个城市一次且仅一次，最后回到出发城市，如何安排才使其所走路线最短.TSP问题不仅仅是一个简单的组合优化问题，其他许多的NP完全问题可以归结为TSP问题，如邮路问题、装配线上的螺帽问题和产品的生产安排问题等，使得TSP问题的有效求解具有重要的意义.本文中的TSP算法主要采用遗传算法与模拟退火算法．遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择，适者生存”的演化法则[3]．遗传算法把问题参数编码为染色体，再按照所选择的适应度函数，利用迭代的方式进行选择、交叉、变异以及进化逆转等运算对个体进行筛选和进化，使适应值大的个体被保留，适应值小的个体被淘汰[4]，新的群体继承了上一代的信息，又优于上一代，这样反复循环，直至满足条件，最后留下来的个体集中分布在最优解的周围，筛选出最优个体作为问题的解．
模拟退火算法的出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性[5]，该算法是一种优化算法，其物理退火过程由三部分组成，分别为：加温过程、等温过程、冷却过程．其中，加温过程对应算法设定初温，等温过程对应算法的Metropolis[6]抽样过程，冷却过程对应控制参数的下降．这里能量的变化就是目标函数，要得到的最优解就是能量最低态[7]．Metropolis准则是SA算法收敛于全局最优解的关键所在，Metropolis 准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱．
2 问题描述
本案例为某旅行社为中国十大旅游城市，分别为珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海，根据全程路径最短为目的，制定最优的旅游顺序依次游玩这十个城市.这类问题就由TSP算法来解决，寻找出一条最短遍历这10个城市的路径.利用google地图找到城市坐标，下表为这十个城市的位置坐标如表2-1所示.
表2-1 10个城市的位置坐标
3 基于遗传算法TSP算法
3.1 基于遗传算法的TSP算法总体框架
TSP问题的遗传算法包括编码设计、种群初始化、适应度函数选择、终止条件设定、选择操作设定、交叉操作设定以及变异操作设定和进化逆转操作.为简化TSP问题的求解，假设每个城市和其它任意一个城市之间都以欧氏距离[8]直接相连.遗传算法TSP问题的流程图如图2-1所示.