资源描述：
《数学实验综合实验》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、标准实用课程名称：数学软件与实验成绩：旅行商问题课程号：50c11033课序号：01任课教师：邢红杰班级：5008信计姓名：郝杰学号：2008477042填写日期:2011-5-24文案大全标准实用旅行商问题5008信息与计算科学郝杰20084770421、实验问题已知30个城市的坐标如下：[4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450]一
2、名推销员要拜访多个地点时，如何找到在拜访每个地点一次后再回到起点的最短路径。2、符号说明Location储存的是个城市的坐标D（i，j）代表城市i和城市j之间的距离Len路径总距离Pc交叉概率Pm变异概率3、问题分析与建模3.1问题分析本题中设定了我国30城市，当一个推销员拜访所有城市后回到起点，31个地点所有路径个数是30文案大全标准实用！个。由于其全局搜索的特性，遗传算法在解决TSP问题中有着其他算法所没有的优势。TSP问题就是寻找一条最短的遍历n个城市的最短路径,或者说搜索子集v={v1,v2,v3,…,vn}(vi的元素表示对n个城市的编号)的一个排列t=(t1,t2,t3
3、,…,ti,…,tn),其中ti∈v(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）返回步骤（2）。3.2程序设计3.2.1坐
4、标系中画出个城市的坐标点矩阵location储存的是个城市的坐标（设：推销员出发点的坐标为（0,0））如下图所示：文案大全标准实用locations=[00;4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450];plot(locations(:,1),locations(:,2),'b*');3.2.2距离矩阵和适应度函数距离矩阵使用一个N×N矩
5、阵D存储，D（i，j）代表城市i和城市j之间的距离。D（i，j）=sqrt(（Xi-Xj）.^2+(Yi-Yj).^2)在该问题的求解中，用距离的总和来衡量适应度，距离的总和越大，适应度越小，进而探讨求解结果是否最优。每个个体（每条路径距离）总合计算公式为：文案大全标准实用len=D(1,N);fori=1:(N-1)len=len+D(i,,i+));endlen纪录总路径格式n×1len(i)代表第i个个体（路径）距离总合。3.2.3选择操作选择的目的是为了从当前群体中选出优良的个体，使他们有机会作为父代产生后代的个体。functionseln=(s,p);inn=size(p
6、,1);fori=1:2r=rand;prand=p-r;j=1;whileprand(j)<0j=j+1;endseln(i)=j;endend文案大全标准实用3.2.4交叉操作群体中的每个个体之间都以一定的概率pc交叉，即两个个体从各自字符串的某一位置（一般是随机确定）开始互相交换，这类似生物进化过程中的基因分裂与重组。例如，假设2个父代个体x1，x2为：x1=0100110x2=1010001从每个个体的第3位开始交叉，交又后得到2个新的子代个体y1，y2分别为：y1＝0100001y2＝1010110这样2个子代个体就分别具有了2个父代个体的某些特征。利用交又我们有可能由父
7、代个体在子代组合成具有更高适合度的个体。functionxoverKids=tsp_crossover_permutation(parents,options,NVARS,...FitnessFcn,thisScore,thisPopulation)nKids=length(parents)/2;xoverKids=cell(nKids,1);index=1;fori=1:nKidsparent=thisPopulation{parents(index)};文案大全标
