多群体云人口迁移算法*

廉侃超，孟朝霞，王琴竹

（运城学院 公共计算机教学部，山西 运城 044000）

人口迁移算法 PMA（Population Migration Algorithm）[1，2]是我国学者周永华、毛宗源于2003年提出的一类模拟人口迁移机理的全局优化算法，已应用于多个领域。但对复杂的优化问题，PMA存在着搜索速度慢、易陷入局部最优等缺点。云模型（Cloud model）是我国学者李德毅教授提出的定性和定量转换模型，已成功应用于众多领域。

提出一种多群体云人口迁移算法CMPMA（Cloudmodel-based Multi-colony Population Migration Algorithm），将云模型和人口迁移算法相结合，增加了群最优记录，进化过程中多个群体协作寻优。典型的测试函数和应用实例的仿真结果表明，CMPMA是可行、高效、稳定的。

1 人口迁移算法和云模型

1.1 基本人口迁移算法原理

原人口迁移算法的基本框架[1]如下：

（1）人们在原籍进行人口流动；（2）受优惠地区吸引出现人口迁移；（3）人口在优惠地区进行流动直到人口压力达到一定限度；（4）人口从优惠地区迁出，向外扩散，寻找新的机会。

在这个持续不断的过程中，人口一方面经迁移而聚集到优惠区域，另一方面又因人口压力的增加而迁离优惠区域向外扩散。可见，人口迁移是人口在不断的聚集和扩散的矛盾运动中寻找优惠区域的过程。

1.2 云模型[3]

定义 设U是一个用精确数值表示的论域 （一维的或多维的），U上对应着定性概念˜A，对于论域中的任意一个元素 x，都存在一个有稳定倾向的随机数 y=μA（x），叫作x对概念˜A的确定度，μA（x）在U上的分布称为云模型，简称云。当μA（x）服从正态分布时，称为正态云模型。

云的数字特征用期望Ex、熵En和超熵He来表征，如图1所示。它们反映了定性概念˜A整体上的定量特征。生成云滴的算法或硬件称为云发生器。

基本云发生器的算法步骤如下：

输入：表示定性概念A˜的3个数字特征值Ex、En、He和云滴数n。

输出：n个云滴的定量值以及每个云滴代表概念A˜的确定度。

（1）生成以En为期望值，He为标准差的一个正态随机数 En′；

（2）生成以Ex为期望值，En′为标准差的正态随机数x；

（3）令x为定性概念A˜的一次具体量化值，称为云滴；

（4）计算 y=

（5）令y为x属于定性概念A˜的确定度；

（6）（x，y）完整地反映了这一次定性定量转换的全部内容；

（7）重复步骤（1）～步骤（6）直到产生 n 个云滴为止。

2 多群体云人口迁移算法

2.1 人口流动思想的改进

在人口迁移算法中，人口流动是“人们在原籍进行人口流动”，即每一次迭代过程中，人口的多次流动都是在初始人口的邻域范围内流动。本文提出一种改进的人口流动方法，人口在其邻域范围流动后，再次流动的邻域范围以新人口为中心重新构建。实验结果表明，改进的人口流动提高了算法效率。

2.2 云模型与人口迁移算法的结合

人口迁移算法初始群体的随机性和人口流动的漫无目的性，在一定程度上影响了算法的寻优性能。云模型具有随机性和稳定倾向性的特点，随机性可以避免搜索陷入局部极值，而稳定倾向性又可以很好地定位全局最值。分别用不同参数的基本云发生器来产生初始群体和实现人口流动操作，同时增加了群最优记录，提出CMPMA算法。

2.3 多群体云人口迁移算法（CMPMA）

设Rn表示搜索空间，人及其所在地用点表示，xi=（，…，)表示第 i个人口，xi∈Rn，表示第 i个人口的第 j个分量；δi=（，…，δni）表示第 i个人口的邻域半径，δi∈Rn，表示 δi的第 j个分量，>0；i=1，2，…，N，N表示人口规模；j=1，2，n，n，表示 Rn的维数。

多群体云人口迁移算法的具体步骤如下：

（1）设定Ex为搜索空间中心点，En为寻优空间的1/6，He=1，用基本云发生器在寻优空间产生N个点，x1，x2，…，xN。 以每一个点 xi为中心确定其邻域上下界 xi±δi，其中取=（bj-aj）/（2N）。 计算 N 个点的值，并按其初始化最优记录和群最优记录。

（2）人口流动（由基本云发生器实现）：对每一个 xi都执行的操作有：①Ex=xi；②En=δi；③He=En/10；（式中的参数10是实验中的经验取值。）④由基本云发生器生成一个云滴更新 xi。 若>bj，则令 xji=bj；若＜aj，则令=aj。更新群最优记录。以更新后的每个xi为中心重新构建邻域空间，构建方法同步骤（1）。人口流动次数若小于预先指定的次数则重复步骤（2）。

（3）群体迁移：对群最优记录中的每个人口执行：以其为中心，按δ各分量的大小确定优惠区域，在该区域内均匀随机产生N个点，更新群最优记录，收缩优惠区域：δ=（1-Δ）δ。若 max δj>α（α 为人口压力参数），则重复步骤（3）。以群最优记录更新最优记录。

（4）人口扩散：用基本云发生器重新产生初始群体并确定人口流动区域，更新最优记录，清空群最优记录。迭代次数m加1，若迭代次数不大于指定次数则转步骤（2）。

（5）输出最优记录。

3 多群体云人口迁移算法（CMPMA）性能分析

3.1 函数测试

本文选取了3个典型的基准测试函数[4]进行仿真实验，仿真均在Matlab2006a下编程运行。

（1）f1（x1，x2）=x12+x22-5≤x1，x2≤5

DeJong 函数，单峰函数，在（x1，x2）处，有最小值 0。（2）f2（x1，x2）=100（x12+x2）2+（1-x1）2-5≤x1，x2≤5 Rosenbrock 函数：二维非凸、病态函数， 在（x1，x2）=（1，1）处，有最小值 0。

Sinc 函数，多峰函数，在（x1，x2）=（0，0）处，有最大值 1。

算法参数为：人口规模N=3，人口流动次数l=10，迭代次数m=2。收缩系数Δ和人口压力参数α的设置如表1所示。

表1 参数Δ和α设置表

表2 本文算法CMPMA与参考文献[4]比较

为便于比较，对函数f1～f3独立运行30次，统计30次中搜索到的最优值中的最好值、最差值、平均值作为评价指标，与参考文献[4]比较，结果如表2所示。

从表 2可知，对函数 f1～f3，参考文献[4]的 CAFSA算法的搜索结果只是接近理论最优，本文算法CMPMA可以稳定收敛到理论上的最优值，且参考文献 [4]的CAFSA算法设定的迭代次数为50，而本文算法CMPMA设定的迭代次数为2。可见，CMPMA算法对复杂函数的寻优效率和精度都较高，搜索结果令人满意。

3.2 实例测试

为进一步验证算法的有效性，将CMPMA应用到最小推力滚珠导轨优化设计模型[5-6]中，该实例设计要求在外载荷一定时，推力最小，即运动最灵敏。优化数学模型描述如下：

s.t.30°≤α≤90°，30°≤β≤60°，0.3≤ε≤1，40≤p0≤80式中，α是负荷p与水平轴夹角；β是导轨V形槽半角；ε是表面硬度系数；p0是初安装负荷；k是滚动摩擦系数；K是许用应力；p是运动件上全部负荷；z是滚珠个数。

各参数采用参考文献 [5-6]的取值：p=50 N，k=0.01 mm，K=0.5 N/mm2，z=4。 CMPMA 各参数设置为：人口规模 N=3，人口流动次数 l=10，收缩系数 Δ=0.01，人口压力参数α=0.1，迭代次数m=2。进行20次独立实验，每次得到的最优推力值T=0.68248707619912（N），优化参数 α=30.000 000 000 000 00°，β=60.000 000 000 000 00°，ε=0.300 000 000 000 00，p0=40.000 000 000 000 00。 参考文献[6]的复合形法得到的最优值 T=0.68 428（N），参考文献[5]的最优结果为 T=0.682 5（N），优化参数 α=30.052 8°，β=59.998 4°，ε=0.3，p0=40.000 5。 可见，与参考文献[5-6]相比，本文的寻优结果精度更高。实例测试表明，CMPMA在工程设计领域是可行、有效的。

基于原人口迁移算法，增加了群最优记录，由多个群体协作寻优，并改进了人口流动的思想。借鉴正态云模型的随机性和稳定倾向性，提出用不同参数设置的基本云发生器分别产生初始群体和实现人口流动。多群体云人口迁移算法通过利用人口迁移算法的进化体制保留了其寻优性能，又通过多群体合作，并结合正态云模型的稳定倾向性、随机性特点进一步提高了算法的搜索效率。经典函数和实例测试结果证明了CMPMA算法的寻优高效性和稳定性。算法在其他领域的进一步拓展和其理论证明是下一步要做的工作。

[1]周永华，毛宗源.一种新的全局优化搜索算法-人口迁移算法（I）[J].华南理工大学学报（自然科学版），2003，31（3）：1-5.

[2]周永华，毛宗源.一种新的全局优化搜索算法-人口迁移算法（II）[J].华南理工大学学报（自然科学版），2003，31（4）：41-43.

[3]戴朝华，朱云芳，陈维荣，等.云遗传算法及其应用[J].电子学报，2007，35（7）：1419-1424.

[4]曲良东，何登旭.一种混沌人工鱼群优化算法[J].计算机工程与应用，2010，46（22）：40-42.

[5]张梅凤，邵诚，甘勇，等.基于变异算子与模拟退火混合的人工鱼群优化算法 [J].电子学报，2006，34（8）：1381-1385.

[6]何献忠，李萍，黄航汗，等.优化技术及其应用（第二版）[M].北京：北京理工大学出版社，1995.