《工程结构反分析理论》课程设计.docx
《《工程结构反分析理论》课程设计.docx》由会员分享，可在线阅读，更多相关《《工程结构反分析理论》课程设计.docx（15页珍藏版）》请在冰点文库上搜索。
《工程结构反分析理论》课程设计
《工程结构反分析理论》
课程设计
题目：
旅行商问题的遗传算法解答
专业：
姓名：
指导教师：
学号：
日期：
2015年月日
1旅行商问题概述
1.1旅行商问题简介
旅行商问题（TrvaelingsalesmanPorblem,简称TSP）是威廉·哈密尔顿爵士和英国数学家克克曼（T.P.Kirkman）于19世纪初提出的一个数学问题。
这是一个典型的NP完全性问题。
其简单描述为：
已知n个城市之间的相互距离,现有一旅行商要遍访这n个城市，并且每个城市只能访问一次，最后又必须返回出发的城市。
应如何选择巡回路径，以使其旅行路线的总长度最短。
1.2旅行商问题的研究意义
TSP是最有代表性的优化组合问题之一,它的应用已逐步渗透到交通运输、电路板线路设计以及物流配送等领域。
在大规模生产过程中,寻找最短路径能有效地降低成本,减少交通费用，节约时间，充分利用有限的资源。
这类问题的解决还可以延伸到其他行业中去,如运输业、后勤服务业等。
然而,由于TSP会产生组合爆炸的问题,因此寻找切实可行的简化求解方法就成为问题的关键。
1.3旅行商问题的数学模型
从图论的角度来看，该问题实质是在一个带权完全无向图中，找一个权值最小的Hamilton回路。
假设有一个图G=（V，E），其中V是顶点集，E是边集，设D=（dij）是由顶点i和顶点j之间的距离所组成的矩阵，旅行商问题就是求出一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。
该问题的可行解是所有顶点的全排列，随着顶点数的增加，会产生组合爆炸。
G=（V，E）为一个带权图，V=｛1，2，…,n｝为顶点集，E=｛eij=（i,j）|i,j∈V，i≠j｝为边集。
dij（i,j∈V，i≠j）为顶点i到顶点j的距离，其中dij＞0且dij≠∞，同时dij=dji（i,j∈V）,则经典TSP（ClassicalTSP,CTSP）的数学模型为：
（1）
（2）
（3）
（4）
（5）
其中xij为决策变量，xij=1表示商人行走的路线包括从城市i到城市j的路径，xij=0表示商人没有选择这条路径。
公式
（1）为目标函数，求经过所有顶点的回路的最小距离；公式（3）要求商人从城市i出来只有一次；公式（4）要求商人走入城市i只有一次；公式
（2）-（4）限定回路上每个顶点仅有一条入边和一条出边，即每个城市只经过一次。
|S|为图S的顶点数，K是V的全部非空子集，|K|是集合K中包含图G的全部顶点个数。
公式（5）限定在回路中不出现子回路。
模型实质上是在一个带权图中求一条Hamilton回路。
若对所有i,j,k∈V，不等式
均成立，则称该问题是满足三角不等式的。
1.4旅行商问题的解法
人们在考虑解决这个问题时,一般首先想到的最原始的一种方法就是:
列出每一条可供选择的路线（即对给定的城市进行排列组合）,计算出每条路线的总里程,最后从中选出一条最短的路线"假设现在给定的4个城市分别为A、B、C和D,各城市之间的距离为己知数（如图1所示）。
我们可以通过一个组合的状态空间图来表示所有的组合（如图2所示）。
从图中不难看出,可供选择的路线共有6条,从中很快可以选出一条总距离最短的路线。
由此推算,若设城市数目为n时,那么组合路径数则为（n一1）！
。
很显然，当城市数目不多时要找到最短距离的路线并不难,但随着城市数目的不断增大,组合路线数将呈指数级数规律急剧增长,以至达到无法计算的地步,这就是所谓的“组合爆炸问题”。
多年来对于求解TSP问题出现了很多传统方法，早期的研究者使用精确算法求解该问题，常用的方法包括：
分枝定界法、线性规划法和动态规划法等。
但是，随着问题规模的增大，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有遗传算法、模拟退火算法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络方法等。
图1城市交通图图2组合路径图
旅行商问题中，对于待定的城市目标，至今还没有确定的算法能够得到精确的解。
因此，有效地解决TSP问题具有重要的理论意义。
相比较而言，遗传算法是一种通用性很好的全局搜索算法，具有通用性、智能性、鲁棒性、全局性和并行性的特点，通过选择、交叉、变异算子等操作，实现非线性问题的求解，能够快速求解旅行商问题，求解收敛性强，不易于陷入局部最优。
因此遗传算法是解决旅行商问题的一种不错的算法。
2遗传算法概述
2.1遗传算法简介
遗传算法（GeneticAlgorithm）是一类借鉴生物界的进化规律（适者生存,优胜劣汰遗传机制）演化而来的随机化搜索方法"它是由美国的J.Holland教授1975年首先提出,是模拟生物的遗传进化过程而形成的，是一种基于概率的全局优化搜索算法。
其基本思想是将某种编码技术作用于称为个体的二进制数串，然后模拟由这些串组成的群体的进化过程，对这个群体进行选择操作、交叉操作、变异操作，通过寻求群体进化中的最优个体，得到所求问题的最优解。
2.2遗传算法的特点
与其它的优化算法相比较，遗传算法具有以下特点：
（1）遗传算法以决策变量的编码作为运算对象，直接对结构对象进行操作,不存在求导和函数连续性的限定；
（2）遗传算法直接以目标函数值作为搜索信息，无需导数等其它辅助信息；
（3）遗传算法同时使用多个搜索点的搜索信息，具有隐含并行性和更好的全局寻优能力；
（4）遗传算法使用搜索概率技术，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。
2.3遗传算法的运算过程
遗传算法的运算过程可以表述为：
将问题的可能解编码表示为染色体，随机产生一个染色体群体，然后将群体中的染色体个体放在一定的环境中，按照适者生存的原则，从中选出适应环境较好的个体，进行交叉、变异等操作，产生下一代更加适应环境的个体。
一代一代进化，当满足一定的收敛条件时，进化停止，得到问题的最优解。
遗传算法的运算过程如图3所示：
图3遗传算法的运算流程
3遗传算法求解旅行商问题的研究及MATLAB程序设计
对于需要解决的TSP问题来说,其n个城市之间的距离实质上构成了一个n×n的矩阵，同时遗传算法的诸多算子（如选择、交叉、变异），都是针对所谓染色体进行的，而染色体实质上是一个向量，可将其看成一个1×n的矩阵，因此这些算子实质上是一些矩阵，比用其它高级语言更简单、灵活、快捷。
3.1初始化群体
在初始化群体之前，需要确定变量的编码方法及适应度函数。
在遗传算法界有一个共识：
旅行的二进制表达对TSP不是最适合的。
这里以城市的遍历次序作为算法编码，即（i1,i2,···，in）是｛1,2,···，n｝的全排列。
因为所求的是目标函数最小值的优化问题，因此以哈密顿圈的长度的倒数作为适应度函数，同时需要对种群大小、最大迭代次数、交叉概率、变异概率等变量赋值，随机生成种群大小M。
染色体长度（城市数目）为num的MATLAB程序为：
%生成初始群体
popm=zeros（M,num）;
fori=1:
M
popm（I,:
）=randperm（num）;%随机产生一个由自然数1到num组成的全排列
end
3.2个体适应度计算
计算个体的适应度,即与种群中某一个个体r相对应的哈密顿圈长的倒数。
functionlem=value（r,dmatrix,num）%dmatrix表示任意两个城市之间的距离构成的距离矩阵
minopt=0;%哈密顿圈长
fori=1:
num-1%按照遍历次序求哈密顿圈长
minopt=minopt+dmatrix（r（i）,r（i+1））;
end
minopt=minopt+dmatrix（r
（1）,r（num））;
lem=1/minopt
3.3比例选择操作
具体执行过程为：
（1）计算种群中所有个体的适应度总和；
（2）计算每个个体的相对适应度大小，即各个个体在选择操作中被选中的概率；
（3）使用模拟赌盘操作，来确定各个个体被选中的次数，得到中间群体。
%计算种群中所有个体的适应度总和
lengthall=0;
fori=1:
M
r=popm（i,:
）;
lengthone=value（r,dmatrix,num）;%调用上面的value函数
lenthall=lengthone+lengthall
end
%确定各个个体的相对适应度大小
Gailu=rands（1,M）;%生成1×n的随机矩阵.用于存储各个个体的相对适应度
fori=1:
M
r=popm（i,:
）;
gailu（1,i）=value（r,dmatrix,num）/lengthall;
end
%确定被选择的群体
father=ones（M,num）;%生成一个矩阵，用于存储被选择的群体
i=1;
whilei<=M
jc=rand;
j=1;
forj=1:
M
ifjc<=gailu（1,j）;%按照随机生成的数.来确定被选择的个体
father（i,:
）=popm（j,:
）;%生成中间群体
i=i+1;
j=M+1;
end
end
end
3.4交叉操作
对选择操作得到的中间群体进行以下操作：
（1）以交叉概率pc从中间群体中随机地选出需要进行交叉的个体，对这些个体随机地两两配对；
（2）在1-（num-1）之间产生两个随机数k,l,这两个数表示交叉点的位置；
（3）对已经配对的两个个体，相互对应地交换第k到l位的数字。
%进行交叉操作
son=father;%用son矩阵表示交叉之后的群体.对其初始化为选择后群体
fori=1:
M*pc*0.5
a=floor（rand*M）+1;
b=floor（rand*M）+1;
father1=father（a,:
）;
father2=father（b,:
）;
k=floor（num*rand）+1;
l=floor（num*rand）+1;
minshu=min（k,l）;
maxshu=max（k,l）;
select1=father1（minshu:
maxshu）;
select2=father2（minshu:
maxshu）;
father12=delet（father1,select2）;
father21=delet（fahter2,select1）;%其中delet是自定义函数
son（a,:
）=[select2,father12];%将两矩阵拼接
son（b,:
）=[select1,father21];
end
%自定义函数delet（x,y）
functionz=delet（x,y）
forn=1:
length（y）
x=（:
find（x==y（n）））=[];%功能为将x中与y相同的元素删除
end
z=x
3.5变异操作
此操作作用于交叉操作之后的群体，其操作方法为：
首先在1-num之间产生两个随机数g和h,这两个数表示变异点的位置；最后再以变异概率随机地从群体中选出的个体上，将g,h两位置上的数互换。
%g,h是两个变异点的位置
fori=1:
M*pm
c=floor（rand*M）+1;
g=floor（rand*num）+1;
h=floor（rand*num）+1;
zhjian=son（c,g）;
son（c,g）=son（c,h）;
son（c,h）=zhjian;
end
4.结果评价
为检验该算法的实际应用效果，文中以16,22,24,48,70,101个城市为例,将该算法得到的结果与用弹性网络算法得到的结果进行了比较,如表1所示。
为了更好地说明遗传算法在求解TSP问题中良好的全局搜索能力，文中以求解101个城市为例进行运算。
通过运算可以发现，随着迭代次数的增加，最佳个体的适应度函数值逐步增加，最后收敛于一个相对稳定值。
用遗传算法求解得到的101个城市的遍历图，如图4所示。
从表1和图6中可以看出，遗传算法有较好的全局最优解的求解能力。
在算法实施过程中，M,T,pc,pm等参数值的设定对于问题能否找到满意解起着非常重要的作用。
如果M,T值太小,则不容易找到最优解；反之，则计算时间长。
对于交叉概率pc来说，如果取值过大，则会破坏以前遗传的结果，因而pc不能取得太大。
对于突变概率pm,其目的是为了保证算法对解空间的覆盖,但pm太大会破坏遗传和交叉选出的染色体而变成随机搜索；反之，染色体种群又会过于单调，从而陷入局部极值。
因此，在实际计算时，要根据具体问题来选择合适的参数。
图4101个城市的遍历图
表1遗传算法与弹性网络算法计算结果比较
城市数
16
22
24
48
70
101
最优解
2.126
2.171
4.399
3.892
6.169
7.811
遗传算法
2.127
2.178
4.400
4.044
6.253
7.887
弹性网络
2.154
2.222
5.047
4.135
6.557
8.253
5.结语
本文利用遗传算法的全局寻优和收敛速度快的特点，设计了一种用于旅行商问题的算法。
很多实际应用问题，如印制电路板的钻孔路线方案、连锁店的货物配送路线等经过简化处理后，均可建模为旅行商问题，因此用遗传算法解决旅行商问题有极大的应用价值。
研究旅行商问题的遗传算法对促进遗传算法本身的发展也有重要意义。
但是要使遗传算法的误差精度和收敛速度进一步得到改进，还需要做出进一步的研究。
附Matlab程序代码
%生成初始群体
popm=zeros（M,num）;
fori=1:
M
popm（I,:
）=randperm（num）;%随机产生一个由自然数1到num组成的全排列
end
functionlem=value（r,dmatrix,num）%dmatrix表示任意两个城市之间的距离构成的距离矩阵
minopt=0;%哈密顿圈长
fori=1:
num-1%按照遍历次序求哈密顿圈长
minopt=minopt+dmatrix（r（i）,r（i+1））;
end
minopt=minopt+dmatrix（r
（1）,r（num））;
lem=1/minopt
%计算种群中所有个体的适应度总和
lengthall=0;
fori=1:
M
r=popm（i,:
）;
lengthone=value（r,dmatrix,num）;%调用上面的value函数
lenthall=lengthone+lengthall
end
%确定各个个体的相对适应度大小
Gailu=rands（1,M）;%生成1×n的随机矩阵.用于存储各个个体的相对适应度
fori=1:
M
r=popm（i,:
）;
gailu（1,i）=value（r,dmatrix,num）/lengthall;
end
%确定被选择的群体
father=ones（M,num）;%生成一个矩阵，用于存储被选择的群体
i=1;
whilei<=M
jc=rand;
j=1;
forj=1:
M
ifjc<=gailu（1,j）;%按照随机生成的数.来确定被选择的个体
father（i,:
）=popm（j,:
）;%生成中间群体
i=i+1;
j=M+1;
end
end
end
%进行交叉操作
son=father;%用son矩阵表示交叉之后的群体,对其初始化为选择后群体
fori=1:
M*pc*0.5
a=floor（rand*M）+1;
b=floor（rand*M）+1;
father1=father（a,:
）;
father2=father（b,:
）;
k=floor（num*rand）+1;
l=floor（num*rand）+1;
minshu=min（k,l）;
maxshu=max（k,l）;
select1=father1（minshu:
maxshu）;
select2=father2（minshu:
maxshu）;
father12=delet（father1,select2）;
father21=delet（fahter2,select1）;%其中delet是自定义函数
son（a,:
）=[select2,father12];%将两矩阵拼接
son（b,:
）=[select1,father21];
end
%自定义函数delet（x,y）
functionz=delet（x,y）
forn=1:
length（y）
x=（:
find（x==y（n）））=[];%功能为将x中与y相同的元素删除
end
z=x
%g,h是两个变异点的位置
fori=1:
M*pm
c=floor（rand*M）+1;
g=floor（rand*num）+1;
h=floor（rand*num）+1;
zhjian=son（c,g）;
son（c,g）=son（c,h）;
son（c,h）=zhjian;
end
升级会员 