遗传算法的收敛性研究

2024-09-18

遗传算法的收敛性研究（精选4篇）

遗传算法的收敛性研究篇1

0 引言

量子计算与遗传算法的结合量子遗传算法 (Quantum Genetic Algorithm, 简称QGA) 从20世纪90年代后期开始, Narayanan将量子多宇宙理论引入遗传算法, 提出了多宇宙量子衍生遗传算法, Han等提出量子衍生演化算法, 它首次将量子的概率幅表达引入遗传算法[1]。后来许多研究者在算法上又进行了相应改进, 并用实验结果证明更好。但是遗传算法的随机性不好把握, 收敛方向无法进行有效控制, 容易陷入局部最优等问题还是不易克服。面对遗传算法的各种问题, 学者们开始探索并构建新的算法模型。近年来, 学者们相继提出多种方法来改进量子遗传算法收敛性。比如引入免疫算子, 或者通过对量子旋转门的旋转角及旋转参数进行调节来改进算法收敛性[2]。本文针对背包问题提出引入惩罚函数来对收敛性进行研究, 并通过实验来对比效果。

1 量子遗传算法

遗传算法的缺点[3]包括:编码不规范及编码存在表示的不准确性;单一的遗传算法编码不能全面地将优化问题的约束表示出来;效率比其他传统的优化方法低;容易出现过早收敛;对算法的精度、可信度、计算复杂性等方面, 还没有有效的定量分析方法。

量子遗传进化算法是量子计算与遗传算法相结合的产物。目前, 这一领域的研究主要集中在两类模型上:一类是基于量子多宇宙特征的多宇宙量子衍生遗传算法 (Quantum Inspired Genetic Algorithm) , 另一类是基于量子比特和量子态叠加特性的遗传量子算法 (Genetic Quantum Algorithm, GQA) [4]。

1.1 量子遗传算法流程

量子遗传进化算法求解问题的基本步骤[5,6]:

(1) 进化代数初始化:t=0。

(2) 初始化种群Q (t) 。

(3) 由Q (t) 生成P (t) :随机产生一个[0, 1]的数, 若它大于|αit|2取1, 否则取0, 然后, 对这一组解进行适应度评估, 记录下最佳适应度个体作为下一代演化的目标值。

(4) 对各个状态计算适应度。

(5) 记录最佳个体及其适应度值。

(6) While (不满足终止条件) do

begin

A.t=t+1;

B.对种群Q (t) 中每个个体实施一次测量, 得到一组状态P (t) ;

C.对每个状态计算适应度;

D.依据一定的调整策略, 利用量子旋转门操作和量子非门对种群个体进行更新, 得到子代种群Q (t+1) ;

E.记录下最佳个体及其适应度。

End

算法如图1所示。

1.2 量子遗传算法的收敛性

研究者针对算法的收敛性[7]提出过很多种方法, 其中就有调整旋转角及其参数的方法。量子遗传算法通过量子门来更新下一代染色体, 量子门可根据具体问题进行选择。目前已有的量子门有很多种, 根据量子遗传算法的计算特点, 选择量子旋转门较为合适。 (αi, βi) 为染色体的第i个量子比特, θi为旋转角, 其大小和方向根据一个事先设计的调整策略而确定。公式如下:

旋转角的选择策略如表1所示。

旋转角θi=s (αiβi) Δθ, s (αiβi) 和Δθ分别代表旋转的方向和角度, 其值根据表1的选择策略确定。该调整策略是将个体qjt当前的测量值的适应度f (xi) 与该个体当前的目标值f (bi) 的适应度值进行比较, 如果f (x) >f (b) , 则调整qjt中相应位量子比特 (xi≠bi) , 使得几率幅对 (αi, βi) 向着有利于xi出现的方向演化;反之, 如果f (x)

上文已经提到量子遗传算法是通过量子旋转门[10]来产生下一代染色体。量子旋转门亦可采用下式:

其中, θ为旋转角度, 其取值为θ=ω*f (αi, βi) , ω是一个与算法收敛速度有关的系数, 如果ω取值很大, 那么算法搜索网格就会很大, 容易出现早熟现象即算法容易收敛于局部的极值点。如果ω取值太小, 算法速度太慢, 甚至可能会出现停滞状态。ω取值往往与适应度值有关。

2 通过实例研究收敛性

2.1 背包问题算法

常规应用于背包问题的量子遗传进化算法有一个修复的过程以确保背包容积的限制, 算法如下;

开始t←0

初始化种群Q (t)

对初始种群观察, 得到一组状态P (t)

修复P (t)

评估P (t)

从P (t) 中选择好的解到B (t) 中

当不满足终止条件时

t←t+1

通过测量Q (t-1) 的状态得到P (t)

修复P (t)

评估P (t)

更新Q (t)

从B (t-1) 和P (t) 中选择好的解到B (t) 中

从B (t) 中选择最好的解b

当满足条件时局部或者全局的将b或bjt放置B (t) 中

结束

2.2 引入惩罚函数

本文在上述算法中引入惩罚功能, 则价值f (x) 表示为:

其中, Pen (x) 起到惩罚功能, 本文选用了以下两种惩罚函数:

其中, ρ是装进背包中所有物体的价值除以质量的值中最大的一项。

为了让量子遗传进化算法适时的结束, 因此需要一个终止条件。最优解概率表示如下:

并且:

则终止条件描述如下:

其中, 0<γ0<1, γ0对算法处理时间影响很大, 表2为在500个物品的背包问题中改变γ0观察其对终止状况的影响。

由表2知, 如果γ0≥0.1, 所有结果趋近相同γ0=0.9, 但是在γ0=0.9处大概是在γ0=0.1处的2.5倍。

为了设计一个新的终止标准, 量子比特收敛Cb被定义如下:

或者;

其中, q是量子比特个体, (αi, βi) 是第i个量子比特, 则收敛条件可以写成:

如果Cav为0.99, 则表示99%的个体趋近于正解, 表3说明了γ的改变。

2.3实验结果

如图3所示, 横坐标为进化的代数, 纵坐标为平均适应度值, 其中的上部分曲线为使用随机修复的量子遗传算法, 中部分曲线为使用线性惩罚的量子遗传算法, 下部分曲线为使用对数惩罚的量子遗传算法。通过引入结束条件, 算法都提前得到了最优解, 使用修复方法的解适应度值2940更好, 并且找到最优解的速度更快, 使用线性惩罚函数的算法其次, 使用对数惩罚函数的算法最优解较差, 速度也最慢, 中间还甚至产生了几个不合格的解。

3 结束语

本文对遗传算法及量子遗传算法进行了介绍, 量子遗传算法通过量子旋转门替代遗传算法的选择、交叉、变异来更新染色体, 其收敛性远远优于遗传算法。本文提及了几种常用于改进量子遗传算法收敛性的方法, 并通过背包问题实例观察引入惩罚函数及结束条件对收敛性的影响, 并得出结论:引入结束条件可以提前结束算法得到最优解, 引入线性惩罚函数后算法的收敛性要优于引入对数函数后的算法, 但是不如使用随机修复的算法更快, 获得的最优解更好。

参考文献

[1]杨俊安, 庄镇泉.量子遗传算法研究现状[J].计算机科学, 2003, 30 (11) :13-15.

[2]张葛祥, 李娜, 金炜东, 等.一种新量子遗传算法及其应用[J].电子学报, 2004, 32 (3) :476-479.

[3]雷英杰, 张善文, 李续武, 等.MATLAB遗传算法工具箱及应用[M].西安电子科技大学出版社, 2005.

[4]Kuk-Hyun Han, Jong-Hwan Kim.Genetic Quantum Algorithm and its Application to Combinatorial Optimization Problem[Z].2000.

[5]Hollot C, Misra V, Towsley D, et al.A control theoretic analysis of RED[C].Proc IEEE INFOCOM, Alaska, 2001.

[6]于洋, 查建中, 唐晓君.基于学习的遗传算法及其在布局中的应用[J].计算机学报, 2001 (12) :1242-1249.

[7]李敏强, 寇纪淞, 等.遗传算法的基本理论与应用[M].北京科学出版社, 2002.

[8]李斌, 谭立湘, 邹谊.量子概率编码遗传算法及其应用[J].电子与信息学报, 2005 (5) :805-810.

[9]Kuk-Hyun Han.Quantum-Inspired Evolutionary Algorithms With a New Termination Criterion, H_Gate, and Two-Phase Scheme[Z].2004.

[10]Quantum-Inspired Evolutionary Algorithm for a Class of Combinatorial Optimization[Z].2002.

差分遗传算法收敛性研究篇2

关键词：遗传算法,差分遗传算法,差分进化

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.

遗传算法的收敛性研究篇3

遗传算法[1] (Genetic Algorithm, GA) 是由美国J.Holland教授和他的学生于1975建立起来的, 主要思想是模拟生物进化中“适者生存”的规律。在解决多参数和非线性问题中, 传统的优化方法不但效率低, 而且有可能得不到结果。遗传算法具有极强鲁棒性和很高的搜索能力, 为解决这类问题提供了一种有效的信息途径, 其强大的搜索能力和突出的优点, 受到人们越来越多的重视。但遗传算法也有自己的不足之处, 其中之一就是早熟收敛 (也称未成熟收敛) 问题, 也是目前最难处理的关键问题。早熟收敛使算法进入局部最优解, 而遗传算法的一些优良性能将无法完全体现。本文深入分析产生早熟现象的原因, 并提出防止早熟收敛的一些措施。

2 遗传算法实现原理

遗传算法模拟生物进化的过程, 设计合理的编码方法将各类实际问题转换为染色体形式的表示方式, 并利用复制、交叉、变异等遗传算子的操作, 经过对逐代解的优胜劣汰, 最终搜索到问题的全局最优的解决方案[2,3]。

遗传算法步骤中的两个关键问题是编码方法和遗传算子的设计。它把需要解决问题的参数编成某种数制的编码, 如二进制或十进制编码, 这种编码我们把它称它称为基因, 若干基因组合就成为一个染色体, 每一个染色体对应问题的一个解决方案, 据此可执行相应的复制、交叉和变异算子的操作[4]。

(1) 复制算子

复制算子任务是按某种方法从父代群体中选取一些个体, 遗传到下一代群体。复制算子按某一概率在群体中成对选择个体, 个体选择的概率与其适应度值成正比, 适应度值高的个体, 被遗传到下一代群体中的概率就大。其在选择算子的操作过程中, 首先根据特定的适应值函数计算方法得到群体中所有个体的适应值, 依一定概率选择需复制的个体, 然后按指定的选择方法确定优良个体。个体复制的分配方法包括按比例的适应度分配、基于排序的适应度分配等方法。

(2) 交叉算子

所谓交叉算子就是将两个相互交配的染色体以某种方式 (点式交叉、基于位置交叉) 相互交换部分基因, 产生两个新的个体。交叉算子可以防止某些遗传信息不会被丢失, 其交叉过程就是产生新个体的过程。交叉运算在遗传算法中新个体的产生起着关键的作用, 是区别于其他进化运算的重要特征。

(3) 变异算子

变异是指在群体中随机选择一个个体, 以较小的概率改变某部分基因, 用新的基因替换原有基因, 改变原个体的编码结构, 实现群体的多样性。

利用复制算子将一些适应度值高的优良的个体遗传到下一代群体中, 体现出自然界优胜劣汰的规律;利用交叉算子进行模式重组, 不但继承了父代个体的优良基因, 而且在一定程度上能够维持群体的多样性;利用变异算子进行模式突变, 能够进一步保证群体的多样性。群体中的个体经过复制、交叉、变异一系列操作, 逐步向较好的方向进化, 最终得到问题的最优解。

3 遗传算法的求解步骤

遗传算法求解步骤如下:

(1) 一组第0代的初始的候选解群体的生成。

(2) 使用复制算子操作生成复制后代。

(3) 根据交叉概率, 将交叉算子作用于候选解群体, 个体随机两两配对, 生成新的候选解。

(4) 根据变异概率, 对步骤 (3) 中生成的候选解群进行变异操作, 形成新一代的候选解群体。

(5) 计算群体中各个候选解的适应值, 如果候选解不满足算法终止条件, 返回步骤 (2) 否则结束算法。

遗传算法的操作流程图如图1所示。

4 遗传算法的早熟问题

4.1 早熟现象

“早熟”是指遗传算法早期, 在种群中出现了超级个体, 该个体的适应值将会大大超过当前种群的平均个体适应值∑fi/N, 从而使得该个体很快在种群中占有绝对的比例, 使算法较早收敛于局部最优点的现象[5]。早熟收敛问题表现为会使接近最优解的个体总是被淘汰和群体中所有个体都陷入同一极值而停止进化。群体中个体结构的多样性急剧减少是遗传算法中的较为突出的问题之一, 在找到最优解或满意解之前, 遗传算法希望群体中个体结构保持多样性, 搜索不断进行。早熟收敛与局部极小值问题有很大的不同, 早熟收敛并不一定在局部极小点出现, 而且早熟是难预见是否会出现, 它是随机性产生的。

4.2 早熟产生的主要原因

早熟产生的主要原因主要有以下几点:

(1) 遗传算法在进化过程中, 会产生一些超常的个体, 这些个体由于竞争力非常强, 常常控制着选择运算过程, 结果只得到算法某个局部最优解, 并非全局最优解, 即遗传欺骗。

(2) 在理论上, 遗传算法中的交叉、复制、变异操作都是精准的, 具有搜索整个空间的能力, 但是在实现时这个要求很难达到。

(3) 由于遗传算法中存在随机取样误差和随机选择误差, 因此当所选的串并非相似子集的代表时, 就会存在误差。如果选择的个体没有按期望的概率进行, 选择误差在所难免。

上述三个方面都有可能过早地丢失群体中个体的多样性, 结果获得只是局部最优解, 而非全局最优解, 即产生早熟收敛现象。当经过多代进化, 算法进行到后期, 种群中超级个体占据了绝大多数, 传统的交叉操作已不能产生新个体, 失去了作用, 而变异操作虽然能够为补充新个体, 但发生的概率毕竟非常小。

通常, 种群规模较大, 可以增加优化信息, 阻止早熟收敛的发生, 但是会增加计算量, 以致收敛时间过长, 收敛速度较慢;种群太小则不能提供足够的采样点, 造成算法性能较差。复制操作使适应度高的个体能够以更大的概率生存, 提高了遗传算法的全局收敛性。交叉操作产生新的个体是在解空间中进行有效搜索, 当交叉概率太大, 种群中个体更新快, 会导致适应度高的个体很快被破坏掉;当概率过小时, 很少会进行交叉操作, 使搜索停滞不前, 造成算法的不收敛。

5 早熟收敛的防止

知道早熟产生的原因之后, 怎样防止早熟收敛现象, 寻找到满意解或最优解呢?解决的方法主要有:

5.1 配对策略

通常, 在物种的形成过程中有目的地选择配对个体, 合理的选择配对策略, 能有效地保持群体的多样性, 防止不相似的个体进行配对[6]。不同种族在生物界一般不会杂交的, 原因是基因结构不同, 会发生互斥作用。因此, 大多数是同种或近种相配, 保存和发扬一个种族的优良特性。Goldberg的共享函数是一种间接匹配策略, 在一定程度上限制了占统治地位的物种内相互匹配。Eshelman提出一种防止相似个体配对的策略, 随机配对参与交配的个体, 对参与配对的个体而言, 只有它们间的海明距离超设定的阈值时, 参与的交配的个体才允许进行交配[7]。在交配时, 可将初始群体海明距离的期望平均值作为阈值初值时, 随着迭代过程的不断深入, 可以逐步减小阈值。在某种程度上, 匹配策略虽然可以维护群体的多样性, 但在交叉操作中会破坏很多模板, 因此也有一定的副作用。

5.2 重新启动法

当遗传算法在搜索过程中由于碰到早熟收敛问题而停滞不前时, 可随机选择一组初始值重新进行遗传算法操作, 即重新启动法。如果每次执行遗传算法后陷入早熟收敛的概率为M (0≤M<1) , 那么经过n次独立的遗传算法操作后, 可避免早熟收敛的概率为F (n) =1-Mn, 随着n的不断增大, F (n) 将渐近于1。但是, 在收敛概率M很大的情况下, 每次执行时间都很长和优化对象很复杂时, 则不宜采用重新启动法。

5.3 重组策略

重组策略就是利用交叉操作产生与其父辈不同的个体, 在某种程度上, 使产生的群体更具有多样性。一种方法是动态改变适应度函数和增加交叉操作的使用频率, 如共享函数方法, 使交叉操作更具有活力;另一种方法是把交叉点选在具有不同值的位的个体上实现群体多样性。当父辈个体存在两位以上不同时, 新产生的子代个体就与父辈不相同。遗传算法中使用具有破坏性的交叉算子时能较好地维持群体的多样性, 如均匀交叉算子。由于该算子交叉近一半的不同位, 因此保留的模板比单点或两点交叉要少得多。总之, 重组策略是通过交叉操作使用频率和交叉点来维持群体的多样性, 对采用随机选择配对个体进行交叉操作有着特定的意义, 但对成比例选择方式, 则效果不一定明显。

5.4 替代策略

匹配策略是在复制阶段通过某种策略来维持群体的多样性, 重组策略是交叉阶段性按照某种策略来维持群体的多样性, 而替代策略则是由复制, 交叉产生的个体中选择某个个体进入新一代群体。De Jong用新产生的个体去替代父辈中类似的个体, 采用的是排挤模式。Syscuda和Whiteley是把父辈各个个体均不相似的新个体添加到群体中[8], 与De Jong的策略类似。这种替换策略不足之处是在交叉操作很多模板被破坏, 有一定的负面影响, 不过与重组策略相比较, 这种影响还是非常小的。

早熟收敛是遗传算法迭代过程中可能发生的问题, 在实际应用中, 需结合具体问题分析, 采用一种或多种方法来设计遗传算法, 消除早熟收敛现象, 使遗传算法的搜索能力得到更好的保证, 在实际应用得到更好地效果。

参考文献

[1]Holland J H.Adaptation in Nature and Artificial Systems[J].2nd ed.Cambridge:MIT Press, 1992:91-92.

[2]Goncalves J F.A hybrid genetic algorithm for job shop scheduling problem[J].European Journal of Operational Research, 2005, 167 (1) :77-95.

[3]陈国良, 王煦法, 庄镇全.遗传算法及其应用[M].北京:人民邮电出版社, 1996:121-125.

[4]曾建潮, 崔志华.自然计算[M].北京:国防工业出版社, 2012:12-18.

[5]曳永芳, 杜永清, 行小帅.一种抑制早熟收敛的改进遗传算法[J].山西师范大学学报 (自然科学版) , 2010 (2) :24-27.

[6]谭丹丹, 曹斌, 刘俊.一种基于配对的改进遗传算法[J].计算机应用, 2007, (12) :45-48.

[7]王春水, 肖学柱, 陈汉明.遗传算法的应用举例[J].计算机仿真, 2005:155-157.

遗传算法的收敛性研究篇4

微粒群优化算法 (ParticleSwarm Optimization, PSO) 1995年由Kennedy和Eberhart率先提出, 它借鉴了鸟群或鱼群捕食过程的社会行为, 是一种有别于遗传算法的并行进化计算技术。经过近10年的发展, PSO已广泛应用于函数优化、人工神经网络训练、模糊系统控制等领域, 成为目前进化计算研究的一个新的热点[1]。1998年Shi等引入惯性权重形成了目前的PSO基本算法, 并对PSO模型中的参数选择作了较详尽的阐述[2]。1999年Kennedy及Suganthan分别从邻域算子角度分析了PSO算法的性能[3,4]。2002年Clerc和Kennedy给出了PSO算法较完整的理论分析[5]。2003年Trelea在确定情形下研究了PSO算法的收敛性及参数选择[6]。在此分析的基础上, 本文就具有随机数的PSO算法的收敛性进行了较严密的分析, 同时给出了参数选择的范围。

1PSO优化算法

标准的PSO算法可描述如下

$\overset{ϖ}{v}_{k + 1} = a \otimes v_{k} + b_{1}^{μ} \otimes (p_{k}^{b} - x_{k}^{ϖ}) + b_{2}^{μ} \otimes (p_{k}^{g} - x_{k})$ (1)

xῶk+1=c⨂xῶk+d⨂vῶk+1 (2)

这里vῶk表示第k次迭代速度向量, xῶk表示第k次迭代微粒所在的位置向量, x $_{k}^{ϖ b}$ 表示到第k次迭代为止微粒的最好位置向量, p $_{k}^{ϖ g}$ 表示到第k次迭代为止所有微粒的最好位置向量, aῶ表示惯性权重向量, 使微粒保持运动惯性使其有扩展搜索空间的趋势, 有能力搜索新的区域, b $_{1}^{μ}$ 和b $_{2}^{μ}$ 表示所有分量随机取正值的随机数向量, ⨂表示两个向量对应分量相乘的向量乘法。由式 (1) 和式 (2) 易见, 每个分量的更新都是彼此独立的, 各个分量之间只是通过目标函数联系在一起, 因此, 不失一般性, 下面先就一组情形对PSO算法进行分析。一维情形下PSO算法的迭代公式为:

vk+1=avk+b1 (p $_{k}^{b}$ -xk) +b2 (p $_{k}^{g}$ -xk) (3)

vk+1=cxR+dxk+1 (4)

为了便于对PSO算法进行分析, 取

b=b1+b2 (5)

$p_{k} = \frac{b_{1} p_{k}^{b} + b_{2} p_{k}^{g}}{b} = λ p_{k}^{b} + (1 - λ) p_{k}^{g}$ (6)

这里 $λ = \frac{b_{1}}{b}$ 为在 (0, 1) 内随机取值的随机数, 于是b1=λb, b2= (1-λ) b, 这样无论b是否是随机数, 都可以保证b1, b2随机取值。在这里为了便于讨论, 只考虑b取常数情形。从而 (3) 式、 (4) 式变成了

vk+1=avk-bxk+bp $_{k}^{}$ (7)

xk+1=cxk+dvk+1 (8)

这里a, b, c, d是确定的实常数。类似于文献[6]的讨论, 这四个参数只有两个真正有用, 而另外两个可以固定, 下面针对c=d=1和c=1两种情形讨论PSO算法的收敛性问题。为此首先给出如下几个引理。

引理1 矩阵级数 $\sum_{k = 0}^{\infty} A^{(k)}$ 为绝对收敛的充要条件是 $\sum_{k = 0}^{\infty} ∥ A^{(k)} ∥$ 为收敛级数。

这里 $∥ A ∥ = \sqrt{λ_{1}} ‚ λ_{1}$ 为A*A的最大特征值, A*为A的共轭转置。

引理2 如果A= (aij) n×n的所有特征值的模均小于1, 则 $\lim_{k \to \infty} A^{k} = 0$ 。

引理3 设A= (aij) n×n, 如果A*A的所有特征值的模均小于1, 则矩阵级数 $\sum_{k = 0}^{\infty} A^{k}$ 绝对收敛。

引理4 设A∈Cn×n, 则A的谱半径ρ (A) 不大于A的任何一种具有相容性的范数值, 即ρ (A) ≤‖A‖。

2收敛性分析

2.1c=d=1时PSO算法收敛性分析

此时, 若令

$y_{k} = (\begin{array}{l} x_{k} \\ v_{k} \end{array}) ‚ A = (\begin{array}{l} 1 - b a \\ - b a \end{array}) ‚ B_{k} = (b b)^{Τ} p_{k}$

, 由 (7) 式和 (8) 式得PSO的矩阵表达形式为

yk+1=Ayk+Bk (9)

定理1 设序列{yk}由PSO算法迭代公式 (9) 产生的迭代序列, 序列{pk}有界, 如果a2<2b (1-b) , 则由PSO算法迭代公式 (9) 产生的迭代序列{yk}收敛, 即序列{xk}收敛到平稳点[6]。

证明由yk+1=Ayk+Bk得:

$y_{k + 1} = A^{k + 1} y_{0} + \sum_{i = 0}^{k} A^{i} B_{k - i}$ (10)

因此由引理1、引理2、引理3和引理4易知, 只要ATA的特征值都小于1, 序列{yk}必收敛。由迭代公式易知vk→0 (k→∞) , 即序列{xk}收敛到平稳点。

下面只需证明当a2<2b (1-b) 时, ATA的特征值都小于1即可。

$\begin{array}{l} | λ Ι - A^{Τ} A | = | \begin{array}{l} λ - (1 - b)^{2} - b^{2} 2 a b - a \\ 2 a b - a λ - 2 a^{2} \end{array} | = \\ λ^{2} - (2 a^{2} + 2 b^{2} - 2 b + 1) λ + a^{2} 。 \end{array}$

$\begin{array}{l} 又 (2 a^{2} + 2 b^{2} - 2 b + 1)^{2} - 4 a^{2} = \\ (2 a^{2} + 2 b^{2} - 2 b + 1 - 2 a) (2 a^{2} + 2 b^{2} - 2 b + 1 + 2 a) = \\ [2 (a - \frac{1}{2})^{2} + 2 (b - \frac{1}{2})^{2}] [2 (a + \frac{1}{2})^{2} + 2 (b - \frac{1}{2})^{2}] > 0 。 \end{array}$

故a, b取任何值时, ATA均有正的实特征值, 其特征值为:

$λ_{1, 2} = \frac{2 a^{2} + 2 b^{2} - 2 b + 1 \pm \sqrt{(2 a^{2} + 2 b^{2} - 2 b + 1)^{2} - 4 a^{2}}}{2}$ 。

由于 $2 a^{2} + 2 b^{2} - 2 b + 1 = 2 a^{2} + 2 (b - \frac{1}{2})^{2} + \frac{1}{2} > 0$ 。

所以, 当

$\frac{2 a^{2} + 2 b^{2} - 2 b + 1 + \sqrt{(2 a^{2} + 2 b^{2} - 2 b + 1)^{2} - 4 a^{2}}}{2} < 1$ 。

即a2<2b (1-b) 时, ATA的特征值都小于1。证毕。

2.2c=1时PSO算法收敛性分析

此时yk和pk与2.1相同, 而矩阵, 由 (7) 式、 (8) 式得PSO算法的矩阵表达形式为

yk+1=Ayk+Bk (11)

定理2 设序列{yk}由PSO算法迭代公式 (11) 产生的迭代序列, 序列{pk}有界, 如果a2d2+b2d2+b2-2bd<0, 则由PSO算法迭代公式 (11) 产生的迭代序列{yk}收敛, 即序列{xk}收敛到平稳点[6]。

证明类似于定理1的证明, 只需证明a2d2+b2d2+b2-2bd<0时, ATA的特征值都小于1即可:

$\begin{array}{l} | λ Ι - A^{Τ} A | = | \begin{array}{l} λ - (1 - b d)^{2} - b^{2} a b - (1 - b d) a d \\ a b - (1 - b d) a d λ - (a d)^{2} - a^{2} \end{array} | = \\ λ^{2} - [(1 - b d)^{2} + a^{2} + b^{2} + a^{2} d^{2}) λ + a^{2} 。 \end{array}$

于是ATA的特征值为:

$λ_{1, 2} = \frac{(1 - b d)^{2} + a^{2} + b^{2} + a^{2} d^{2} + \sqrt{[(1 - b d)^{2} + a^{2} + b^{2} + a^{2} d^{2}]^{2} - 4 a^{2}}}{2} 。$

由ATA为实对称阵知

$[(1 - b d)^{2} + a^{2} + b^{2} + a^{2} d^{2}]^{2} - 4 a^{2} \geq 0$ , 从而当

$\frac{(1 - b d)^{2} + a^{2} + b^{2} + a^{2} d^{2} + \sqrt{[(1 - b d)^{2} + a^{2} + b^{2} + a^{2} d^{2}]^{2} - 4 a^{2}}}{2} < 1$ 。

即a2d2+b2d2+b2-2bd<0时, ATA的特征值都小于1。证毕。

参考文献

[1]杨燕, 靳蕃, Kamd M.微粒群算法研究现状及其进展.计算机工程, 2004; (21) :3—4

[2]Shi Y, Eberhart R C.A modified particle swarm optimization.Pro IEEE International Conference on Evolutionary Computation, Anchor-age, 1998;69—73

[3]Kennedy J, Small worlds and mega-minds:effeets of neighborhood to-pology on particle swarm performance.Proc of the IEEE Congress of Evolutionary Computation, 1999;3:1938

[4]Suganthan P N.Particle swarm optimizer with neighborhood operator.Proc of the IEEE Congress of Evolutionary Computation, 1999;3:1958

[5]Clerc M, Kennedy J.The particle swarm:explosion stability and con-vergence in a multi-dimensional complex space.IEEE Trans Evolu-tion Comput, 2002;6 (1) :58—73

【遗传算法的收敛性研究】推荐阅读：

遗传算法研究概述07-19

函数优化的遗传算法08-31

遗传基因算法08-21

遗传禁忌算法09-01

元胞遗传算法05-11