遗传算法.docx
- 文档编号:14474813
- 上传时间:2023-06-23
- 格式:DOCX
- 页数:15
- 大小:115.66KB
遗传算法.docx
《遗传算法.docx》由会员分享,可在线阅读,更多相关《遗传算法.docx(15页珍藏版)》请在冰点文库上搜索。
遗传算法
基于MATLAB仿真的遗传算法研究
姓名:
王兴林崔永超
学号:
120120023341201002153
专业:
电子与通信工程
摘要:
本文论述了遗传算法的基本原理、特点,并介绍遗传算法的应用领域。
对遗传算法的各个基本步骤做出简单的介绍,举出详细的实例,并重点论述了遗传算法解决TSP问题,最后用Matlab实验平台进行了仿真。
从而得出结论:
遗传算法不是一种单纯的优化算法,而是一种以进化思想为基础的全新的一般方法,是解决复杂问题的有力工具。
关键词:
遗传算法,TSP问题,Matlab实验平台
1.遗传算法介绍
遗传算法(geneticalgorithms,GA)是一种模拟自然选择和遗传机制的寻优方法,它是建立在达尔文的生物进化论和孟德尔的遗传学说基础上的算法。
基因杂交和基因突变可能产生对环境适应性强的后代,通过优胜劣汰的自然选择,适应值高的基因结构就保存下来。
遗传算法就是模仿了生物的遗传、进化原理,并引用了随机统计原理而形成的。
1.1遗传算法发展简介
遗传算法是近年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darwin的进化论和Mendel的遗传学说。
50年代末60年代初,生物学家Fraser试图通过计算的方法来模拟生物界"遗传与选择"的进化过程,这便是GA的雏形。
受此启发,Holland教授认识到自然遗传可以转化为人工遗传算法。
1967年Bagley在其博士论文中首次提出了"遗传算法"这一术语。
1975年,Holland出版了《自然与人工系统中的适应性行为》。
该书系统地阐述了遗传算法的基本理论和方法,提出了遗传算法的基本定理-模式定理,从而奠定了遗传算法的理论基础。
20世纪80年代初,Holland教授实现了第一个基于遗传算法的机器学习系统--分类器系统(ClassifierSystem简称CS),开创了基于遗传算法的机器学习的新概念。
l992年,JohnR.Koza出版了专著《遗传编程》,提出了遗传编程的概念,并成功地把遗传编程的方法应用于人工智能、机器学习、符号处理等方面。
经过数年的努力,遗传算法作为一种简单通用、鲁棒性强、适合并行的全局最优算法,发展极为迅速,已引起了国内外学者的高度重视。
1.2遗传算法的基本原理
遗传算法是一个迭代过程,在每次迭代中都保留一组候选解,按其解的优劣进行排序,并按某种指标从中选出一些解,利用遗传算子对其进行运算,产生新一代的一组候选解,重复此过程,直到满足某种收敛指标为止。
遗传算法是一种基于自然选择和群体遗传机理的搜索算法,它模拟了自然选择和自然遗传过程中发生的繁殖、杂交和突变现象。
与传统搜索算法不同,遗传算法从一组随机产生的初始解,称为群体,开始搜索过程。
群体中的每个个体是问题的一个解,称为“染色体”。
这些“染色体”在后续迭代中不断进化,称为遗传。
遗传算法主要通过交叉、变异、选择运算实现。
交叉或变异运算生成下一代“染色体”,称为后代。
“染色体”的好坏用适应度来衡量。
根据适应度的大小从上一代和后代中选择一定数量的个体,作为下一代“染色体”,再继续进化,这一群新个体由于继承了上一代的一些优良性状,因而在性能上要优于上一代,这样逐步朝着更优解的方向进化。
经过若干代之后,算法收敛于最好的染色体,它很可能就是问题的最优解或次优解,它是一种迭代式算法。
图1.1示出了简单遗传算法的流程。
图1.1简单遗传算法的流程
遗传算法的基本求解步骤如下:
(1)编码:
确定用何种码制,然后将问题参数编码形成基因码链,每一个码链代表一个个体,表示优化问题的一个解。
(2)初始化:
随机产生一个规模为P的初始种群,其中每个个体为一定长度的码链,该群体代表优化问题的一些可能解的集合。
(3)估计适应度:
计算种群中每个个体的适应度,适应度为群体进化时的选择提供了依据。
一般来说适应度越高,解的素质越好。
适应度函数可以根据目标函数而定。
(4)选择:
根据每个个体的相对适应度,计算每个个体的再生次数,并进行再生操作,产生新的个体加人下一代群体中,一般再生的概率与其适应度成正比。
(5)交叉:
从种群中随机选择两个染色体,按一定的概率进行基因交换,交换位置的选取是随机的。
(6)变异:
从种群中随机地选择一个染色体,按一定的变异概率P进行基因变异,GA的搜索能力主要是由选择与交叉赋予的,变异算子则保证了算法能搜索到问题空间的每一点,从而使算法具有全局最优性,它进一步增强了GA的能力。
(7)重复:
若发现最优解,则算法停止,否则转(3),对产生的新一代群体进行重新评价、选择、交叉、变异操作,如此循环往复,使群体中最优个体的适应度和平均适应度不断提高。
2.遗传算法的应用
遗传算法的初期应用研究主要围绕组合优化问题求解,但近年来已迅速扩展到机器学习、设计规划、神经网络优化、自律分布控制和人工生命等众多领域。
此外,还在核反应控制和喷气发动机设计等工程应用中进行了十分有意义的尝试。
基于GA的机器学习是当前GA应用研究的热点,特别是分类器系统,在很多领域中都得到了应用。
Holland的分类器系统是基于遗传算法机器学习的一个典型例子,GA部分的主要任务是产生新的分类器,如获取规则集合以预测公司的利润。
Brooker等对分类器系统和GA进行了更加详细的评述。
2.1遗传算法简单应用
用遗传算法求解
,
为整数时
的最大值。
步骤如下:
(1)编码:
在区间[0,31]上的整数可以用一个5位的二进制位串进行编码,x的值直接对应二进制位串的数值,如:
9对应01001,31对应11111。
(2)初始化:
在[0,31]范围内按某种分布,随机产生一个规模为P的初始种群,本例中假定初始种群取为4个二进制串,x1=01100,x2=11001,x3=01000,x4=10010。
以上5位字串称为染色体,每个分量称为基因,每个基因有两种状态0或者1。
(3)适应度:
计算种群中每个个体的适应度,本题中,适应度函数可定为:
于是
,
,
,
。
(4)选择:
初始种群中每个个体入选种群的概率为:
。
利用上述概率,对这四个整数进行四次有放回的随机抽取,产生四个新的整数,显然概率大的有更多的机会被抽中,四个新的整数
=01100,
=11001,
=11001,
=10010.经前四步后,具体情况如表2.1所示:
表2.1前四步骤计算结果
序号
初始种群
X值
适应度
人选种群概率
期望复制数
实际复制数
1
01100
12
144
12%
0.48
1
2
11001
25
625
51%
2.04
2
3
01000
8
64
5%
0.2
0
4
10010
20
400
32%
1.28
1
合计
1233
100%
4
4
平均
308.3
25%
1
1
(5)交叉:
将
(
=1,2,3,4)随机结合成两组,每组两个数;对每组再进行一次随机抽样,以等概率从1,2,3,4中选取一个数n.假设在上述例子中恰
=01100,
=11001分为一组,随机抽取n=3,那么将由二进制表示的
,
从后三位开始互换,得到两个新的二进制整数,记为
,
。
同样对另外一组数作类似处理,假设另一组抽得n=2,这样得到四个新的整数,结果为
=01001,
=11100,
=11010,
=10001.具体情况如表2.2所示:
表2.2交叉后的结果
序号
复制后种群
复制对象
交叉点n
交叉后种群
X值
适应度
1
01100
2
3
01001
9
81
2
11001
1
3
11100
28
784
3
11001
4
22
11010
22
484
4
10010
3
10001
17
289
合计
1638
平均
409.5
(6)变异:
将交叉得到的四个二进制数,每个数的每个二进位进行一次随机抽样,以一个小概率P,例如1、1000将该位取反,即由1变为1,由1变为0,以概率
保持该位数字不变。
这样得到四个新的数记为
(
=1,2,3,4),计算其函数值
回到步骤(4)。
对产生的新一代群体进行重新计算适应度、选择、交叉、变异操作,如此循环往复,使群体中最优个体的适应度和平均适应度不断提高。
变异可保持群体的多样性,可使遗传算法跳出局部极值点。
以上的简单例子,从开始随机产生的种群到经过一次再生、交叉、变异操作后的新种群中,我们不难看出初始种群的平均适应度为303.8,新种群的平均适应度为409.5,最大值从初始种群的625增加到新种群的784。
可见经过一次遗传算法的操作后,问题的解向最优解的方向前进了一大步。
因此经过以上多次类似计算,问题的解最终会接近最优解。
当然在应用遗传算法时,可以事先规定一个最大允许循环次数,以使计算得到终结,而以计算过程达到的最大函数值的
作为所要的解,遗传算法实际上是一种搜索方式,对那些标准数学方法难以奏效的问题给出了一种处理办法。
2.2遗传算法解决TSP
旅行商问题(TSP),也称为货郎担问题,是一个较古老的问题。
最早可以追溯到1759年Euler提出的骑士旅行问题。
1948年,由美国兰德公司推动,TSP成为近代组合优化领域的一个典型难题。
应该说,TSP是一个具有广泛应用背景和重要理论价值的组合优化难题,它已经被证明属于NP难题。
对TSP问题的大量研究使得TSP问题成为了一个著名的组合优化问题目前,求解TSP问题的较为常用的方法有二叉树描述法、启发式搜索法、最近邻法、神经网络法、模拟退火法和遗传算法等。
遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局概率搜索算法,具有良好的全局寻优能力,成为解决问题的有效方法之一。
TSP(旅行商问题)的简单描述是:
一名商人欲到n个城市推销商品,每两个城市i和j之间的距离为d,存在i,j如何使商人每个城市走一遍后回到起点,且所走的路径最短。
用数学符号表示为:
设n维向量表示一条路径
,目标函数为
(2.1)
用图语言来描述TSP,给出一个图G=(V,E),每边e∈E上有非负权值w(e),寻找G的Hamilon圈C,使得C的总权W(C)=
最小。
TSP搜索空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!
/2。
5个城市的情形对应120/10=12条路线,10个城市的情形3628800/20=181440条路线,100个城市的情形则对应有4.6663×
条路线。
在次庞大的搜索空间中寻求最优解,对于常规方法和现有的搜索而言,存在诸多的计算困难。
借助遗传算法的搜索能力解决TSP问题是很自然的想法。
遗传算法用于TSP问题如下:
(1)编码:
用遗传算法求解TSP时,算法的编码表示是算法设计的重点,它对遗传基因的操作有一定的限制。
TSP的编码策略主要包括二进制表示、顺序表示、路径表示、矩阵表示和边表示等。
由于二进制编码具有如下的特点数据冗长,并且表达能力有限,计算机无法承受如此巨大的计算量甚至根据调整不同的参数时,所运行的时间,有时会达到近几个小时,从时间效率来说,工作效率实在是低下,并达到无法忍受的程度,所以实际中很少使用。
顺序表示是指将所有城市依次排列构成一个顺序表,对于一条旅程,可以依次旅行经过顺序处理每个城市,每个城市在顺序表中的顺序就是一个遗传因子的表示。
每次处理完一个城市,从顺序表中去掉该城市。
处理完所有城市后,将每个城市的遗传因子连接起来,即成为一条旅程的基因表示(染色体编码)。
路径表示是表示旅程岁应的基因编码的最自然,最简洁的表示方法。
(2)初始化群体和适应度函数及其终止条件的设定:
根据编码方法,随机产生初始群体,直到达到所需规模为止。
适应度函数,由于是求最短路径,适应度函数一般采用求函数最大值,例如取路径总长度T的倒数,即
。
其中,
=
(2.2)
适应度越小的个体,该个体的路径越短,该个体则越好。
也有采用
计算适应度的算法。
也有的算法采用
,其中
为未遍历的城市的个数,
为惩罚函数系数,常取城市间最长距离的两倍多,路径
越大,适应度函数越小。
迭代停止条件一般是:
若某代群体中的最差个体与最好的个体适应度的差不大于某个数(根据问题规模变化),则终止算法。
若最佳个体连续保持一定代数,则终止算法。
若算法迭代次数达到一定代数,则终止算法。
(3)选择算子:
选择是从一个旧种群中选择生命力强的个体位串产生新种群的过程。
或者说,选择是个体根据其适值函数f拷贝自己的过程。
直观地讲,可以把适值(或目标)函数f看作是我们期望的最大效益或好处的某种量度。
根据个体的适值拷贝位串意味着:
具有高的适值的个体更大可能在下一代中产生一个或多个子孙。
显然这个操作是模仿自然选择现象,将达尔文的适者生存理论运用于个体的选择。
对于求解TSP问题,常用的选择机制有轮盘赌选择机制、随机遍历抽样法、局部选择法、截断选择法、锦标赛选择法等。
遗传算法中一个较难解决的问题是如何较快地找到最优解并防止“早熟”收敛问题。
为了保证遗传算法的全局收敛性,就要维持解群体的个体多样性。
这种做法会明显改善遗传算法的行为,因为其增加了体在种群中的分布区域,但增加了计算时间。
(4)交叉算子:
Goldberg提出基于路径表示的部分映射交叉(partially—mapped,PMX),首先随机地在父个体中选取两杂交点,并交换相应的段再根据该段内的城市确定部分映射。
在每代父个体上先填入无冲突的城市。
而对有冲突的城市分别执行这些部分映射直到填人无冲突,刚可获得交叉后的两后代。
由Davis提出顺序交叉(order,OX),它与PMX操作非常类似。
也是首先随机地在父个体中选择两杂交点,再交换杂交段,其它位置根据保持父代个体中城市的相对次序来确定。
由Oliver等提出的循环交叉(CX),将另一个父个体作为参照以对当前父个体中的城市进行重组。
先与另一父个体实现一个循环链.并将对应的城市填入相应的位置,循环组成后.再将另一父体的城市填入相同的位置。
上述几种TSP操作基本上考虑的是城市的位置和顺序,未考虑城市间的连Grefenstette认为遗传算法应用与TSP,其遗传操作不仅要考虑城市间的位置,而且有必要考虑城市间的关系,城市间的关系定义为边,让子个体继承父个体中边的信息设计边的遗传操作很有意义。
1989年,Whitle等提出了一种边重组(EdgeRecombination.ER)交叉操作,使个体能够从父个体继承95%~99%的边信息。
ER操作是根据继承两个父个体定义的旅程中城市间的相邻关系生成子个体。
1991年,Starkweather等提出了一种改进的方法,在ER操作中不再保留父个体中共同部分的序列。
实验结果表明这种处理方法比随机选择的处理的性能有相当的改善。
(5)变异算子:
尽管复制和交叉操作很重要,在遗传算法中是第一位的,但不能保证不会遗漏一些重要的遗传信息。
在人工遗传系统中,变异是用来防止这种不可弥补的遗漏,在简单遗传算法中,变异就是某个字符串某一位的值偶然的(概率很小的)随机的改变,即在某些特定位置上简单地把1变成0,或反之。
变异是沿着个体字符空间的随机移动,当它有节制地和交叉一起使用时,它就是一种防止过度成熟而丢失重要概念的保险策略。
变异本身是一种局部随机搜索,与选择/重组算子结合在一起,保证了遗传算法的有效性,使遗传算法具有局部的随机搜索能力;同时使得遗传算法保持种群的多样性,以防止出现非成熟收敛。
在变异操作中,变异率不能取得太大。
变异算子的设计要比交叉算子的设计灵活得多。
简单的倒位操作,即首先在父个体中随机地选择两截断点,然后将该两点所夹的子串中的城市进行反序。
也有一种贪婪倒位变异算子,它的主要思想是:
首先随机选择一个城市C,然后在除外的其他城市中选除C、cRight、cLeft以外的距离C最近的城市
,在对cRight到
之间的城市进行倒位。
3.基于Matlab的实验仿真
3.1简单一元函数优化
求函数
的最大值,程序见附录所示,绘制出的图像如图3.1所示。
图3.1函数图像
3.2遗传算法的matlab实现
用Matlab编写程序实现整个遗传算法的过程,程序见附录,运行成功后得到的结果如图3.2所示。
图3.2遗传算法仿真结果
从上图可以明显看出目标函数、进化代数、种群均值、最优解之间的各种关系。
4.结论
本文详细介绍了遗传算法的理论和应用研究,并进行了系统分析,列举了遗传算法的应用。
在实验部分用Matlab进行了仿真,得到了遗传算法的基本求解集模型。
得到了如下的结论:
遗传算法不是一种单纯的优化算法,而是一种以进化思想为基础的全新的一般方法,是解决复杂问题的有力工具;遗传算法应用日趋广泛,其本身的发展也是不断进化的过程,理论研究需要引入新的数学工具、吸收生物学的最新成果。
参考文献:
[1]黄少荣.遗传算法及其应用[J].电脑知识与技术.2008(34)
[2]张文,李祥.基于优化组合的遗传算子的研究与应用[J].数值计算与计算机应用.2005(03)
[3]段杨.遗传算法的若干改进及其在支持向量机中的应用研究[D].南京邮电大学2012
[4]PingChen,HoukuanHuang,XingyeDong.AnAntColonySystemBasedHeuristicAlgorithmfortheVehicleRoutingProblemwithSimultaneousDeliveryandPickup.2007SecondIEEEConferenceonIndustrialElectronicsandApplications.2007
[5]Gu,W-j,Zhang,R.-c,Zhao,H.-c.Onfuzzyslidingmodeguidancebasedonself-adaptivegeneticannealingalgorithm.IEEETransactionsonSystemsManandCybernetics.2008
[6]高建兵.基于遗传算法的模糊推理控制系统的参数优化研究[D].辽宁工程技术大学2011
[7]陈鹏.遗传算法的改进及在调度优化中的应用研究[D].中国地质大学2011
[8]李振业.多向变异遗传算法及其优化神经网络的研究[D].华南理工大学2011
附录:
figure
(1);
fplot('variable.*sin(10*pi*variable)+2.0',[-1,2]);%画出函数曲线
%定义遗传算法参数
NIND=40;%个体数目(Numberofindividuals)
MAXGEN=25;%最大遗传代数(Maximumnumberofgenerations)
PRECI=20;%变量的二进制位数(Precisionofvariables)
GGAP=0.9;%代沟(Generationgap)
trace=zeros(2,MAXGEN);%寻优结果的初始值
FieldD=[20;-1;2;1;0;1;1];%区域描述器(Buildfielddescriptor)
Chrom=crtbp(NIND,PRECI);%初始种群
gen=0;%代计数器
variable=bs2rv(Chrom,FieldD);%计算初始种群的十进制转换
ObjV=variable.*sin(10*pi*variable)+2.0;%计算目标函数值
whilegen FitnV=ranking(-ObjV);%分配适应度值(Assignfitnessvalues) SelCh=select('sus',Chrom,FitnV,GGAP);%选择 SelCh=recombin('xovsp',SelCh,0.7);%重组 SelCh=mut(SelCh);%变异 variable=bs2rv(SelCh,FieldD);%子代个体的十进制转换 ObjVSel=variable.*sin(10*pi*variable)+2.0;%计算子代的目标函数值 [ChromObjV]=reins(Chrom,SelCh,1,1,ObjV,ObjVSel);%重插入子代的新种群 variable=bs2rv(Chrom,FieldD); gen=gen+1;%代计数器增加 %输出最优解及其序号,并在目标函数图像中标出,Y为最优解,I为种群的序号 [Y,I]=max(ObjV);holdon; plot(variable(I),Y,'bo'); trace(1,gen)=max(ObjV);%遗传算法性能跟踪 trace(2,gen)=sum(ObjV)/length(ObjV); end variable=bs2rv(Chrom,FieldD);%最优个体的十进制转 holdon,grid; plot(variable,ObjV,'b*'); figure (2); plot(trace(1,: )); holdon; plot(trace(2,: ),'-.');grid legend('解的变化','种群均值的变化')
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)