版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、TSP 问题的遗传算法求解摘要:遗传算法是模拟生物进化过程的一种新的全局优化搜索算法,本文简 单介绍了遗传算法,并应用标准遗传算法对旅行包问题进行求解。关键词 :遗传算法、旅行包问题一、旅行包问题描述:旅行商问题,即TSP问题(Traveling Saleman Problem)是数学领域的一 个著名问题,也称作货郎担问题,简单描述为:一个旅行商需要拜访n个城市(1, 2,,n),他必须选择所走的路径,每个城市只能拜访一次,最后回 到原来出发的城市,使得所走的路径最短。其最早的描述是1759年欧拉研究的骑士周游问题,对于国际象棋棋盘中的 64个方格,走访 64个方格一次且最 终返回起始点。用图
2、论解释为有一个图G= (V,E),其中V是顶点集,E是边集,设D=(dj)是有顶点i和顶点j之间的距离所组成的距离矩阵,旅行商问题就是求出 一条通过所有顶点且每个顶点只能通过一次的具有最短距离的回路。若对于 城市V=v1,v2,v3,vn的一个访问顺序为T=(t1,t2,t3,ti, tn),其中ti V(i=1,2,3,n),且记tn+1= t1,则旅行商问题的数学模型 为:min L=2 d(i),t(i+1)(i=1,n)旅行商问题是一个典型组合优化的问题,是一个NP难问题,其可能的路径数为(n-1)!,随着城市数目的增加,路径数急剧增加,对与小规模的旅 行商问题,可以采取穷举法得到最优
3、路径,但对于大型旅行商问题,则很难 采用穷举法进行计算。在生活中 TSP 有着广泛的应用,在交通方面,如何规划合理高效的道路 交通,以减少拥堵;在物流方面,更好的规划物流,减少运营成本;在互联 网中,如何设置节点,更好的让信息流动。许多实际工程问题属于大规模 TSP, Korte于1988年提出的VLSI芯片加工问题可以对应于 1.2e6的城市TSP, Bland于1989年提出X-ray衍射问题对应于14000城市TSP,Litke于1984 年提出电路板设计中钻孔问题对应于17000城市TSP,以及Grotschel1991年提出的对应于442城市TSP的PCB442问题。二、遗传算法简介
4、遗传算法(Genetic Algorithm, GA)是借鉴生物界自然选择和自然遗传 机制“适者生存”的一种高度并行、随机化和自适应的全局优化算法,其首 先由 Holland 与 1975 年提出。其将问题的求解表示成“染色体”的适者生存 过程,通过“染色体“群的一代代不断进化,包括复制、交叉和变异等操作, 最终收敛到”最适应环境“的个体,从而得到问体的最优解。标准的遗传算法的只要步骤可描述为为:1、随机产生一组初始个体构成初始种群,并评价每一个体的适配值;2、判断算法的收敛准则是否满足。若满足则输出搜索结果,否则执行 下面步骤;3、根据适配值大小以一定的方式执行复制操作;4、按交叉概率 pc
5、 执行交叉操作;5、按变异概率 pm 执行变异操作。6、返回 2执行新一轮的复制、交叉、变异。在算法中,适配值是对染色体进行评价的一种指标,是遗传算法进行优 化所用的主要信息,与个体的目标值存在一种对应关系;复制操作通常采用 比例复制,即复制概率正比于个体适配值,适配值高的个体在下一代中复制 自身的概率大,从而提高种群的平均适配值;交叉操作通过交换两父代个体 的部分信息构成后代个体,使得后代继承父代的有效模式,从而有助于产生 优良个体;变异操作通过随机改变个体的某些基因而产生新个体,有助于增 加种群的多样性,避免早熟收敛。遗传算法利用生物进化和遗传的思想实现优化过程,区别与传统优化算 法1、算
6、法进行全空间并行搜索,并将搜索重点集中于性能高的部分, 从而能够提高效率并且不易陷入局部最小。2、算法具有固有并行性, 通过对种群的遗传处理可以处理大量的模 式,并且容易并行实现;其主要设计如下:1、确定问题的编码方案。2、确定适配值函数。3、遗传算子的设计。4、算法参数(种群数目、交叉与变异概率和进化代数等)的选取。5、确定函数终止条件。三、对TSP问题的遗传算法实现设计思路:1、初始化城市距离采用一个 city_xy 函数获取 n 个城市的 TSP 问题的坐标,保存在 city 矩 阵中,并且用 city_dis 矩阵表示任意两个城市之间的距离,矩阵中的元素 city_dis( i,j)
7、代表第 i 个城市与第 j 个城市间的距离。2、初始化种群通过 randperm 函数,生成一个一维随机向量(是整数 1,2,3,4,5 的 任意排列),然后将其赋给二维数组 group 的第一列,作为一个个体。如此循 环 N 次,生成了第一代种群,种群的每个个体代表一条路径。3、计算适应度 采用的适应度函数为个体巡回路径的总长度的函数。具体为adapt(1,i)=(n*maxdis-dis) (1)在式(1)中,adapt(1,i)表示第i个个体的适应度函数,maxdis为城市间 的最大距离, dis 为个体巡回路径的总长度,这样定义的适应度,当路经越 短时适应度值越大。 在适应度值的基础上
8、, 给出的计算个体期望复制数的表 达式为adaptnum(1,i)=(N*adapt(1,i)/ sumadapt)(2)其中,sumadapt为种群适应度之和。4、复制采用优秀个体的大比例保护基础上的随机数复制法。 具体做法为在生成 下一代个体时,先将最大适应度对应的路径个体以较大的比例复制到下一 代,然后再用随机数复制法生成下一代的其他个体。 其中,有一个问题必须 考虑,即若某一次生成的随机数过大, 结果能复制一个或极少个样本。 为了 避免这一情况,采用了限制措施,即压低了随机数的上限。5、交叉采用的方法为按步长的单点交叉, 为随机选择一对样本, 再随机选择一 个交叉点位置, 按一定的步长
9、进行交叉点的选择。 选择一个步长而不是将其 设为 1,是因为若某一位置处的城市代码因为进行了交叉而发生了改变,则 其经过该处的两个距离都会改变。这种交叉兼有遗传和变异两方面的作用, 因为若交叉点处的城市编号都相同,则对两个个体而言交叉后样本无变化, 否则样本有变化。6、变异方法为随机两点I ,J的交互位置法。对于A= 1 2 3 4 5 6 7 8 9 10,若匸 3, J=8,则变异后B= 1 2 8 4 5 6 7 3 9 10虽然是简单的随机两点交互,但实际 上已经有40%的距离发生了改变。若用dij表示城市i与j之间的距离,则变 异后与变异前样本路径的距离差为 B23 十 B34 +
10、B78 十 B89 一 A23 十 A34 + A78 + A89 可见,随机两点交互足以产生新的模式样本。较大地提高变异率 就会产生大量的新样本,全局最优样本出现的概率随之提高。为了收敛到最 优解,借鉴模拟退火算法的思想,采取了变异率由很大逐渐衰减到较小的数 量,这样做也利于找到全局最优解。7、将复制,交叉,变异后得到的种群 group1重新赋给group然后重复3, 4, 5, 6 步操作。直至满足循环停止条件,即找到最优路径。仿真实验:TSP实验数据点取为:10城市TSP (自己随机选取10个点):0,0;12,32;5,25;8,45;33,17;25,7;15,15;15,25;25
11、,15;41,1230 城市 TSP 问题(d=423.741 by D.B.Fogel):41,94;37,84;54,67;25,62;7,64;2,99;68,58;71,44;54,62;83,6 9;64,60;18,54;22,60;83,46;91,38;25,38;24,42;58,69;71,71; 74,78;87,76;18,40;13,40;82,7;62,32;58,35;45,21;41,26;44, 35;4,5050 城市 TSP 问题(d=427.855 by D.B.Fogel):31, 32;32, 39;40, 30;37, 69;27, 68;37,
12、52;38, 46;31, 62;30, 48;21, 47;25, 55;16, 57;17, 63;42, 41;17, 33;25, 32;5, 64;8, 52; 12, 42; 7, 38; 5,56, 37; 52, 41; 49, 49;21; 48, 28; 52, 33; 58,21, 10; 30, 15; 36, 16;25; 10, 17; 45, 35;58, 48; 57, 58; 39,27; 61, 33; 62, 63;62, 42; 63, 69; 52,42, 57; 32, 22; 27, 23;10; 46, 10; 59, 15; 51,20, 26
13、; 5, 6; 13, 13;64; 43, 67对与10点TSP问题,城市数比较少,每一代个体数目为 200,进化代数取为1000代,算法执行结果为:最优路径为:95106713428每一代的最小距离收敛图为:每一代种群最短距离的收敛过程175170离距短最群种代一每16516015515014501002003004005006007008009001000遗传代数最后得到的最优路径为:45闭合曲线即为最优路径40353025y20151050 =!0510152025303540x对于30城市TSP问题,每一代个体数目为200,将其遗传代数取为 算法执行结果为:4510000,最优路径为
14、:62 1 202110151839117814192425262728291617222330121345其每一代的最小距离的收敛图为:每一代种群最短距离的收敛过程11001000900离距短最群种代一每700600500X:1e+004Y: 425.34000 1000 2000trr700080009000100003000400050006000遗传代数得到的最优路径为:闭合曲线即为最优路径100LLL19080*70-604 -3-y 50L *r +*40*4+30-20-10-0rtrr r0102030405060708090100x对于50城市TSP问题,每一代的个体数目选取
15、为 200,遗传代数为20000, 则算法执行结果为:离距短最群种代一每最后得到的优化路径为:X: 2e+004丫: 474.1最优路径为:3516131479118513171812101920212242434426244504948403130292823363839472737153433324645252641每一代最小距离收敛图如下:闭合曲线即为最优路径7060厂11L1c-*缶-* *寺卡50r*JL*40J-y/ 士*4-.*30卡nJrsfcr20-卡7二二 g二-*/严10一-01rrrrr010203040506070x在30城市TSP问题中,得到的最终的优化距离为 42
16、5.3,与实际的最小 值423.471相差很少,在50城市TSP问题中,得到的最终优化解为 474.1, 与实际的最优路线的最小距离427.855相差较大。这是由于标准遗传算法的 缺点所确定的,标准遗传算法在前期搜索的效果比较良好,算法后期搜索比 较缓慢,从收敛图中可以验证这一点。在50城市TSP问题中,遗传代数范围内一个优化解的最小距离开始出现之后经过5000代才继续下降寻找更好的解。此外,遗传算法实现的效果很大程度上取决与问题的多种参数,如交 叉率,变异率,每一代的个体数目,如果这些参数设置不好,遗传算法将类 似随机搜索方法,出现“早熟收敛”。在50城市TSP中,如果增加每一代个 体数目、
17、遗传总代数、优化变异率和交叉率,会更靠近最优化解。鉴于标准遗传算法的缺点,现阶段出现了许多遗传算法的改进。在交叉 操作方面,有部分匹配交叉算子、增强边缘重组算子、序号交叉算子、均匀 排序交叉算子、循环交叉算子以及单点交叉算子等。在变异方面还有自适应 变异、多级变异等。此外,一些高级的基因操作如双倍体、显性遗传、倒位 操作、静态繁殖等被应用于遗传算法之中,以改进和优化遗传算法。参考文献:1、王凌,智能优化算法及其应用D,清华大学出版社2、曾宪钊,军事最优化新方法D,军事科学出版社3、蒋腾旭,智能优化算法概述J,人工智能及识别技术4、郑伟、孙文生,遗传算法及其在求解 TSP问题中的应用,中国科技论
18、文 在线5、符一平、陈光喜,一种求解TSP问题的改进遗传算法,桂林电子科技大 学学报6、http:/read.pud n. com/dow nloads76/sourcecode/math/288006/travelsale.doc7、& http:/we 附:MATLAB程序function yichaung_TSP2 clc,close all clear all n=50;city=city_xy(n); city_dis=zeros(n,n); for i=1:n%获取城市坐标信息for j=1:ncity_dis(i,j)=sqrt(city(i,1)-city(j,1).A2+(c
19、ity(i,2)-city(j,2).A2); endend maxdis=max(max(city_dis); N=200;-maxlun=20000;for i=1:Nttemp=randperm(n);for j=1:n group(j,i)=ttemp(j); end end%初始化城市距离%城市间最大距离%每一代种群中的个体数%迭代次数%初始化种群,即随机产生 N种路径,放在n行,N列的矩阵group中for lun=1:maxlun sumadapt=0; maxadapt(1,lun)=0; minadapt(1,lun)=100; viprate=0.1; copyrate=0
20、.02; maxadaptloc=0; mindisiii(1,lun)=100000;for i=1:Ndis(1,i)=0;for j=1:n-1%迭代循环maxlun次%适度值之和%最大适度值初值%最小适度值初值%最优个体复制率9复制率参数%最大适应值对应的个体号码初值%每一代的最忧路径对应的旅行距离总和初值dis(1,i)=dis(1,i)+city_dis(group(j,i),group(j+1,i); end dis(1,i)=dis(1,i)+city_dis(group(1,i),group(n,i); adapt(1,i)=n*maxdis-dis(1,i); sumada
21、pt=sumadapt+adapt(1,i);if dis(1,i)maxadapt(1,lun)maxadapt(1,lun)=adaptnum(1,i); maxadaptloc=i;endif adaptnum(1,i)minadapt(1,lun) minadapt(1,lun)=adaptnum(1,i);endend%. %复制操作tcopyN=0;%复制个数初值num=(maxadapt(1,lun)-copyrate-minadapt(1,lun)*rand(1)+minadapt(1,lun);%生成随机数 vipnum=viprate*N ;for tcopyN=1:vip
22、numfor i=1:ngroup1(i,tcopyN)=group(i,maxadaptloc);endendwhile tcopyNnum&tcopyNN tcopyN=tcopyN+1;for k=1:ngroup1(k,tcopyN)=group(k,i);endendendend%确定最优个体复制个数%先复制vipnum个最优个体至中间矩阵 groupl%再复制其余 N-vipnum 个%由于针对n个城市,故每个个体有n个元素%交叉操作pc=0.5-(0.5-0.4)*(lun-1)/(maxlun-1);pair=pc*N/2;step=2;pairno=0;while pairn
23、opaira=floor(N*rand(1)+1);b=floor(N*rand(1)+1);marri(1,a)=2;%交叉率%最多交叉对数%交叉步长取为 2%当前交叉过的个体数%随机产生两个交叉个体,floor 为向负无穷取整函数%参与交叉的个体标记初值marri(1,b)=3;if marri(1,a)=1&marri(1,b)=1&a=bmarri(1,a)=1;%参与交叉的个体标记为1%用随机数确定个体中单交叉点位置%以下按步长 step 进行交叉%用 for 确定交叉位置marri(1,b)=1;pairno=pairno+1; location=floor(n*rand(1)+1
24、); l1=0;l2=0;for i=location:step:ngroup1(i,a)=group1(j,b)for j=1:n if l1=j;endendfor j=1:nif group1(i,b)=group1(j,a)l2=j;endendtemp=group1(i,a); group1(i,a)=group1(l2,a);group1(l2,a)=temp;temp=group1(i,b); group1(i,b)=group1(l1,b);group1(l1,b)=temp;endendend% %变异操作pb=0.1; bnum=pb*N;for i=1:bnum%逐个取个
25、体,随机选择位置进行变异enda1=floor(n*rand(1)+1);a2=floor(n*rand(1)+1); b=floor(N*rand(1)+1);temp=group1(a1,b);group1(a1,b)=group1(a2,b);group1(a2,b)=temp;end% for i=1:Nfor j=1:ngroup(j,i)=group1(j,i);end变异后的矩阵, group, 准备下次循环endend disp( 最优路径为: );for i=1:nfprintf( %.d ,group(i,1); if rem(i,10)=0 fprintf( n ); end end figure(1); lun=1:1:maxlun;mindis=mindisiii(1,lun); plot(lun,mindis); ti
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 商场电梯故障救援应急预案演练方案
- 小学环保手工艺创作方案
- 新兴游戏类型的内容审查制度
- 智慧消防监控解决方案
- 化工生产燃气蒸汽锅炉施工方案
- 急救中心抗菌药物使用管理制度
- 环境保护科研项目管理制度
- 地下室SBS防水卷材材料选用方案
- 国际美食博览会摊位合作协议书
- 高职院校劳动教育改革方案
- 部编人教版三年级上册语文 交流平台与初试身手 教学设计
- 苹果树绩效管理办法
- 《农村公共管理》
- 动物感觉系统-眼(动物解剖生理课件)
- 系统运维年终总结模板
- 脑梗死静脉溶栓流程优化-课件
- 刑事撤案申请书
- 软件正版化培训课件
- 普通货物运输安全生产管理制度
- 2023年上海市徐汇区中考一模英语试卷(附听力音频)含详解
- 普外科科室医疗质量持续改进记录
评论
0/150
提交评论