遗传算法毕业论文..pdf
《遗传算法毕业论文..pdf》由会员分享,可在线阅读,更多相关《遗传算法毕业论文..pdf(32页珍藏版)》请在三一文库上搜索。
1、目 录 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 遗传算法优
2、缺点 14 5.2 模拟退火算法的优缺点 . 15 6 结语 . 15 参考文献 . 17 附录: 错误!未定义书签。 廊坊师范学院本科生毕业论文 论文题目 :基于遗传算法与模拟退火算法的TSP算法求解 10大城市最短旅途 论文摘要 : TSP 问题为组合优化中的经典的NP完全问题 . 本论文以某旅行社为中 国十大旅游城市 -珠海、西安、杭州、拉萨、北京、丽江、昆明、成 都、洛阳、威海制定最短旅途为例,分别利用基于遗传算法的TSP 算法与基于模拟退火算法的TSP 算法求解 10 大城市旅游路线问题 . 本论文给出了遗传算法与模拟退火算法中各算子的实现方法,并展示 出求解系统的结构和求解系统基于
3、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
4、 problem about combinatorial optimization This article takes a travel agency looking for the shortest trip of 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 al
5、gorithm and simulated annealing algorithmThe articlegives 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
6、software ,and compare the results based on genetic algorithm and simulated annealing algorithmAnd 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 algorit
7、hm ;TSP;the shortest path 1 1 引言 TSP问题为组合优化中的经典问题, 已经证明为一 NP 完全问题 1 ,即其 最坏情况下的时间复杂性随着问题规模的扩大,按指数方式增长 2 ,到目前 为止不能找到一个多项式时间的有效算法.TSP问题可描述为 :已知 n个城市相 互之间的距离,某一旅行商从某个城市出发访问每个城市一次且仅一次,最 后回到出发城市,如何安排才使其所走路线最短.TSP 问题不仅仅是一个简单 的组合优化问题,其他许多的NP 完全问题可以归结为TSP 问题,如邮路问 题、装配线上的螺帽问题和产品的生产安排问题等,使得TSP 问题的有效求 解具有重要的意义
8、.本文中的 TSP 算法主要采用遗传算法与模拟退火算法 遗传算法是一种进化算法,其基本原理是仿效生物界中的“物竞天择, 适者生存”的演化法则 3 遗传算法把问题参数编码为染色体,再按照所选 择的适应度函数,利用迭代的方式进行选择、交叉、变异以及进化逆转等运 算对个体进行筛选和进化,使适应值大的个体被保留,适应值小的个体被淘 汰 4 ,新的群体继承了上一代的信息,又优于上一代,这样反复循环,直至 满足条件,最后留下来的个体集中分布在最优解的周围,筛选出最优个体作 为问题的解 模拟退火算法的出发点是基于物理中固体物质的退火过程与一般的组合 优化问题之间的相似性 5 ,该算法是一种优化算法,其物理退
9、火过程由三部 分组成,分别为:加温过程、等温过程、冷却过程其中,加温过程对应算 法设定初温, 等温过程对应算法的Metropolis 6 抽样过程,冷却过程对应控制 参数的下降这里能量的变化就是目标函数,要得到的最优解就是能量最低 态 7 Metropolis 准则是 SA 算法收敛于全局最优解的关键所在,Metropolis 准则以一定的概率接受恶化解,这样就使算法跳离局部最优的陷阱 2 2 问题描述 本案例为某旅行社为中国十大旅游城市,分别为珠海、西安、杭州、拉萨、 北京、丽江、昆明、成都、洛阳、威海,根据全程路径最短为目的,制定最优的 旅游顺序依次游玩这十个城市.这类问题就由 TSP 算
10、法来解决,寻找出一条最短 遍历这 10 个城市的路径 .利用 google地图找到城市坐标, 下表为这十个城市的位 置坐标如表 2-1 所示 . 表 2-1 10 个城市的位置坐标 城市编号X坐标Y坐标城市编号X坐标Y坐标 1 22.31 113.58 6 26.86 100.23 2 34.37 108.95 7 24.89 102.83 3 30.29 120.16 8 30.59 104.07 4 29.66 91.14 9 34.65 112.46 5 39.95 116.41 10 3753 122.13 3 基于遗传算法 TSP 算法 3.1 基于遗传算法的 TSP 算法总体框架
11、TSP问题的遗传算法包括编码设计、种群初始化、适应度函数选择、 终止条 件设定、选择操作设定、交叉操作设定以及变异操作设定和进化逆转操作. 为简 化 TSP 问题的求解,假设每个城市和其它任意一个城市之间都以欧氏距离 8 直 接相连 .遗传算法 TSP问题的流程图如图2-1 所示. 3 N Y 图 2-1 算法流程框架图 3.2 算法的详细设计 3.2.1 解空间的表示方式 遗传算法对解空间的表示大多采用二进制编码形式,但是二进制编码方式不 适合 TSP 问题的解的表示,因为它要求特殊的修补算子 9 来修复变化算子所产 生的非法路径(即不可行路径). 给出城市编号,用十进制数编码来表示解更合
12、适,例如:近邻表示、次序表示和路径表示等等. 这里采用了最简单的路径表示 法. 它是最自然、最接近人类思维的表示法 . 因此对十大旅游城市按照珠海、 西安、 杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海顺序依次编号为1,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,则解空间就用二维数组 来表示: Path200
13、10 实 际 问 题 参 数集 编 码 初始种群 计算适应度 选择 适 应 度 高 的 染色体 变异 交叉 进 化 逆 转 新种群 代 数 满 足 终 止 解决实际问题解码 4 3.2.2 种群初始化 种群的规模选择应适当, 盲目的增大种群规模不能使算法得到改进,反而大 大增加了计算的开销 . 10个城市 TSP问题,可以选择小规模的种群(例如200) , 种群初始化时,先产生1,2,10 的一条规则路径,然后在这条路径中随机 选两个数,将它们交换位置,这样做若干次(本文采用200 次) ,保证这条路径 变成了一条随机的路径 . 以这条随机路径为基础, 对一些随机的位, 做两两交换, 这样产生
14、了一个个体;同样地产生种群里其它的个体. 3.2.3 适应度函数 适应度表明个体或解的优劣性 10 ,不同的问题,适应度函数的定义方式也 不同,本文设 12610 | k |k |kk为一个采用整数编码的染色体, ij k k D为城市 i k 到 城市 j k 的欧氏距离,则该个体的适应度为 11 : 1 1 1 1 ijn n k kk k i fitness DD (1) 即适应度函数为恰好走遍10 个城市,在回到出发城市的总距离的倒数.优化的目 标就是选择适应度函数值尽可能大的染色体,适应度函数值越大的染色体越优 质,反之越劣质 .求得种群中所有个体的适应值后,将适应值最大的个体保存起
15、 来,到演化完毕时,这个个体就是最后要求的最优解. 3.2.4 选择操作 选择操作的目的是为了从当前群体中以一定的概率选择优良个体到新群体 中,将选择算子作用于群体, 从而使优化的个体有机会直接遗传到下一代或通过 配对交叉产生新的个体再遗传到下一代;个体被选中的概率与适应度值有关,适 应度值越大,被选中的概率也就越大 12 ,而适应度值越大的染色体越优质.本案 例选择轮盘赌法,即基于适应度比例的选择策略,个体i被选中的概率为: 5 1 i i N j j F p F (2) 其中, i F为个体i的适应度值; N 为种群个体数目 . 3.2.5 交叉操作 交叉操作是遗传算法中最主要的遗传操作,
16、通过交叉操作可以得到新一代个 体,新个体结合了其父辈个体的特性,交叉体现了信息交换的思想利用不同映 射杂交,确定交叉操作的父代,将父代样本两两分组,每组重复以下过程: (1)产生两个 1,10区间的随机整数 1 r和 2 r,确定两个位置,对两个位置的 中间数据进行交叉,如 1 4r, 2 7r 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)交叉后,对同一个个体中有重复的城市编号,不重复的数字保留,有冲 突的数字(带 *的位置)采用部分映射的方法消除冲突,即
17、利用中间段的对应关 系进行映射 .结果为: 4 1 2 3 5 8 9 6 7 10 10 5 2 4 3 6 7 8 1 9 交叉是希望不同的个体在产生下一代时,能够结合各自的优势基因, 产生更 好质量的下一代 . 6 3.2.6 变异操作 变异可以看作是外界对种群的影响.变异是为了引入新的因素,希望个体在 外界的作用下,能够实现自我优化,生好的基因.将变异算子作用于群体 .即是对 群体中的个体串的某些基因位置上的基因值作变动.变异算子采用了简单的倒序 变换,以 10 城市为例,随机的产生两个小于10 的整数,对某个个体进行分割, 假设 1 4r , 2 7r,将分割段倒序并放回原来的位置即
18、可,如下数组所示: 5 1 2 4 3 6 7 9 8 10 得到的新解为: 5 1 2 7 3 6 4 9 8 10 由于这种变异算子仍能保持个体中的路径片段,即倒序前后这个切割段的路 径是一样的,只是两端点与整个路径的连接颠倒了,这使得变异不是漫无边际, 而是有所取舍的 .这种简单反序可以保证后代仍然是一条合法途径. 3.2.7 进化逆转操作 为了改善遗传算法的局部搜索能力,在选择、交叉、变异之后引进连续多次 的进化逆转操作,这里的“进化”是指逆转算子的单方向性 13 ,即只有经逆转 后,适应度值有所提高的才接受下来,否则逆转无效. 产生两个 1,10区间内的随机整数 1 r和 2 r,确
19、定两个位置,将其对换位置, 例如 1 4r, 2 7r 5 1 2 4 3 6 7 9 8 10 进化逆转后为: 5 1 2 7 3 6 4 9 8 10 对每个个体进行交叉变异,然后代入适应度函数进行评估,x 选择出适应值 大的个体进行下一代交叉和变异以及进化逆转操作循环操作:判断是否满足设定 的最大遗传代数 MAXGEN 14 , 不满足则跳入适应度值计算; 否则结束遗传操作 . 7 3.3 实验结果分析 1-10 的十个数字按顺序为珠海、西安、杭州、拉萨、北京、丽江、昆明、成 都、洛阳、威海的编号. 利用各城市坐标构成的102的矩阵及初始化随机值和 DrawPath函数画出闭合路径图,为
20、优化前的随机路线轨迹图,如图3-1 所示: 图 3-1 随机路线轨迹图 图中三角标注的数字6 代表起点,依次按照箭头方向遍历,最终再次回到 起点 6 初始种群中的一个随机值: 637851249106 总距离: 165.2494 对照 1-10 数字编号所代表的的城市,随机路线为: 丽江 杭州 昆明 成都 北京 珠海 西安 拉萨 洛阳 威海 丽江 8 优化后的最优路线图如图3-2 所示: 图 3-2 最优路线图 最优解 : 467131059284 总距离: 77.1532 即最优路线如下所示: 拉萨 丽江 昆明 珠海 杭州 威海 北京 洛阳 西安 成都 拉萨 9 此遗传算法在解决 TSP 问
21、题过程中的优化迭代过程如下图3-3 所示: 图 3-3 优化过程 其中横坐标表示迭代次数,纵坐标为优化过程中路线长度. 由该优化过程图 可知,优化前后路径长度有了很大的改进,20 代以后路径长度基本上已经保持 不变了,可以认为是最优解了. 总距离由原来的165.2494 变为 77.1532,降低为 原来的 46.69%,表明利用遗传算法解决TSP 问题可以起到较好的作用 10 4 基于模拟退火算法的TSP 算法 4.1 SA 算法的实现过程 4.2 算法流程图 N N Y Y 图 4-1 模拟退火算法求解流程框图 4.3 模拟退火算法的实现过程 (1)控制参数的设置 需要设置的主要控制参数有
22、降温速率 q、取初始温度 0 T 足够大,令T= 0 T , 任取初始解 1 S ,确定每个T时的迭代次数,即 Metropolis 链长 L,如图表 4-1 所 示 表 4-1 参数设定 降温速率 q初始温度 0 T 结束温度 end T 链长L 0.9 1000 0.001 500 (2)初始解 对于 10 个城市的 TSP 问题,得到的解为1 n一个排序, 其中每个数字为对 应城市的编号, 10 个城市的 TSP 问题1,2,3,4,5,6,7,8,9,10 ,则 设 置 控 制参数 初始解 1 S count=0 k=1 解变换 得新解 M 准则判断是 否接受新解 新的 1 S, k=
23、k+1 count=count+1,T=qT kL? end TT? 输出当前解 2S 结束 11 |1|2|3|4|5|6|7|8|9|10 就为一个合法解,采用随机排列的方法产生一个初始解 1 S (3)解变换生成新解 通过对当前解 1 S 进行变换,产生新路径的数组即新解, 这里采用的变换是产 生随机数的方法来产生将要交换的两个城市,用二邻域变换法 15 产生新的路径, 即新的可行解 2 S . 例如 n=10 时,产生两个 1,10 范围内的随机整数 1 r和 2 r确定 两个位置,将其对换位置,如 1 r=4, 2 r=7 5 1 2 4 3 6 7 9 8 10 得到的新解为: 5
24、 1 2 7 3 6 4 9 8 10 (4)Metropolis 准则 若路径长度函数为( )f S,则当前解的路径为 1 ()f S,新解的路径为 2 ()f S, 路径差为df= 2 ()f S- 1 ()f S 16 ,则 Metropolis 准则为 17 : 1 exp() P df T (3) 若0df,则接受 2 S 作为新的当前解, 即 1 S 2 S ;否则计算 2 S 的接受概率 exp(/)dfT,即随机产生的(0, 1)区间上均匀分布的随机数rand,若 exp(/)dfTrand 1 8, 也接受 2 S 作为新的当前解, 1 S 2 S ; 否则保留当前解 1 S
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 毕业论文
链接地址:https://www.31doc.com/p-5165773.html