快速收敛算法

快速收敛算法（共9篇）

快速收敛算法 篇1

0 引言

所谓遗传算法收敛的复杂条件,是指约束条件苛刻、可行解的可行区域狭窄的条件。降低发动机颤振故障发生的几率,对发动机压气机转子的制造、安装作出一系列的限制措施是必要的。其中,最重要的两个问题是如何控制叶片静质量矩和叶片固有频率。除了在制造时采取措施以外,在安装时降低叶片静质量矩和保证转子叶片具有合格的固有频率也是必不可少的。这就需要对叶片安装施加必要的约束条件。在复杂条件下,人工叶片排序效率很低。

利用计算机求解此类问题时,叶片排序问题被看作是一个组合优化问题。采用常规的组合优化求解叶片排序问题,算法复杂,对于某些“恶劣”的数据可能求不出正确的排序结果。遗传算法在求解组合优化问题上具有很大的优势,但是当叶片排序条件较为复杂时,收敛速度慢、甚至不能求出优化排序结果;适应度函数设计也较为困难。为解决这个问题,本文利用改进遗传算法,在此基础上进行了适应度函数设计,并采用植入种子染色体导引法和内外交换法进行排序,所得结果正确,收敛速度快。

1 叶片排序约束条件

某航空设备制造厂根据实际工作需要提出了下述叶片安装条件:

1)整级中的每个叶片与相邻叶片应具有频率差,且各叶片频率应为一大一小锯齿型分布,不允许连续增大或减小。即为“错频”排列。

2)在整级叶片中,其中三对叶片1～2、8～9、16～17的频率差应不小于11Hz,且应比其它的相邻叶片对的频率差高出不小于2Hz。允许这三对叶片的频率差比这三对中的任一叶片与相邻叶片的频率差高出不小于2Hz。

3)整级叶片中,相邻的4个叶片之间的三个频率差不得完全相同。

4)相邻叶片之间频率差应不小于6Hz,允许在互不相邻的三处,与相邻叶片频率之差不小于4Hz。

5)整级叶片的最大频率与最小频率之差应不小于14Hz。

6)整级叶片中的每六分之一位置(即1～4号、5～8号、9～12号、13～16号、17～20号、21～24号)上的叶片静质量矩的和之差应当不大于138g·cm,相邻象限叶片静质量矩的和之差应当不大于115g·cm。

7)压缩机全部叶片共分为3级,每级叶片都必须符合上述条件。为了生产率,单级叶片所提供的备选叶片数量不得大于26枚。程序运行时,一次最多可以输入100枚备选叶片,至少输出4组叶片数据。

8)非可行解可行化。如果叶片数据确实“恶劣”,有一组输出数据不是可行解。则应给出最佳备选叶片的频率和静质量矩范围(也就是如果有一组输出叶片不合格,这时,更换里面的一枚或几枚叶片,则更新后的叶片组是合格的。此时,应当给出更换叶片的频率和静质量矩的值)。

上述约束条件,给出了叶片优化排序的多个目标。为了方便求解,把3级叶片逐次求解,因此,三级叶片可以采用同一目标函数。因此,一个多目标优化问题转化为三个单目标函数求解问题。

2 单级叶片目标函数

本文的研究目标就是要求排列在180°相对位置的两片叶片的静质量矩差的绝对值之和最小,即

式中:k为叶片个数的一半,(mr)i为第i个叶片的静质量矩(g·mm)。因此:目标函数设计为:

3 适应度函数设计

适应度函数的优良与否在很大程度上影响程序的收敛速度。在构造遗传算法时,处理约束条件主要有三种方法:搜索空间限定法、惩罚函数法、可行解变换法。本文采用罚函数法。本文将约束条件作为罚函数包含到适应度函数中去,从而将约束优化问题转换为无约束优化问题进行求解。此时适应度函数可以写为:

其中,r1、r2、r3、r2为罚函数尺度系数,f(x)为目标函数,Hz1为整级叶片中相邻叶片的频率差。Hz2是约束条件中(2)所允许的三对大频率差值与其他相邻叶片频率差值的频率差。

4 种群初始化

由于条件要求在100枚叶片里同时输出4组数据,因此本文把4组数据作为4条染色体,每条染色体代表一组叶片。程序同时对4组叶片优化排序。但是,在种群初始化时,一次只能产生一条染色体。这样做的结果是:最先产生的染色体把性状好的叶片挑选了,留到最后的是性状“恶劣”的叶片,这样很可能最后一组得不到可行解,造成资源浪费。为了避免这个问题,我们先来看单级叶片染色体的产生办法:

在单级叶片中,由于对1和2号位、8号和9号位、16和17号位的频率差要求严格,因此,为了加快收敛速度,在每条染色体中,本文先在原始数据中选取三个频率最大的叶片,随机放入1、9、17号位置;然后,选取三个频率最小的叶片,随机放入2、8、16号位置。这样,每一级叶片中,还有18个位置没有安放叶片。原始数据的剩余叶片,程序自动按照频率把它分成两部分,叶片频率大于平均频率的为一部分,小于平均频率的为另一部分。利用轮盘赌法按照一大一小的原则,先从大频率数据组里面随机抽取一个,再从小频率数据组里面随机抽取一个。以此类推,安装完毕一条染色体的剩余基因位置。利用同样方法,产生其他染色体。通过在种群初始化时,实施人工干扰,间接减少了排序的约束条件。

由单级叶片染色体的产生办法可知:每条染色体在挑选叶片时,总是把频率最大和最小的叶片优先选取。因此,本文在种群初始化时,先选取12枚频率最大的和12枚频率最小的叶片。在产生每一条染色体时,其关键位置的叶片都从这两组叶片里随机选取。其余叶片按照单级叶片办法产生。这样就较好的保证了最后一条染色体的叶片性状。

这样做的结果是产生了4个种群。程序同时对4个种群进行优化。

5 遗传算法编码与算子

5.1 编码方式

常用的编码方式包括二进制编码、浮点数编码、顺序编码、布尔矩阵编码等。为了调试程序的方便,本文采用十进制编码方式。本文把一级叶片中的总叶片数目(24个叶片)作为作为一条染色体,即每条染色体含有24个基因,每个基因包含一片叶片的相关信息。染色体上,第一号基因位置表示第一枚叶片安装位置。

5.2 选择算子

从适应度函数的设计上可以看出适应度大的个体优于适应度小的个体,这与一般遗传算法中适应度大的个体优于适应度小的个体一致,因此适于直接采用基于比例的适应度分配方法。本文采用轮盘赌选择法。

5.3 交叉算子

本文的编码方式允许一个个体的染色体编码中在不同位置出现相同的基因码,如果出现相同的基因码,则表明有两个或多个叶片的相关参数是相同的,这与实际工作情况是相符合的。本文采用多点交叉。但并非完全随机交叉。由于在种群初始化时的人为因素,每个染色体中的1～2、8～9、16～17号位置基因不能和其他位置基因交叉。

5.4 变异算子

变异算子较为简单,对个体内的基因排列按一定的变异率进行随机交换即可。同样,每个染色体中的1～2、8～9、16～17号位置基因不能和其他位置基因交换。只能相同性质的基因交换,即:1、9、17可以随机交换,2、8、16可以随机交换。

6 种子染色体

普通遗传算法程序,在多约束条件下,如果原始数据比较恶劣,容易陷入局部寻优。并且,一旦陷入局部寻优,很难跳出这个局部“陷阱”,从而影响收敛速度。为了加快收敛速度,本文采用了种子染色体导引法。即事先给定一个性状比较好的染色体作为种子,其作用是引导种群向最优点靠近。在多约束条件下,人工给出性状较好的染色体可行性不高。为了减少人工工作量,本文采用种群自动产生种子的方法。通常情况下,在程序运行时,把种群最大遗传代数作为程序循环次数。本文只设定较低的最大遗传代数。例如,设定100代,即程序循环100次。在程序初次运行时,把初始种群中适应度最大个体作为种子染色体。程序运行结束后,如果没有得到优化解,所产生的种群中适应度最大个体被用来当作下一次程序运行是的种子染色体。该种子染色体被植入下一次运行时的初始种群。通过植入种子染色体不仅能够引导种群向最优点靠近;而且,当种群遗传若干代后,种群变得过于庞大,从而影响运算速度,通过再一次种群初始化,可以有效解决这个问题。

7 内外交换法

染色体一旦产生,其交叉、变异等操作只能在染色体内部进行,不能再与外部数据进行数据交换。这不但造成剩余叶片资源浪费,也会使收敛速度变慢。本文用内外交换法解决了这个问题。即:在一个种群里,随机选取一条染色体。计算它的频率差和单元静质量矩之和等相关参数。如果叶片静质量矩的和之差大于138g.cm,或相邻象限叶片静质量矩的和之差大于115g.cm,则查找出静质量矩之和大的单元;然后,在这个单元里,查找一枚静质量矩最大的叶片,并记为big。此时,原始数据的剩余叶片里,查找一枚叶片,其静质量矩比big要小,并且其频率在代替big的频率后,新的频率差应符合上述约束条件;或者与big的频率相等。同样,查找一枚静质量矩最小的叶片,并记为small。在原始数据的剩余叶片里,查找一枚叶片,其静质量矩比small要大,在代替small后,其频率要求同上。实践证明,这种方法对解决陷入局部最优解问题行之有效。

8 非可行解可行化

如果有非可行解问题,则用虚拟叶片片法解决非可行解寻优问题。在初次种群初始化时,每枚叶片都是随机选取,并且只能选取一次。对非可行解叶片组,允许部分叶片可重复选取,等于增加了叶片数量。得到可行解后,有个别叶片在染色体里出现了两次。则该叶片参数即为待更新叶片的参数。

9 实例验证

给定一组叶片原始数据如表1所示。(因篇幅限制,只给出一组数据)。

在没有种子染色体引导和没有利用内外交换法的情况下,普通遗传算法,程序循环运行了25分钟,没有得出正确结果。在有种子染色体引导和利用内外交换法时,程序循环运行20分钟,得出正确结果如表2所示。

1 0 结论

程序运行结果表明:在多约束条件下,该程序收敛速度大为加快,并且运行结果正确。同时,以上算例证明,改进遗传算法在多约束和原始数据恶劣条件下,利用种子引导法和内外交换法并在种群初始化时施加人工干扰使程序收敛速度较快,结果准确。用此方法编制的程序实用性强。能有效解决在复杂条件下的多级叶片排序问题。

参考文献

[1]杨训.基于遗传算法的转子叶片优化排序[J].计算机仿真,2008,25(11).YANG Xun Optimum Arrangement of Rotor Blade Basedon Genetic Algorithms[J].simmulink of Computer 2008,25(11).

[2]彭国华.混合遗传算法在叶片排序问题中的应用[J].西南民族大学学报,32.PENG Gguohua Application of hybrid genetic algorithm inblade arrangement of engine[J].32.

[3]DeJong Ka An Analysis of the Behavior of a Classof Gentic Adaptive Systems[J].Dissertion AbstractsInternational,1975(10).

[4]Back T,Schwefel H P.An Over View of EvolutionaryAlgorithms for Paramater Optimization[J].EvolutionaryComputation,1999(1).

快速收敛算法 篇2

考虑基于Facchinei F等(1997)提出的解决非线性互补问题的非光滑牛顿算法的收敛性质.对该算法我们在较弱的条件下给出了一般性的全局收敛结果,改进了Facchinei F(1997)和Dan H(2002)文中的相关结果,作为这个定理的`推论,我们得到的迭代序列的每一个聚点x*或者是非线性互补问题的解或者是稳定点.最后,在局部误差界的条件下给出了超线性(二阶)收敛速度的证明.

作 者：马骋 阴志民 王长钰 MA Cheng YIN Zhi-min WANG Chang-yu 作者单位：马骋,王长钰,MA Cheng,WANG Chang-yu(曲阜师范大学运筹与管理学院,276826,日照市)

阴志民,YIN Zhi-min(济南市第五职业中专学校,250001,山东省济南市)

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

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

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.

快速收敛算法 篇4

本文针对非线性不等式约束优化问题,提出了-个可行内点型算法.在每次迭代中,基于积极约束集策略,该算法只需求解三个线性方程组,因而其计算工作量较小.在-般的.条件下,证明了算法具有全局收敛及超线性收敛性.

作 者：朱志斌 简金宝 ZHU ZHIBIN JIAN JINBAO 作者单位：朱志斌,ZHU ZHIBIN(桂林电子科技大学数学与计算科学学院,桂林,541004)

简金宝,JIAN JINBAO(广西大学数学与信息科学学院,南宁,530004)

量子遗传进化算法的收敛性研究 篇5

量子计算与遗传算法的结合量子遗传算法 (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.

快速收敛算法 篇6

遗传算法[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.

快速收敛算法 篇7

微粒群优化算法 (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算法可描述如下

$\stackrel{\text{ϖ}}{{\displaystyle \mathit{v}}}{}_{\mathit{k}+1}=\mathit{a}\otimes \mathit{v}{}_{\mathit{k}}+\mathit{b}{}_1^{\mathit{\mu }}\otimes (\mathit{p}{}_{\mathit{k}}^{\mathit{b}}-\mathit{x}{}_{\mathit{k}}^{\text{ϖ}})+\mathit{b}{}_2^{\mathit{\mu }}\otimes (\mathit{p}{}_{\mathit{k}}^{\mathit{g}}-\mathit{x}{}_{\mathit{k}})$ (1)

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

这里vῶk表示第k次迭代速度向量, xῶk表示第k次迭代微粒所在的位置向量, x${}_{\mathit{k}}^{\text{ϖ}\mathit{b}}$表示到第k次迭代为止微粒的最好位置向量, p${}_{\mathit{k}}^{\text{ϖ}\mathit{g}}$表示到第k次迭代为止所有微粒的最好位置向量, aῶ表示惯性权重向量, 使微粒保持运动惯性使其有扩展搜索空间的趋势, 有能力搜索新的区域, b${}_1^{\mu }$和b${}_2^{\mu }$表示所有分量随机取正值的随机数向量, ⨂表示两个向量对应分量相乘的向量乘法。由式 (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}=\lambda p{}_k^b+(1-\lambda )p{}_k^g$ (6)

这里$\lambda =\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 矩阵级数${\displaystyle \sum _{k=0}^{\infty }A}{}^{(k)}$为绝对收敛的充要条件是${\displaystyle \sum _{k=0}^{\infty }\parallel }A{}^{(k)}\parallel$为收敛级数。

这里$\parallel A\parallel =\sqrt{\lambda {}_1}‚\lambda {}_1$为A*A的最大特征值, A*为A的共轭转置。

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

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

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

2收敛性分析

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

此时, 若令

$y{}_k=\left(\begin{array}{l}x{}_k\\ v{}_k\end{array}\right)‚A=\left(\begin{array}{l}1-ba\\ -ba\end{array}\right)‚B{}_k=\left(bb\right){}^{\text{Τ}}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+{\displaystyle \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}|\lambda {\rm I}-A{}^{\text{Τ}}A|=\left|\begin{array}{l}\lambda -(1-b){}^2-b{}^{2}2ab-a\\ 2ab-a\lambda -2a{}^2\end{array}\right|=\\ \lambda {}^2-(2a{}^2+2b{}^2-2b+1)\lambda +a{}^2。\end{array}$

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

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

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

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

所以, 当

$\frac{2a{}^2+2b{}^2-2b+1+\sqrt{(2a{}^2+2b{}^2-2b+1){}^2-4a{}^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}|\lambda {\rm I}-A{}^{\text{Τ}}A|=\left|\begin{array}{l}\lambda -(1-bd){}^2-b{}^{2}ab-(1-bd)ad\\ ab-(1-bd)ad\lambda -(ad){}^2-a{}^2\end{array}\right|=\\ \lambda {}^2-[(1-bd){}^2+a{}^2+b{}^2+a{}^{2}d{}^2)\lambda +a{}^2。\end{array}$

于是ATA的特征值为:

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

由ATA为实对称阵知

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

$\frac{(1-bd){}^2+a{}^2+b{}^2+a{}^{2}d{}^2+\sqrt{\left[(1-bd){}^2+a{}^2+b{}^2+a{}^{2}d{}^2\right]{}^2-4a{}^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

快速收敛算法 篇8

禁忌搜索算法(TS)由Glover教授于1986年正式提出。禁忌搜索算法与模拟退火、进化计算、蚁群算法、粒子群优化、人工免疫系统等一样,都属于自然计算的研究范畴。禁忌搜索算法是智能优化算法中的一种,是人工智能的一种体现。是对人类智力过程的一种模拟[1-2]。迄今为止,TS算法在组合优化、生产调度、机器学习、电路设计和神经网络等领域取得了很大的成功,近年来又在函数全局优化方面得到较多的研究,并大有发展的趋势。

在TS算法中,不同的参数设定将会影响算法求解的效率和最优解的精度,因此本文以多极值一维函数为例,对TS算法参数设定进行实验,以找出算法求解参数的较佳组合[3,4]。在MATLAB工具开发环境下,讨论算法的参数选择,通过在以上三种终止准则下的比较和研究,总结了它们的差异和优缺点。

2 禁忌搜索算法

禁忌搜索算法是对局部邻域搜索的一种扩展,是一种全局逐步寻优算法,是对人类智力过程的一种模拟。TS算法引入一个灵活的存储结构和相应的禁忌准则来避免迂回搜索,并通过藐视准则来赦免一些被禁忌的优良状态,进而保证多样化的有效探索以最终实现全局优化[5]。

2.1 禁忌搜索算法的局部邻域搜索

局部邻域搜索是基于贪婪思想持续地在当前解的邻域中进行搜索,虽然算法通用易实现,且容易理解,但其搜索性能完全依赖于邻域结构和初始解,尤其容易陷入局部极小而无法保证全局优化性。针对局部邻域搜索,为了实现全局优化,可尝试的途径有:以可控性概率接受劣解来逃逸局部极小;扩大邻域搜索结构;多点并行搜索;变结构邻域搜索;另外,就是采用TS的禁忌策略尽量避免迂回搜索,是一种确定性的局部极小突跳策略。

2.2 禁忌搜索算法的相关参数

禁忌搜索是人工智能的一种体现。禁忌搜索最重要的思想是标记对应已搜索的局部最优解的一些对象,并在进一步的迭代搜索中尽量避开这些对象,而不是绝对禁止循环,从而保证对不同的有效搜索途径的探索。禁忌搜索涉及到邻域(neighborhood)、禁忌表(tabu list)、禁忌长度(tabu 1ength)、候选解(candidates)、藐视准则(aspiration criterion)等概念[6]。简单的禁忌搜索是在邻域搜索的基础上,通过设置禁忌表来禁忌一些已经历的操作,并利用藐视准则来奖励一些优良状态,其中邻域结构、候选解、禁忌长度、禁忌对象、藐视准则、终止准则等是影响禁忌搜索算法性能的关键。

2.3 禁忌搜索算法流程

简单TS算法的基本思想是:给定一个当前解和一种邻域,然后在当前解的邻域中确定若干候选解;若最佳候选解对应的目标值优于“best so far”状态,则忽视其禁忌特性,用其替代当前解和“best so far”状态,并将相应的对象加入禁忌表,同时修改禁忌表中各对象的任期;若不存在上述候选解,则选择在候选解中选择非禁忌的最佳状态为新的当前解,而无视它与当前解的优劣,同时将相应的对象加入禁忌表,并修改禁忌表中各对象的任期;如此重复上述迭代搜索过程,直至满足终止准则[7]。

算法具体步骤可描述如下:

(1)给定算法参数,随机产生初始解x,置禁忌表为空。

(2)判断算法终止条件是否满足?若是,则结束算法并输出优化结果;否则,继续以下步骤。

(3)利用当前解的邻域函数产生其所有(或若干)邻域解,并从中确定若干候选解。

(4)对候选解判断藐视准则是否满足?若成立,则用满足藐视准则的最佳状态y替代x成为新的当前解,即x=y,并用与y对应的禁忌对象替换最早进入禁忌表的禁忌对象,同时用y替换“best so far”状态,然后转步骤6;否则,继续以下步骤。

(5)判断候选解对应的各对象的禁忌属性,选择候选解集中非禁忌对象对应的最佳状态为新的当前解,同时用与之对应的禁忌对象替换最早进入禁忌表的禁忌对象元素。

(6)转步骤(2)。

3 禁忌搜索算法优化函数设计方案

3.1 适配函数的定义

以适配值或其变化为禁忌对象则将处于同一适配值的状态视为相同状态,这在函数优化中经常采用。由于一个值的变化隐含着多个状态的变化,因此这种情况下的禁忌范围相对于状态的变化将有所扩大。目标函数的任何变形都可以作为适配值函数。因为通信系统中传输信号多为一维多极值余弦函数的变形,故本文的目标函数多极值一维函数,其图像如图2.1:

本文目标函数为一个有具有普遍性的信号形式,有研究意义,故无需任何变形,故直接用目标函数作为适配值函数,对适配值函数的优化即是寻找最大值的过程。

3.2 禁忌对象的设计

禁忌对象是被置入禁忌表中的那些变化元素,其主要目的是为了尽量避免迂回搜索而多搜索一些有效的搜索途径。通常可选取状态本身、状态分量、适配值的变化作为禁忌对象。本文将适配值的变化作为禁忌对象。

3.3 邻域结构的设计

本文的邻域结构是以当前产生的最优解X为中心,随机产生满足在0

3.4 禁忌表及禁忌长度

禁忌长度大小是影响TS算法性能的关键参数。禁忌长度是禁忌对象在不考虑藐视准则情况下不允许被选取得最大次数,对象只有当其任期为0时才被解禁。在算法的构造和计算过程中,一方面要求计算量和存储量尽量小,这就要求禁忌长度尽量小;但是禁忌长度过短将造成搜索循环。

本文的禁忌表包括的元素有禁忌长度,与状态信息相应的适配值[8]。本文的禁忌长度是定长不变的,它的选取是通过实验仿真讨论确定的,对于不同的禁忌长度,画出禁忌长度和当前最优解的曲线。通过曲线,便可以恰当的选择禁忌长度,使禁忌搜索算法具有最佳的优化性能。本文将讨论禁忌长度对算法优化性能的影响,并采用最佳的禁忌长度。

3.5 候选解的选择

候选解的选择首先要确定候选解的数量,然后确定最佳候选解的选取方案。原则上应该做到对当前解的邻域解的遍历,但考虑到邻域搜索的效率,通常仅取当前解的邻域解的一个子集作为候选解集。最佳候选解通常是候选解集中满足藐视准则或非禁忌的最佳状态[9]。候选解集的大小是影响TS算法性能的一个关键参数,本文将通过对不同解集大小下算法的实验仿真,选取能使函数优化性能最好的候选解集大小来进行仿真。

3.6 藐视准则

本文应用的是基于适配值准则中的全局形式,这也是最常用的一种方式。它的具体操作是:若某个候选禁忌解的适配值优于“best so far”状态,则无视其禁忌属性,解禁此候选解为当前状态和新的“best so far”状态。该准则可理解为算法搜索到了一个更好的解。

3.7 终止准则

禁忌搜索需要一个终止准则来结束算法的搜索进程,而严格的实现理论上的收敛条件,即在禁忌长度充分大的条件下实现状态空间的遍历,是不切合实际的因此实际设计算法时通常采用近似的终止准则[10]。常用的方法如下:

(1)给定最大迭代步数。迭代步数即是每次运行后总共搜索循环的次数,用它来控制算法的收敛。

(2)设定某个对象的最大禁忌频率。即,若某个状态、适配值或对换等对象的禁忌频率超过某一阈值,则终止算法,其中也包括最佳适配值连续若干步保持不变的状况。本文应用的第二种终止准则采用的禁忌对象是当前最优解连续若干步保持不变的状况。

(3)设定适配值的偏离幅度。即,首先有估界算法估计问题的下界,一旦算法中最佳适配值与下界的偏离值小于某规定幅度时,则终止搜索。

4 实验及结果分析

在以不同终止准则收敛的情况下,讨论禁忌搜索算法两个关键参数——禁忌表长度和邻域候选解个数对算法优化性能的影响,并找出最优的参数。并在每种终止收敛准则参数最优时比较三种终止准则优化本文所定义的函数时哪一种的性能更好。在MATLAB环境下对禁忌搜索算法过程用MATLAB语言编译仿真,优化本文目标函数,输出最优解。

4.1 以最大迭代步数为终止条件

在以限定最大迭代步数为终止准则情况下,邻域解集个数选为500,终止迭代步数为3000,记录找到最优解时的迭代步数,并求平均值,以此来考验算法优化性能表1是禁忌表长度与对应迭代步数的图表。

从表中可以看出,在禁忌长度等于7和9时收敛较快,但在9时收敛更好,且比较稳定,所以认为禁忌长度H=9时收敛性最好,故选择9作为禁忌长度,在以下讨论邻域解集大小时,也选此为禁忌长度。

禁忌表长度选择9,迭代次数仍然选择3000,记录找到最优解时的迭代步数,并求平均值,如表4.2是邻域解集个数与达到最优时对应迭代步数的图表。

由表2可见在邻域解集数为600时,达到最优解时迭代次数最小,但当邻域解选择大于6 0 0时,运算量增大,运行速度减慢,所以,综合考虑,选择邻域个数解为6 0 0作为最佳优化参数,并认为,在此种终止准则下,对于本文需优化函数,邻域解集个数600可以是寻到最优解的最好参数。

选择禁忌长度H=9,邻域解集数选择600,变化最终迭代步长,讨论迭代步数对优化性能的影响。同一最大迭代次数情况下,仿真运行5次,看终止最大迭代步数对最优解的影响。

在保证算法计算量和速度的前提下,应尽量减少迭代次数,如表3可见,当终止时最大迭代次数K小于1500时,无法保证每次都优化出最优解,说明迭代步数越大,结果越优,在最大迭代次数K选择1500时,每次优化出的解都是正确解7.8567,所以在此种收敛准则下,主要参数选择为禁忌长度H=9、邻域解集个数600、最大迭代步数为1500,可认为在此终止准则下此参数的选择是对本文需优化函数最佳的情况。

4.2 以某对象的最大禁忌频率为终止条件

本文应用的第二种终止准则采用的禁忌对象是当前最优解连续若干步保持不变的状况。

与4.1中仿真过程类似,可以得出以限制最优解禁忌频率为终止准则情况下最优的参数禁忌表长度和邻域候选解个数,具体图表省略。

在保证算法计算量和速度的前提下,应尽量减少候选解的禁忌频率,如表4可见,当终止时候选解的禁忌频率小于12时,无法保证每次都优化出最优解,说明候选解的禁忌频率越大,结果越优,在候选解的禁忌频率选择12时,每次优化出的解都是正确解7.8567,所以在此种收敛准则下,主要参数选择为禁忌长度H=9、邻域解集个数500、候选解的禁忌频率为12,可认为在此终止准则下此参数的选择是对本文需优化函数最优的情况。

4.3 以适配值的偏离幅度为终止准则

首先有估界算法估计问题的下界,一旦算法中最佳适配值与下界的偏离值小于某规定幅度时,则终止搜索。算法收敛时其适配值之间的差值必须连续多次小于一个较小的范围,经多次实验仿真,规定连续次数为3 0,在此参数下,进行以下研究讨论,找出最优的参数。

与4.1和4.2中仿真过程类似,可以得出以限制适配值为终止准则情况下最优的参数禁忌表长度和邻域候选解个数,具体图表省略。

在保证算法计算量和速度的前提下,应尽量增大适配值的偏离幅度,如表4可见,当终止时适配值的偏离幅度大于0.0001时,无法保证每次都优化出最优解,说明适配值偏离幅度越小,结果越优,在适配值偏离幅度选择0.0001时,每次优化出的解都是正确解7.8567,所以在此种收敛准则下,主要参数选择为禁忌长度H等于9、邻域解集个数600、适配值的偏离幅度为0.0001,可认为在此终止准则下此参数的选择是对本文需优化函数最优的情况。

4.3 三种终止准则的收敛特性比较

在上文讨论的最优参数下,把三种终止准则横向比较,在各自选择对本准则最优性能的参数基础上优化本文设定函数,并用MATLAB仿真,观察结果。

多次仿真试验后,得出结论基本相同,选出代表性曲线,如图4.1。

通过曲线可以看出,在三种终止准则下优化本文所设定的函数的时,在上文所讨论的参数下,都可以准确的优化出本函数的最优解,只是达到最优解时的迭代步数不同,由图可见,在以候选解的禁忌频率为终止准则的情况明显优于其它两种终止准则,在这种终止准则下,算法最快寻到最优解,而且曲线相对更平稳。

以适配值的偏离幅度为终止准则的情况下,算法终止时迭代步数最小,但不是最快寻到最优解,且相对于以禁忌频率为收敛准则的情况找到最优解附近邻域更慢,且没有其平稳。

以最大迭代步数为终止准则的情况下,相对于其他两种收敛准则算法找到最优解附近邻域最慢,但最后在最优解附近邻域搜索时曲线较平稳,且迭代步数足够长,可以保证算法全解空间精细搜索。

所以,对于本文优化的多极值函数:

在用禁忌搜索算法的思想进行优化时,选择终止准则不同时,其优化性能也不同,经本文讨论研究并且仿真,认为在以候选解的禁忌频率为终止准则时,其收敛性最好。

5 结束语

本文论述了禁忌搜索算法的产生背景、原理及算法框架,并就禁忌搜索算法的三种终止准则的收敛性进行了研究探讨,做了大量的仿真试验,验证了本文所提出的各种终止准则的有效性。通过这些研究工作,我们对禁忌搜索算法可得到以下结论:

禁忌搜索的最大优点在于具有记忆功能,由于“禁忌表”的作用,使得搜索可以确定性地跳出局部最优,这也是禁忌搜索算法区别于其它启发式算法的地方,与SA、G A比较而言,禁忌搜索往往能得到更好的解的质量。初始解的选取和邻域范围的确定很重要,若按简单的禁忌搜索流程来优化本函数,则陷入局部最优,所以本文提出变邻域搜索策略,使得算法可以在整个解空间遍历,验证了算法的有效性和可发展性。禁忌搜索有三种准则,对于本文所优化的函数来说,用三种收敛准则都可达到最优解。在三种终止准则下,以候选解的禁忌频率为终止准则的情况下,本文函数可以更快更稳地被优化。

摘要：禁忌搜索(Tabu Search,TS)是一种新的智能优化算法.TS以其灵活的存储结构和相应的禁忌准则来避免迂回搜索,在组合优化和函数优化领域中得到了广泛应用。本文重点研究了禁忌搜索算法的参数选择和其收敛特性的关系,侧重研究了禁忌搜索算法的两个关键参数——禁忌表长度和邻域候选解集个数对算法优化性能的影响,最后比较了本文定义的函数在三种终止准则下的优化性能。

关键词：禁忌搜索算法,终止准则,收敛特性

参考文献

[1]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001:62-82.

[2]ZHAO CHUNHUI,CUI YING.Optimal Stack Fil-ters Based on Tabu Search Algorithm[A].Proceedings of the6th international symposium on advanced intelligent systems[C].Korea:Korea University Lishui,2005:1085-1089.

[3]贺一,刘光远.禁忌搜索算法求解旅行商问题的研究[J].西南师范大学学报(自然科学版),2002,27(3):34l-345.

[4]贺一,刘光远.变异操作对禁忌搜索性能的影响研究[J].计算机科学,2002,29(5):115-116.

[5]刑文训,谢金星.现代优化计算方法[M].北京:清华大学出版社,1999:62-82.

[6]GLOVER F,HANAFI S.Tabu Search and Finite -e s..Convergence[J].Discrete Applied Mathematics,2002,229(4):3-36.

[7]CHELOUAH R,SIARRY P.Tabu search applied to global optimization[J].European Journal of Operational Research,2000,123(43):256-270.

[8]孙云凯,刘民,吴澄.变邻域结构Tabu搜索算法及其在Jop shop调度问题上的应用[J].电子学报,2001,29(5):622-625.

[9]柯珂,张世英.禁忌—阶梯遗传算法研究[J].控制与决策,2001,16(4):480-483.

快速收敛算法 篇9

近年来，由于人们阅读文献不同，从而对RIP协议褒贬不一。RIP协议虽然没有之后的一些路由协议(诸如EIGRP、OSFP、IS-IS)功能强大，但它简单易用，应用也很广泛。我通过如何解决RIP协议收敛慢的问题，从四个定时器出发，深入研究。

关于RIP协议的一些基本理论这里不做介绍了，简单介绍四个定时器分别为：

路由更新定时器(Update Timer)、路由失效定时器(Invalid Timer)、抑制定时器(Holddown Timer)、路由刷新定时器(Flush Timer)。

2. 定时器的讨论

2.1 时间问题

更新定时器的时间影响着网络的效率，过长的时间将增加带宽的负担，同时也会影响网络的收敛时间，在RIP协议中四个定时器的时间是可以更改的。

默认情况下，在运行RIP协议的路由器上使用“show ip protocols”命令，显示如下：

Routing Protocol is"rip"

Sending updates every 30 seconds, next due in 11 seconds

Invalid after 180 seconds, hold down 180, flushed after 240

通过timer basic 5 15 15 30进行更改后显示如下：

Routing Protocol is"rip"

Sending updates every 5 seconds, next due in 2 seconds

Invalid after 10 seconds, hold down 15, flushed after 20

必须注意的是其他三个RIP定时器都依赖于更新定时器的值。原则上来说失效定时器的值必须至少是更新定时器的三倍，抑制定时器的值必须至少是更新定时器的三倍，刷新定时器的值至少是失效定时器和抑制定时器的和。但是根据实际情况，我们可以自己决定各定时器的时间。无论怎样如果更新定时器的值改变，那么失效定时器、抑制定时器、刷新定时器的值也要相应改变。

在RIP的database里面，失效定时器的时间秒到180，就会进入抑制定时器的180秒。但是刷新定时器是和失效定时器一起开始的，所以总共240秒一到，本路由就会被清除掉，而不是等到抑制定时器的180秒走完。计算时间得出总共要等180+180=360 (s)，与实际的时间(240秒左右)有一定的偏差。

2.2 定时器启动问题

更新定器比较容易理解，只是路由选择协议用来发送更新数据的时间间隔。从路由协议启动以后就开始生效，每发送一次更新报文后重新倒计时，失效定时器是针对路由表上的路由条目。这个定时器是路由条目在路由表生效后开始倒计时。每收到公告该路由条目的路由更新报文后重新倒计时。刷新定时器和抑制定时器是同时启动的。收到更新报文后重新倒计时。如果你把刷新定时器设置的比失效定时器短那么会出现路由条目还没出现possibly down的时候就已经被刷掉了。

抑制定时器的启动比较特殊，由于它是收到路由表上的路由条目METRIC大的时候所启动的定时器，也就其存在两种情况。

2.2.1 如果收到路由表上的某个路由条目的同一个公告源发送过来的路由更新比路由器上的距离大，那么启动抑制定时器。例如：路由表上到达10.0.0.0网络的度量是3，发送该更新的路由器是A。如果收到来自A的关于10.0.0.0路由更新的报文并且度量大于3的时候，那么在路由表上对10.0.0.0的路由条目启动一个抑制定时器。

2.2.2 如果是来自路由器B的关于10.0.0.0网络的更新且度量大于3的时候，接受方就会丢弃路由器B的更新。因为路由表中已经存在经过A到达10.0.0.0网络且距离小于B路由器。此时路由表上则不会启动一个抑制定时器。

3. RIP协议网络快速收敛中的研究

3.1 收敛的含义

RIP互联网络中拓扑变化带来的最重要可能是它会改变相邻节点集，这种变化也会导致下一次计算距离向量时得到不同的结果。因此，新的相邻节点集必须得到汇聚，从不同的起始点汇聚到新拓扑结构的一致看法，得到一致性拓扑视图的过程称为收敛 (convergence) 。简单地讲，收敛就是路由器独立地获得对网络结构的共同看法，即使所有路由选择表都达到一致状态的过程。

全网实现信息共享以及所有路由器计算最优路径所花费的时间总和就是收敛时间。

3.2 收敛慢的后果

RIP每隔30s更新一次，从人的角度来看，等待30秒进行一次更新不会感到不方便。但是路由器和计算机的运行速度非常快，不得不等上30秒进行一次更新会有很明显的不利结果。比仅仅等上30秒进行一次更新更具破坏性的却是不得不等上180秒来作废一条路由，而这只是一台路由器开始进行收敛所需的时间量。

无线网络依赖于互联的路由器个数及它们的拓扑结构，可能需要重复更新才能完全收敛于新拓扑。RIP协议收敛速度慢会创造许多机会使得无效路由仍被错误地作为有效路由进行广播。显然，这样会降低网络性能。

3.3 利用定时器调整网络收敛时间

利用上面的网络拓扑图，我们进行了RIP定时器的实验，就其分析如何利用定时器调整网络的收敛时间。

3.3.1 路由器基本配置

三台路由器的基本配置这里不做详细揭示了，值得一提的是network命令是必须的。因为它允许选择进程决定哪些端口将参与发送和接受路由选择更新信息，能在路由器上所有位于特定网络内的接口上启动路由选择协议，network命令也将使得路由器将该网络发布出去。

3.3.2 通过debug观察路由表的变化情况

我们可以看到图中红色和黄色框内的时间变化，路由每次更新的时间是30s，通过实验验证了一般时间为25-32s，都认为是30s左右。

3.3.3 在R1上，做个访问列表，不接收来自R2的rip数据包

再次用debug命令查看路由器的输出信息查看时间发现180s之后，来自B路由条目，被宣告无效(即invalid定时器走完)。

此时的路由表:

路由表已经出现了possibly down，进入抑制定时器阶段。

通过上面时间的对比，宣布无效的时间是00:59:51，在宣布无效之后的大概60s内(允许有5s的浮动值)，来自B的路由条目在路由表里面被删除，即刷新定时器如图所示为180s+60s=240s。

3.3.4 调整网络的收敛时间

通过以上的实验我们知道但路由器A不再接受路由器B的更新信息时，网络进行重新收敛花了240s的时间。慢收敛会导致的问题在前文已经提到，此时我们就需要来采取方法使网络收敛变快。

4 个定时器的值分别改为10s, 20s, 30s, 40s。路由器B和路由器C都与路由器A一样，进行相同的设置。

断开路由器A与路由器C的链接，同时使用debug ip rip命令观察路由表的输出。

路由器A的输出：

从以上debug结果观察到，第一次通告不可达(metric 16)的时间为14:13到来自C的路由消失时间为14:32的间隔约为20s(即是Invalid定时器和Flush定时器差为20s)，与我们设置的时间一致。由此可见网络收敛速度明显变快。

查看路由器C的输出

在配置完成后，我们可以在路由器C上看见1.1.1.1的路由。关闭端口的20s内，我们看见该条路由变成不可达。在调整定时器的值之前，这一过程则需要180s的时间。

从路由器A和路由器C的输出可见，调整定时器后，RIP网络的收敛时间明显缩短了。

4. 结语

本文在研究协议应用的同时，细致地分析了协议中的4个定时器，通过定时器的讨论分析，到实际案例的应用，深度剖析了RIP网络收敛的工作机制，为RIP收敛慢的应用问题提供了一种可靠的解决方案。

参考文献

[1]JEFF DOYLE.TCP/IP路由技术第一卷.人民邮电出版社.

[2]JEFF DOYLE.TCP/IP路由技术第二卷.人民邮电出版社.

[3]Hedric C.RFC1058:Routing Information Protocol[S].

[4]Malkin G.RFC2453:Routing Information Protocol (Ver-sion2) [S].

[5]程林.如何在路由器上配置RIP协议[N].蚌埠党校学报, 2008, (4) .