进化算法（精选9篇）
进化算法 篇1
0引言
差分进化算法是1995年由Storn和Price提出来的一种基于种群的随机性搜索算法, 差分进化算法在求解各式样的优化问题中表现出了良好的全局寻优能力[1], 同时其结构简单、操作容易, 具有很多优点, 但不可避免的是其容易陷入局部最优导致无法快速准确的收敛到全局最优值。 不同学者也提出了很多对差分进化算法的改进, 主要有对控制参数的改进以及对突异策略的改进等[2,3,4]。
本文研究主要分为以下几个部分, 首先对差分进化算法简要介绍, 之后提出改进的差分进化算法, 并对改进算法进行Benchmark函数实验, 最后给出结果及结论。
1基本差分进化算法
差分进化算法是一种经常用于解决优化问题的随机性搜索算法, 它采用实数编码方式。 算法主要包括突变、交叉以及选择操作[5], 涉及到的参数主要包括种群大小Np, 突变概率F (一般取值范围0到1) , 交叉概率Cr (一般取值范围0到1) 。 算法的流程主要分为以下几部分: (以下i∈[1, Np], j∈[1, D], G迭代次数)
1) 种群初始化:算法采用随机初始化方式产生一定大小的初始种群, 具体生成方式如下:
2) 突变操作:是差分进化算法中最重要的操作, 随机产生的三个互不相同的个体, 选取一个作为目标向量, 通过另两个向量的差来引导目标向量进行突变操作, 具体形式如下:
除了上述最经典变异策略之外, 还有几种常见变异策略见文献[6]。
3) 交叉操作:在突变操作之后, 为增加种群的多样性, 我们对突变个体和父代个体进行交叉操作, 常用的二项式交叉具体形式如下:
4) 选择操作:算法的选择操作采用的是一种一对一的贪婪选择机制, 将交叉操作后生成的试验向量与父代个体进行比较, 选取具有更优适应度的个体进入下一代, 具体如下:
2改进差分进化算法
本文对差分进化算法的改进主要分为以下两个方面:
1) 突变和交叉操作的改进:本文主要针对常用突变操作中的vi, G=xi, G+F· (xbest, G-xi, G) +F· (xr1, G-xr2, G) 突变方式, 我们随机的从种群选取种群个数的百分之p, 选取这部分个体中具有最有适应度的个体, 用xgr_best, G来代替替代xbest, G。除此之外, 突变概率F我们采取如下方式生成:
其中, F0是一给定数值, Fmin和Fmax分别是突变概率的下限和上限。交叉概率在前百分之80次迭代中取0.2, 之后取0.85。
2) 增加扰动:随着迭代次数增加, 个体间差异越来越小容易陷入局部最优。本文在选择操作后加入扰动机制, 在迭代进行一定次数后随机选取种群中的z个, 进行如下操作:
其中Gauss (0, 1) i为产生的高斯随机数组。
3 Benchmark函数测试及结果
为了验证本文提出的改进差分算法的性能, 本文主要选取了10组Benchmark函数来测试改进算法的性能, 分别是:Sphere Model、 Schwefel 2.22和1.2、Rosenbrock、Step、Quartic、Rastrigin、Ackley、Griwank、Penalized Function十个全局最小值为0的函数。分别针对了低维D=5以及高维D=30两种情况进行计算, 每组用Matlab进行仿真求解50次, 求得最优值、平均值及标准差与文献[3]的其他算法结果进行对比。具体的参数如下:低维和高维情况下Np分别取20和100, p=0.15, F0=0.5, fmax=1, Fmin=0.1, z=0.1, Cr0=0.5, Cr1=0.85。所得结果如表1所示。
4结束语
通过上表中所得函数测试结果与文献[3]中所给数据相比对 (较优结果黑体显示) 可以看出, 改进后的差分进化算法能够取得较基本差分进化算法及其他改进差分进化算法更理想的结果, 改进后的算法有效并有一定的适用性。
摘要：本文提出了一种改进的差分进化算法, 算法采用一种新的突变方式, 同时在选择操作之前引入扰动机制以增强算法的全局搜索能力。之后对改进算法进行了Benchmark函数实验, 得到的仿真结果证明了算法的有效性。
关键词：差分进化算法,Benchmark函数,扰动
参考文献
[1]R.Storn, K.Price., “Differential evolution-a simple and efficient adaptive scheme for global optimization over continuous spaces”, Berkeley, CA, Technical Report[C].TR-95-012, 1995.
[2]A.K.Qin and P.N.Suganthan, ”Self-adaptive differential evolution algorithm for numerical optimization”[C].IEEE Congress on Evolutionary Computation, vol.2, pp.1785-1791, 2005.
[3]Jinqiao Zhang, Arthur C.Sanderson, ”JADE:Self-adaptive differential evolution with fast and reliable convergence performance”[C].IEEE Congress on Evolutionary Computation, 1-4244-1340-0/07.
[4]刘明广.差异演化算法及其改进[J].系统工程, 2005, 23 (2) :108-111.
[5]赵斌.基于改进差分进化算法的火电厂负荷分配问题研究[D].武汉理工大, 2013.
[6]郭鹏.差分进化算法改进研究[D].天津大学, 2011.
进化算法 篇2
用于快速仿真优化的改进差分进化算法及其应用
提出一种改进的差分进化算法,采用一种“位变”方法计算收缩因子,该方法首先根据适应值对种群排序,然后根据各个体的排列位置确定收缩因子;采用正态分布函数对算法参数进行随机扰动来维持种群的多样性;该算法还提出一种新的变异算子,并将其与基本的.差分变异算子结合使用以提高算法的寻优精度.经过对多个Benchmark函数的测试、分析和比较,结果表明该算法具有较高的收敛精度和较快的收敛速度.最后将该算法用于火箭发动机涡轮气动优化,以较小的计算成本将涡轮气动效率提高了2.5%.应用结果表明该算法适用于快速仿真优化问题,能有效地节约计算成本.
作 者：饶大林 蔡国飙 RAO Da-lin CAI Guo-biao 作者单位：北京航空航天大学宇航学院,北京,100191刊 名：宇航学报 ISTIC PKU英文刊名：JOURNAL OF ASTRONAUTICS年，卷(期)：31(3)分类号：V434关键词：差分进化 “位变”收缩因子 正态分布 变异算子 仿真优化 涡轮 Differential evolution “Position” varying scale factor Normal distribution Mutation operator Simulation optimization Turbine
进化算法 篇3
关键词：约束多目标进化算法；种群聚类；聚集密度；分布性
中图分类号：TP3016文献标志码：A文章编号：1672-1098（2016）01-0050-06
Abstract：The constrained multi-objective evolutionary algorithm based on group clustering was improved， and crowding-density was introduced to measure the relationship among individuals and maintain the diversity of population. The basic idea is that the initial population is divided into four groups with different fitness by multi-criterion clustering method， and the crowding-density of each group is calculated. A poset is defined according to the objective function value and crowding-density， and the individuals are selected from poset by the principle of proportion selection， then the elite set is updated. The convergence and distribution of improved algorithm were studied by means of numerical experiments， and the results showed that the convergence of improved algorithm is roughly equal to the conventional multi-objective evolutionary algorithm， but the distribution of improved algorithm is significantly improved.
Key words：constrained multi-objective evolutionary algorithm； group clustering； crowding density； distribution
约束多目标优化问题的关键是对约束条件的处理，目前已有一些典型的带约束多目标进化算法和约束处理机制：文献[1]提出的COMOGA算法，将向量评估遗传算法和Pareto排序分级的方法结合起来处理约束问题。文献[2]提出的约束VEGA，将群体划分成几个子群体来处理。文献[3]提出的约束MOGA，将基于Pareto优胜的选择方案用来处理遗传算法中的约束方程。文献[4]提出了一种基于群体分类的复杂约束多目标进化算法，根据聚类方法来处理复杂约束，算法的基本思想是：按照类内距离平方和最小，类间距离平方和最大等多种判据将种群聚类处理，再按类赋以适当的适应度值。这种算法对于处理Pareto边界比较光滑的三目标的优化问题效果较好，收敛速度较快，基本上二百代即已达到较好的优化效果，但在维持种群的多样性和分布性方面欠佳，现将此算法做了改进，在进化过程中引入聚集密度以调控种群，可以达到维持种群多样性的目的，并根据量化评价指标和数值实验结果对改进算法的性能特别是分布性进行了评测。
1多目标优化问题的相关概念
11多目标优化问题及其最优解
多目标优化问题可表述为[5]
min y=f（x）=（f1（x），f2（x），…，fk（x））
s.t e（x）=（e1（x），e2（x），…，em（x））≤0
x=（x1，x2，…，xn）T∈X
y=（y1，y2，…，yn）∈Y
（1）
式中：x为决策向量，f（x）为目标向量，X表示决策向量x形成的决策空间，Y表示目标向量y形成的目标空间，约束条件e（x）≤0确定决策向量的可行取值范围。
定义1[6]满足式（1）中的约束条件e（x）的决策向量x的集合，即
Xf={x∈X|e（x）≤0} （2）
称为可行解集。
定义2[7]设xA，xB是两个可行解，若f（xA）≤f（xB）， 则称xA比xB优越； 若f（xA） 定义3若可行解x*满足：比x*更优越的可行解不存在，则称x*为弱Pareto最优解； 比x*优越的可行解不存在，则称x*为强Pareto最优解。 定义4Pareto最优解的集合称为Pareto最优解集或非支配解集，记为P*。 定义5Pareto最优解集P*中的所有Pareto最优解集对应的目标向量组成的曲面称为Pareto最优前沿或Pareto最优前端，记为 两目标优化问题的Pareto最优前沿是一条平面曲线，三目标优化问题的Pareto最优前沿则为一张空间曲面。多目标优化问题的结果习惯上多采用Pareto最优前沿表示。
12最优解集的评价标准
多目标优化算法性能的评价包括算法的效率和最优解集的质量。算法的效率主要指算法的复杂性即算法占用的CPU时间，而最优解集的质量包括算法的收敛性和最优解集的分布性。
评价多目标优化算法性能主要依靠量化评价标准和有代表性的测试问题。
常用的量化评价指标有：
1） 世代距离[8]（GD）
GD=∑ni=1d2i n （4）
式中：n为算法所得最优前端PFknown中向量个数，di为PFknown中每一维向量到最优前端PFtrue中最近向量的距离。
GD主要反映了PFknown对PFtrue的逼近程度。
2） 错误率[9]（ER）
ER=∑ni=1ein （5）
式中：n为PFknown中的向量个数，且PFknown={X1，X2，…，Xn，ei定义如下
ei=0， Xi∈PFtrue
1， 其它（6）
ER描述了PFknown对PFtrue的覆盖程度，即最优解集的分布性。
3） 分散性（SP） [10]
SP=1n-1∑ni=1（di-）2 （7）
式中：n和di同GD。
显然，SP即为di的均方差。根据方差的含义，SP反映的是最优解集的均匀性。
2基于聚集密度的约束多目标算法
上述群体分类的复杂约束多目标进化算法具有较好的收敛性，但在分布性方面存在着的一定的缺陷，原因是算法仅考虑了群体中个体的R适应度，并没有考虑群体中个体间的距离，即群体的拥挤程度，这极有可能降低种群的多样性，影响解的分布性。
在进化算法中，保持解的分布性的常用方法有：小生境技术，信息熵，聚集密度，聚类分析等[11]。
本文将聚集密度引入选择过程，改善解的多样性和分布性。
21聚集密度
聚集密度的概念是Deb在[12]中提出来的。聚集密度可以从个体的相似度，影响因子或者聚集距离几个方面来度量，本文选择从聚集距离角度度量。聚集密度与聚集距离成反比关系，聚集距离大的聚集密度小。一个个体的聚集距离可以通过计算其与相邻的两个个体在每个子目标上的距离差之和来求取。
如图1所示，设有两个子目标f1（x）和f2（x），Pm[i]为个体i在子目标m上的函数值，则个体i的聚集距离P[i]d是图中四边形的长与宽之和，即
计算出聚集距离后，再按照个体间的聚集距离越大，则个体的聚集密度就越小的原则，即可定义个体的聚集密度。这里，为了简单起见，定义聚集密度为聚集距离的倒数。
22基于聚集密度的约束多目标进化算法
基于聚集密度的约束多目标进化算法的步骤如下
1） 用多判据聚类方法将整个群体分成四类，不可行群体、可行非Pareto群体、聚类Pareto群体以及聚类Pareto最优群体。分别赋以适应度：R（不可行群体）≤R（可行非Pareto群体） ≤R（聚类Pareto群体）≤R（聚类Pareto最优群体）。
2） 当迭代次数小于最大迭代次数时，构造如下偏序集：① 计算种群中个体的目标函数值；② 计算每个个体的聚集密度；③ 根据目标函数值和聚集密度定义一个偏序集，该偏序集中的元素有两个属性：个体的目标函数值和聚集距离。
3） 根据比例选择原则，依次从偏序集中选择个体。
4） 对群体进行交叉运算。
5） 对群体进行均匀变异运算。
6） 条件终止判断。不满足终止条件，则进行新一轮运算，若满足终止条件，则输出计算结果，算法结束。
算法流程图如下
下面用基于聚集密度的约束多目标进化算法对两个标准约束多目标测试函数Binh4和Viennet 4进行了优化，并将计算结果与文献[12]中的原算法的计算结果进行了比较，从而检验改进算法的性能。
1） Binh4测试函数
F=（f1（x，y），f2（x，y），f3（x，y））
f1（x，y）=15-x（1-y）
f2（x，y）=225-x（1-y2）
f3（x，y）=2625-x（1-y2） （10）
约束条件为
-10≤x，y≤10
x2+（y-05）2≥9
（x-1）2+（y-05）2≤625 （11）
Binh4测试函数的PFlocal如图3所示。
2） Viennet4测试函数
Viennet4测试函数的PFlocal如图4所示。图4Viennet4 PFtrue 图图5Binh4 PFknown 图（改进算法）图6Binh4 PFknown 图（原算法）图7Viennet4 PFknown 图（改进算法）图8Viennet4 PFknown 图（原算法）
图5～图8分别是用改进算法和原算法求出的Binh4和Viennet4的Pareto最优边界。可以很直观地看出，改进算法在解的分布性和均匀性方面均明显优于原算法。
为了更进一步定量地评价改进算法的性能，下面给出改进算法和原算法的世代距离、错误率和分散性指标的对比数据。
考虑到计算结果的随机性，表中给出的是20次实验结果的平均值。
从表1和表2中可以很清楚地看出，原算法和改进算法的GD指标相差不大，但改进算法的ER和SP指标与原算法相比明显占优。
综合图5～图8和表1～表2，可以得出明确的结论：基于聚集密度的改进约束多目标进化算法的收敛性与原算法相当，但分布性和均匀性有了明显的提高。
4结束语
本文根据聚集密度的特点，将聚集密度引入群体聚类约束多目标进化算法，数值实验结果和量化指标表明：与原算法相比，改进算法解的分布性有了明显的提高。
由于多目标进化算法的理论基础目前还很薄弱，收敛性和分布性等关键理论问题无法从理论层次进行证明，所以算法的改进验证只能基于对比实验。
提高多目标优化算法解的分布性和均匀性的方法有多种，如小生境技术，信息熵，聚集密度，聚类分析等。本文采用的聚集密度方法与其它方法相比，优点是既能从宏观上刻画群体的多样性与分布性，也能从微观上描述个体间的内在关系，缺点是计算复杂度偏高。这完全符合优化中的“没有免费的午餐定理（No Free Lunch， NFL）”。
参考文献：
[1]SURRY P D， RADCLIFFE N J. The COMOGA Method： Constrained Optimisation by Multi-objective Genetic Algorithms[J].Control and Cybernetics，1997，26：391-412.
[2]COELLO CAC. Treating Constraints as Objectives for Single-Objective Evolutionary Optimization[J].Engineering Optimization，2000，32：275-308.
[3]COELLO C A C.Constraint-handling using an evolutionary multi-objective optimization technique[J].Civil Engineering and Environmental System，2000，17：319-346.
[4]张丽丽， 许峰. 基于群体分类的复杂约束多目标优化遗传算法[J]. 教育技术导刊， 2009（12）：38-41.
[5]催逊学. 多目标进化算法及其应用[M].北京：国防工业出版社，2008：6.
[6]催逊学. 多目标进化算法及其应用[M].北京：国防工业出版社，2008：7.
[7]郑金华. 多目标进化算法及其应用[M].北京：科学出版社，2010：3-4.
[8]VELDHUIZEN D A， LAMONT G B. Evolutionary computation and convergence to a Pareto front[C]// In John R Koza. Late breaking papers at the genetic programming 1998 conference， Stanford University， California. Stanford Bookstore：221-228.
[9]COELLO COELLO C A. Evolutionary algorithms for solving muli-objective problems [M]. Kluwer Acedemic， 2002：14-18.
[10]E ZITZLER，K DEB，L THIELE.Comparison of multiobective eveolutionary algorithms：Empirical results[J]. Evolutionary Computation，2002，8（2）：173-195.
[11]郑金华. 多目标进化算法及其应用[M]. 北京： 科学出版社， 2007：118-124.
改进差分进化算法研究及应用 篇4
近年来,差分进化算法(DifferentialEvolution Algorithm,DE)逐渐被各国学者广泛关注,作为进化算法的一个分支,最早由Rainer Storn和Kenneth Price于1995年提出,2000年后开始被大多数学者研究,目前已取得不少研究成果。与其他进化算法相比,DE[1]算法简单,控制参数少,收敛速度快,所需背景领域知识少。
1 标准差分进化算法
1.1 算法描述
DE算法的基本思想[2]是:首先在问题的可行解空间随机初始化种群,使当前种群父代个体间的差分矢量构成变异算子,接着按照一定的概率,父代个体与变异个体进行交叉,生成试验个体,然后在父代个体与试验个体之间根据适应度的大小进行选择,选择适应度更优的个体作为子代。
1.2 标准DE算法
1.2.1 初始化
NP个D维的实数参数向量,每个个体表示为:xi,G(i=1,2,…,NP)(i为个体在种群中的序列,G为进化代数)设参数界限为,一般假定对所有随机初始化种群均符合均匀概率分布:
(NP为种群规模,D为目标函数决策变量的个数,rand为在[0,1]之间产生的均匀随机数)
1.2.2 变异操作
对于每个目标向量,其变异矢量如下产生:
其中,随机选择的序号r1、r2、r3互不相同,变异算子F为常数,按文献[2]其取值范围为[0,2]。
1.2.3 交叉操作
为增加参数向量的多样性,引入交叉操作,试验向量如下:
其中,CR为交叉算子,按文献[2]所述,。
1.2.4 选择操作
DE采用贪婪搜索策略,经过变异与交叉操作后产生的试验个体()与()进行竞争,带入适应度函数进行计算,取适应度更优的进入下一代。
其中f为适应度函数,这里为最小值优化问题。
1.3 DE算法参数设置
种群规模NP一般取5D和10D之间,D为目标函数决策变量的个数,不能少于4,否则无法进行变异操作,NP越大,种群多样性越强,获得最优解概率越大,但是计算时间更长。
DE算法中重要的两个参数变异算子F和交叉算子CR。F用来控制种群的多样性和收敛性,CR的值用来控制个体各个维数对交叉的参与度。
由于DE采用贪婪的搜索策略[3],可以加快收敛的速度,随着进化的进行,其他个体会迅速向当前最优点靠拢,若该点为局部的最优点,随着种群的不断进化,个体间的差异越来越小,所有的个体都会趋向这个局部最优点,种群就无法重新搜索。因此,DE容易出现早熟收敛现象,陷入局部最优,没有找到全局最优点。
1.4 测试函数实验研究
为验证DE算法的可行性与有效性,用以下三个典型的测试函数[4]进行试验。其中f1为Griewank函数,多峰,存在一定数量局部极小点;f2为Sphere单峰二次函数;为Rastrigin函数,多峰,有大量局部极小点。
实验参数设置如下:种群规模NP都为100,最大进化代数为1000,标准DE的变异算子F=0.8,交叉概率CR=0.8。GA遗传算法的交叉概率为0.8,变异概率为0.05。
表1给出了利用以上两种算法运行10次后的统计结果。对于多维多峰的函数,GA算法基本都不能收敛到最优解。DE算法对f1和f2都有很好的优化精度,而对于f3,由于过早的收敛于局部最优解,从而寻优失败。可以看出,标准DE算法在处理一般问题时,收敛速度明显较快,但是如1.3节所述标准DE算法存在的缺点,需要运用改进的DE算法来处理有大量局部极小点的问题。
2 改进差分进化算法
2.1 DE算法的改进
经过十几年的研究,DE算法得到了较大发展,出现了很多改进的DE算法。总的来说,可以采用改进DE中的控制参数,多种群处理,加入新操作[5]等方法。
2.2 改进差分进化算法在函数优化中的应用
2.2.1 有约束条件的处理
实际应用中多为有约束的问题,经过一系列的转化,可描述为:
此约束问题可以通过罚函数法转化为无约束问题,DE算法求解约束问题的关键是对约束条件的处理。由于等式约束是能包含到适应度函数中的,所以重点考虑不等式约束,采用式(6)的形式将罚函数包含到适应度函数中。
f(x)为适应度函数,>0为罚函数尺度系数,罚函数P(x)为满足式(7)条件的函数,x为问题的可行解域:
如何设计罚函数来有效地惩罚非可行解,对问题的解决至关重要,对式(5)的约束问题,设计一种简单有效的罚函数,经其转化后的无约束问题为式(8),其中和为大于零的罚函数尺度系数。
2.2.2 具有自适应参数的改进差分进化算法
标准DE的参数在进化过程中是保持不变的,对于不同的优化问题要确定合适的参数是比较困难的[6],为使参数选择独立于优化问题本身,试采用自适应参数策略。
由式(3)可知,CR越大,越有利于局部搜索,但对目标矢量的破坏也越大;CR越小,有利于保持种群的多样性但不易产生新的个体。采用随着适应度值变化的自适应参数,对适应度差的个体,取较大的CR,让变异个体对试验个体贡献大,使该个体加快被淘汰,而适应度好的个体,取较小的CR,使该个体进入新种群的机会增大。自适应参数如式(9):
CRi为当前第i个个体的CR值,fi为第i个个体的适应度值,fminfmax分别为当前种群中适应度最好和最差的个体适应度值。
改进后的DE算法可以在进化初始阶段有较强的全局搜索能力,尽可能多地发现可能的全局最优点,而在后期有较强的局部搜索能力,提高了DE算法的收敛速度和求解精度。
为验证参数自适应改进差分进化算法的有效性,用以下函数测试算法的性能。函数f1和f2的种群规模都取10D,最大迭代次数为100。对于标准的DE,F=0.8,CR=0.8;对改进的DE取F=0.8,CRmin=0.2,CRmax=0.9。
函数f1,用标准DE算法优化,在100代内并未收敛。而改进的DE在进化到67代时收敛于0.09。优化f2,标准DE算法在47代的时候收敛于1.20,而经过改进的DE算法在迭代到第12代的时候就收敛于1.18。
2.3 改进差分进化算法在整数规划问题中的应用
2.3.1 问题描述
差分进化算法采用实数编码[7],在连续空间进行优化计算,若将DE用于求解整数规划问题时,必须进行改进。这是因为初始种群在经过差分变异操作后,可能产生非整数解的情况。
可以对变异后的矢量进行向上或向下取整运算,使得变异操作先在实数域中进行,既扩大了寻优的空间,又保证变异后为整数解。通过对变异矢量进行改进后,DE算法就可以应用于整数规划和混合整数的优化问题了。式(10)为对变异后的矢量进行取整改进。
2.3.2 函数优化应用
函数f3参数设置为NP=6 0,G=1 0 0,F=0.8,CRmin=0.2,CRmax=0.9。经过改进DE算法计算可以在第7代得到最优解f3(1,0,1,0,0)=-4。由图3可知,改进DE在解决整数规划问题时有很好的寻优能力,收敛速度快,算法稳定。
3 结论与展望
差分进化算法是继遗传算法后又一种全局优化算法,以其简单的算法理论,快速的收敛速度和较好的全局搜索能力得到国内外学者的广泛关注。但与其他成熟的智能算法相比,还存在待改进的地方,特别是其应用的领域还很小。这是因为DE采用实数编码,主要应用在连续空间的优化问题,而现实中多为离散、非线性的问题,如旅行商问题、0-1背包问题、车辆调度问题等,限制了DE算法的应用。因此有必要继续研究DE算法,从而扩大DE算法的应用领域,解决更多的实际问题。
参考文献
[1]Price K V.An introduction to differential evolution[M].New Ideas in Optimization,UK:McGraw Hill,1999:79-108.
[2]Storn R,Price K V.Differential evolution:a simple and efficient heuristic for global optimization over continuous space[J].Journal of Global Optimization,1997(11):341-359.
[3]王培崇,钱旭.差分进化计算研究综述[J].计算机工程与应用.2009,45(28):13-16.
[4]吴亮红.差分进化算法及其应用研究[D].长沙:湖南大学硕士学位论文.2007.
[5]郭振宇,程博.一种并行混沌差分演化算法[J].西安交通大学学报,2007,41(3):299-302.
[6]Brest J,Greiner S.Self-adapting control parameters in differential evolution:A comparative study on numerical benchmark problems[J].IEEE Transactions on Evolutionary Computation,2006,10(6):646-657.
量子遗传进化算法的收敛性研究 篇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.
求解JSP的改进差分进化算法 篇6
随着市场竞争的日趋激烈,每个企业都在寻求先进制造系统,以提高企业的生产管理效率,从而提高企业的核心竞争优势。而有效的调度方法和优化技术是实现先进制造的基础和关键。为了更好地应用于生产实践,生产调度问题的研究已由经典作业车间调度问题JSP(Job-Shop Scheduling Problem)逐渐向多目标、实用化、动态化等方向发展。动态柔性作业车间调度DFJSP(Dynamic Flexible Job-Shop Scheduling Problem)是JSP的重要扩展,它体现了实际生产环境中存在并行机和多功能机的特征。
目前常用的求解JSP问题方法主要是智能算法或者多个智能算法的混合算法[1,2,3,4,5,6]。然而这些成果的共同的缺陷是,编码都存在一定的局限性,缺少通用性。比如,文献[5]中采用扩展工序的编码方式,每个染色体用N×max{nj}个代表工件号的自然数组成,各工件号均出现max{nj}次。对于工序数小于max{nj}的工件,多出的部分表示“虚工序”,解码时将其加工时间均设为0,虽然“虚工序”不影响问题本身,但显然“虚工序”增加了编码的无谓的长度。
针对上述问题,本文提出了一种改进的差分进化算法。该算法为了适应差分进化算法的实数编码特点,改进了文献[1]中提出的双层编码机制,新的编码具有很强的通用性,适用于完全柔性、部分柔性、静态、动态、单目标和多目标等不同情况下的作业车间调度问题;在次序号编码基础上,对应改进了变异算子,使得在进化过程中,不会产生无效解,进而提高算法的运行速度;还改进了缩放因子,提高种群的多样性;最后通过多个典型实例计算验证了算法的可行性和有效性。
1 作业车间调度问题描述
Job Shop问题可以描述为:设有N个工件在M台机器上加工,由于工件的加工工艺的要求,每个工件使用机器的顺序及其每道工序所花时间已给定,调度问题就是如何安排在每台机器上工件的加工顺序,使得某种指标最优。具体满足下面条件:(1)每一工件在机器上的加工顺序一定;(2)每一台机器每次只能加工一个工件;(3)每一工件在机器上的加工被称为一道工序,工序加工时间是固定的;(4)工件在机器上被加工时不允许被打断;(5)机器与工件可能开始时间都为0[7]。
Makespan为调度的最小生产周期,即所有工件的最大完成时间的最小值,调度问题要求确定机器上工件加工顺序,使Makespan时间达到最小。上述问题的数学描述如下:
其中,cik和pik分别为i工件在机器k上的完成时间和加工时间;M是一个足够大的正数;若机器h先于机器k加工工件i,则aihk=1,否则aihk=0;若工件i先于工件j在机器k上加工,则xijk=1,否则xijk=0。
2 求解JSP的改进差分进化算法
2.1 实数次序号编码
实际情况,一方面,JSP大多是动态的、柔性的和多目标的,因此编码要综合考虑这些情况;另一方面,因为DEA算法是一种基于实数编码的演化算法[8],而作业车间调度中的机器编号、工序编号以及工序加工次序都是整数,所以作业车间调度常用的编码方法不能直接应用到差分进化算法中。
为了同时解决上述两方面问题,本文改进了文献[1]中的编码方法。一方面,将第二层中的编码表示为每个工序加工机器的动态实数次序号,而不是加工机器,这样就可以将编码直接应用在DEA算法中,而且改进后的编码可以直接进行DEA交叉变异进化操作;另一方面将编码的长度设置为动态可变的,这样可以适应JSP的动态多变的特性。具体方案如下。
编码的长度为所有加工工件的所有工序数。对于一个有n个工件、m台机器的动态FJSP,每个工件的未加工工序数量分别为s1,s2,…,sn,则编码的长度为s1+s2+…+sn。以3工件3机器的P-FJSP为例,每个工件的未加工工序数量分别为2,1,3,则编码的长度为2+1+3=6。加工约束条件和加工时间如表1所示。其中Jik(1≤i≤3,1≤k≤3)表示工件i的第k个工序。
由表1汇总出每个工序可用的加工机器数量如表2所示。
本文提出的编码列数为工序数量之和,层数为2层。第一层表示每个工序的加工优先级,取值为实数。第二层表示每个工序加工机器的次序号。加工次序号不同于加工机器编号。每个工序的次序号的取值范围为介于[0,Sij)(Sij表示第i个工件的第j道工序可使用的加工机器数量)之间的小数。如表2的工序数量之和为6,因此编码为6列,表3给出了表1问题的一个个体的编码。
如果加工次序号取整后为0,则在表1中,从左往右,选择工序的第1个加工机器,如果加工次序号取整后为1,则在表1中,从左往右,选择工序的第2个加工机器,依次类推。
解码的主要工作是排定工序加工顺序,并选定加工机器。解码时,首先将第二层编码取整。然后对编码中的第一层实数从小到大排序,从而得到一个各工件加工的优先级序列。然后根据优先级序列和作业车间调度问题的约束条件,分别将工序分配到对应的机器上。得到一个调度解。
对表3第二层编码取整后结果如表4所示。
然后将表1中所有工序集中在一起看作AOV网络图,结合各工序的优先权随机数对AOV图进行拓扑排序,进行解码。其过程与文献[9]类似。在此不赘述。
2.2 与常用编码方法比较
本文提出的实数次序号编码主要有以下优点:
(1)编码能适应于完全柔性、部分柔性、静态和动态,通用性好,无论哪种情况发生,只要根据实时情况,根据工件的未加工工序数量更改个体编码的列数即可。
比如,当某个工件的一个工序完成后,又新增加了一个工件。此时,编码时,将已完成工序的工件工序数量减1,然后增加新的工件工序数,重新执行调度算法就能得到新的调度方案。操作简单。
再比如,当某台机器发生故障时,只需要将使用该机器的工序的加工机器中去掉该机器,然后执行调度算法就能得到新的调度方案,操作也很简单。
(2)编码的每一位都是有效的,没有冗余,因此,编码、解码的时间复杂度也低,算法运行快。
(3)编码不会产生无效解。无论初始种群还是,交叉变异的中间个体,都不会产生无效解。2.4节介绍了如何避免变异时产生无效解。
表5将文献[1]编码、本文的编码、常用的基于操作的编码和基于工件的编码进行了比较。
其中,operation-based representation表示基于操作的编码;jobbased representation表示基于工件的编码。order number表示本文提出的实数次序号编码。n表示工件个数;m表示每个工件号出现m次。
基于操作的编码方式将每个染色体用n×m个代表操作的基因组成,各工件号均出现m次,这种编码不灵活,不能适应动态变化的作业调度。
基于工件的编码方式将每个染色体用n个代表工件的基因组成,编码长度虽然比较短,但也是固定长度的编码,不灵活,不能适用动态多变的作业车间调度。
从表5可以看出,本文提出的次序号编码方法是一种可行、简单、灵活的编码方法。
2.3 变异算子的改进
差分进化的变异算子结果为实数,而且实数范围是不确定的,而本文编码第二层的每一位实数的范围为[0,Sij),超出这个范围的编码将是不合法的编码,如果不合法的冗余编码出现,将会降低算法执行速度,因此,就要把变异运算的结果,调整为[0,Sij)范围内,这样就能避免冗余的不合法编码出现,提高算法的效率。
本文采取将变异结果取绝对值后多次开方运算进行调整,多次开方一直到变异结果的值调整为[0,Sij)范围内为止。第3节的实验结果证明,这种方法是可行有效的。
2.4 F的改进
DEA是目前演化计算研究领域中的一个著名算法。算法中的缩放因子F决定着经过变异操作,产生的差分矢量的缩放比例,是影响算法性能优劣的重要因素之一[13]。缩放因子对算法的影响,主要是收敛速度和种群多样性。本文提出了一种自适应的缩放因子F,使缩放因子能够随着迭代次数的改变而改变,适应当前种群的变化情况,使得最优解可以保存。自适应的缩放因子F为:
其中,NP为种群规模,f(Xi)为个体Xi的适应度函数值,f(Xbest)为最优个体Xbest的适应度函数值。
显然,式(2)使得F的取值为动态的。迭代次数越小,种群个体差异越大,种群个体的平均适应度函数值越小,F值越大,种群多样性越多,提高了前期迭代时算法的全局收敛速度。随着迭代次数的增加,种群个体的差异性降低,种群个体的平均适应度函数值越接近Xbest的适应度函数值,F的值越小,提高了算法后期的局部搜索能力。
2.5 求解JSP的改进差分进化算法
设种群规模NP,最大迭代次数Gmax,种群当前的迭代次数为generation,每代的最好个体为BestIndividual。
改进的差分进化算法IDEA伪码如下:
算法IDEA算法
1)初始化种群,确定generation=0
2)计算初始种群个体的适应度值,初始化BestIndividual
3) while generation<Gmax do
4)采用DE/best/1/bin模式进行变异运算,F由式(2)得。
5)变异运算结果使用2.3节方法进行调整;
6)进行交叉操作,Pc根据具体实例设定,详见表6所示。
7)对种群进行选择操作;更新BestIndividual的值。
8) generation=generation+1
9) end while
10) print (BestIndividual)
3 实验
3.1 算法比较
对12个国际通用的标准实例进行了测试,参数设置如表6所示,与已知最优解的比较结果如图1所示
从表6可以看出,针对不同的问题需设置不同的种群规模值、种群最大迭代次数和交叉概率。如果问题的机器数m比较少时,种群规模一般设置为40～65之间,迭代次数设置的相对小些,杂交概率设置范围为0.05～0.1之间,但当m值比较大时,种群规模要设置的大一些。迭代次数也要设置的大一些,杂交概率设置的要小一些,范围为0.04～0.05之间。
横坐标数字1—10表示算法执行次序。纵坐标=(每次计算的最优值-C**)/C**×100;C**为问题的基准最优解。
从图1可以看出,与已知最优解相比,IDEA算法在求解典型实例时,对FT06、LA01、LA02、LA04、LA05、LA06、LA07、LA11这些实例,IDEA算法所求解的结果与基准最优解相同,对FT10、FT20、LA03、LA16这些实例的求解,虽然没有得到和基准最优解一样的解,但偏差比较小,说明IDEA算法是高效的算法,而且标准差也比较小,说明IDEA算法是很稳定的。
3.2 IDEA与其它权威文献中的算法比较
将混合算法随机运行20次的最优结果与JSP研究领域的权威文献[10,11,12]比较,如表7所示。其中,P表示基准测试问题;n和m分别表示工件和机器数目;C*为问题的基准最优解。表中的其它数据为各算法得到的最小完工时间。
从表7可以看出,IDEA算法、GA算法、SA算法和TS算法在求解FT06、LA01、LA06、LA11、LA26和LA31问题时,求解结果相同,并且和已知最优解也是相同的;在求解FT10、FT20、LA16、LA21和LA36问题时,虽然IDEA算法所求的最优解略差于GA算法、SA算法和TS算法,但差距很小。综上说明本文算法是可行有效的。
4 结语
针对作业车间调度问题,本文基于差分进化算法,提出了一种新的编码方式,该方式具有强的通用性,既适用于静态调度,也适用于动态调度,既适用于柔性调度,也适用于非柔性调度;还改进了差分进化算法的变异算子和缩放因子,分别提高了算法的运行效率和种群多样性。多个典型实例计算表明,本文提出的算法是可行有效的。下一步工作,一方面是将本文算法应用到其它NP难问题上,以验证其效果和增加算法应用的广泛性,另一方面是进一步改进算法,提高其效率。
参考文献
[1]夏蔚军,吴智铭.基于混合微粒群优化的多目标柔性Job-Shop调度[J].控制与决策,2005,20:137-141.
[2]Balas E,Vazacopoulos A.Guided local search with shifting bottleneck for job shop scheduling[J].Management Science,1998,44(2):262 -275.
[3]Sabuncuoglu Ihsan,Kizilisik Omer Batuhan.Reactive Scheduling in a Dynamic and Stochastic FMS Environment[J].International Journal of Production Research,2003,41(17):4211 -4231.
[4]夏柱昌,刘芳,公茂果,等.基于记忆库拉马克进化算法的作业车间调度[J].软件学报,2010,21(12):3083-3093.
[5]吴秀丽.柔性作业车间动态调度问题研究[J].系统仿真学报, 2008,20(14):3828-3832.
[6]Ho N B,Tay J C,Lai E M K.An effective architecture for learning and evolving flexible Job Shop schedules[J].European Journal of Operational Research,2007,179(2):316-333.
[7]王凌.车间调度及其遗传算法[M].北京:清华大学出版社,2003.
[8]Storn R,Price K.Differential evolution—A simple and efficient adaptive scheme for global optimization over continuous spaces[R].Berkeley: University of California,2002.
[9]张青.基于遗传算法的数控车间作业调度系统研究与应用[D].武汉:武汉理工大学,2006.
[10]Corce F D,Tadei R,Volta G.A genetic algorithm for the Job Shop problem[J].Computers and Operations Research,1995,22(1):15 -24.
[11]Laarhoveh P V,AartsE,Lenstra J K.Job Shop scheduling by simulated annealing[J].OperationsResearch,1992,40(1):113-125.
一种新的微分进化文化算法 篇7
文化算法是Reynolds[1]提出的一种多进化模型的计算方法。根据实际的需要, 不同模型的文化算法应运而生。现主要介绍微分进化如何来完成文化算法群体空间的进化, 并用典型的标准来测试其解决约束优化问题的性能。
1文化算法
文化算法是一种双重遗传进化方法。其主要由两部分 (群体空间和信念空间) 组成, 分别实现了微观层面和宏观层面的进化。群体空间有一组问题的可能解构成, 可以被任何基于群体的进化技术来模拟, 如:遗传算法、粒子群算法等。信念空间是一个用来存储个体经验的知识库, 个体可以在信念空间中间接地学到其他个体获得的社会经验。群体空间和信念空间相互联系、相互影响。他们之间的相互作用是通过accept () 和influence () 通讯协议完成的。
图1显示了文化算法的基本框架。
2 微分进化文化算法
2.1 微分进化
微分进化是Storn和Price[2]提出的一种新颖的并行搜索方法。在搜索空间中, 随机地产生初始群体, 通过将群体中两个成员间的差向量增加到第三个成员的方法来生成新的个体。如果新个体的适应度值更好, 那么新产生的个体将代替原个体。图2为其基本流程图。图2中, t表示代数, f为个体的评价函数, D为问题的维度, P为空间的大小, CR为交叉常数 (Crossover Constant) , F为缩放因子 (Scaling Factor) , jrand为[1, d]之间的随机整数, rand (0, 1) 为[0, 1]之间满足正态分布的随机数。从算法的流程可以看出, 微分进化过程使用了交叉、变异和选择三种操作。
2.2 微分进化文化算法
微分进化文化算法用微分进化模拟文化算法群体空间的进化过程, 实现文化算法在微观方面的进化, 图3显示了其大概的流程。
对后代来说, 微分进化文化算法的突变操作受信念空间的影响。要解决约束优化问题, 自适应函数不能提供足够的信息引导适当的搜索。为了检测后代是否优于父辈, 是否可以替代父辈, 采用如下的规则:
(1) 可行个体总是优于不可行个体;
(2) 如果两个个体均为可行的, 有最好目标函数值的个体更优;
(3) 如果两个个体都为不可行的, 测量它们的标准化约束条件, 拥有少量约束条件的个体更优。
3 信念空间
3.1 知识资源
根据微分进化的特点和需要, 将信念空间的知识资源分为四种基本类型。
3.1.1 情境知识 (Situational Knowledge)
情境知识由进化过程中找到的最优样本E组成。在此影响下微分进化的变异操作为:
x′x, j=Ei+F* (xi, r1-xi, r2)
Ei是最优样本E的第i部分。为了个体的再结合, 用E代替随机选择的个体, 使其子代更接近已找到的最优点。如果在当前群体中找到的最优个体xbest优于E, 用xbest代替E完成情境知识的更新。
3.1.2 标准化知识 (Normative Knowledge)
标准化知识包含已找到的最优解向量所在的区间。其结构如图4所示。
其中, li和ui分别是解向量的第i个分量的上下界, Li和Ui为与边界相关的自适应函数值。标准化知识包含一个影响微分进化突变操作的比例因数dmi。在此影响下设计微分进化的突变操作为:
标准化知识的更新能够缩小或扩大其存储区间。当可接受个体不在当前区间时扩大当前区间;当所有可接受个体都在当前区间内, 并且它们的极值有一个更好的自适应函数值时, 缩小当前区间。用在上一代变异操作中发现的最优差分|xi, r1-xi, r2|更新dmi的值。
3.1.3 地形知识 (Topographical Knowledge)
地形知识的作用是创建一张进化过程中问题的适应值景观图。它由一组单元组成, 每个单元包含一个最优个体。根据每个单元最优个体的适应值, 形成一个最优单元序列表b。为了更好的存储管理, 在高维情况下, 用空间数据结构k_d树或k维二叉树。在k_d树中, 每个结点仅仅有两个孩子 (假如它是叶子结点, 没有孩子结点) , 表示任何一个k维的中间分割 (见图5) 。
Influence () 函数努力把孩子移到最优单元序列表b中, 微分进化突变操作相应的更改为:
li, c和ui, c是单元c的上下界, 单元c是从最优单元序列表b中随机选取的。如果在单元中找到了更好的解并且二叉树还没有达到其最大深度, Update () 函数分裂一个结点。被分割的维数是存储解和新解偏差较大的那个。
3.1.4 历史知识 (History Knowledge)
历史知识起初是为动态目标函数提出的, 用它在环境变化时找到样品。历史知识有一个列表, 其记录了环境变化前最优个体的位置。该列表最大为ω。图6为历史知识的结构, ei为第i个环境变化前找到的最优个体, dsi是参数i的平均变化距离, dri是在参数i有变化时的一般变化方向。如果在连续的p代中, 最优解保持不变, 那么不是探索环境的变化而是存储这个解。如果出现了这种情况, 假设陷入了局部最优。
在历史知识中影响下Influence () 函数的表达式如下:
xi, ew是历史知识列表中最优个体eω的第i个分量, dmi是标准化知识中第i个分量的最大偏差, lbi和ubi是输入问题变量xi的上下界, rand (a, b) 是a、b之间的一个随机数。为更新历史知识, 在进化过程中添加一个局部优化列表。如果该列表达到了它的最大长度ω, 放弃最早的元素。变化的距离和方向由下式来计算:
式中函数sgn (a) 返回标记a。
3.2 accept () 函数
Saleem[3]根据动态接收函数Accept () 的设计来计算更新信念空间需要接收的个体数目。可接收个体的数目随着代数的增加不断减少。Saleem提出环境变化时要重新设置可接收个体的数目。本文的方法中, 如果最优解在最后p代中没有改变, 将重新设置可接收个体的数目。可接收个体的数目naccepted用下述表达式得到:
%p是介于 (0, 1) 之间的参数, Saleem建议用0.2。g是代计数器, 当最优解在最后p代中没有发生改变的时将其重设为1。
3.3 Influence () 函数
Influence () 函数用来选择用于微分进化变异操作的知识资源。开始, 所有的知识资源被使用的概率是相同的, %pks=1/4;但在进化过程中, 知识资源ks被使用的概率为:
vks表示知识资源ks产生的个体在当前代中优于父辈的次数, v表示任何知识资源产生的个体在当前代中优于父辈的次数。为保证任何知识资源总有被使用的可能性, %p的下界为0.1。如果在其中一代中v=0, 那么%pks以1/4开始。Influence () 函数是对该算法以前版本[4]最重要的修改。
4 测试
为验证本文提出的方法, 采用文献[5]中著名的验证约束处理技术的实例进行测试, 并将结果与迄今为止处理约束优化最好的进化算法结果相比较。测试中参数设置如下:P=100, 最大迭代次数1 000, F=0.5, CR=1, k-d树的最大深度为12, 最优单元序列表b的长度为10, 历史知识列表的大小ω=5, a=b=0.45, %p=0.2。表格中的值是对每个问题独立运行30次得到的。
表1给出了本文提出方法的试验结果。表2给出了用随机队方法 (至今为进化算法提出的最好的约束处理技术) 得到的结果。
与随机队方法相比, 微分进化文化算法显现出很大的竞争力。微分进化文化算法在八个问题中达到全局优化, 随机队在九个问题得到全局最优化。但是, 除g02和g13外 (这里随机队显示出优势) , 微分进化文化算法在所有其它问题中得到的结果都很接近全局最优。此外, 微分进化文化算法在很多情况下表现出低标准偏差, 在一些情况下改善了随机队偏差大的缺陷。值得注意的是随机队不能在g10达到全局最优, 并表现出很大的结果偏离。另一个例子是随机队在g06与本文的方法相比也表现出很大的偏离。不过, 随机队在g01、g03、g05、g11比本文的算法显得稳定。
5 结束语
本文介绍了新的微分进化文化算法的整个实现过程。即用微分进化来模拟文化算法的群体空间, 并根据群体空间的需要对信念空间知识资源进行划分, 设置通讯协议accept () 和influence () , 实现两空间之间的相互通讯和协作。测试结果显示出微分进化文化算法在解决约束优化问题时自己的优越性。
摘要：考虑到文化算法的双重性和微分进化在解决约束优化问题中的优异, 提出用微分进化来模拟文化算法的群体空间, 完成其微观方面的进化。根据群体空间调整文化算法的信念空间并设置相应的通讯协议——accept () 和influence () 。最后, 用典型实例对微分进化文化算法进行测试, 结果显示出它在解决约束优化问题的优越性。
关键词：微分进化,文化算法,约束优化
参考文献
[1] Robert R G. An introduction to cultural algorithms. In: Proceedings of the 3rd Annual Conference Evolution Programming. Singapore: World Scientific Publishing, 1994:131—136
[2] Price K V.An introduction to differential evolution. In:Corne D, Dorigo M, Glover F, eds.New Ideas in Optimization. McGraw-Hill, London, UK, 1999:79—108
[3]Saleem S M.Knowledge-based solution to dynamic optimization prob-lems using cultural algorithms.PhD thesis, Wayne State University, Detroit, Michigan2001
[4]Landa B R, Coello C A.Culturizing differential evolution for con-strained optimization.In:ENC2004, IEEE Service Center.2004Ac-cepted for publication.
竞争和合作型协同进化算法 篇8
1 算法设计
1.1 算子设定
为实现上文所提到的目的, 首先给出以
定义2.1:
式中ci代表每个子种群的个体在全局非支配集中所占的个数, 为Pareto最优解集, k代表总的种群个数, 这样li可以称为该子种群的优势度。若存在ci=max{cm}, 则称子种群i为优势种群, 其他种群为弱势种群。
同样, 优势种群在面对可以战胜外部强敌 (即全局约束条件) 的情况下, 尽可能的保存弱势种群的存在性以满足种群的多样性。那么根据式 (2-1) 给出责任度的定义。
首先假设在当前进化过程存在某一子种群为Pt, 而Qt为该子种群在Pareto最优解集中的集。基于多目标优化理论可以知道在子种群Pt在其最优解附近或许可能存在着更优秀的解。基于此理论给出合作算子对Pareto最优解进行局部爬坡操作。
1.2 合作算子
设现有两个父代子种群
其中i=1, 2, 3, …, n通过合作算子的作用, 让两个独立在不同决策空间搜索的子种群Pa和Pb相互引进对方的优秀基因, 以扩大算法的搜索区域。
1.3 竞争——保护算子
设现存在总种群的总个体数为N, 经过第n代进化的种群中每个子种群的优势度分别为, 则其下一代每个子种群的规模大小为, 如果经过计算下一代中的某个子种群的优势度低于预设值, 则清除该子种群。若该子种群由于外部条件必须得到保护, 则根据其他子种群的责任度对该子种群给予保护。
1.4分裂算子
当某个子种群Pt={x1, x2, …, xn}中的个体数目过大时, 该子种群多数个体不易引入其他种群的优势基因, 仅依靠自身种群内部进行的独立进化, 这样种群的多样性会较快的消失, 使得算法发生早熟。设计分裂算子如下:
其中t代表该种群进化的代数, G (0, 1/t) 为满足高斯分布的随机数。
1.3.1 测试函数一
该测试函数为一带约束条件两目标函数, 其主要用于测试多目标优化算法在pareto前沿的收敛的能力。
从表3.1可以看出CCEA算法在Spreed这个指标上具有很大的优势, 从图3-1也可以看出CCEA算法比NSGAII算法在这个测试函数的计算上具有更大的优势。
1.3.2 测试函数二
该函数为带约束的两目标测试函数, 在其约束条件内含有两个可调变量a、b, 本文选取a=0.1, b=16来对CCEA算法和NSGAII算法进行测试。该函数的PFtrue曲线为三段相互之间不连续的曲线, 在对多目标优化算法测试时, 通常对中间一段进行关注, 其主要特点在于这个区段的部分点不易被搜索到, 性能较差的算法在这部分通常表现为断开。该函数因此可以检测算法在pareto前沿的搜索能力。
由表3.2可以看出CCEA算法除了在GD这个指标上占优势以外, 在其他两个指标上并不占优势, 甚至在Spreed这个指标上略有不如。但从图3-2看出来在中间一段曲线上CCEA算法搜索出来的为一条连续曲线, 而NSGAII算法在这部分是断开的, 这可证明CCEA算法对pareto前沿解的搜索性能要强于NSGAII算法。
2 结论
本文基于本文利用大自然中种群竞争和合作的特性, 基于大自然中种群首领在种群遇到外部危险时会对整个种群进行保护的特点, 引入优势度和责任度的概念。提出一种个体之间相互竞争和协助的协同进化算法CCEA来控制各子种群繁殖的数量, 在总的种群个体数量一定的前提下, 使得优势种群拥有更多的繁殖机会, 达到扩大搜索空间的目的, 并迫使弱势种群更多的引入其他种群的优秀基因, 达到增强自身优势度的目的。通过测试报表明该算法可以显著的提高其搜索性能, 对于复杂的多目标优化问题具有较大的实用价值。
摘要：本文基于大自然进化过程中种群之间、种群与环境之间的在进化过程中的协同作用, 提出一种个体之间相互竞争和协助的协同进化算法CCEA (Coexistence co-evolutionary Algorithm) 。基本思想为通过优势度和责任度概念, 来控制各子种群繁殖的数量, 在总的种群个体数量一定的前提下, 使得优势种群拥有更多的繁殖机会, 达到扩大搜索空间的目的, 并迫使弱势种群更多的引入其他种群的优秀基因, 达到增强自身优势度的目的。通过计算表明能有效的增强算法的搜索性能。
多种群粒子群分层进化优化算法 篇9
粒子群优化算法 (Partical Swarm Optimization Algorithm, PSO) 是由美国学者Kenndy和Eberhart于1995年提出的一种群体智能优化算法[1], 现已广泛应用于科学和工程领域。但它存在收敛速度慢、容易陷入局部最优值的缺陷。本文介绍的多种群粒子群分层进化算法, 对具有不同适应度值的粒子采取不同的进化方式, 加快了算法收敛的速度和精度。
2 多种群粒子群分层进化优化算法
2.1 标准PSO
用标准PSO求解时, 先初始化一群随机粒子, 通过让粒子不断更新自己的位置, 来找到函数的最优解。在每次更新中, 粒子通过两个“极值”来调整自己的位置:粒子本身取到的最优值Pbest和粒子群找到的最优值Gbest。更新公式为:
其中, c为加速因子, rand () 是0-1之间的随机函数。
2.2 算法改进
美国的Shi和Eberhart引入惯性权重的概念[2], 将更新公式变为:
通过惯性权重w来控制前一速度对当前速度的影响。文献[3,4]基于控制理论分层控制的思想, 把PSO用于多种群2层优化, 文献[5]提出把粒子群分成两部分, 让粒子分别朝向最好最坏方向飞行。本文提出的分层进化让适应度值优的粒子采取较小的w值, 增加其局部搜索能力;让适应度值差的粒子采取较大w值, 增加其全局搜索能力, 并让适应度值特别差的用好的粒子代替, 便于粒子更快更好的找到最优值。
2.3 算法流程
Step 1.初始化n个种群, 每个种群m个粒子, 每个粒子记为Xij, 即第i个子群的第j个粒子;
Step 2.计算粒子的适应度值, 找出个体最优Xijbest、子群最优Li和种群最优G;
Step 3.根据不同适应度值将粒子分成不同层次, 对不同层次的粒子分别采取不同的惯性权重ωi, 将适应度值特别差的粒子用好的粒子替换;
Step 4.按如下公式逐个更新粒子:
Step 5.达到迭代次数或误差要求结束, 否则转Step2。
3 算法验证
为了比较算法的性能, 取Sphere、Ackley、Rastrigin、Griewank四个基准函数进行测试, 并与粒子群算法进行比较。四个函数形式为:
实例中取3个粒子群, 每群30个粒子, 每个粒子设定为3维, c1, c2, c3均取2, w按分层取得
对于适应度值与最优值差值大于10000的用最优粒子代替, 基本PSO中取w=0.7, 其他参数一样, 让每个函数分别运行100遍, 迭代90000次, 两种算法最优适应度值的平均值分别为[0.045064 0.68787 0.24894 0.14151], [0.259410.69659 0.26889 0.12891]。四个函数里边三个比基本粒子群寻到的结果要优, 两个算法的结果图像如图1、图2所示。
4 结论
本文提出的粒子群分层进化方法让具有不同适应度值的粒子取不同的惯性权重, 独立的改变自己的速度和位置, 这比基本粒子群对所有粒子采取相同操作更具针对性, 能让粒子更快更好的收敛到最优值, 通过对测试函数进行计算的结果图像很好地显示了粒子朝最优值逼近的趋势。但用来进行划分的适应度值的区间还有待进一步研究, 本文只是根据经验提出, 希望以后能有一种更好的划分适应度值的理论方法。
参考文献
[1]Kennedy J, Eberhart R C.Particle Swarm Optimization[C].IEEE International Conference on Neural Networks, Piscataway:IEEE Service Center, 1995:1942-1948.
[2]Shi Y, Eberhart R C.A Modified Particle Swarm Optimizer[C].IEEE World Congress on Computational Intelligence, 1998:69-73
[3]吕林, 罗绮, 刘俊勇等.一种基于多种群分层的粒子群优化算法[J].四川大学学报 (工程科学版) .2008;40 (5) :171-176
[4]吕林, 罗绮, 刘俊勇等.基于多种群分层粒子群优化的配电网络重构[J].电网技术.2008;2 (32) :42-45