数学实验综合实验.docx

《数学实验综合实验.docx》由会员分享，可在线阅读，更多相关《数学实验综合实验.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河 北 大 学 工 商 学 院第1页旅行商问题旅行商问题5008 信息与计算科学 郝杰20084770421、实验问题、实验问题已知 30 个城市的坐标如下：41 94；37 84;54 67；25 62；764；2 99;68 58；71 44;54 62;8369；64 60；18 54;22 60；83 46;91 38；25 38;24 42；58 69；71 71;7478；87 76;18 40;13 40；82 7；62 32;58 35；45 21；41 26;44 35;450一名推销员要拜访多个地点时,如何找到在拜访每个地点一次后再回到起点的最短路径。2、符号说明、符号说明

2、Location储存的是个城市的坐标D(i,j）代表城市i 和城市 j 之间的距离Len路径总距离Pc交叉概率Pm变异概率3、问题分析与建模、问题分析与建模3.1问题分析问题分析本题中设定了我国 30 城市，当一个推销员拜访所有城市后回到河 北 大 学 工 商 学 院第2页起点，31 个地点所有路径个数是 30！个。由于其全局搜索的特性，遗传算法在解决 TSP 问题中有着其他算法所没有的优势。TSP 问题就是寻找一条最短的遍历 n 个城市的最短路径，或者说搜索子集 v=v1,v2，v3，,vn（vi 的元素表示对 n 个城市的编号)的一个排列 t=（t1,t2，t3,，ti,，tn)，其中 t

3、iv（i=1，2，3，,n),且记 tn+1=t1，使 len=d（Vi，Vi+1）+d（V1,Vn)取最小值，式中的 d（Vi，Vi+1)表示城市 Vi 到城市 Vi+1 的距离.标准的遗传算法包括群体的初始化,选择,交叉，变异操作。其主要步骤可描述如下1：（1）随机产生一组初始个体构成的初始种群，并评价每一个个体的适配值.（2）判断算法的收敛准则是否满足。若满足输出搜索结果；否则执行以下步骤。（3）根据适配值大小以一定方式执行选择操作。（4)按交叉概率Pc执行交叉操作。（5）按变异概率Pm执行变异操作.（6 6）返回步骤(2).3 3。2 2 程序设计程序设计3。2。1 坐标系中画出个城市

4、的坐标点坐标系中画出个城市的坐标点矩阵 location 储存的是个城市的坐标（设：推销员出发点的坐河 北 大 学 工 商 学 院第3页标为（0，0）如下图所示：10090807060504030201000102030405060708090100locations=0 0;41 94;37 84；54 67;25 62;7 64;2 99;6858;71 44；54 62；83 69;64 60；18 54;22 60;83 46；9138；2538;24 42;58 69；7171;74 78;87 76；1840;13 40;827；62 32;58 35;45 21;41 26;44

5、 35;4 50；plot(locations（：,1),locations(：,2）,b)；3.2。2 距离矩阵和适应度函数距离矩阵和适应度函数距离矩阵使用一个 NN 矩阵 D 存储,D（i,j）代表城市i 和城市 j 之间的距离。D（i，j）=sqrt(（Xi-Xj).2+（YiYj)。2)在该问题的求解中，用距离的总和来衡量适应度，距离的总和越大，适河 北 大 学 工 商 学 院第4页应度越小，进而探讨求解结果是否最优。每个个体（每条路径距离）总合计算公式为：len=D（1，N)；for i=1：(N-1)len=len+D（i，i+）；endlen 纪录总路径格式 n1 len(i）代

6、表第 i 个个体（路径)距离总合.3。2.3 选择操作选择操作选择的目的是为了从当前群体中选出优良的个体，使他们有机会作为父代产生后代的个体。functionseln=(s，p)；inn=size（p,1)；fori=1:2r=rand；prand=pr；j=1;whileprand（j)0j=j+1；endseln（i)=j;end河 北 大 学 工 商 学 院第5页end3.2。4 交叉操作交叉操作群体中的每个个体之间都以一定的概率pc 交叉，即两个个体从各自字符串的某一位置（一般是随机确定）开始互相交换,这类似生物进化过程中的基因分裂与重组。例如,假设 2 个父代个体 x1，x2 为：x

7、1=0100110 x2=1010001从每个个体的第 3 位开始交叉,交又后得到 2 个新的子代个体 y1，y2 分别为:y1 0100001y2 1010110这样 2 个子代个体就分别具有了 2 个父代个体的某些特征。利用交又我们有可能由父代个体在子代组合成具有更高适合度的个体。functionxoverKids=tsp_crossover_permutation(parents，options,NVARS,.。FitnessFcn，thisScore，thisPopulation）nKids=length（parents）/2;xoverKids=cell(nKids，1);index

8、=1；河 北 大 学 工 商 学 院第6页fori=1:nKidsparent=thisPopulationparents(index）;index=index+2;p1=ceil（(length（parent）-1)*rand）；p2=p1+ceil(length(parent）p1-1）rand);child=parent；child（p1:p2）=fliplr(child（p1：p2）);xoverKidsi=child；end3.2.5 变异操作变异操作基因的突变普遍存在于生物的进化过程中。变异是指父代中的每个个体的每一位都以概率 pm 翻转，即由“1”变为“0”，或由“0”变为“1”

9、。遗传算法的变异特性可以使求解过程随机地搜索到解可能存在的整个空间，因此可以在一定程度上求得全局最优解。functionmutationChildren=mutate_permutation(parents,options，NVARS,。.FitnessFcn,state，thisScore,thisPopulation,mutationRate）mutationChildren=cell（length(parents）,1）;fori=1:length(parents）河 北 大 学 工 商 学 院第7页10090807060504030201000102030405060708090100

10、parent=thisPopulationparents(i);p=ceil(length(parent）*rand（1，2)；child=parent；child(p(1）=parent（p（2)）；child(p(2）)=parent（p（1）);mutationChildreni=child；End4、MATLB 求解求解迭代后的最优路径如下图所示河 北 大 学 工 商 学 院由上图可知推销员所走的最短路径 fval=504。78885、总结体会、总结体会TSP 问题还有很多其他算法，比如说最临近算法、模拟退火、粒子群算法、最小权匹配算法等等论文用遗传算法对 TSP 问题进行了求解，熟悉

11、遗传算法地算法流程,证明了遗传算法在求解 TSP 问题时,具有可行性，MATLAB 在进行算法优化编程时具有一定的优势。遗传算法在设计过程中要照顾好两个原则子代要具有父代优良的基因信息即继承性子代要保持群体的多样性，即变异。虽然这两个第8页河 北 大 学 工 商 学 院原则在设计过程中经常会出现冲突,我们必须统筹的把握。遗传算法是一种高效率的，适用面较广的最优问题解决方法。一般遗传算法解决旅行商问题的效率不高.在做实验的这段时间里,自己更加深入的了解到遗传算法的合理性和有效性。同时,我也更加熟练的掌握了 matlab 应用软件的用法和各种命令的使用方法，也发现了 matlab 软件的功能很实用。第9页