强收敛性（精选4篇）
强收敛性 篇1
摘要：传统遗传算法全局搜索性能的不确定性和随机性,对种群的局部多样性造成影响,容易产生早熟收敛等问题。将差分思想应用到遗传算法中进行全局寻优,并通过测试函数将其与传统遗传算法的收敛性进行分析。结果表明,差分进化遗传算法降低了传统算法的时间复杂度和搜索的盲目性,并在一定程度上提高了种群的收敛速度和多样性。
关键词：遗传算法,差分遗传算法,差分进化
0 引言
遗传算法(Genetic Algorithm,GA)由美国教授Holland于1975年根据生物进化过程和遗传机制基本知识而提出,是建立在随机选择和遗传学基础上的并行寻优算法[1]。遗传算法虽具有很好的全局搜索能力,但同时也存在一些自身的局限性。初始种群是随机生成的,寻优方向不确定且不断发生变化,复杂度较大,存在局部收敛造成的“早熟”现象[2],致使输出的局部最优解并非全局最优,只能作为问题的近似局部最优解,给实际应用问题带来很大不足。本文引入差分思想,在传统遗传算法的基础上进行改进,通过交叉率、缩放因子和种群规模大小3个控制参数来实现,在生成初始种群后采用差分思想进行变异、交叉操作,产生试验个体,在父代个体与试验个体之间根据适应度大小进行排序,保留适应度较高的个体,实现种群的进化。差分进化算法原理简单、易于理解和实现,本文通过实验表明其运行结果可靠、鲁棒性强、收敛速度快,能更好地保持群体的多样性,同时具有更高的全局寻优能力,可在很多领域得到广泛应用。
1 基本差分进化遗传算法
1.1 差分进化算法
差分进化算法[3](Differential Evolution Algorithm,DE)是1996年由Rainer Storn等提出,正如其它演化算法,差分算法是一种基于实数编码的、随机的,基于群体差异的并行直接搜索算法,它可对非线性的不可微连续空间函数进行最小化。从整体来看,它与遗传算法有很大的相似之处,同样差分算法也存在着变异、交叉和选择操作,但是它又不同于遗传算法。
与传统进化算法相比,差分进化算法保留了基于种群的全局搜索策略和实数编码,变异操作是个体算术组合的结果,并使用一对一的替换方式,只有在子代个体优于父代个体时才进行替换,很大程度上降低了遗传操作的复杂性。
1.2 差分进化算法基本思想
差分进化算法的基本思想[4]是根据父代个体间的差分向量执行变异、交叉和选择操作,是从某一随机产生的初始种群开始,在初始种群中选取任意两个个体的差向量作为一个基本个体,选择出的其余个体为参照个体,将差向量加权后按照一定的规则与第三个个体求和产生变异个体,接着按一定的概率,变异个体与某个预先确定的目标个体之间进行交叉操作,生成一个试验个体。如果试验个体的适应度值大于与之相比较的目标个体的适应度值,则在下一代中就用该试验个体取代目标个体;否则,保存目标个体。在每一代的进化过程中,每一个体向量作为目标个体一次,通过反复地迭代进行,保留优良个体,引导搜索过程逼近全局最优解,实现种群进化[5],如图1所示。
2 差分算法基本操作
差分进化算法的主要步骤与其它进化算法基本一致,主要包括变异(Mutation)、交叉(Crossover)、选择(Selection)3种操作。与传统遗传算法不同的是操作的执行顺序,差分算法先进行变异操作,然后利用变异个体与父代进行交叉操作,最后执行选择操作,选择出适应度高的个体作为新一代个体[6]。
种群初始化:设种群规模M,在n维空间中,随机生成初始种群Xi.(0)以及初始种群的第i个个体的第j个基因Xij(0)分别表示如下:
其中,i=1,2,...,M;j=1,2,...,n;xijmax和xijmin分别是第j个样本个体的取值范围,rij是[0,1]上的一随机数。
设当前进化代数为t,Xi(t)=(xti1,xti2,...,xtin)T为种群中的第i个个体,最大迭代代数为t-max,对于每个个体依次进行编译、交叉、选择操作[7]。
2.1 变异操作(Mutation)
变异操作是差分进化的主要操作,它是基于群体的差异向量来修正各个体的值,从初始种群中随机选择两个不同的个体,然后将它们的差向量加权后按一定的准则与第3个个体向量求和产生新个体的过程。
随机选择3个样本个体Xa、Xb、Xc且i≠a≠b≠c,生成的新的变异个体用Vij来表示,则变异操作为:
其中,j=1,2,...,n;Xbj(t)-Xcj(t)为差异向量,η∈(0,2)为变异算子,a、b、c为小于M的随机整数。
2.2 交叉操作(Crossover)
为了弥补局部早熟收敛造成种群的多样性减弱问题,在初始种群中随机选择两个父代个体的差向量来执行交叉操作,交叉后生成的变异个体Vij与另一个预先确定的目标个体进行交叉操作生成试验个体。
设rij(0≤rij≤1)是一随机数,k(0≤k≤1)为执行交叉操作的交叉算子,试验个体为Tij,r(i)(1≤r(i)≤n)是随机整数,以确保Ti至少可以从变异个体Vi中获得元素,具体操作如下:
若rij≤k或j=r(i),则
若rij>k且j≠r(i),则
2.3 选择操作(Selection)
差分进化算法的选择策略是从父代个体Xi和试验个体Ti中选择一个适应度值最好的作为下一代个体Xi(t+1)。设适应度函数Fit(f(s))=f(s),为了确定Xi(t)是否成为下一代成员,对向量Ti(t+1)和目标向量Xi(t)的适应度值进行比较:
3 差分算法与传统遗传算法收敛性对比
为了对差分进化遗传算法的性能进行定性评价[8],选择典型的Benchmarks函数,对差分进化算法和传统遗传算法的收敛性进行对比。本文选择典型的Sphere函数和Rosenbrock函数,通过对差分进化遗传算法和传统遗传算法的进化代数和适应度函数值之间的对应函数关系进行分析对比[9,10]。结果表明,在同样的环境条件下,差分进化遗传算法在适应度值收敛于0时,进化代数明显要少于传统遗传算法,并且程序的运行时间也相应缩短。
图2和图3是差分进化算法与遗传算法分别在Sphere和Rosenbrock函数下的函数值与种群的迭代数进化曲线。在种群个体数M=100,每个个体编码的维度n=25的情况下,设定最大迭代数初始值t-max=3 000,交叉因子η=0.3,交叉率k=0.7,可以看出,差分进化算法的收敛速度迅速,进化初期函数值变化幅度较大,浮动逐渐缓慢,直到趋于稳定状态。相比差分进化算法,遗传算法在相同参数条件下的收敛速度较缓慢。在相同硬件设施下,从程序运行速度来看,差分进化遗传算法和传统遗传算法在Sphere函数下的程序运行时间分别为16.255 304ms和22.635 745ms;而Rosenbrock函数下,程序的运行时间分别为17.986 915ms和24.414 156ms,由此可知,使用差分进化算法时,程序的运行速度明显比遗传算法要快,降低了算法的时间复杂度。
图4和图5分别是两种算法在种群规模、个体编码维度、最大进化代数以及交叉率不变的情况下,将其交叉因子变为η=0.5。可以看出,差分进化的收敛速度较之前变得缓慢,但随着其进化的进行,函数值不再随着进化代数的增长而改变,而是逐渐趋于0,收敛到稳定状态,在一定程度上表明变异因子对收敛速度的影响,且变异率越大,收敛速度越缓慢。相比差分进化算法,遗传算法在相同参数条件下的收敛速度更显得缓慢。从程序的运行速度进行分析,Sphere函数下,差分进化算法的程序运行时间为15.350 498ms,而遗传算法的运行时间为21.824540ms;Rosenbrock函数下差分进化与传统遗传算法的运行时间分别为13.540 887ms、20.451 731ms。同样可知,相同参数条件下,差分进化的性能比传统遗传算法的性能更优。
4 结语
由Matlab实验测试结果可知,差分进化遗传算法在传统遗传算法的基础上进一步提高了算法的全局寻优能力,在交叉因子一定的情况下,变异因子越大收敛速度越缓慢,而种群规模会影响程序的运行时间。本实验仿真验证了差分进化遗传算法的有效性,从实验对比数据可以看出,该算法在求解最优解的过程中,相比传统遗传算法,差分进化算法在迭代次数较少的情况下就可以达到稳定状态,在较短时间内就能够搜索到较高精度的解,程序运行速度也明显提高。因此,本文提出的算法具有较强的全局搜索能力,同时缩短了算法的搜索时间,在一定程度上降低了算法的复杂度。
参考文献
[1]苗振华,孙旭东.基于交叉库与并行变异的自适应遗传算法[D].大连:大连理工大学,2015.
[2]王岚.基于自适应交叉和变异概率的遗传算法收敛性研究[J].云南师范大学学报,2010,30(3):32-37.
[3]杨启文,蔡亮.差分进化算法综述[J].模式识别与人工智能,2008,21(4):506-513.
[4]魏玉霞,林健良.差分进化算法的改进及其应用[D].广州:华南理工大学,2013.
[5]LIU JUNHONG,LAMPINEN J.A fuzzy adaptive differential evolution algorithm[J].Soft Computing:A Fusion of Foundations,Methodologies and Applications,2005,9(6):448-462.
[6]郭鹏,赵正.差分进化算法改进研究[D].天津:天津大学,2011.
[7]BABU B V,JEHAN M M L.Differential evolution for multi-objective optimization[J].Evolutionary Computation,2003,4(12):8-12.
[8]高岳林,刘军民.差分进化算法的参数研究[J].黑龙江大学自然科学学报,2009,21(1):81-85.
[9]汪民乐.遗传算法的收敛性研究[J].计算技术与自动化,2015,34(1):58-62.
[10]宁桂英,周永权.基于差分进化算法的收敛性分析[J].南通大学学报:自然科学版,2014,13(3):90-94.
强收敛性 篇2
本文研究一类新的.解无约束最优化问题的记忆梯度法,在强Wolfe线性搜索下证明了其全局收敛性.当日标函数为一致凸函数时,对其线性收敛速率进行了分析.数值试验表明算法是很有效的.
作 者：汤京永 时贞军 TANG Jingyong SHI Zhenjun 作者单位：汤京永,TANG Jingyong(信阳师范学院数学与信息科学学院,信阳,河南,464000)
时贞军,SHI Zhenjun(曲阜师范大学运筹与管理学院,日照,山东,276826)
三重级数收敛性的讨论 篇3
关键词：级数,重级数,柯西收敛准则
1 引言及相关定义
作为高等数学内容重要组成部份的级数是数学中非常重要的概念与计算手段, 级数不论在数学理论及现实中均有广泛应用。高等数学中已经介绍了级数相关定义及性质, 为了以示区别将这些级数称为一重级数。考虑到数学理论的完善及现实中应用, 有必要将该定义推广到多重级数, 鉴于二重级数已经有较多结论, 本文讨论三重级数定义及性质, 对于更高重数级数有类似讨论。下面先回顾一重级数定义及重要性质。
在建立级数收敛性判据时, 核心的结果是如下的柯西收敛准则:
下面类比的给出三重级数定义:
注:为了叙述上的简介, 本文将三重级数简称为重级数。
显然由于三重级数收敛性需要讨论重极限与逐次极限, 所以三重级数收敛的判定显得更为复杂, 但是幸运的是, 我们仍可以找到类比一重级数的柯西收敛准则及比较判别法。
2 重级数收敛性的若干重要性质
下面首先给出若干重级数的例子, 再逐步给出本文重要结论。
解
即该级数收敛。
下面讨论重级数的性质:
证明:下证任意加括号后结论成立, 改变有限项的证明类似。
注:由例2容易知道收敛级数在加括号后收敛性不变, 但反之不成立。
定理2.4 (重级数的柯西收敛准则) 重级数 收敛当且仅当它的部分和序列 为柯西列
3 结论
本文在回顾了高等数学中级数定义后, 对重级数定义及性质进行了有益地探索, 文章给出了三重级数若干重要性质, 对三重级数收敛性的讨论起到了重要的抛砖引玉之用, 围绕三重级数收敛性的更深入讨论是之后研究的重点。
参考文献
[1]Double Sequences and Double Series.Eissa D.Habil_.Islamic University of Gaza.P.O.Box 108, Gaza, Palestine.
[2]陈纪修, 於崇华, 金路.数学分析 (上册) .2版[M].北京:高等教育出版社, 2009.
[3]杨小远, 孙玉泉, 薛玉梅等.工科数学分析教程 (上下册) [M].北京:科学出版社, 2011.
[4]裴礼文.数序分析中的典型问题和方法[M].北京:高等教育出版社, 2010, 11.
迁移方程的扩散近似的收敛性 篇4
作 者：王胜华 郭柏灵 WANG Sheng-hua GUO Bo-ling 作者单位：王胜华,WANG Sheng-hua(上饶师范学院数学与计算机系,江西,上饶,334001)
郭柏灵,GUO Bo-ling(北京应用物理和计算数学研究所,北京,100088)