1 / 23
文档名称:

遗传算法在最优化问题中的应用.docx

格式:docx   大小:135KB   页数:23页
下载后只包含 1 个 DOCX 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

遗传算法在最优化问题中的应用.docx

上传人:niupai11 9/28/2022 文件大小:135 KB

下载得到文件列表

遗传算法在最优化问题中的应用.docx

相关文档

文档介绍

文档介绍:该【遗传算法在最优化问题中的应用 】是由【niupai11】上传分享,文档一共【23】页,该文档可以免费在线阅读,需要了解更多关于【遗传算法在最优化问题中的应用 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。遗传算法在最优化问题中的应用
摘要:自改革开放以来,经济持续高速增长,人民生活水平和社会发展水平大幅度提高,旅游业也随之兴盛起来,越来越多的人选择旅游放松精神增长见识。本文通过分析景点坐标与最短路径的关系,利用遗传算法求解最短路径,进而最大降低旅行花销成本,带动我国旅游业健康可持续发展。
关键词:旅游业;最短路径;遗传算法;
Abstract:Sincethereformandopeningup,theeconomyhassustainedhighgrowth,andthepeople'slivingstandardsandsocialdevelopmenthavebeengreatlyimproved,aswellastourismhasbeenthriving,,thispaperusesGeneticAlgorithmtosolvetheshortestpath,thusminimizingthecostoftravelexpensesandpromotingthehealthyandsustainabledevelopmentoftourisminChina.
Keywords:Thetravelindustry;Theshortestpath;Geneticalgorithm;
目录
摘要 I
Abstract I
目录 II
1引言 1
1
1
2
2
3
8
8
9
2遗传算法在求解TSP问题的应用 9
10
11
3数据验证分析 14
14
16
附录 18
1引言

在1950年左右,伟大的生物学家们就发现了基因在自然进化过程中所扮演的重要角色及其作用,并通过模拟该过程实现了在新型计算机上定量研究基因与进化之间的关系,实现了生物学上的一个伟大飞跃。而有的学者则更重视用它解决优化问题,基于该种背景下,遗传算法被提出并被广泛应用,特别是在解决数值优化(如多目标优化)、组合优化(如背包问题)、生产计划等领域有突出贡献。
本文拟采用遗传算法,对TSP问题(TravelingSalesmanProblem)进行优化,求其最短路径。所谓TSP问题也就是旅行商问题,其要求是商人在旅行过程中,每个城市只去一次,并且在最终能够回到原出发城市的前提下求出所有可能路径中的最短路径[8]。

文献随着生活水平的不断提升,我国人民越来越注重精神上的享受,旅游成为大家娱乐放松的不二选择,该行业也乘胜追击,蓬勃发展。那么如何计划一份旅行攻略,选择最短路径成为我们思考的问题。本文从各文献中了解到遗传算法的原理及其实现过程,知道了遗传算法的一般应用及求解问题的思路,并了解了如何使用遗传算法求解TSP问题。
韩瑞锋(2007)主要阐述了遗传算法的原理,向我们进一步阐述通过使用遗传算法应用到各方面的实例。张青凤(2017)通过使用遗传算法来求解非线性函数最值中,证明了该算法也是解决函数优化问题的最有效方法之一。赵娟(2012)在前人研究的基础上,将遗传算法引入到了布井优化中,通过最大化净现值来优化井数。肖智,钟波,何跃群(1998)应用遗传算法的思想和方法,采用十进制的编码方法,解决了在最优决策中一类仅含权值约束的最优化问题。吕晋君(2010)通过试验函数的实验以及对TSP问题的应用,把改进的遗传算法与标准的遗传算
法进行对比,并证明了改进算法的高效性和灵活性。钟敏玲(2009)将常微分方程及偏微分方程求解问题转化为最优化问题,使用遗传算法并最终得到了最优解,进一步验证了该方法的可行性。李玉生(2006)将遗传算法应用到生活中,运用遗传算法对列车能源消耗问题转化为最优问题,使用遗传算法求解该非线性规划问题,并通过Matlab软件仿真验证所提方法的有效性。林志毅(2006)对TSP问题的历史、研究现状数学模型、时间复杂度、评价标准进行了综述,并介绍了遗传算法对求解TSP问题的进展。王娜(2010)在对TSP问题的分析上,针对其特点提出用改进的遗传算法求解TSP问题,并通过仿真实验验证了该方法的可行性以及高效率性。
以上学者通过使用遗传算法以及改进的遗传算法来求最优解,但相对来说还存在一些不成熟的地方。比如(1)韩瑞峰的理论知识过重,在用Matlab解决问题这方面还不够完善,有点头重脚轻的感觉;(2)张青凤、肖智、钟波、何跃群钟敏玲虽然应用遗传算法求最优解,但却局限于书本,未能将其应用于我们的实际生活中;(3)赵娟、李玉生已将遗传算法应用于实际问题,但却只注重应用,忽视遗传算法的理论知识;(4)吕晋君对遗传算法的应用主要是为了证明改进后的遗传算法的优越性,所以在遗传算法具体应用这块还有所欠缺;(5)林志毅只是介绍遗传算法求解TSP问题的进展,并无实际操作,略显空洞;(6)王娜用改进的遗传算法求解TSP问题,可一旦遇到城市数目较多的TSP问题,虽然能够得一个可行解,但收敛到全局最优解的能力不足,还有待研究。
因此我们继续研究遗传算法在最优化问题中的应用是十分必要的,丰富更多的文献资料,从而提出更多的建议措施,以便使结论能够满足普遍性。


在20世纪50年代,科学家们根据生物进化的理论,尝试着把生物进化系统引入工程优化,于是遗传算法应运而生。十年后,Holland出版专著《自然系统和人工系统的自适应》,创造性提出了一种位串编码技术,全面阐述了遗传算法的
基本理论及其应用方法[1]。通过这些编码不仅能够实现变异操作,而且能够进行交叉操作,将其应用于优化问题。此外,,将选择、交叉和变异操作进行完善和系统化,遗传算法更加趋于成熟。在实际生活中,我们通过使用遗传算法来解决实际问题或模型的应用范围也不断扩大。自
80年代以来,遗传算法应用蓬勃发展,不断得到国际间的重视和认可,比如在美国召开专门性的国际会议,成立国际遗传算法学会,规定每两年举行一次等[9]。

遗传算法是模拟生物界的进化过程演化而来的计算模型,符合适者生存、优胜劣汰的自然规律。它无视空间的限制,突破领域的限制,降低了其他算法对人机依赖的特点,在现实生活中具有重要的意义。遗传算法的流程如图1-1所示:
是否最优解
结束
开始
初始群体
变异
下一代种群
选择
交叉
评估每个个体
图1-1遗传算法的流程图
1)编码
编码是将问题改变为遗传,将解决方案参数改变为个体染色体。对于实际应用,如果我们想要找到一个问题的最简单的编码方案,遗传算法相对于其他传统算法效率较高,特别是近年来,遗传算法主要为实践于解决复杂的优化问题以及复杂的维度,这是因为实际的数字使问题解决方案的表示更加自然,更加通熟易懂,而且在相关领域中引入知识也很容易,所以其用途越来越多[2][。8]
最熟知的编码方式有二进制编码、十进制编码以及自然数编码等,本文拟采用自然数对30个城市的坐标进行随机编码,通过使用遗传算法解决TSP问题,从而求得最短路径。
(2)初始化
初始种群设置通常可以使用以下规则:首先确定基于最优解的整体问题的循
环范围(最大进化代数T),最终确定初始种群;通过随机函数生成多个个体,并从个体中选出最好的个体来增加种群。本文在解决TSP问题时,首先先定义总体(若干条不同的旅游路线),总体是由各个个体(每一条旅游路线)组成的,而每个个体都有自己的一套染色体(城市坐标的随机编码)。为方便理解,现假设
将上图中的4条染色体看作总体初始值,也就是对5个城市进行旅游的计划路线。
(3)适应度根据适应度,对个体的优劣程度进行评价,适应度越大则个体越好,反之适应度越小则个体越差。我们可以通过适应度的大小选择个体,从而能够保证适应性能好的个体有较高的机率繁殖后代,以得到最优解[3]。在遗传算法中,要求适应度函数值必须是非负数,但在生活中遇到的大多数实际问题,要求求解的目标一般都不是最大值,而是最小值(比如本文中我们是求最短路径),所以需要将所要求的最小目标根据适应度非负函数原则转化成求最大目标的形式。
比如本文计算A1、A2这两条染色体的路径长度,假设对于A1染色体路径长度为1100,对于A2染色体路径长度为1200,路径长度代表了适应度,路径长度越短则适应性更强。此时,可以认为,染色体A1适应性比染色体A2的适应性更强。
(4)选择
选择操作是遗传算法的重要组成部分,因为操作的选择不仅可以避免遗传泄漏,而且还可以提高计算遗传算法的效率和全局收敛性,其关键就是要选择个体的数量,以及确定有多少后代
[2][8]。
可从初始总群中选择合适的染色体,进行互相交配,进而产生下一代。但在选择的过程中,为了防止种群多样性的丢失,使染色体在几代之后相互差异不会减小,本文决定采用***赌选择法。所谓***赌选择法,就是一个圆形的***,根据总体中有多少个染色体,就将***相应地分成若干个部分,每个部分所占比例将根据适应度分数成比例表达出来,见下图:

路径长度
比例
染色体1
1100
%
染色体2
1200
%
染色体3
1250
%
染色体4
1150
%
合计
4700
100%
染色体 染色体
A1 A4
■染色体A1■染色体A2
■染色体A3■染色体A4
图1-2***赌选择法
在图中,可以标注一个固定指针,然后转动***进而得到第一个父代亲本,然后转动第二次,得到第二个父代亲本,如果发生第一个父代亲本和第二个父代亲本相同的情况,则继续转动***,直到得到和第一个父代亲本不同的亲本。
(5)交叉
交叉又称基因重组或杂交,是父代染色体的某一位置和母代染色体的相同位置,在DNA切断后,重新交叉组合后从而形成新的两个子代染色体。从生物学的专业性术语说,交叉就是繁殖。在整个遗传算法中,交叉操作是最重要的一步,其主要目的是能够让各个个体的部分染色体获得交叉机会并进行交换[2][。7]
交叉分为两种,一种是单点交叉,一种是多点交叉。单点交叉是最简单最基
本的交叉形式。本文通过选择单点交叉,对基因进行重组,比如我们对染色体A1
和染色体A3进行交叉,见下图
Parent
2
3
5
4
6
4
6
3
9
10
2
3
5
9
10
4
6
3
4
6
off-springs可以
图1-3单点交叉
这就是单点交叉,先随机选择一个交叉点,然后再将交叉点前面的染色体部分或后面的染色体部分进行染色体间的交叉对调,便得到新的后代。
(6)变异
在学****高中生物知识后我们知道,在生物进化中,各个个体的染色体会有突变,如A突变为B从而导致个体产生变异。这种变异会带来一个新的染色体,并表现出新的性状。虽然产生这种突变的机率非常的小,但它确实是存在的,遗传算法就是通过变异从而得到新的个体,最终满足种群的适应度值,并得到最优解
[2][。8]
正因为变异,种群才表现出多样性。本文选择单点变异,其中红色的标记表示染色体的变异点,见下图
2
3
15
5
6
N
染色体utati°n 3
图1-4单点变异
选择、交叉、变异完成后,就得到了新的个体,进化过程也就完成了,整个过程见下图:
selection
evaluation
品品
iimtatioii
crossover
图1-5进化流程
(7)适应度函数评估
当生成新的个体后,需要通过适应度函数对这些新的后代进行评估,看它们是否满足适应度函数,进行优胜劣汰。当它们满足条件时,则替代掉前代适应度不足的染色体,反之,则保留。在判断后代达到最佳适应度水平时,常用的终止条件有如下几个: