自适应柯西变异人口迁移算法*

廉侃超

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

人口迁移算法PMA（Population Migration Algorithm）[1]于2003年由我国学者周永华、毛宗源提出，是一个性能较好的全局优化搜索算法。该算法主要模拟人类迁移的社会活动机理：随经济重心而转移，随人口压力增大而扩散。但算法步骤繁琐，对较复杂的优化问题，存在着优化精度低，易陷入局部最优等缺点。为进一步改善算法的性能，提出一种自适应柯西变异人口迁移算法ACMPMA （Adaptive Cauchy Mutation Population Migration Algorithm），数值实验表明，改进后的人口迁移算法有效提高了算法的性能，具有搜索质量高，性能稳定等特点。

1 柯西变异

1.1 柯西分布

高斯分布和柯西分布[2]是概率论与数理统计中的常见分布。图1是标准柯西分布和标准高斯分布概率密度函数曲线。柯西分布两端趋于零的速度比高斯分布慢，如在PMA中对人口状态变异，相对于高斯变异，柯西变异显然具有更强的扰动能力，人口更易跳出局部极值，可提高搜索速度和全局寻优能力。

图1 标准柯西、高斯分布概率密度函数图

1.2 柯西变异

鉴于柯西分布及人口迁移算法的特点，本文对人口迁移后优惠区域的人口 xi=（x，…，x）进行柯西变异，规则如下：

由随机变量生成函数定理[2]，式中标准柯西分布的随 机 变 量 生 成 函 数 Cauchy（0，1）为：Cauchy（0，1）=tan[（ξ-0.5）π]，其中 ξ是[0，1]上服从均匀分布的随机变量。

表1 本文算法（ACMPMA）与PMA的比较

2 自适应柯西变异的改进人口迁移算法

本文取消人口扩散过程，将算法步骤简化为5步；当算法限入局部最优时，自适应对优惠区域的人口进行柯西变异。算法步骤如下：

设：Rn表示搜索空间，xi＝（x，…，x）表示第 i个人口，xi∈Rn，x表示第 i个人口的第 j分量；δi＝（，…，）表示第 i个人口的邻域半径，δi∈Rn，表示 δi的第 j个分量，＞0；i＝1，2，…，N，N 表示人口规模；j＝1，2，…，n，n表示 Rn的维数。

步骤 1：在搜索空间随机产生 N 个点，x1，x2，…，xN。以每一个点 xi为中心确定其邻域上下界 xi±δi，其中取δ＝（bj-aj）/（2N）。 计算 N 个点的值，并更新最优记录。

步骤2：人口流动：在每个人口xi的邻域内随机产生一个人口，用其更新xi和最优记录，人口流动次数加1。人口流动次数l若小于预先指定的次数，则重复步骤2，否则执行步聚3。

步骤3：人口迁移：以最优记录的邻域为优惠区域，在优惠区域随机产生N个人口，替换原人口群体，更新最优记录。若最优记录连续两次未变化，则对优惠区域的每个人口进行柯西变异，并更新最优记录。收缩优惠区域：δ＝（1-Δ）δ。 若 maxδj＞α（α 为人口压力参数），则重复步骤3，否则执行步骤4。

步骤4：迭代次数M加1，若迭代次数小于指定次数则转步骤1，否则执行步骤5。

步骤5：输出最优记录。

3 算法的性能测试

本文采用 Windows XP操作系统、CPU为 Intel（R）Core（TM）2 Duo CPU T5870@2.00 GHz，内存为 2.00 GB的ThinkPad SL400笔记本电脑。编程软件为Matlab R2006a。

3.1 本文算法与PMA的比较

选取以下4个函数对本算法及PMA算法进行测试：

该函数在（0，0）处有全局最小值 0.9。

该函数在（0，0）处有全局最小值 0。

该函数在（0，0）处有全局最小值-2。

该函数在（0，0）处有全局最小值 0。

实验中，两种算法分别对每个函数独立运行50次，取最好值、最差值、平均值、成功率和标准偏差作为评价算法的性能指标。若运行的结果在全局最优值的1%范围内，则称本次运行是成功的。两种算法的参数设置保持一致，均为：人口规模 N＝3，收缩系数△＝0.01，人口压力参数 α＝1e-7，迭代次数 M＝2，人口流动次数 L＝10。测试结果如表1所示。

由表1知，本文算法从平均值、成功率和标准偏差几个方面比PMA都更优。

3.2 本文算法与其他优化算法的比较

选取Schaffer函数作为测试函数。

该函数仅在（0，0）处有最小值 0，但在最小值附近有无穷多个局部极小值，使得寻优极为困难。

测试中，本文算法对Schaffer函数独立运行50次，以平均最优值和收敛成功率作为评价指标。实验比较数据如表2所示。

表2 本文算法（ACMPMA）与其他算法的比较

从表2可知，从平均最优值和收敛成功率来看，本文算法比NSMPSO、IOANGA、PMA算法效果都好。可见，ACMPMA具有较好的寻优性能。

基于人口迁移算法，算法步骤精简，借用柯西变异的强扰动性，自适应地促使人口跳出局部极值，提高了算法的寻优精度，增强了算法的全局寻优能力。实验数据表明，该算法具有较好的稳定性能和较高的求解质量，可有效求解无约束复杂函数的优化问题。但算法的理论证明有待研究，在更多领域的应用需进一步探索。

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

[2]王梓坤.概率论基础及其应用[M].北京：科技出版社，1979.

[3]FAN S K S，ZAHARA E.A hybrid simplex search and particle swarm optimization for unconstrained optimization[J].European Journal of Operational Research， 2007， 108（2）：527-548.

[4]华洁，崔杜武.基于个体优化的自适应小生境遗传算法[J].计算机工程，2010，36（1）：194-196.

[5]邓辉，王勇，陈士亮.融合模式搜索与人口迁移的优化算法[J].计算机工程，2011，37（13）：175-177.