结合混沌搜索的自适应混沌粒子群算法

董 勇，李梦霞 （长江大学信息与数学学院，湖北 荆州 434023）

郭海敏 （油气资源与勘探技术教育部重点实验室 （长江大学），湖北 武汉 430100）

结合混沌搜索的自适应混沌粒子群算法

董 勇，李梦霞 （长江大学信息与数学学院，湖北 荆州 434023）

郭海敏 （油气资源与勘探技术教育部重点实验室 （长江大学），湖北 武汉 430100）

针对基于群体适应度方差的自适应混沌粒子群算法存在的局部搜索能力较弱的不足，在该算法中引入了混沌变异以及混沌搜索操作。使用An混沌映射对部分粒子进行混沌变异，对全局最优粒子进行混沌搜索，提出了一种综合考虑粒子位置、寻优空间的自适应变尺度规则。数值仿真结果表明，改进算法的收敛性、全局和局部搜索能力都有所提高，能有效避免早熟收敛。

混沌映射；粒子群算法；适应度方差；收敛比率

粒子群优化 （Particle Swarm Optimization，PSO）算法参数简单，容易实现，对目标函数的性态基本没有要求，能以一定的概率收敛到全局最优解，所以PSO算法得到了广泛应用，如过程动态优化［1］、约束优化［2］、交通控制［3］等。作为一种随机性算法，粒子群优化算法在高维、多峰搜索问题中容易出现早熟收敛现象。研究者给出了多种改进形式［4－7］，其中之一是结合混沌系统，利用混沌系统的伪随机性及遍历性提高粒子跳出局部最优点的能力，从而提高全局收敛的概率和速度［8］。但普遍使用Logistic混沌映射来产生混沌序列［9－10］，注意到Logistic混沌映射产生的序列均匀性较差，会在一定程度上影响算法的优化性能。文献 ［11］提出采用An混沌映射构建自适应混沌粒子群算法，利用An混沌映射初始化粒子群的位置和速度，并类似文献 ［12］，通过适应度方差的变化来自适应控制部分粒子进行混沌更新。其优化性能强于类似结构的基于Logistic混沌映射的混沌粒子群算法。原因在于An混沌映射产生的混沌序列的均匀性优于由Logistic混沌映射产生的混沌序列。但正如其所指出的，在迭代的末期，算法的局部搜索能力有大的削弱。为了改善算法的性能，笔者引入2种修改方式：一是基于An混沌映射，放宽混沌变异的触发条件，以一定的概率对非全局最优粒子进行混沌变异；二是对全局最优粒子进行混沌搜索。利用混沌系统的伪随机性及遍历性提高算法的全局和局部寻优能力。

1 An混沌映射

混沌映射产生的点，其运动轨迹复杂，具有伪随机性、遍历性等性质，介于完全随机现象和确定性现象之间。An引入的混沌映射随机数生成递推式为［13］：

2 改进的PSO算法

考虑如下所示的全局最优化模型：

2.1 标准PSO算法

标准PSO算法的速度和位置迭代公式是：

2.2 混沌映射产生初始种群

随机在0、1之间取一个值，用An混沌映射N×D－1次迭代，一共得到N×D个值，依次取出D个值构成向量，可得N个D维向量，记为cx1，cx2，cx3，…，cxN。用式（8）转换到优化空间（lb，ub），作为初始种群。

2.3 迭代更新的改进

对粒子x（t），产生［0，1］上的均匀分布随机数p，如果p＞0.5，则对该粒子按照式（12）、（1）、（3）、（8）进行变异，变异点落入区间［lb（t＋1），ub（t＋1）］，若适应度值变小则接受变异，否则拒绝变异；如果p≤0.5，则对该粒子不进行混沌变异。

2）混沌搜索 对全局极值gbest，反复利用式 （12）、（1）、（3）、（9）进行混沌迭代。如果直到混沌迭代次数达到设定上限时适应度值都没变小，则终止混沌搜索；否则，当适应度值变小时，即终止混沌搜索，更新gbest。

混沌搜索的区间如前式 （9）～ （11）所示逐步缩小。

3）混沌扰动 参考文献 ［11］，利用相邻迭代中群体适应值方差的变化大小来判断是否发生早熟收敛。如果相邻两次迭代的方差很接近，小于某给定值，例如eps＝10－6，就认为需要进行扰动。先确定当前粒子群中需要扰动的粒子比率，得到需要更替的粒子数s。按照2.2节的步骤利用An混沌映射，产生s个粒子，替代当前粒子群中适应值最差的s个粒子，然后继续迭代。

2.4 迭代终止条件

迭代终止条件可以选达到最大迭代次数或者适应度值达到事先设置的收敛标准。笔者采用最大迭代次数作为终止条件。

2.5 改进的PSO算法的具体流程

算法流程图如图1所示：

步1 初始化参数：wmax、wmin、c1、c2、N、maxDT、D，方差差异上限eps＝10－6；设置优化空间［lb，ub］、速度限制vmax、混沌搜索的最大迭代次数HDT。

步2 在 ［0，1）中随机生成一个D维空间粒子，按照2.2节的叙述，得到N个D维粒子，记为xi，i＝1，2，…，N；类似生成N个D维向量，作为初始化的粒子飞行速度；令迭代次数为0，转步3。

步3 将xi代入目标函数计算适应度fi，确定gbest、pbesti，i＝1，2，…，N，计算适应度方差σ2，转步4。

步5 混沌扰动，替换适应度最差的s个粒子；然后转步4。

步6 若迭代次数小于maxDT，转步4；否则，转步7。

步7 输出寻优结果：gbest、fbest。

图1 算法流程图

3 数值仿真

选用如表1所示的5个非线性标准函数，以测试改进算法的性能，同时也便于与文献 ［11，16］中的数值仿真结果对比。其中，f1、f2为高维单峰函数；f3、f4为高维多峰函数；f5为低维多峰函数。

表1 标准测试函数

如同文献 ［16］所指出的，部分测试函数的理论最优解很难达到，因此，给出了收敛标准，在实践中以达到收敛标准判断算法收敛。表1中的收敛标准和文献 ［16］的收敛标准是一致的。

参数取值为c1＝c2＝2；变量维数D、定义域［lb，ub］、收敛标准如表1所示；wmax＝0.9，wmin＝0.2；混沌扰动时粒子的比例更替是61.8%；eps＝10－6。迭代次数maxDT＝1000，混沌搜索迭代次数为100，粒子群规模取100，运行20趟。为比较算法搜索效率，定义如下标准：①搜索成功的前提下，最优平均值，记为mB；②成功搜索的比率，记为Ir，结果对比如表2所示。

对高维单峰函数f1、f2，改进算法的收敛比率为1.0，平均最优值也最优。原因是An混沌映射的均匀性较好，而且混沌搜索强化了对混沌特性的利用；对多峰高维函数f3，改进算法收敛比率为1，平均最优值就是理论最优值。对f4，改进算法直接得到理论最优值，收敛比率是1.0，和文献 ［16］的算法有相同效果。对f5，改进算法的最优值有0.95的比率是理论最优值0，高于文献 ［11］的算法，略低于文献 ［16］算法的效果。分析原因是理论最优点所在谷形的面积过小，占搜索范围比率不足0.000256。而且改进算法对f5函数做20次优化时，得到的优化结果只有2个值：0、0.0097159，十分接近，表明需要进一步提高算法的局部搜索能力。

对各个测试函数运行20趟，每趟迭代1000次，1000次迭代对应1000个全局最优值，将20趟的结果平均，记为far，取以10为底数的对数，作为纵坐标，以迭代次数为横坐标，对比了标准粒子群算法 （PSO），文献 ［11］算法 （ACPSO），改进算法 （MACPSO）的收敛速度，如图2所示。测试结果表明，采用An混沌映射做粒子群初始化，利用适应度方差的变化来启动混沌扰动机制，对非全局最优粒子做混沌变异，对全局最优粒子做混沌搜索，并动态的调整变异和搜索范围，该算法表现出了良好的收敛效果。

图2 平均全局最优值与迭代次数关系对比

表2 函数搜索结果

［1］莫愿斌，陈德钊，胡上序 .混沌粒子群算法及其在生化过程动态优化中的应用 ［J］.化工学报，2006，57（7）：2123-2127.

［2］李炳宇，萧蕴诗，吴启迪 .一种基于粒子群算法求解约束优化问题的混合算法 ［J］.控制与决策，2004，19（5）：804-807.

［3］任子晖，王坚 .模拟退火粒子群算法在新交通控制模型中的应用 ［J］.计算机应用，2008，28（4）：2652-2654.

［4］Kadirmanathan V，Selvarajah K，Fleming P J.Stability analysis of the particle dynamics in particle swarm optimizer ［J］.IEEE Transactions on Evolution Computation，2006，10 （3）：245-255.

［5］Jiang M，Luo Y P，Yang S Y.Stochastic convergence and parameter selection of the standard particle swarm optimization algorithm ［J］.Information Processing Letters，2007，102 （1）：8-16.

［6］Del Valle Y，Venayagamoorthy G K，Mohagheghi S，et al.Particle swarm optimization：Basic concepts，variants and applications in power systems［J］.IEEE Transactions on Evolution Computation，2008，12 （2）：171-195.

［7］Kameyama K.Particle swarm optimization-A survey ［J］.IEICE Transactions on Information and Systems，2009，E92D （7）：1354-1361.

［8］颜琳莉 .混沌模拟退火粒子群优化算法 ［J］.山西建筑，2008，34（1）：97-98.

［9］冯斌，王璋，孙俊 .基于混沌变异算子的小生境量子粒子群算法 ［J］.计算机应用与软件，2009，26（1）：50-52.

［10］刘华蓥，林玉娥，张君施 .基于混沌搜索解决早熟收敛的混合粒子群算法 ［J］.计算机工程与应用，2006，42（10）：77-79.

［11］董勇，郭海敏 .基于群体适应度方差的自适应混沌粒子群算法 ［J］.计算机应用研究，2011，28（3）：854-856.

［12］吕振肃，侯志荣 .自适应变异的粒子群优化算法 ［J］.电子学报，2004，32（3）：416-420.

［13］冯艳 .一种产生随机数新方法的研究与实现 ［D］.北京：北京工业大学，2002.

［14］张广强 .均匀随机数发生器的研究和统计检验 ［D］.大连：大连理工大学，2005.

［15］Shi Y，Eberhart R C.A modified swarm optimizer［C］.IEEE International Conference of Evolutionary Computation.Anchorage，Alaska：IEEE Press，May，1998.

［16］李荣钧，常先英.PSO算法速度更新时随机数产生的分析 ［J］.计算机工程，2009，35（7）：192-194.

Adaptive Chaos Particle Swarm Optimization Combined with Chaos Search

DONG Yong，Ll Meng-xia（Yangtze University，Jingzhou434023）
GUO Hai-min（Key Laboratory of Exploration Technologies for Oil and Gas Resources（Yangtze University），Ministry of Education，Jingzhou434023）

In order to improve the local search ability of adaptive chaos particle swarm optimization based on colony fitness variance（ACPSO），chaos mutation and chaos search into ACPSO are introduced.A chaos mapping is used for chaos mutation for some particles，and chaos search is performed for the global optimal particle.The results of the numerical simulation indicates that the convergence，global searching ability and local searching ability of the presented algorithm are enhanced，the algorithm can effectively avoid trapping in local minima.

chaos mapping；particle swarm optimization（PSO）；fitness variance；convergent percentage

TP301.6

A

1673-1409（2013）31-0057-04

2013-07-14

国家自然科学基金项目 （61273179）；湖北省教育厅重点项目 （D20101304）；湖北省教育厅科学技术项目 （Q20121216）。

董勇 （1980-），男，博士，讲师，现主要从事生产测井资料的解释与最优化算法方面的教学与研究工作。

［编辑］ 洪云飞