2022年遗传算法的TSP的求解 .pdf
《2022年遗传算法的TSP的求解 .pdf》由会员分享,可在线阅读,更多相关《2022年遗传算法的TSP的求解 .pdf(16页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、智 能 优 化 计 算 及 应 用 课 考 核 论 文第1页遗传算法的TSP (旅行商问题 ) 的求解学生姓名:宗满意指导老师:乔立红摘要TSP 问题是典型的 NP 完全问题 , 遗传算法是求解 NP 完全问题的一种常用方法。本文针对解决 TSP 问题, 在MATLAB 中用遗传算法施行对 TSP 问题进行了求解,进行了选择、交叉和变异算子进行了算法设计,最后在MATLAB 软件上进行编程实现。最后探讨了遗传算法解决旅行商问题自身具备的特点1 。关键词:遗传算法; TSP 问题; MATLAB 软件名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - -
2、 - - - - 名师精心整理 - - - - - - - 第 1 页,共 16 页 - - - - - - - - - 智 能 优 化 计 算 及 应 用 课 考 核 论 文第2页SOLVING TSP (Travelling Salesman Problem ) BASED ON GENETIC ALGORITHM Author : Zong Man-yi Tutor : Qiao Li-hong Abstract TSP( Traveling Salesman Problem) is a typical NP complete problem ,genetic algorithm is
3、the perfect method for solving NP complete problem. This paper use genetic algorithm in the MATLAB software to solve the a typical TSP problem . It probes into the realization of genetic operator program through TSP solving by genetic algorithm , design the each function of each genetic operator(sel
4、ect, intercross, mutate).Finally ,We programm in Matlab language and discuss the characteristic of genetic algorithm in solving TSP Key words : genetic algorithm; TSP Matlab ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 16 页 - - - - - - - - - 智 能 优 化 计 算 及 应
5、 用 课 考 核 论 文第3页目录引言 . . 41 GA概述 . 42 旅行商问题 (TSP) . 43 用遗传算法解决旅行商问题 . 54 论文的主要构成 . 5遗传算法的设计 . . 61 问题分析 . 62 总体设计 . 73 详细设计 . 83.1 编码与随机和初始群体生成. 83.2 城市位置及距离矩阵和适应度函数 . 83.4 选择 . 93.4 交叉 . 93.5 变异 . 103.6 群体的跟新和终止条件 . 10MATLAB 编程验证 . 111MATLAB 计算 . 112 算法分析优化 . 13结论 . . 15参考文献 . . 16名师资料总结 - - -精品资料欢迎
6、下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 16 页 - - - - - - - - - 智 能 优 化 计 算 及 应 用 课 考 核 论 文第4页引言1 GA概述遗传算法 (Genetic Algorithm , GA ) 是由美国 J. Holland 教授提出的一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它起源于达尔文的进化论, 是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型。其主要特点是群体搜索策略和群体中个体之间的信息交换, 搜索不以梯度信息为基础。 它尤其适用于处理传统
7、搜索方法难于解决的复杂和非线性问题, 可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。作为一种全局优化搜索算法, 遗传算法以其简单通用、鲁棒性强、适于并行处理以及应用范围广等特点, 使其成为 21 世纪智能计算核心技术之一。进入 80 年代 , 遗传算法迎来了兴盛发展时期, 无论是理论研究还是应用研究都成了十分热门的话题 2 。2 旅行商问题 (TSP) 一个有名的组合优化问题就是旅行商问题(Travelling Salesman Problem , TSP)。TSP 问题是典型的、易于描述却难以处理的组合优化问题。由于遗传算法方法的本质是处理复杂问题的一种鲁棒性强的启发
8、性随机搜索算法, 故而利用遗传算法求解这类问题是有效的。假设平面上有 n个点代表 n个城市的位置 , 寻找一条最短的闭合路径 , 使得可以遍历每一个城市恰好一次。这就是旅行商问题。旅行商的路线可以看作是对n个城市所设计的一个环形 , 或者是对一列 n个城市的排列。 由于对 n个城市所有可能的遍历数目可达(n- 1)! 个, 因此解决这个问题需要 0(n!) 的计算时间。假设每个城市和其他任一城市之间都以欧氏距离直接相连。 也就是说 , 城市间距可以满足三角不等式, 也就意味着任何两座城市之间的直接距离都小于两城市之间的间接距离。是一个典型的优化组合问题3 。名师资料总结 - - -精品资料欢迎
9、下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 16 页 - - - - - - - - - 智 能 优 化 计 算 及 应 用 课 考 核 论 文第5页3 用遗传算法解决旅行商问题目前针对 TSP 问题有许多种解法,较为常用的算法有神经网络法、列表寻优法、二叉树描述法、模拟退火法和遗传算法等等。遗传算法是近几年发展起来的一种崭新的全局优化算法,它借用了生物遗传学的观点,通过选择、遗传、变异和免疫等作用机制,使每个个体的适应性提高。由于其全局搜索的特性,遗传算法在解决TSP 问题中有着其他算法所没有的优势。
10、提出的TSP 问题包括 31个城市的编号和各自的位置。本文针对这个TSP 问题进行了遗传算法的编程和求解。4 论文的主要构成本论文在 MATLAB 中用遗传算法施行对TSP问题进行了求解,进行了选择、交叉和变异、免疫等算子进行了算法设计,最后在MATLAB 软件上进行编程实现。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 16 页 - - - - - - - - - 智 能 优 化 计 算 及 应 用 课 考 核 论 文第6页遗传算法的设计1 问题分析TSP 问题的描述
11、十分简单 , 简言之, 就是寻找一条最短的遍历 n 个城市的最短路径 , 或者说搜索自然数子集 X = 1 , 2 , ?, n ( X 的元素表示对 n 个城市的编号 ) 的一个排列( X) = V1 , V 2 , ?, Vn , 使len = d ( Vi , Vi+1) + d ( V1 , Vn) 取最小值, 式中的 d ( Vi , Vi+1) 表示城市 Vi 到城市 Vi + 1的距离. (图 1)3 本实例中设定了我国 31个省会城市, 当一个旅行商彼遍历了所有城市后回到出发城市,求其最短路径的走法。一个最容易想到的方法是利用排列组合的方法把所有的路径都计算出来,并逐一比较,选
12、出最小的路径。虽然该方法在理论上是可行的,但路径的个数与城市的个数成指数增长,当城市个数较大时,该方法的求解时间是难以忍受的,甚至是不可能完成的, 31个城市所有路径个数是 30!个。由于其全局搜索的特性,遗传算法在解决 TSP 问题中有着其他算法所没有的优势。本文针对这个 TSP 问题进行了遗传算法的编程和求解。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 16 页 - - - - - - - - - 智 能 优 化 计 算 及 应 用 课 考 核 论 文第7页2 总
13、体设计标准的遗传算法包括群体的初始化,选择,交叉,变异操作。其主要步骤可描述如下1 :(1) 随机产生一组初始个体构成的初始种群,并评价每一个个体的适配值。(2)判断算法的收敛准则是否满足。若满足输出搜索结果;否则执行以下步骤。(3) 根据适配值大小以一定方式执行选择操作。(4)按交叉概率 Pc执行交叉操作 . (5)按变异概率 Pm 执行变异操作。(6)返回步骤( 2)。本TSP 问题的遗传算法总体设计选择交叉变异N2N2跟新群体N最优解加入下次迭代1随机路径产生随机路径使群体数目不变N-N2-1产生初始群体N随机产生初始群,计算各个个体的适配值依适配值大小选择变异交叉算法是否达到收敛NPc
14、=rand?Pm=rand?YY输出YNN(图 2)标准遗传算法的流程图名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 16 页 - - - - - - - - - 智 能 优 化 计 算 及 应 用 课 考 核 论 文第8页(图 3)总体设计说明: (1) 本算法的判断结束准则是固定指定了迭代的次数当算法达到迭代次数时,算法结束,输出当前的最优解(2)在根据适配值计算并选择的时候,记录下来的当前最优值,在变异后加入跟新的群体,保证新的迭代循环中TSP 解越来越好(不会变
15、差) 。(3)在选择的一种操作是拿最优的K个替换最差的 K个个体,本例是按适配值选择,并使群体数目变少,当每次变异操作后,产生随机路径补充群体是群体数目不变,再次循环,一定程度上防止因初始群体的选择问题而陷入局部最优。3 详细设计3.1 编码与随机和初始群体生成给所有城市编码,以城市的遍历次序作为遗传算法的编码。在MATLAB 中使用randperm(N) 产生一个 1N 的矩阵( N 为所有城市的个数,本例中为31)为一个随机路径。利用 nN矩阵存储 n个随机群体产生初始群体。3.2 城市位置及距离矩阵和适应度函数城市的位置为编译前指定,也可以使用随机生成的坐标参数。距离矩阵使用一个NN 矩
16、阵 D 存储, D(i,j)代表城市i 和城市 j 之间的距离。D(i,j)=sqrt((Xi-Xj ).2+(Yi-Yj).2) 在该问题的求解中,用距离的总和来衡量适应度,距离的总和越大,适应度越小,进而探讨求解结果是否最优。每个个体(每条路径距离)总合计算公式为:len=D(1,N); for i=1:(N-1) len=len+D(i,i+); end len 纪录总路径格式 n1 len(i)代表第 i 个个体(路径)距离总合。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年遗传算法的TSP的求解 2022 遗传 算法 TSP 求解
限制150内