《遗传算法毕业论文.》由会员分享，可在线阅读，更多相关《遗传算法毕业论文.（33页珍藏版）》请在金锄头文库上搜索。
1、目录1 引言12 问题描述23 基于遗传算法TSP算法23.1 基于遗传算法的TSP算法总体框架23.2算法的详细设计33.2.1 解空间的表示方式33.2.2 种群初始化43.2.3适应度函数43.2.4选择操作43.2.5交叉操作53.2.6变异操作63.2.7进化逆转操作63.3 实验结果分析74 基于模拟退火算法的TSP算法104.1 SA算法的实现过程104.2 算法流程图104.3模拟退火算法的实现过程104.4实验结果115 对两种算法的评价145.1遗传算法优缺点145.2 模拟退火算法的优缺点156结语15参考文献17附录：19 廊坊师范学院本科生毕业论文论文题目：基于遗传算
2、法与模拟退火算法的TSP算法求解10大城市最短旅途 论文摘要：TSP问题为组合优化中的经典的NP完全问题.本论文以某旅行社为中国十大旅游城市-珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海制定最短旅途为例，分别利用基于遗传算法的TSP算法与基于模拟退火算法的TSP算法求解10大城市旅游路线问题. 本论文给出了遗传算法与模拟退火算法中各算子的实现方法，并展示出求解系统的结构和求解系统基于MATLAB的实现机制 利用MATLAB软件编程，运行出结果，并对基于遗传算法的TSP算法结果与基于模拟退火算法的TSP算法的结果进行比较，描述其优缺点，并选择最为恰当的TSP算法，实现最短旅途的最优
3、解. 关键词： 遗传算法；模拟退火算法；TSP；最短路径；Title： TSP Algorithm Based on Genetic Algorithm or Simulated Annealing Algorithm for Solving the Shortest Journey of 10 CitiesAbstract：TSP problem is a classic NP problem about combinatorial optimization This article takes a travel agency looking for the shortest trip of
4、 ten tourist cities in ChinaZhuhai， Xian， 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 algo
5、rithm 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 algorithmAnd describe their
6、 advantages and disadvantages so that choose the most appropriate TSP algorithm to achieve the optimal solution for the shortest pathKeywords：genetic algorithm；simulated annealing algorithm；TSP；the shortest path各产品过程检验的检验时机应在操作者对首件加工完成后自检，并判定合格。再由车间依据计划将需进行专检的部件填写报检单报检，在报检后首先由检验人员应检查车间是否按程序文件的规定开展了自
7、检，然后接受报检进行检验、记录及判定。1 引言TSP问题为组合优化中的经典问题，已经证明为一NP完全问题，即其最坏情况下的时间复杂性随着问题规模的扩大，按指数方式增长，到目前为止不能找到一个多项式时间的有效算法.TSP问题可描述为:已知n个城市相互之间的距离，某一旅行商从某个城市出发访问每个城市一次且仅一次，最后回到出发城市，如何安排才使其所走路线最短.TSP问题不仅仅是一个简单的组合优化问题，其他许多的NP完全问题可以归结为TSP问题，如邮路问题、装配线上的螺帽问题和产品的生产安排问题等，使得TSP问题的有效求解具有重要的意义.本文中的TSP算法主要采用遗传算法与模拟退火算法遗传算法是一种进
8、化算法，其基本原理是仿效生物界中的“物竞天择，适者生存”的演化法则遗传算法把问题参数编码为染色体，再按照所选择的适应度函数，利用迭代的方式进行选择、交叉、变异以及进化逆转等运算对个体进行筛选和进化，使适应值大的个体被保留，适应值小的个体被淘汰，新的群体继承了上一代的信息，又优于上一代，这样反复循环，直至满足条件，最后留下来的个体集中分布在最优解的周围，筛选出最优个体作为问题的解 模拟退火算法的出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性，该算法是一种优化算法，其物理退火过程由三部分组成，分别为：加温过程、等温过程、冷却过程其中，加温过程对应算法设定初温，等温过程对应算法
9、的Metropolis抽样过程，冷却过程对应控制参数的下降这里能量的变化就是目标函数，要得到的最优解就是能量最低态Metropolis准则是SA算法收敛于全局最优解的关键所在，Metropolis准则以一定的概率接受恶化解，这样就使算法跳离局部最优的陷阱2 问题描述本案例为某旅行社为中国十大旅游城市，分别为珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海，根据全程路径最短为目的，制定最优的旅游顺序依次游玩这十个城市.这类问题就由TSP算法来解决，寻找出一条最短遍历这10个城市的路径.利用google地图找到城市坐标，下表为这十个城市的位置坐标如表2-1所示.表2-1 10个城市的位置
10、坐标城市编号X坐标Y坐标城市编号X坐标Y坐标122.31113.58626.86100.23234.37108.95724.89102.83330.29120.16830.59104.07429.6691.14934.65112.46539.95116.41103753122.133 基于遗传算法TSP算法3.1 基于遗传算法的TSP算法总体框架TSP问题的遗传算法包括编码设计、种群初始化、适应度函数选择、终止条件设定、选择操作设定、交叉操作设定以及变异操作设定和进化逆转操作.为简化TSP问题的求解，假设每个城市和其它任意一个城市之间都以欧氏距离直接相连.遗传算法TSP问题的流程图如图2-1所
11、示.N初始种群实际问题参数集计算适应度编码 选择适应度高的染色体交叉变异新种群进化逆转代数满足终止条件Y解决实际问题解码图2-1算法流程框架图3.2算法的详细设计3.2.1 解空间的表示方式遗传算法对解空间的表示大多采用二进制编码形式，但是二进制编码方式不适合TSP问题的解的表示，因为它要求特殊的修补算子来修复变化算子所产生的非法路径（即不可行路径）.给出城市编号，用十进制数编码来表示解更合适，例如：近邻表示、次序表示和路径表示等等.这里采用了最简单的路径表示法.它是最自然、最接近人类思维的表示法.因此对十大旅游城市按照珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海顺序依次编号为1
12、，2，3，4，5，6，7，8，9，10，例如，下面的路径（闭合的）：512436798105表示从城市5出发，经过1，2，4，3，6，7，9，8，10最后回到城市5的一条路径，可以自然地用一维数组来表示：（5，1，2，4，3，6，7，9，8，10）10个旅游城市的TSP问题，如果将种群规模设为200，则解空间就用二维数组来表示：Path200103.2.2 种群初始化种群的规模选择应适当，盲目的增大种群规模不能使算法得到改进，反而大大增加了计算的开销.10个城市TSP问题，可以选择小规模的种群（例如200），种群初始化时，先产生1，2，10的一条规则路径，然后在这条路径中随机选两个数，将它们交
13、换位置，这样做若干次（本文采用200次），保证这条路径变成了一条随机的路径.以这条随机路径为基础，对一些随机的位，做两两交换，这样产生了一个个体；同样地产生种群里其它的个体.3.2.3适应度函数适应度表明个体或解的优劣性，不同的问题，适应度函数的定义方式也不同，本文设为一个采用整数编码的染色体，为城市到城市的欧氏距离，则该个体的适应度为： （1）即适应度函数为恰好走遍10个城市，在回到出发城市的总距离的倒数.优化的目标就是选择适应度函数值尽可能大的染色体，适应度函数值越大的染色体越优质，反之越劣质.求得种群中所有个体的适应值后，将适应值最大的个体保存起来，到演化完毕时，这个个体就是最后要求的最
14、优解.3.2.4选择操作选择操作的目的是为了从当前群体中以一定的概率选择优良个体到新群体中，将选择算子作用于群体，从而使优化的个体有机会直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代；个体被选中的概率与适应度值有关，适应度值越大，被选中的概率也就越大，而适应度值越大的染色体越优质.本案例选择轮盘赌法，即基于适应度比例的选择策略，个体被选中的概率为： （2）其中，为个体的适应度值；N为种群个体数目.3.2.5交叉操作交叉操作是遗传算法中最主要的遗传操作，通过交叉操作可以得到新一代个体，新个体结合了其父辈个体的特性，交叉体现了信息交换的思想利用不同映射杂交，确定交叉操作的父代，将父代样本两两分组，每组重复以下过程： （1）产生两个1，10区间的随机整数和，确定两个位置，对两个位置的中间数据进行交叉，如， 5 1 2 4 3 6 7 9 8 10 10 6 2 3 5 8 9 4 1 7交叉为： * 1 2 3 5 8 9 * * 10 10 * 2 4 3 6 7 * 1 * （2）交叉后，对同一个个体中有重复的城市编号，不重复的数字保留，有冲突的数字（带*的位置）采用部分映射的方法消除冲突，即利用中间段的对应关系进行映射.结果为：4 1 2 3 5 8 9 6 7 10 10 5 2 4 3 6 7 8 1 9交叉是希望不
