优化求最值中遗传法的应用分析

白 灏

(淮南职业技术学院学生处, 安徽淮南232001)

优化求最值中遗传法的应用分析

白 灏

(淮南职业技术学院学生处, 安徽淮南232001)

简单介绍了遗传算法,并对遗传算法进行改进,对于多峰值问题,为了避免陷入局部最优,结合Matlab作出图像,利用遗传算法,调整控制参数,得到全局的最优解,并加以举例验证。

非线性规划; 多峰值问题; 遗传算法控制参数

一、遗传算法介绍

遗传算法是数学领域近年来发展起来的一种智能算法,已经广泛地应用于各个行业。根据名称也可以看出遗传算法其实是人们模仿自然界的遗传进化规律而衍生出来的,它在可行空间内自动地进行搜索,而后通过不断地重复淘汰最终获得最优值。第一次提出遗传算法的是Michigan大学Holland教授,他通过多年对自然界发展规律的研究探索与实践经验在1975年的时候提出了这种可以在全局内搜索的智能算法。传统的优化问题一般是通过导数的方法来求解的,但是计算的前提是函数必须是连续而且可导的,这对于解决实际的工程问题具有很大的局限性,而遗传算法的出现彻底解决了这一问题,这是因为其鲁棒性和随意性都较强,可以更为客观充分地解决实际问题。

学过生物的人都知道生物可以继承亲代的某些性状,所以才使得瓜农种下的瓜只能长出瓜来,想让它长成豆是不可能的,这就是遗传。可以决定这种遗传特性的物质是基因(DNA),基因是遗传物质的基本单位,生物体所有的遗传性状都来自于基因的控制。生物体是由一个个细胞构成的,在细胞核内有一种很容易被染色的物质,人们通常叫它染色体或染色质,染色体和染色质是同一物质在不同时期的两种表现形式,生命体的基因就是附着在这种染色体上的。细胞具有可以分裂的特性,在有丝分裂刚开始的时候完成DNA的复制和蛋白质的合成,而后相同的染色体随着细胞的分裂分别进入两个细胞内,这就完成了遗传物质的复制与传递过程,这是高等生物遗传物质的传递介质和方法。而在那些低等的原核生物细胞内,根本没有成型的细胞核,也没有相应的染色体,它们的遗传物质是在RNA上面,RNA与DNA从结构组成上有点类似,只是DNA是双链的,而RNA是单链结构。在有性生殖过程中,细胞内的染色体首先两两形成同源染色的联会,同源染色体是指控制同一性状不同表现形式的染色体,他们通过交叉互换随着细胞的分裂进入两个不同的子细胞内,染色体交叉互换的过程就是变异,通过变异过程可以产生全新的染色体,由这些新的染色体又可以使生物体出现一些新的性状,这样循环下去就完成了生命体的遗传变异过程。

根据上述的分析可以看出,我们平常所用的遗传算法也是采用同样的机理和步骤进行的。遗传算法的第一步就是确定遗传算子,遗传算子如果应用于P(t)代的话就可以得到P(t+1)代。遗传算法中几个比较重要的概念是选择、交叉和变异。其中选择主要是指从第t代中按照某种规律选出部分比较好的个体,将这些个体遗传到第t+1代,形成第t+1代的种群P(t+1),而选择这些个体的规律我们称之为适应度,一般用函数的形式表示。交叉主要是指把第t代的种群P(t)内的个体按照随机组合的方式两两配对,相互交叉。遗传算法中的变异主要是指针对种群内的个体,按照一定的概率将它们上面的某些基因换成它们的等位基因,具体的操作步骤:第一步是初始化,也就是建立一个遗传算法进化代的计数器,将它的最大进化代数用字母T来表示,而后就是先随机生成初始种群,用字母M来表示;第二步就是对这些生成的种群内的个体进行评价分析,也就是按照前文所说的方法根据适应度函数分别计算它们的适应度值;第三步就是进行优良个体的选择,将那些适应度值高的个体选择出来;第四步是遗传算法的交叉运算,将选出的遗传算子根据一定的概率两两交叉配对;第五步是遗传算法的变异操作,遗传算子的某些部位发生变异,而产生新一代的种群P(t+1);第六步就是终止条件的判断,根据前面设置的最大遗传代数,当t没有达到T时,t加上1跳转到算法的第二步循环运算。如果t已经达到了最大遗传代数,则整个计算结束,此时适应度值虽大的解有就是整个运算的最优解。

在通常的情况下染色体的长度应该是固定不变的,但是在个别情况下可以发生变化,此时的等位基因可以用整数或者实数来表示,当然也是可以用0和1来表示的,当用0和1表示的时候,染色体其实就是一串二进制的符号,每串二进制符号代表一种性状,而且一般呈现出一一对应的关系。对于遗传算法中的每个个体,都是要根据提前设定的适应度函数进行计算,求出它们各自的适应度值,而后根据对应的选择概率从中找出较好的个体进行交叉变异的操作,从而形成新一代的个体,这样循环下去种群中较好的适应度值与最优值之间的差距越来越小,最终趋近于最优值。

二、算法的改进

(一) 约束优化问题

其中x=(x1,x2,…,xn)T,Ω为有界闭集。

(二) 改进遗传算法的步骤

第二步进行变异。令xi+m(t)=xi(t)+αξ(i=1,2,…,m),其中ξ=N(0,σ)=(N(0,σ1), N(0,σ2),…,N(0,σm))T,N(0,σi)为均值为0、方差为的正态分布,且ξ的n个分量具有相互独立性.α∈(0,1]为压缩因子.若xi+m(t)∈Ω,则转进入第三步;否则重做第二步。

第三步新个体计算。计算新个体xi+m(t)(i=1,2,…,m)处的目标函数值f(xi+m(t)),(i= 1,2,…,m)。

第五步终止检验。判别X(t+1)是否已达到终止检验的条件,若已满足,则计算结束,并输出最优解x*(t+1);否则,令t=t+1,返回第二步。

三、数值举例

该函数在[0,1]区间内有多个局部极值点,其全局最优值为f小(x)=-7.456 2,f大(x)= 1.1730。

例2 f(x,y)=(cos(2πx)+cos(2.5πx)-2.1)×(2.1-cos(3πy)-cos(3.5πy),其中(x,y)∈[0,3]×[0,1.5],利用Matlab作图,如图2所示。

该函数在[0,3]×[0,1.5]区域内具有多个局部极值点和一个全局最优点,全局最优值为: f(0.438 974,0.305 734)=-16.091 72。

虽然该函数是一个单峰函数,但却十分光滑,其全局最优值为f(0,0)=0,如图3所示。

表1是算法A对上述三算例的计算结果:

四、结果与分析

由以上遗传算法的解题过程不难看出,无论是搜索能力还是计算速度,改进后的遗传算法都有了很大的提高。在实际的工程应用中,遗传算法中的三个参数σ、m和α要根据具体的情况来定值,具体来说是从以下几个角度着手。三个参数中种群m对遗传算法结果的影响很大,如果我们选择的种群太小,那么搜索就具有一定的局限性,也有可能陷入局部收敛的极值点内,但是也不是说种群规模就是越大越好,如果种群规模过大,会使得整个运算的速度大大降低,这样要花费更多的时间,影响运算的效率;变异算子是遗传算法中生成新种群的关键,有了它的存在搜索空间才可以不断的得到更新和扩展,使循环过程不至于过早地进入局部的收敛中去,这是因为变异产生的新个体有很大的随机性,可以覆盖空间中的任何一个点,这里的σ表示正太分布的均方差,在遗传算法中其实就相当于步长,随着循环迭代次数的增加,步长值应该越来越小,只有这样才能提高运算的精度。

改进后的遗传算法是在循环迭代过程中修正步长。如果在好几代内都没出现合适的下降点,那么就表明选择的步长不合适,要进行缩小。如果在计算中发现问题的可行解范围很大,那么初始步长σ的设定也应该大一些,这样就可以使整个运算的搜索能力大大的提升。所以步长σ的主要作用就是用来将循环迭代的精度和速度控制在合理的范围内的。

[1] 吴昌友,孙福田,王福林.改进实数遗传算法在减速器设计中的应用[J].东北农业大学学报,2006(1): 78-81.

[2] 刘立民,靳晨霞,杨丽芸,等.两阶段遗传算法的结构及性能分析[J].河北科技大学学报,2007(1):44-48.

[3] 詹仁超,李应岐.基于混合算法的导弹部队铁路机动路径选择[J].四川兵工学报,2012(7):62-65.

TP18

B

1671-4733(2014)06-0080-04

10.3969/j.issn.1671-4733.2014.06.021

2014-11-20

淮南职业技术学院科技基金项目“高校贫困生认定的模糊综合评判”(项目编号:HKJ12-10),安徽省高等学校省级优秀青年人才基金项目“基于遗传算法的DNA编码序列优化设计与探索”(项目编号:2012SQRL259)

白灏(1978-),男,山东菏泽人,讲师,研究方向为模式识别与数字图像处理,电话:0554-6656532。