遗传算法毕业论文.doc
- 文档编号:4732065
- 上传时间:2023-05-07
- 格式:DOC
- 页数:32
- 大小:502KB
遗传算法毕业论文.doc
《遗传算法毕业论文.doc》由会员分享,可在线阅读,更多相关《遗传算法毕业论文.doc(32页珍藏版)》请在冰点文库上搜索。
目录
1引言 1
2问题描述 2
3基于遗传算法TSP算法 2
3.1基于遗传算法的TSP算法总体框架 2
3.2 算法的详细设计 3
3.2.1解空间的表示方式 3
3.2.2种群初始化 4
3.2.3 适应度函数 4
3.2.4 选择操作 4
3.2.5 交叉操作 5
3.2.6 变异操作 6
3.2.7进化逆转操作 6
3.3实验结果分析 7
4基于模拟退火算法的TSP算法 10
4.1SA算法的实现过程 10
4.2算法流程图 10
4.3模拟退火算法的实现过程 10
4.4实验结果 11
5对两种算法的评价 14
5.1遗传算法优缺点 14
5.2模拟退火算法的优缺点 15
6结语 15
参考文献 17
附录:
19
廊坊师范学院本科生毕业论文
论文题目:
基于遗传算法与模拟退火算法的TSP算法求解10大城市最短旅途
论文摘要:
TSP问题为组合优化中的经典的NP完全问题.本论文以某旅行社为中国十大旅游城市--珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海制定最短旅途为例,分别利用基于遗传算法的TSP算法与基于模拟退火算法的TSP算法求解10大城市旅游路线问题.本论文给出了遗传算法与模拟退火算法中各算子的实现方法,并展示出求解系统的结构和求解系统基于MATLAB的实现机制.利用MATLAB软件编程,运行出结果,并对基于遗传算法的TSP算法结果与基于模拟退火算法的TSP算法的结果进行比较,描述其优缺点,并选择最为恰当的TSP算法,实现最短旅途的最优解.
关键词:
遗传算法;模拟退火算法;TSP;最短路径;
Title:
TSPAlgorithmBasedonGeneticAlgorithmorSimulatedAnnealingAlgorithmforSolvingtheShortestJourneyof10Cities
Abstract:
TSPproblemisaclassicNPproblemaboutcombinatorialoptimization.ThisarticletakesatravelagencylookingfortheshortesttripoftentouristcitiesinChina-Zhuhai,Xi'an,Hangzhou,Lhasa,Beijing,Lijiang,Kunming,Chengdu,LuoyangandWeihaiforinstance,andsolvesthisproblembyTSPalgorithmbasedongeneticalgorithmandsimulatedannealingalgorithm.ThearticlegivestheimplementationsofeveryoperatorofgeneticalgorithmandsimulatedannealingalgorithmanddemonstratesthearchitectureandtheimplementationmechanismofthesolvingsystembasedonMATLAB.IprogramandoperatetheresultsbyMATLABsoftware,andcomparetheresultsbasedongeneticalgorithmandsimulatedannealingalgorithm.AnddescribetheiradvantagesanddisadvantagessothatchoosethemostappropriateTSPalgorithmtoachievetheoptimalsolutionfortheshortestpath.
Keywords:
geneticalgorithm;simulatedannealingalgorithm;TSP;theshortestpath
1引言
TSP问题为组合优化中的经典问题,已经证明为一NP完全问题,即其最坏情况下的时间复杂性随着问题规模的扩大,按指数方式增长,到目前为止不能找到一个多项式时间的有效算法.TSP问题可描述为:
已知n个城市相互之间的距离,某一旅行商从某个城市出发访问每个城市一次且仅一次,最后回到出发城市,如何安排才使其所走路线最短.TSP问题不仅仅是一个简单的组合优化问题,其他许多的NP完全问题可以归结为TSP问题,如邮路问题、装配线上的螺帽问题和产品的生产安排问题等,使得TSP问题的有效求解具有重要的意义.本文中的TSP算法主要采用遗传算法与模拟退火算法.
遗传算法是一种进化算法,其基本原理是仿效生物界中的“物竞天择,适者生存”的演化法则.遗传算法把问题参数编码为染色体,再按照所选择的适应度函数,利用迭代的方式进行选择、交叉、变异以及进化逆转等运算对个体进行筛选和进化,使适应值大的个体被保留,适应值小的个体被淘汰,新的群体继承了上一代的信息,又优于上一代,这样反复循环,直至满足条件,最后留下来的个体集中分布在最优解的周围,筛选出最优个体作为问题的解.
模拟退火算法的出发点是基于物理中固体物质的退火过程与一般的组合优化问题之间的相似性,该算法是一种优化算法,其物理退火过程由三部分组成,分别为:
加温过程、等温过程、冷却过程.其中,加温过程对应算法设定初温,等温过程对应算法的Metropolis抽样过程,冷却过程对应控制参数的下降.这里能量的变化就是目标函数,要得到的最优解就是能量最低态.Metropolis准则是SA算法收敛于全局最优解的关键所在,Metropolis准则以一定的概率接受恶化解,这样就使算法跳离局部最优的陷阱.
2问题描述
本案例为某旅行社为中国十大旅游城市,分别为珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海,根据全程路径最短为目的,制定最优的旅游顺序依次游玩这十个城市.这类问题就由TSP算法来解决,寻找出一条最短遍历这10个城市的路径.利用google地图找到城市坐标,下表为这十个城市的位置坐标如表2-1所示.
表2-110个城市的位置坐标
城市编号
X坐标
Y坐标
城市编号
X坐标
Y坐标
1
22.31
113.58
6
26.86
100.23
2
34.37
108.95
7
24.89
102.83
3
30.29
120.16
8
30.59
104.07
4
29.66
91.14
9
34.65
112.46
5
39.95
116.41
10
37.53
122.13
3基于遗传算法TSP算法
3.1基于遗传算法的TSP算法总体框架
TSP问题的遗传算法包括编码设计、种群初始化、适应度函数选择、终止条件设定、选择操作设定、交叉操作设定以及变异操作设定和进化逆转操作.为简化TSP问题的求解,假设每个城市和其它任意一个城市之间都以欧氏距离直接相连.遗传算法TSP问题的流程图如图2-1所示.
N
初始种群
实际问题参数集
计算适应度
编码
选择适应度高的染色体
交叉
变异
新种群
进化逆转
代数满足终止条件
Y
解决实际问题
解码
图2-1算法流程框架图
3.2 算法的详细设计
3.2.1解空间的表示方式
遗传算法对解空间的表示大多采用二进制编码形式,但是二进制编码方式不适合TSP问题的解的表示,因为它要求特殊的修补算子来修复变化算子所产生的非法路径(即不可行路径).给出城市编号,用十进制数编码来表示解更合适,例如:
近邻表示、次序表示和路径表示等等.这里采用了最简单的路径表示法.它是最自然、最接近人类思维的表示法.因此对十大旅游城市按照珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海顺序依次编号为1,2,3,4,5,6,7,8,9,10,例如,下面的路径(闭合的):
5→1→2→4→3→6→7→9→8→10→5
表示从城市5出发,经过1,2,4,3,6,7,9,8,10最后回到城市5的一条路径,可以自然地用一维数组来表示:
(5,1,2,4,3,6,7,9,8,10)
10个旅游城市的TSP问题,如果将种群规模设为200,则解空间就用二维数组来表示:
Path[200][10].
3.2.2种群初始化
种群的规模选择应适当,盲目的增大种群规模不能使算法得到改进,反而大大增加了计算的开销.10个城市TSP问题,可以选择小规模的种群(例如200),种群初始化时,先产生1,2,…,10的一条规则路径,然后在这条路径中随机选两个数,将它们交换位置,这样做若干次(本文采用200次),保证这条路径变成了一条随机的路径.以这条随机路径为基础,对一些随机的位,做两两交换,这样产生了一个个体;同样地产生种群里其它的个体.
3.2.3 适应度函数
适应度表明个体或解的优劣性,不同的问题,适应度函数的定义方式也不同,本文设为一个采用整数编码的染色体,为城市到城市的欧氏距离,则该个体的适应度为:
(1)
即适应度函数为恰好走遍10个城市,在回到出发城市的总距离的倒数.优化的目标就是选择适应度函数值尽可能大的染色体,适应度函数值越大的染色体越优质,反之越劣质.求得种群中所有个体的适应值后,将适应值最大的个体保存起来,到演化完毕时,这个个体就是最后要求的最优解.
3.2.4 选择操作
选择操作的目的是为了从当前群体中以一定的概率选择优良个体到新群体中,将选择算子作用于群体,从而使优化的个体有机会直接遗传到下一代或通过配对交叉产生新的个体再遗传到下一代;个体被选中的概率与适应度值有关,适应度值越大,被选中的概率也就越大,而适应度值越大的染色体越优质.本案例选择轮盘赌法,即基于适应度比例的选择策略,个体被选中的概率为:
(2)
其中,为个体的适应度值;N为种群个体数目.
3.2.5 交叉操作
交叉操作是遗传算法中最主要的遗传操作,通过交叉操作可以得到新一代个体,新个体结合了其父辈个体的特性,交叉体现了信息交换的思想.利用不同映射杂交,确定交叉操作的父代,将父代样本两两分组,每组重复以下过程:
(1)产生两个[1,10]区间的随机整数和,确定两个位置,对两个位置的中间数据进行交叉,如,
51243679810
10623589417
交叉为:
*123589**10
10*24367*1*
(2)交叉后,对同一个个体中有重复的城市编号,不重复的数字保留,有冲突的数字(带*的位置)采用部分映射的方法消除冲突,即利用中间段的对应关系进行映射.结果为:
41235896710
10524367819
交叉是希望不同的个体在产生下一代时,能够结合各自的优势基因,产生更好质量的下一代.
3.2.6 变异操作
变异可以看作是外界对种群的影响.变异是为了引入新的因素,希望个体在外界的作用下,能够实现自我优化,生好的基因.将变异算子作用于群体.即是对群体中的个体串的某些基因位置上的基因值作变动.变异算子采用了简单的倒序变换,以10城市为例,随机的产生两个小于10的整数,对某个个体进行分割,假设,,将分割段倒序并放回原来的位置即可,如下数组所示:
51243679810
得到的新解为:
51273649810
由于这种变异算子仍能保持个体中的路径片段,即倒序前后这个切割段的路径是一样的,只是两端点与整个路径的连接颠倒了,这使得变异不是漫无边际,而是有所取舍的.这种简单反序可以保证后代仍然是一条合法途径.
3.2.7进化逆转操作
为了改善遗传算法的局部搜索能力,在选择、交叉、变异之后引进连续多次的进化逆转操作,这里的“进化”是指逆转算子的单方向性,即只有经逆转后,适应度值有所提高的才接受下来,否则逆转无效.
产生两个[1,10]区间内的随机整数和,确定两个位置,将其对换位置,例如,
51243679810
进化逆转后为:
51273649810
对每个个体进行交叉变异,然后代入适应度函数进行评估,x选择出适应值大的个体进行下一代交叉和变异以及进化逆转操作循环操作:
判断是否满足设定的最大遗传代数MAXGEN,不满足则跳入适应度值计算;否则结束遗传操作.
3.3实验结果分析
1-10的十个数字按顺序为珠海、西安、杭州、拉萨、北京、丽江、昆明、成都、洛阳、威海的编号.利用各城市坐标构成的的矩阵及初始化随机值和DrawPath函数画出闭合路径图,为优化前的随机路线轨迹图,如图3-1所示:
图3-1随机路线轨迹图
图中三角标注的数字6代表起点,依次按照箭头方向遍历,最终再次回到起点6.
初始种群中的一个随机值:
6—>3—>7—>8—>5—>1—>2—>4—>9—>10—>6
总距离:
165.2494
对照1-10数字编号所代表的的城市,随机路线为:
丽江—>杭州—>昆明—>成都—>北京—>珠海—>西安—>拉萨—>洛阳—>威海—>丽江.
优化后的最优路线图如图3-2所示:
图3-2最优路线图
最优解:
4—>6—>7—>1—>3—>10—>5—>9—>2—>8—>4
总距离:
77.1532
即最优路线如下所示:
拉萨—>丽江—>昆明—>珠海—>杭州—>威海—>北京—>洛阳—>西安—>成都—>拉萨
此遗传算法在解决TSP问题过程中的优化迭代过程如下图3-3所示:
图3-3优化过程
其中横坐标表示迭代次数,纵坐标为优化过程中路线长度.由该优化过程图可知,优化前后路径长度有了很大的改进,20代以后路径长度基本上已经保持不变了,可以认为是最优解了.总距离由原来的165.2494变为77.1532,降低为原来的46.69%,表明利用遗传算法解决TSP问题可以起到较好的作用.
4基于模拟退火算法的TSP算法
4.1SA算法的实现过程
4.2算法流程图
N N
count=0
k=1
解变换得新解s2
设置控制参数
初始解
新的,k=k+1
M准则判断是否接受新解
count=count+1,T=qT
k>L?
Y
?
输出当前解
结束
Y
图4-1模拟退火算法求解流程框图
4.3模拟退火算法的实现过程
(1)控制参数的设置
需要设置的主要控制参数有降温速率、取初始温度足够大,令=,任取初始解,确定每个时的迭代次数,即Metropolis链长L,如图表4-1所示.
表4-1参数设定
降温速率
初始温度
结束温度
链长
0.9
1000
0.001
500
(2)初始解
对于10个城市的TSP问题,得到的解为一个排序,其中每个数字为对应城市的编号,10个城市的TSP问题{1,2,3,4,5,6,7,8,9,10},则|1|2|3|4|5|6|7|8|9|10就为一个合法解,采用随机排列的方法产生一个初始解.
(3)解变换生成新解
通过对当前解进行变换,产生新路径的数组即新解,这里采用的变换是产生随机数的方法来产生将要交换的两个城市,用二邻域变换法产生新的路径,即新的可行解.例如n=10时,产生两个[1,10]范围内的随机整数和确定两个位置,将其对换位置,如=4,=7
51243679810
得到的新解为:
51273649810
(4)Metropolis准则
若路径长度函数为,则当前解的路径为,新解的路径为,路径差为=-,则Metropolis准则为:
(3)
若,则接受作为新的当前解,即;否则计算的接受概率,即随机产生的(0,1)区间上均匀分布的随机数rand,若,也接受作为新的当前解,;否则保留当前解.
(5)降温
利用降温速率q进行降温,即T=qT,则T小于结束温度,则停止迭代输出当前解为最优解,结束程序,否则按衰减函数衰减后逐渐降低控制温度,重复Metropolis过程,继续迭代,直至满足结束准则,求出最优解.
4.4实验结果
利用各城市坐标构成的的矩阵及初始化随机值和DrawPath函数分别画出优化前的随机路径轨迹图与优化后的最优闭合路径图,以及优化过程图.并利用计时器记录了运行结果所花费的时间.
为优化前的随机路线轨迹图,如图4-2所示.
图4-2随机路线轨迹图
初始种群中的一个随机值:
8—>1—>7—>4—>3—>6—>10—>2—>9—>5—>8
总距离:
149.0742
优化后的最优路线轨迹图如图4-3所示.
图4-3最优路线轨迹图
最优解:
9—>2—>8—>4—>6—>7—>1—>3—>10—>5—>9
总距离:
77.1532
即最优路线如下所示:
洛阳—>西安—>成都—>拉萨—>丽江—>昆明—>珠海—>杭州—>威海—>北京—>洛阳
本次运行的时间如下所示:
Elapsedtimeis12.232553seconds.
优化过程如图4-4所示:
图4-4优化过程
由图4-4可以看出,优化前后的路径长度得到很大的改进,由优化前的149.0742变为77.1532,变为原来的51.75%,50代以后路径长度基本上已经保持不变了,可以认为是最优解了.
5对两种算法的评价
5.1遗传算法优缺点
遗传算法优点:
(1)对可行解表示的广泛性;
(2)群体搜索特性;
(3)不需要辅助信息;
(4)内在启发式随机搜索特性;
(5)遗传算法在搜索过程中不容易陷入局部最优,即使在所定义的适应度函数是不连续的,非规则的或有噪音的情况下,也能以很大的概率找到全局最优解;
(6)遗传算法具有固有的并行性和并行计算能力;
(7)遗传算法具有可扩展性,易于同别的技术混合.
遗传算法缺点:
(1)编码不规则或编码存在表示的不规则性;
(2)单一的遗传算法编码不能全面的将优化问题的约束表示出来;
(3)遗传算法通常的效率比比其他传统的优化方法低;
(4)遗传算法容易出现过早收敛;
(5)遗传算法对算法的精度,可信度,计算复杂性等方面,还没有有效的定量分析方法.
5.2模拟退火算法的优缺点
模拟退火法优点:
(1)它能够处理具有任意程度的非线性、不连续性、随机性的目标函数;
(2)目标函数可以具有任意的边界条件和约束;
(3)比其他线性优化方法,SA的编程工作量小,且易于实现;
(4)统计上可以保证找到全局最优解.
模拟退火算法缺点:
(1)找到最优解需要耗费非常多的时间;
(2)相对于其他一些技术对某一个具体问题的求解需要更困难的参数调整;
(3)使用不当致使降温过快,导致模拟退火变为了模拟淬火(SQ),而SQ是无法从统计学上保证找到最优解的.
6结语
遗传算法利用自然界的“物竞天择、适者生存”的演化法则,把问题参数编码为染色体,再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息,最终生成符合优化目标的染色体.实践证明,遗传算法在搜索优秀解的过程中模拟生物遗传,实现优中选优的过程,在解空间中快速收敛到优秀解.遗传算法对于解决TSP问题等组合优化问题具有较好的寻优性能.模拟退火算法是利用自适应启发式概率性搜索的算法,可以用以求解不同的非线性问题,对不可微甚至不连续的函数优化,能以较大的概率求得全局最优解,并且能处理不同类型的优化设计变量(离散的,连续的,混合型的),不需要任何的辅助信息,对目标函数和约束函数没有任何要求.利用Metropolis算法适当地控制温度的下降过程,在优化问题中具有很强的竞争力,但是其优化过程效率略低于遗传算法.因此,解空间较小的情况下,遗传算法与模拟退火算法均可采用,但是解空间较大时,考虑结果运行时间,应采用遗传算法.
参考文献
[1]毕晓君.信息智能处理技术[M].北京:
电子工业出版社.2010.
[2]储理才.基于MATLAB的遗传算法程序设计及TSP问题求解[J].集美大学学报:
2001,6(01):
14-19
[3]代桂平,王勇,侯亚荣.基于遗传算法的TSP问题求解算法及其系统[J].微计算机信息,2010(04):
15-16,19
[4]Negnevistsky,M.顾力栩,沈晋惠译.人工智能——智能系统指南[M].北京:
机械工业出版社.2010.
[5]任春玉.基于混合遗传算法的TSP问题优化研究[J].哈尔滨商业大学学报.2007.
[6]MichalewiczZ.GeneticAlgorithms+DataStructure=EvolutionPrograms.Springer-Verlag,Berlin.2011
[7]易敬,王平,李哲.基于遗传算法的TSP问题研究[J].信息技术,2006,30(7):
110-112.
[8]邓辉文.离散数学[M].北京:
清华大学出版社.2006.
[9]刘雁兵,刘付显.基于遗传算法的TSP问题求解与仿真[J].电光与控制.2007.
[10]张春霞,王蕊.基于遗传算法求解TSP问题的算法设计[J].安阳工学院学报.2007.
[11]郑阿奇.MATLAB实用教程[M].北京:
电子工业出版社.2004.
[12]李飞,白艳萍.用遗传算法求解旅行商问题[J].中北大学学报.2007.
[13]翟梅梅.基于交叉算子改进的遗传算法求解TSP问题[J].淮南师范学院学报.2009.
[14]MerzP.Acomparisonofrecombinationoperatorsforthetravelingsalesmanproblem[A].ProceedingsoftheGeneticandEvolutionaryConference.2007
[15]周涛.基于改进遗传算法的TSP问题研究[J].微电子学与计算机,2006,23(10):
104-107.
[16]JungS,MoonBR.TowardMinimalRestrictionofGeneticEn-codingandCrossoversfortheTwo-DimensionalEuclideanTSP[J].IEEETransactionsonEvolutionaryComputation,2011,6(12):
557~565
[17]TsaiCheng-Fa
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 毕业论文