胡廉民 黄翰 蔡昭权

(1.华南理工大学 计算机科学与工程学院，广东 广州 510006;2.华南理工大学 软件学院，广东 广州 510006;3.惠州学院 科技处，广东 惠州 516007)

在演化计算领域，经典的演化算法包括了三类:遗传算法(GA)、演化规划(EP)和演化策略(ES)［1］.GA 主要针对组合优化问题，EP 和ES 多用于求解连续优化问题.演化规划最初是以有限状态机技术出现，后来推广应用到连续优化问题、组合优化问题和实际的工程优化问题［1］.在20 世纪90 年代，EP的研究主要在于参数对求解效果的影响和自适应策略的设计.研究学者又提出了多种EP 的版本，主要是将不同的分布函数融入变异算子的设计.

简单的EP 算法来源于GA 的一个简化变型，主要是采用基于均匀分布的变异算子.比较成功的第一种演化规划算法是基于Gauss 变异的EP(CEP)算法，其求解结果比非自适应高斯变异EP 算法更好.Yao 等［2］曾指出Gauss 变异EP 比较适用于单峰优化函数的求解，或者峰值分布较密的多峰函数，具有较强的局部搜索能力.他的一项重要研究成果是将Cauchy 分布引入到演化规划中［2］，设计了Cauchy 变异EP 算法(FEP)，得到了比Gauss 变异EP 更高效率的优化结果.Lee 等［3］将Lévy 分布引入到演化规划的变异算子设计，设计了Lévy 变异演化规划(LEP).Gauss 变异EP 适用于峰值分布较密的优化问题，Cauchy 变异EP 则适用于峰值分布较疏的优化问题.

除了EP 的设计研究以外，EP 的理论研究也有一定的进展，主要是集中在收敛性的分析研究上.刘峰等［4］基于Markov 过程也给出了Gauss 变异EP 算法的收敛性分析.Rudolph 和刘峰等［4-5］的主要研究成果是针对连续状态空间，比Fogel［6］的研究更有普遍性意义.高永超等［7］将模拟退火策略引入了EP，并分析了其收敛性.王向军等［8-9］设计了双种群和多种群的演化规划算法.杜海峰等［10］设计了自适应混沌克隆演化规划算法，并证明了该算法的收敛性.郝志峰等［11-12］分析了Gauss 变异和Cauchy 变异演化规划算法的计算时间，为EP 算法的改进提供了理论依据;蔡昭权等［13］分析了Lévy 变异进化规划算法的计算时间.黄翰和蔡昭权等［11，13-14］总结了这些工作，提出了分析进化算法收敛性对比的模型与分析框架.张宇山等［15］发展了这一理论并分析二元演化策略的计算时间，强调了启发式策略对算法的重要作用.上述工作为研究演化规划算法的改进提供了重要的理论依据.

变异扰动的设置和更新是演化规划算法改进设计的关键点［16-17］.现有的EP 算法的变异扰动与优化变量无关，所以很难有效地引导算法求解.本研究将重新设计变异步长向量，使得EP 算法的变异扰动可以随着优化变量的状态动态更新，实现算法的启发式迭代.

1 演化规划算法基本介绍

演化规划算法主要是用于求解连续优化问题.

可以假设f 满足:f 是有界函数;整体的极小(极大)值点集arg f*非空;f 是定义在S 上的;对于ε ＞0，集合}满足:Mε的Lebesgue测度m(Mε)＞0.其中，f*=min{f(x )x∈S}(以极小化问题为例).

演化规划算法主要包含以下步骤:

(1)任意生成K 个初始个体，每个个体是一对实值向量(xi，σi)，i =1，2，…，K.其中，xi是待优化的目标向量，σi是xi的变异步长向量.设置t=1.

(2)据目标函数f(xi)评估每一个个体(xi，σi)的适应值.

(3)对于每个个体(xi，σi)，执行相应的分布函数生成子代个体(x'i，σ'i).

(4)将父代个体和子代个体合并一起，用锦标赛法［3］选择出K 个获胜次数最多的个体作为下一次迭代的父代.

(5)若满足停机条件，则输出当前最优解并退出算法;否则，迭代次数t=t+1，返回步骤(3).

在步骤(2)中，不同的EP 算法用不同的分布函数产生变异扰动，体现在式(2)的Fj.

式中:N(0，1)为一个标准正态分布的随机变量，对于每个i 产生一次;Nj(0，1)为对于每个j 产生一次的标准正态分布随机变量，j =1，2，…，n;参数 =Fj为服从某个分布的随机数，对应第j 个分量.

2 非启发式变异EP 算法的不足

定义2 假设P{x'i∈Mε}是EP 算法中的个体xi经过式(1)和(2)变异后进入最优邻域Mε的概率.

由于Mε中的ε 可以是任意小，在连续优化问题中，个体到达最优邻域相当于达到问题的最优解.定义2 中的P{x'i∈Mε}相当于EP 算法基于该个体求得最优解的概率.

从文献［11-13］的分析可以看出，P{x'i∈Mε}是分析的关键，因为它可以决定算法的期望收敛时间.根据式(2)，有

式中:ψ 为随机向量;v 为集合的元素向量;pF(y)是随机变量的密度函数，在CEP 算法［3］中是Gauss 密度函数，在FEP 算法［4］中是Cauchy 密度函数，而在LEP［5］中是Lévy 密度函数.当参数固定时，密度函数pF(y)是固定的，即不会随着迭代时间t 变化.因此，式(3)主要是由M'ε所决定，而根据式(4)，M'ε主要由Mε和变异扰动σi所决定.Mε求解的目标问题由EP 算法所决定，问题和算法确定后Mε就固定了.根据前一段分析，∫M'εpF(y)dy 值主要由迭代中的σ、目标问题(Mε)和密度函数pF(y)所决定［18］.

因此，对于相同的问题和σ 初值，CEP、FEP 和LEP 算法的∫M'εpF(y)dy 由密度函数pF(y)所决定，3 种算法求解相同问题时会因为密度函数不同会出现性能差别.文献［7］已说明CEP、FEP 和LEP 算法分别适合求解不同的函数优化问题:CEP 算法比较适用于单峰优化函数的求解，或者峰值分布较密的多峰函数;FEP 算法适合求解多峰函数，特别是峰值分布较疏的多峰函数［19］;而LEP 算法在求解峰值分布非常稀疏的函数时有明显优势.

为了进一步研究，需要再分析变异扰动向量σi，因为CEP、FEP 和LEP 算法都是采用式(1)和(2)更新σi，所以σ'i(j)以较大的概率在σ'i(j)=σi(j)exp{-1.96('+ )}和σ'i(j)=σi(j)exp{1.96·('+)}之间变动.考虑参数和 ' =即σ'i(j)在σi(j)基础上作小范围波动.因此，随σ 变化而变化，而且σ 是迭代过程中唯一可能引起变化的因素.然而，σ 在迭代过程中的变化是完全随机波动，并非启发式地变化.

因此，σ 的设置和更新是演化规划算法改进设计的关键点.原有EP 算法中σ 的变化与变量x 的状态无关，所以无法有效地引导算法求解.本研究将重新设计变异步长向量σ，使得σ 可以根据x 动态地更新，使得:即使σ 初值令值较小时，迭代过程中σ 的动态更新仍可以令以较大概率增大，从而提高算法的性能.

3 启发式变异EP 算法的设计与分析

3.1 启发式变异算子

文中提出了一种启发式变异的EP(HMEP)算法.HMEP 算法沿用EP 算法的框架(见第2 节)，主要修改的内容集中在σ 和x 的更新.

变异步长向量改为下式，每个个体(xi，σi)，执行下面公式生成子代个体的变异步长σ'i:

r1和r2是{1，2，…，K}中的均匀随机整数，满足r1、r2和i 互不相同.式(6)的设计主要是以随机抽取的两个个体差异来更新变异步长.在生成σ'之后，按照式(6)产生新的变异个体.

其中，当t=0 时，i取(0，1］中的均匀随机数;当t ＞0 时，i以0.1 的概率取(0，1］中的均匀随机数作更新，以0.9 的概率保持不变.对于i=1，2，…，K，j=1，2，…，n，α(j)是［0，1］之间的均匀随机数，Ci为变异控制系数，当α(j)≤Ci时，个体在第j 维发生变异.O(i)则是{1，2，…，n}中的均匀随机整数，为保证个体至少有一维发生变异.当α(j)＞Ci且j≠O(i)时，个体在第j 维不发生变异，即第j 维值保持原状.Ci以0.1 的概率取(0，1］中的均匀随机数作更新，以0.9 的概率保持不变.

式(6)与式(2)最大的不同是允许个体有机会在某些维数保持原状，只是进行部分维数上的变异，使得优秀的个体片段可以保留，这是HMEP 算法与CEP、FEP 和LEP 算法的一个根本区别.当然，式(6)也可能如式(2)一样使个体在所有的维数上发生变异.为避免固定控制系数Ci影响变异效果，对于每个i 执行式(6)进行更新时，都用较小的概率重新取值.

3.2 算法性能分析

HMEP 算法的其他处理过程与CEP、FEP 和LEP 算法一样.从式(5)和式(6)可得，HMEP 算法虽然比3 种常用EP 算法增加了 i 和Ci更新步骤，但是却省略了生成Gauss、Cauchy 或者Lévy 分布随机数的生成步骤.因此，HMEP 算法并没有比CEP、FEP 和LEP 算法明显地增加计算量.

启发式变异EP(HMEP)算法是针对CEP、FEP和LEP 算法不足而改进的EP 算法，第4 节用实验结果说明了HMEP 的性能优势，本节将从理论上给出HMEP 算法的期望收敛时间分析.HMEP 采用如式(5)和(6)的变异算子，x'i(j)等价于在区间［li(j)，hi(j)］取服从均匀分布的随机值.其中，li(j)=min(xi(j)，σi(j))，hi(j)=max(xi(j)，σi(j)).

当r1和r2确定时，x'i(j)服从均匀分布对应的概率密度函数:

其中，

因此，

其中，i=1，2，…，K 和U0.CEP、FEP 和LEP 算法中σ 的变化与变量x 的状态无关，σ 在迭代过程中的变化是完全随机波动，且非启发式地变化，所以无法有效地引导算法求解.HMEP 算法设计了变异步长向量σ，使σ 可以根据x 动态地更新，使得:即使σ初值令值较小时，迭代过程中σ 的动态更新仍可以令以较大概率增大.因此，HMEP 算法可以适应更多种类的优化问题［2］，比CEP、FEP 和LEP 算法有更好的收敛速度和鲁棒性.第4 节的实验结果也证明了本节理论分析的结论.

4 实验结果与分析

在实验中，对HMEP、CEP、FEP、LEP 和ALEP算法设置相同的种群规模K=100，相同的最大迭代次数.5 种算法的50 次独立运行的均值和标准差见表1 和表2，测试问题见文献［2］.

表1 中的结果表明，HMEP 算法比FEP 和CEP算法在大多数的测试问题上求解更优;HMEP 算法在多个单峰和多峰问题求得的平均最优解明显优于FEP 和CEP 算法，而且HMEP 算法在标准差上也明显小于另外两种算法.

由表2 可知，对于单峰函数问题f1、f 3 和f5，HMEP 算法比LEP 和ALEP 算法更优.对于带多个局部最优的多峰函数问题，除了f 8 以外，HMEP 算法在f9—f13 问题求解上明显优于LEP 和ALEP 算法，且稳定性更强.对带少量局部最优的多峰函数问题f14 和f16，3 种算法则旗鼓相当.ALEP 算法被证明是目前最优的演化规划算法之一，HMEP 算法从整体上比ALEP 算法更优更稳定，可以认为是一种改进的EP 算法.

笔者还将提出的HMEP 算法与最近学者们提出的IMEP 算法［20］和LSEP 算法［21］进行了总体性能对比.结果见表3，HMEP 算法在16 个标准测试函数问题的求解上有着绝对优势，改进效果非常显著.

表1 HMEP、CEP 和FEP 算法求解性能的总体对比Table 1 Performance comparison among HMEP，CEP and FEP algorithms

表2 HMEP、LEP 和ALEP 三算法求解性能的总体对比Table 2 Performance comparison among HMEP，LEP and ALEP algorithms

表3 HMEP、IMEP 和LSEP 算法求解性能的总体对比Table 3 Performance comparison among HMEP，IMEP and LSEP algorithms

5 结语

文中基于演化规划算法计算时间分析的一般理论，分析了CEP、FEP 和LEP 等非启发式变异算法的不足，设计了一种基于个体差异的进化规划算法HMEP，从实验和理论上都证明了HMEP 算法比CEP、FEP、LEP、IMEP 和LSEP 等算法有更高的收敛速度和更好的鲁棒性.未来的工作将分析差异进化算法、免疫算法和粒子群算法等其他连续优化算法的改进，并且对算法的参数选择作进一步研究.

［1］Yao X，Xu Y.Recent advances in evolutionary computation［J］.Journal of Computer Science and Technology，2006，21(1):1-18.

［2］Yao X，Liu Y，Lin G.Evolutionary programming made faster［J］.IEEE Transactions on Evolutionary Computation，1999，3(2):82-102.

［3］Lee C Y，Yao X.Evolutionary programming using mutations based on the Lévy probability distribution［J］.IEEE Transactions on Evolutionary Computation，2004，8(1):1-13.

［4］刘峰，刘贵忠，张茁生.进化规划的Markov 过程分析及其收敛性［J］.电子学报，1998，26(8):76-79.Liu Feng，Liu Gui-Zhong，Zhang Zhuo-sheng.Markovian process analyses and convergences of evolutionary programming［J］.Acta Electronica Sinica，1998，26(8):76-79.

［5］Rudolph G.Self-adaptation and global convergence:A counter-example［C］∥Proceedings of the Congress on Evolutionary Computation.Piscataway:IEEE，1999:646-651.

［6］Fogel D B.An introduction to simulated evolutionary optimization ［J］.IEEE Transactions on Neural Networks，1994，5(1):3-14.

［7］高永超，李歧强.退火进化规划算法及其收敛性［J］.系统仿真学报，2006，18(3):577-580.Gao Yong-chao，Li Qi-qiang.Annealing evolutionary programming algorithm and its convergence ［J］.Journal of System Simulation，2006，18(3):577-580.

［8］王向军，嵇斗，张民.一种多群竞争进化规划算法［J］.电子学报，2004，32(11):1824-1828.Wang Xiang-jun，Ji Dou，Zhang Min.A multi-subgroup competition evolutionary programming algorithm［J］.Acta Electronica Sinica，2004，32(11):1824-1828.

［9］王向军，向东，蒋涛，等.一种双种群进化规划算法［J］.计算机学报，2006，29(5):835-840.Wang Xiang-jun，Xiang Dong，Jiang Tao，et al.A novel bigroup evolutionary programming［J］.Chinese Journal of Computers，2006，29(5):835-840.

［10］杜海峰，公茂果，刘若辰，等.自适应混沌克隆进化规划算法［J］.中国科学E 辑信息科学，2005，35(8):817-829.Du Hai-feng，Gong Mao-guo，Liu Ruo-chen，et al.Adaptive chaotic clone evolutionary programming algorithm［J］.Sciences in Chinese Ser.E Information Sciences，2005，35(8):817-829.

［11］黄翰，郝志峰，秦勇，进化规划算法的时间复杂性分析［J］.计算机研究与发展，2008，45(11):1850-1857.Huang Han，Hao Zhi-feng，Qin Yong.Time complexity of evolutionary programming［J］.Journal of Computer Research and Development，2008，45(11):1850-1857.

［12］Hao Z F，Huang H，Li H Z，et al.A relation-based model for convergence analysis of evolutionary algorithm［C］∥Swarm，Evolutionary，and Memetic Computing.Berlin，Heidelberg:Springer，2010:190-197.

［13］蔡昭权，罗伟，张宇山，等.Lévy 变异进化规划算法的计算时间分析［J］.计算机科学，2011，38(9):197-200.Cai Zhao-quan，Luo Wei，Zhang Yu-shan，et al.Runningtime analysis of evolutionary programming based on Lévy mutation［J］.Computer Science，2011，38(9):197-200.

［14］黄翰，林智勇，郝志峰，等.基于关系模型的进化算法收敛性分析与对比［J］.计算机学报，2011，34(5):801-811.Huang Han，Lin Zhi-yong，Hao Zhi-feng，et al.Convergence analysis and comparison of evolutionary algorithms based on relation model ［J］.Chinese Journal of Computers，2011，34(5):801-811.

［15］张宇山，郝志峰，黄翰.二元进化策略的收敛性分析［J］.计算机科学，2011，38(7):231-234.Zhang Yu-shan，Hao Zhi-feng，Huang Han.Convergence analysis of two-membered evolution strategy［J］.Computer Science，2011，38(7):231-234.

［16］Lu T C，Juang J C.A region-based quantum evolutionary algorithm(RQEA)for global numerical optimization［J］.Journal of Computational and Applied Mathematics，2013，239:1-11.

［17］Zhao L，Wang L，Cui D W.Hoeffding bound based evolutionary algorithm for symbolic regression［J］.Engineering Applications of Artificial Intelligence，2012，25(5):945-957.

［18］郝志峰，蔡瑞初.并行多任务环境下Agent 联盟的快速生成算法［J］.华南理工大学学报:自然科学版，2008，36(9):11-14，30.Hao Zhi-feng，Cai Rui-chu.Fast generation algorithm of Agent coalition in parallel multi-task environment［J］.Journal of South China University of Technology:Natural Science Edition，2008，36(9):11-14，30.

［19］李学强，郝志峰，黄翰.基于分方向选择搜索的多目标进化算法［J］.华南理工大学学报:自然科学版，2011，39(2):130-135.Li Xue-qiang，Hao Zhi-feng，Huang Han.Multi-objective evolutionary algorithm based on direction selection search［J］.Journal of South China University of Technology:Natural Science Edition，2011，39(2):130-135.

［20］Shen L，He J.Evolutionary programming using a mixed strategy with incomplete information.［C］∥2010 UK Workshop on Computational Intelligence(UKCI).Colchester:IEEE，2010:1-6.

［21］Shen L，He J.A mixed strategy for evolutionary programming based on local fitness landscape［C］∥Proceedings of 2010 IEEE World Congress on Computational Intelligence.Barcelona:IEEE，2010:350-357.