一种极值导向的自适应演化规划

林广明，唐飞，卢鑫

（1.深圳信息技术学院科研处，广东 深圳 518172；2.深圳信息职业技术学院信息技术研究所，广东 深圳 518172）

一种极值导向的自适应演化规划

林广明1，唐飞1，卢鑫2

（1.深圳信息技术学院科研处，广东 深圳 518172；2.深圳信息职业技术学院信息技术研究所，广东 深圳 518172）

传统的演化规划（CEP）依赖高斯变异算子，而快速演化规划（FEP）选择柯西分布作为主要的变异算子。改进的快速演化规划（IFEP）是将柯西变异算子和高斯变异算子的搜索倾向混合起来。每个父代生成两个子代，一个有柯西变异算子，另一个有高斯变异算子，然后比较这两个子代，将变现好的一个保留作为下一代。在本文，我们提出了一种极值导向的自适应变异算子演化规划（OSDEP）,它的基本思想是将当前最优搜索方向引入柯西变异算子中，在OSDEP中每个个体在柯西变异算子作用下,再沿着当前最优解的方向进行搜索。大量的数值试验对OSDEP,IFEP,FEP 和 CEP进行比较。从这些具有广泛代表性的七个测试函数的数值试验结果，我们可以观察到对于单峰函数、有少数局部最优的多峰函数和有很多局部最优的多峰函数DSEP比IFEP,FEP 和 CEP都要表现好。

演化规划，高斯变异，柯西变异，极值导向自适应变异

尽管演化规划(EP)最早是作为一种人工智能的方法提出来[1]，但后来它被成功用来求解数值优化和组合优化问题[2-4],[18]。用EP来求解优化问题可用以下两个主要步骤来解释：

（1）在当前解的群体中产生变异；

（2）从当前解和变异结果群体中选择下一代的群体。

这两个主要步骤可以认为传统的“生成-测试”方法[5]的基于群体的版本，其中变异算子可以看成用来“生成”新的解（子代）而选择算子用来“测试”那些新的解能成活下来到下一代。EP的公式化为了将它看成“生成-测试”方法的特殊情况，为EP和其它的搜索方法建立一座桥梁。这些搜索方法如演化策略(ES)、遗传算法(GA)、模拟退火算法(SA)、禁忌搜索算法（TS）、微粒群算法（PSO）、蚁群算法（ACO）、差分进化（DE）等，我们可以将它们混合在不同的研究领域中形成新的算法。

EP在求解一些多峰函数优化问题是有一个缺点，是它在接近最优解时收敛较慢。EP的“生成-测试”设计指出变异算子从当前解生成新解的关键搜索操作。在文献[6],[19]中一种基于柯西随机数的变异算子被引用到EP中，并对23个测试函数进行了数值试验。这种带柯西变异算子的新EP对于具有很多局部最优的多峰函数明显优于用高斯异算子的传统EP（CEP）,而对于具有少数局部最优的多峰函数它的表现也与CEP相当。在文献[6]，[19]中将这些新EP分别定义为“快速演化规划”简记FEP和“改进的快速演化规划” 简记IFEP。

文献[6],[19]中做了大量的数值试验比较FEP和CEP的优缺点，试验表明柯西变异算子对于大部分多峰优化问题是一个有效的搜索算子,而FEP的性能在本文中将进一步得到改善。

1 用传统演化规划和快速演化规划求解优化问题

其中f不需要是连续的，单必须是有界的。本文仅讨论无约束函数优化问题。

1.1 传统演化规划（CEP）

Fogel[1],[3]和，Schwefel[7]曾经对他们测试的函数指出带自适应变异算子的传统演化规划通常比不带自适应变异算子的传统演化规划表现要好。基于这个理由，在本文中我们来观察带自适应变异算子的传统演化规划。像和Schwefel[7]所描述的那样，本文所研究的带自适应变异算子的传统演化规划的实现步骤如下：

1）在初始种群中产生μ个个体，并且设k=1，每个个体是一对实数向量，其中是变量，高斯变异的标准方差（它也是被自适应演化算法认为的策略参数）。

7）如果满足停机条件则停止；否则设k=k+1并转到步骤3.

1.2 快速演化规划(FEP)

以原点为中心的一维柯西密度函数定义如下：

其中t＞0 是规模参数。它对应的分布函数是：

本文所研究的快速演化规划除了上节方程（1）有以下方程（4）替换以外，其他步骤完全与CEP相同[6]：

其中σj是当t=1时对于每个j产生的柯西随机数。在这里值得一提的是我们在快速演化规划FEP中保留方程（2）不变，是为了使传统演化规划CEP的改变最少。因此在其他参数保持不变的情况我们很方便地观察到柯西变异算子对于FEP 的影响的情况。

1.3 改进的快速演化规划 (IFEP)

在文献[19]的研究中，我们提出了一种改进的快速演化规划（IFEP）,其基本思想是基于不同变异算子的“融合”而不是“交替”。在算法的运行过程中“融合”柯西变异算子和高斯变异算子的搜索倾向。IFEP的实现非常简单，它与FEP 和CEP的区别仅仅在上节2.1算法描述中的第三步。对于CEP而言仅仅替换方程（1），或对于FEP而言仅仅替换方程（4），而对于IFEP的每一个父代产生两个子代，一个由柯西变异算子产生，另一个由高斯变异算子。然后再比较评估这两个子代，选择两个子代中好的一个作为下一个子代，算法的其他部分与FEP 和CEP完全相同。对于有兴趣的读者，可以参考Chellapilla[10]对演化规划中不同变异算子做的比较。

2 极值导向自适应演化规划（OSDEP）

一般来说，在当前搜索点远离整体最优时，柯西变异算子的表现较好，而高斯变异算子在给定的区域内找局部最优表现较好。这表明在当前搜索点远离整体最优解时用柯西变异算子比较合适，而在当前搜索点在整体最优解邻域用高斯变异算子比较合适。不幸的是对于未解决的问题最优解在什么地方是事先不知道的，决定何时从柯西变异算子转到高斯变异算子是非常困难的。自适应高斯变异算子[2],[7],[9]是部分解决这个问题的一种出色的技术。在这种情况下，算法自己将学着何时从一种步长“转换”到另一种步长。这意谓将来是否集成自适应算法和CEP或FEP留下一定的空间。然而，经典的搜索理论告诉我们，搜索步长搜索方向是设计高性能搜索算法的两个关键因素，上述方法仅从搜索步长方面设计算法，而忽略了搜索方向。下面我来讨论如何将搜索方向的因素加到演化规划中。

微粒群算法 (particle swarm optimizer，简称PSO)是Kennedy和 Eberhart[20]于1995年开发的一种演化计算技术，其基本思想是受到他们早期对鸟类群体行为研究结果的启发 ,并利用和改进了生物学家的生物群体模型 ,以使微粒能够飞向解空间，并在最优解处降落。PSO算法自提出以来 ,引起了国际上相关领域众多学者的关注和研究 ,成为国际演化计算界研究的热点。PSO初始化为一群随机微粒 (随机解)，然后通过迭代找到最优解。在每一次迭代中，微粒通过跟踪两个“极值 ”来更新自己：第一个就是微粒本身所找到的最优解，这个解叫做个体极值 pBest；另一个极值是整个种群目前找到的最优解，这个极值是全局极值 gBest。PSO算法的卓越性能正是引入了两个“极值 ”来引导个体向最优解的搜索方向进行搜索。我们从PSO中受到启发,将“极值 ” 的搜索方向引入演化规划中，构造一个极值导向的变异进程如下：

其中Nj（0,1）为（0，1）高斯中的随机数，gBest是当前最优值，σj是当t=1时对于每个j产生的柯西随机数。

OSDEP的实现非常简单，它与FEP 和CEP的区别仅仅在上节2.1算法描述中的第三步。对于CEP而言用方程（5）替换方程方程（1），或对于FEP而言用方程（5）替换方程方程（4），算法的其他部分与 FEP 和CEP完全相同。

3 测试函数

采用适当和标准化的测试函数集合来对演化算法在有效性和效率方面下定论是非常重要的[11]。

本文从不同的测试函数集合[2],[7],[12],[13]中取七个测试函数做数值试验研究。这些函数被精心挑选的目的不是为了显示OSDEP的表现比IFEP,FEP或CEP要好或差，而是要找出OSDEP什么时候并且为什么表现比IFEP,FEP或CEP要好或差。Wolpert 和Macready[14]已经证明了在一般情况的假设下，没有一个单一的算法对所有的问题都好。如果测试函数集合太小，我们很困难得到一般的定论，因为测试函数集合太小会有被挑选的问题的倾向所误导的风险，这些倾向不一定对其它问题有用。

我们对这些用来观察连续函数领域优化问题表现的测试函数做个简介，测试函数中包括简单的单峰函数、仅有少数局部最优的多峰函数和具有很多局部最优的多峰函数。它们有低维问题也有高维问题。有些甚至专门安排来测试求解全局演化优化的性能的，它们局部最优的数目随维数的增加呈指数增长。

七个测试函数有以下表1给出：

表1 用于数值试验的七个测试函数（其中n是函数的维数，是函数的最小值，）Tab.1 The 7 benchmark functions and used in our experimental study,where n is the dimension of the function;fminis the minimum value of the function and

表1 用于数值试验的七个测试函数（其中n是函数的维数，是函数的最小值，）Tab.1 The 7 benchmark functions and used in our experimental study,where n is the dimension of the function;fminis the minimum value of the function and

函数f1和f2是高维单峰问题，函数f3和f4是多峰问题，并且局部最优值随函数维数的增加呈指数增长[12,13]，这类型函数对大部分优化算法（包括演化规划算法）都表现出来非常难求解。函数f5到f7是仅有少数局部最优的低维问题[13]。

4 数值试验和讨论

4.1 数值试验

为了公平比较OSDEP,IFEP,FEP 和 CEP,对于所有的试验IFEP种群的大小是FEP和CEP的一半，因为IFEP每个个体都要产生两个子代。这种方法提供了一个简单便于实现的比较方案。

OSDEP的测试使用与IFEP,FEP 和 CEP同样的试验设置。在所有的试验中，对于方程Eq.(2.2)中的参数和算子设置如下：种群的大小 (μ=100),锦标选择大小(q=10),初值 =3.0。OSDEP,IFEP,FEP 和CEP的初始种群一样。这些参数是，Schwefel[7]和Fogel[2]建议考虑的，表2是50次独立运行结果的平均总和。

表2 关于函数f1到f7，OSDEP,IFEP, FEP 和 CEP的比较（其中Mean Best表示在最后一代发现函数最好值的平均）Tab.2 Compuring among OSDEP,1FEP,FEP and CEP on function f1to f7

4.2 讨论

从表2我们可以清楚地看到，OSDEP明显好于IFEP、FEP和CEP的表现。这些结果显示对于有很多最小值的多峰函数，OSDEP比IFEP要好，并且对于单峰函数OSDEP表现非常好。对于有很少最小值的多峰函数OSDEP也表现非常好，而这类型函数对于IFEP、FEP来说处理起来有困难，此时OSDEP比CEP表现也好。

对于两个单峰函数，FEP明显比CEP表现差，而OSDEP在f1，f2比CEP表现好。我们再仔细观察，在f1、f2上OSDEP比CEP几乎好一个数量级。

对于三个Shekel函数f5到f7，OSDEP明显改进了IFEP、FEP在三个Shekel函数上的表现。

我们有信心地认为对于大部分的测试函数，OSDEP的表现要比IFEP、FEP和CEP都要好。这是个非常有意义的成果，通过对已有的FEP和CEP仅仅做了很小的改动，却可以得到显著的变化。不需要对问题预先了解和使用复杂的算子，也不需要更多的参数。OSDEP的优点还表现在混合不同搜索步长对于鲁棒的搜索算法是很重要的。

事实上，柯西变异算子在演化早期起着主要的作用，因为一般来说在演化早期当前解与整体最优解有相当大的距离，因此大步长的柯西变异算子表现会好些。然而，随着演化的进步，当前解与整体最优解越来越近，由大步长柯西变异算子产生的子代就要比小步长的高斯变异算子产生的子代表现要差。高斯变异算子在演化后期就要起着主要的作用了。将“极值 ” 的搜索方向引入演化规划后使搜索有的明确的方向，明显提高了搜索的效率。

5 总结与展望

OSDEP 同时用柯西和高斯两个变异算子,并且通过当前解与整体最优解作为搜索方向，而不是它们单独一个变异算子或者交替使用它们两个变异算子。不像其它交替算法必须决定什么时候交替使用不同的变异算子，OSDEP不需要任何交替的决定和与交替相关的参数。OSDEP 是一种鲁棒的算法，即使事先对问题没有任何了解，对于所有的测试函数，OSDEP都比CEP好，有的甚至比IFEP和FEP要好。将来何以将OSDEP与其它的自适应算法（比如 Oman's 算法[15]）进行比较，并且将柯西变异算子和极值导向用到其它的演化算法中[16]。

OSDEP和 FEP的思想可以用到其它的演化算法中设计快速优化算法[17]，对于 (μ+λ) 和 (μ,λ)演化策略（其中 μ＜λ），OSDEP 会特别注目，因为一个父代可以产生几个子代，如果每个子代由不同的变异算子产生，那么得到更好的子代的机率会更大。

（

）

[1]Fogel,L.J.,Owens,A.J.and Walsh,M.J.:Artificial Intelligence Through Simulated Evolution.John Wiley &Sons,New York,NY 1966.

[2]Fogel,D.B.:System Identification Through Simulated Evolution:A Machine Learning Approach to Modeling.Ginn Press,Needham Heights,MA 02194,1991.

[3]Fogel,D.B.:Evolving Artifical Intelligence.PhD thesis,University of California,San Diego,CA,1992.

[4]Fogel,D.B.:Applying evolutionary programming to selected traveling samlesman problems.Cybernetics and Systems,24:27-36,1993.

[5]Yao,X.:An overview of evolutionary computation.Chinese Journal of Advanced Software Research (Allerton Press,Inc.,New York,NY 10011),3(1):12-29,1996

[6]Yao,X.and Liu,Y.:Fast Evolutionary Programming.In Fogel,L.J.,Angeline,P.J.and Bck,T.,editors,Evolutionary Programming V:Proc.of the Fifth Annual Conference on Evolutionary Programming,pages 257-266,Cambridge,MA,1996,The MIT Press.

[8]Fogel,D.B.:An Introduction to Simulated Evolutionary Optimization.IEEE Trans.On Neural Networks,5(1):3-4,1994.

[9]Fogel,D.B.:Evolutionary computation:Towards a new philosophy of machine intelligence.IEEE Press,New York,NY,1995.

[10]Chellapilla,K.:Combining mutation operators in evolutionary programming.IEEE Trans.On Evolutionary Computation,2(3):91-96,1996.

[12]Schwefel,H.-P.:Evolution and Optimum Seeking.John Wiley &Sons,New York,1995.

[14]Wolpert,D.H.and Macready,W.G.:No free lunch theorems for search.IEEE Transcation on Evolutionary Computation,1(1):67-82,1997.

[15]Omran,M.G.H.,Salman,A.and Engelbrecht,A.P.:Selfadaptive Differential Evolution.Hao,Y.et al (Eds.):CIS 2005,Part I,LNAI 3801,192-199,Springer-Verlag Berlin Heidelberg 2005.

[16]Lam,T.,Soliman,O.and Abbass,H.A.:A Modified Strategy for the Constriction Factor in Particle Swarm Optimization.Randall,M.,Abbass,H.A.and Wiles,J.(Eds):ACAL 2007,LNAI 4828,333-344, Springer-Verlag Berlin Heidelberg 2007.

[17]Yao,X.and Liu,Y.:Fast Evolution Strategies.Control and Cybernetics,26(3):467-496,1997.

[18]Duan,M.and Povinelli,R.:Nonlinear Modeling:Genetic Programming vs.Fast Evolutionary Programing,Intelligent Engineering Systems Through Artificial Neural Networks (ANNIE 2001) pages 171-176,2001.

[19]Yao,X. Liu,Y.and Lin,G.:Evolutionary programming made faster.IEEE Trans.Evolutionary Computation,1999,3(2):82-102

[20]Kennedy,J.and Eberhart,R.C.:Particle swarm optimization[A].Proc IEEE international conference on Neural Networks [ C].USA:IEEE Press ,1995 ,4.1942 - 1948.

A Self-adaptive evolutionary programming based on optimum search direction

LIN Guangming1,TANG Fei1, LU Xin2
（1.Scientific Research Division of Shenzhen Inititute of Information Technology.Shenzhen 518172,P.R.China 2.Information Technology Research Center,Shenzhen Information Technology,Shenzhen 518172,P.R.China）

The Classical Evolutionary Programming (CEP) relies on Gaussian mutation,whereas Fast Evolutionary Programming (FEP) selects Cauchy distribution as the primary mutation operator,Improved Fast Evolutionary (IFEP) selects the better Gaussian and Cauchy distribution as the primary mutation operator.In this paper,we propose a self-adaptive Evolutionary Programming base on Optimum Search Direction (OSDEP) in which we introduce the current best global individual into mutation to guide individuals to converge according to the global search direction.Extensive empirical studies have been carried out to evaluate the performance of OSDEP,IFEP,FEP and CEP.From the experimental results on seven widely used test functions,we can show that OSDEP outperforms all of IFEP,FEP and CEP for all the test functions.

evolntionary programming;gaussion mutation;cauchy mutation;optimum search direction adaptive mutation

O221

A

1672-6332（2015）01-0011-05

【责任编辑：杨立衡】

2015-03-01

广东省自然基金项目（S20130014108）；深圳市科技计划项目（JCYJ20130401095559825，JC201006020807A）；深圳市经济信息委员会项目（20130806094356）

林广明（1963-），男（汉），广东广州人，研究员，博士，主要研究方向：演化计算，计算智能，计算机网络通信。E-mail:lingm@sziit.com.cn