种群自适应调整的克隆多峰函数优化

1.湖南机电职业技术学院 信息工程系，长沙 410151

2.华中科技大学 计算机科学系，武汉 430074

3.同济大学 软件学院，上海 230021

1.湖南机电职业技术学院 信息工程系，长沙 410151

2.华中科技大学 计算机科学系，武汉 430074

3.同济大学 软件学院，上海 230021

1 引言

现实生活中的很多问题都可以建模为函数优化问题。同时，由于问题本身的特点，很多问题都属于多峰函数优化问题[1]，即需要求出多个全局最优解和局部最优解，进而为决策者提供多种选择。如何求得多峰函数的极大值（包括全局和局部），一直是研究者关注的课题。

求解多峰函数优化问题主要有两类方法：传统的数学优化和智能优化算法。智能优化算法由于对目标函数没有特殊要求而成为求解此类问题的有效方法。不同的研究者采用不同的智能优化算法对此问题进行求解[2-8]，如蜂群算法、遗传算法、粒子群算法、免疫克隆算法等。已有研究表明，免疫克隆算法在求解多峰值函数优化问题方面表现出了优异的性能。

克隆优化算法是一种基于种群的优化方法，种群规模的大小直接影响算法的搜索能力和计算成本[3-4]。一般来说，种群规模越大，越有利于找到全局最优解，但也会增加计算时间，导致收敛速度较慢；如果种群规模过小，虽然运行时间较快，但种群多样性不足，搜索的有效区域有限。对于多峰函数优化问题，还容易陷入局部最优，导致早熟收敛。所以，合适的种群大小对算法的效果具有重要的意义。显然，如果种群大小能随着进化代数动态变化，则能大大提高算法的性能。

基于此，本文提出了一种种群大小自适应变化的免疫克隆算法，并结合多峰函数的特点，采用基于拉马克的局部搜索机制。实验结果表明，算法可以找到更多的局部最优值，并且收敛速度较快。

2 关键技术

对于种群大小可变的克隆优化算法，需要解决3个问题：（1）种群规模大小什么时候变化，即用什么机制触发增加/删除个体的操作；（2）种群规模大小变化多少，即增加/删除个体的数目如何确定；（3）种群规模大小如何变化，即增加/删除个体具体如何实现。下面分别介绍。

2.1 种群规模大小的变化规则

对于种群规模什么时候变化的问题（第1个问题），本文主要思想为：个体是否更新来进行增加/删除个体的操作。设 psmax、psmin分别表示种群规模大小的上界和下界，psg表示第g代的种群规模。具体更新规则如下：如果全局最优个体连续k代都更新，且 psg＞psmin，则认为现有个体对种群的搜索有冗余，执行删除ninc个体的操作。反之，如果全局最优个体连续k代都不更新，则认为现有个体不足导致搜索区域不够，则执行增加算子：当 psg＜psmax时，增加一个新个体；当 psg=psmax，则删除一个性能较差的个体。其中，k是一个正整数，表示激活阈值。

2.2 种群规模变化数目

对于种群规模大小变化多少的问题（第2个问题），从本质上看，增加或者删除个体的数目，决定了种群规模 psg的变化幅度。基本思路如下：随着 psg的增大，种群规模会逐渐增加，由于资源有限，增加个体的数目ninc应该逐渐减小，而删除个体的数目dinc应该逐渐增大。而且，当 psg较小时，ninc应该大于dinc，即种群规模的增长速率应大于收缩速率，以增强种群的全局探索能力;相反地，当 psg较大时，dinc应该大于ninc，以增强深度搜索能力。

对于种群规模变化问题，本文设计了自适应确定增加/删除数目的方法。其中，增加个体的数目变化采用逻辑斯蒂（Logistic）模型直接实现[3]。

β为大于0的常数。

删除个体数目方程：

2.3 种群规模变化策略

对于种群规模大小如何变化的问题（第3个问题），本文设计了一种兼顾有效性和多样性的增加算子。

新个体的生成方法如下：

首选生成一个大小为ninc的父代个体集合s，设x1，x2为s中的任意两个个体，新个体的产生方法如下，其中a为（0，1）之间的任意数。

可见，增加算子可以为种群带来新个体，较好地改善种群的多样性，同时，新生成的个体为种群的进化提供了有用信息，从而加速搜索过程。

2.4 Larmark局部搜索机制

对于多峰函数优化问题，应该尽可能多地找到局部最优值。因此，需要设计必要的局部搜索策略。这里，使用Lamarck学习进行局部搜索。

Lamarck进化理论认为，个体后天学习获得的性状能直接反馈在基因型上[10]。已有的研究表明，Lamarck学习是一种非常有效的学习策略。局部搜索可以看作是一个个体的后天学习过程，搜索到好的抗体片段直接反馈到抗体上，并且修改个体的适应度，通过遗传作用遗传给下一代。因此，局部搜索是父代个体在其邻域上的学习过程，可以引导个体向更好的解移动。

具体如下：

假设抗体Ai原来的亲和度值为 f(Ai)，学习后的抗体亲和度为 f'(Ai)，则

其中，η为服从正态分布的随机数。若 f'(Ai)＞f(Ai)并且f'(Ai')＞fbest(t)，则学习成功，用抗体基因 Ai'替换 Ai。其中，fbest(t)为第t代最高的适应度值。

3 算法具体实现

针对多峰函数优化问题，本文设计的克隆算法具体实现步骤如下：

步骤1分别设置种群最小值PSmin，最大值PSmax，设进化代数为g，令g=0，psg为第g代的种群规模，psg=PSmin，种群增加个数cinc、删除个数dinc分别为0。

步骤3以进化代数g作为终止条件，判断是否满足结束条件。如果满足结束条件，则终止程序，输出最优解；否则，转步骤4。

步骤4根据各个抗体的亲和度值，进行克隆扩增操作。克隆采用自适应克隆[8]，即亲和度高的抗体克隆数目较多。

步骤5对克隆种群进行自适应高频变异；计算抗体的亲和度；并对亲和度较高的抗体进行larmrck学习（见2.4节）。

步骤7若cinc＞2k且 psg＞PSmin，则按2.3节执行删除操作，psg-1=psg-dinc，dinc=0，否则，转步骤10。

步骤8若cinc＜k，转步骤9。

步骤9 若 psg＜PSmax，则按2.3节执行增加操作，psg-1= psg+dinc，dinc=0 。

步骤10 g=g+1，转步骤3。

4 仿真实验与结果分析

在Windows环境下，使用Matlab7.0进行编程实现。使用基准多模态测试函数对算法性能进行比较，并与文献[7-8]进行比较。算法参数设置如下：种群PSmin=4，PSmax=100，采用二进制编码，变异概率 pm=0.5，最大进化次数 g=300，β=0.8，k=2，学习系数η=1.3。每种算法独立运行100次，结果如表1所示。

表1 相关算法性能比较

测试函数如下：

（1）Schaffer函数

（2）Shubert函数

（3）Rastrigin函数

（4）Griewank函数

（5）Schwefel函数

（6）Rosenbrock函数

上述测试函数中，Schaffer函数是具有强烈振荡的多峰函数，理论最优值为－1；Shubert函数在搜索区域内约有760个局部极值点和18个全局最优点，理论最优值为－186.730 9；Rastrigrin函数为多极值函数，在解空间内存在大约10n个（n为解空间维数）局部极小点，理论最优值为0；Griewank函数有众多局部极值，在（0，…，0）处取得全局最小值0；Schwefel函数是多峰多极值函数，在（420.96，…，420.96）处取得理论最优值0。

测试表明，本文算法表现出较强的全局寻优能力和较高的搜索精度。同时，本文算法方差较小，说明算法较为稳定。此外，本文算法运行速度较快，收敛次数较多。这些都说明本文设计的各种策略是有效的。

为了进一步说明算法在求解全局最优解方面的能力，以下面的多峰函数为例，进行说明。

该函数为多峰函数，有四个全局最大值2.118，对称分布于（+0.64，+0.64），（－0.64，+0.64），（+0.64，－0.64），（－0.64，－0.64）。该函数存在大量局部极大值，尤其是在中间区域有一取值与全局最大值很接近的局部极大值（2.077）。

图1、图2为两算法运行结束后所搜索到的最优解分布。由算法结果可以看出：本文算法具有较优的全局搜索能力，同时还可搜索到部分次优解；而文献[7]算法容易陷入局部最优，且全局搜索能力差，说明本文设计的各种算子是有效的。

图1 文献[7]运行结束后的最优解分布

以上分析表明，本文算法对于解决上述多峰函数优化问题是非常有效和可靠的。

5 结论

图2 本文算法运行结束后的最优解分布

本文提出了一种种群大小可变的克隆优化算法求解多峰函数优化问题，给出了种群变化的具体介绍和局部搜索机制。仿真实验证明，本算法寻优能力更强，同时也更加稳定可靠。

[1]郭忠全，王振国，颜力.基于种群分类的变尺度免疫克隆选择算法[J].国防科技大学学报，2011，33（5）：36-40.

[2]余航，焦李成，公茂果，等.基于正交试验设计的克隆选择函数优化[J].软件学报，2010，21（5）：950-967.

[3]傅清平.基于新型免疫算法的多峰函数优化[J].计算机应用研究，2011，43（10）：10-15.

[4]戚玉涛，刘芳，焦李成.基于信息素模因的免疫克隆选择函数优化[J].计算机研究与发展，2008，45（6）：991-997.

[5]魏臻，吴雷，葛方振，等.基于Memetic框架的混合粒子群算法[J].模式识别与人工智能，2012，46（12）：301-305.

[6]陆青，梁昌勇，杨善林，等.面向多峰值函数优化的自适应小生境遗传算法[J].模式识别与人工智能，2009，43（2）：86-91.

[7]叶文，欧阳中辉，朱爱红，等.求解多峰函数优化的小生境克隆选择算法[J].系统工程与电子技术，2010，23（5）：210-214.

[8]薛文涛，吴晓蓓，徐志良.用于多峰函数优化的免疫粒子群网络算法[J].系统工程与电子技术，2009，34（5）：213-217.

[9]王蓉芳，焦李成，刘芳，等.自适应动态控制种群规模的自然计算方法[J].软件学报，2012，23（7）：1760-1772.

[10]Gong Maoguo，Jiao Licheng，Liu Fang，et al.Memetic computation based on regulation between neural and immune systems：the framework and a case study[J].Science China：Information Sciences，2010，45（11）：2131-2138.

[11]陈杰，陈晨，张娟，等.基于Memetic算法的要地防空优化部署方法[J].自动化学报，2010，32（2）：234-238.

[12]夏柱昌，刘芳，公茂果，等.基于记忆库拉马克进化算法的作业车间调度[J].软件学报，2010，21（12）：3082-3093.

[13]罗晓明.求解VRP的变种群规模混合自适应遗传算法[J].统计与决策，2011，346（22）：30-35.

[14]Gong M G，Jiao L C，Zhang L N，et al.Immune secondary responseand clonal selection inspired optimizers[J].Progress in Natural Science，2009，19：237-253.

[15]Chen Jie，Xin Bin，Peng Zhihong.Statistical learning makes the hybridization of particle swarm and differential evolution more efficient-a novel hybrid optimizer[J].IEEE Transactions on Evolutionary Computation，2008，6（3）：239-251.

种群自适应调整的克隆多峰函数优化

裴 芳1，2，张 洁1，2，唐 俊3

PEI Fang1，2,ZHANG Jie1，2,TANG Jun3

1.Department of Information Engineering,Hunan Mechanical&Electrical Polytechnic,Changsha 410151,China
2.Department of Computer Science,Huazhong University of Science and Technology,Wuhan 430074,China
3.School of Software,Tongji University,Shanghai 230021,China

In order to get the best solutions of the multi-model function,an immune clonal algorithm with self-adaptive population size is proposed.The self-adaptive population size changes with the evolutionary process are achieved to balance the impact of population size on the efficiency of the algorithm.In addition,in terms of multi-modal function optimization characteristics, Larmark learning is used as a local search strategy to enhance the search ability for the optimal solution.The experimental results show that the algorithm has better performances.

clone optimization;multi-model function;population size;local search

为了尽可能求得多峰函数的最优解，提出了一种种群规模自适应调整的克隆算法。实现了种群规模根据进化过程自适应的变化，平衡了种群规模对算法效率的影响。此外，结合多峰函数优化的特点，为了增强算法搜索最优解的能力，采用Larmack学习策略作为局部搜索机制。实验结果表明，该算法求解效果较好。

克隆优化；多峰函数；种群规模；局部搜索

A

TP18

10.3778/j.issn.1002-8331.1210-0275

PEI Fang,ZHANG Jie,TANG Jun.Multi-model function optimization based on clonal optimization with self-adaptive population size.Computer Engineering and Applications,2013,49（11）：50-53.

湖南省教育厅自然科学研究项目（No.12C1065，No.11C0231，No.11C0232）。

裴芳（1979—），女，讲师，主要研究方向为计算智能、网络安全。

2012-10-26

2013-01-21

1002-8331（2013）11-0050-04