第11章 人口迁移算法
人口迁移是人们跨过特定的地域界限改变常住地的移动，是人口在不断聚集和扩散的矛盾运动中寻找优惠区域的过程。人口迁移是具有某种优化特征的群体演化过程。人口迁移算法是一种基于人口迁移机制的全局优化搜索算法。该算法通过比较函数全局优化和人口迁移两者的相似之处，模拟了人口随经济重心而转移、随人口压力增加而扩散的机制，前者促使算法选择较好的区域搜索，后者可在一定程度上避免陷入局部最优点。本章介绍人口迁移算法的原理、描述及实现步骤。
11.1 人口迁移算法的提出
人口迁移算法（Population Migration Algorithm，PMA）是2003年由周永华和毛宗源提出的一种基于人口迁移机制的全局优化搜索算法[44]，[45]。该算法通过比较函数全局优化和人口迁移两者的相似之处，模拟了人口随经济重心而转移、随人口压力增加而扩散的机制，前者促使算法选择较好的区域搜索，后者可在一定程度上避免陷入局部最优点。
数值仿真表明，人口迁移算法具有良好的全局优化性能。
11.2 人口迁移算法的原理
人口移动是指人口在空间或地域位置上的一切移动，包括人口流动和人口迁移。人口是有生命的群体，为了生存和发展，人口一直不断地进行移动。“逐水草而居”即是较早的一种人口移动。人口流动是人们在居留的地域环境上的移动，是带有某种自发性质的、移居规律性相对较差的人口行为。
人口迁移是人们跨过特定的地域界限改变常住地的移动，通常是带有选择性质的人口行为。物质方面的因素或经济因素是对人口迁移经常起作用的主要因素，人口重心随经济重心转移。换句话说，人们一般总是迁往经济发展水平高、就业机会多的优惠区域。中国经济体制改革以来的人口迁移具有明显的“人往富处流”的基本流向特征。
如果相对过剩人口不断增多，人口压力增大，人口密度增加，经济发展水平高的地区也会出现人口向外扩散，通常扩散到人口密度低的未开发地区或谋生相对容易的地区。
由上述讨论可归纳出人口迁移的基本框架如下。
（1）人们在原籍进行人口流动。
（2）受优惠区域吸引出现人口迁移。
（3）人口在优惠区域进行流动直到人口压力达到一定限度。
（4）人口从优惠区域迁出，向外扩散，寻找新的机会。
在这个持续不断的过程中，人口一方面经迁移而聚集到优惠区域，另一方面又因人口压力的增加而迁离优惠区域向外扩散。人口迁移是人口在不断聚集和扩散的矛盾运动中寻找优惠区域的过程。可见，人口迁移是具有某种优化特征的群体演化过程，通过比较函数全局优化和人口迁移两者的相似之处，进而建立了基于人口迁移机制的全局优化搜索算法。该算法模拟了人口随经济重心而转移的机制和随人口压力增加而扩散的机制，前者促使算法选择较好的区域搜索，后者可在一定程度上避免陷入局部最优点。
11.3 人口迁移算法的描述
考虑无约束函数优化问题为
其中，f：S→R1为一实值映射；x∈Rn；
为搜索空间，且ai＜bi。
假定式（11.1）恒有全局最优解f（x∗）存在，全局最优点集合M非空。函数全局优化是在搜索空间内寻找最优解，人口迁移是在地域空间内寻找优惠区域，两者存在相似之处。表11.1给出了两者要素之间的类比关系。
表11.1 函数全局优化与人口迁移之间的要素类比
人口迁移是一个比较复杂的过程，它与函数全局优化并不是完全对应的。因此，通过模拟人口迁移机制建立全局优化搜索算法的原则是提取人口迁移过程中有用的要素，而不是完全照搬。下面讨论各环节模拟的具体实现。
人口流动是在各个地球表面被规定居留区域内的空间进行的，在PMA中将其扩展为被规定的空间。模拟时，如果直接按行政区域或经纬线划分法来划分，那么随着优化问题维数的增加，会出现维数灾问题。因此，采用随机划分法，在搜索空间S内随机生成N个点x1，x2，…，xN，对于每一点xi及预先确定的δi（δixi，∈Rn；δi＞0；i=1，2，…，N；j=1，2，…，n），得到一个区域
考虑到人口流动的规律性较差，为使区域内各处的搜索机会均等，将人口流动处理成均匀随机的变动。模拟时，可以在每一区域内随机生成若干个点，再随机变动这些点。还可以用更为简单的等效方法来处理，即用一个点的多次随机变动来等效多个点的一次随机变动，这样，每一区域内便只有一个随机变动的点做预定次数的均匀随机变动。
优惠区域将其他区域的人口吸引过来。为简单起见，将迁移过程做简化处理，即迁移时所有人都向优惠区域迁移。模拟时，在优惠区域内随机生成N点，替换掉其他区域内的点。优惠区域是以当前最大的f（x）值所在的点为中心重新划定的。在算法中，用当前最大的f（x）值来衡量优惠区域的吸引力，用每一个f（x）值来表示每一点的人口收入。
人口迁入优惠区域后进行人口流动。优惠区域此时有N点，这N点每完成一次随机变动，就要找出收入最高的点，并以它为中心重新划定区域，这是为了模拟人口重心随经济重心的转移。同时还要收缩该区域，以模拟人口压力（或密度）的增加。
当优惠区域收缩到一定程度时，也就是人口压力增加到一定程度后，出现人口向外扩散，人口迁出优惠区域扩散到人口密度低的未开发区域。模拟时，将人口均匀随机扩散到整个搜索空间内，在搜索空间内重新随机生成N点，并重新划分区域。
最后是优惠区域信息传媒的模拟。将亲友、媒体广告、劳务市场等传媒抽象为最优点记录单元。在算法中，最优点记录单元全程记录f（x）的当前最大值和相应的点x，为优惠区域的确定提供依据。
以上就是无约束函数优化问题的基于人口迁移机制的全局优化搜索算法的优化原理。
11.4 人口迁移算法的实现步骤
在算法中，人及其所在地用点表示，
表示第i点，xi∈Rn，
表示第i点的第j分量；
，δi∈Rn，
表示δi的第j分量，
；i=1，2，…，N，j=1，2，…，n，N表示人口规模。
人口迁移算法实现的具体步骤如下。
（1）在搜索空间内均匀随机产生N点x1，x2，…，xN。对每一个i，令第i区域的中心centeri=xi，确定第i区域的上下界centeri±δi，其中
，i=1，2，…，N，j=1，2，…，n（
的上述取法使得各δi是相等的，故下面的步骤中取消δi的上标）。
（2）计算各点的收入／吸引力f（xi）。
（3）按步骤（2）所得的计算值，初始化最优记录值和最优记录点。
（4）在各自区域内进行人口流动。均匀随机变动每一个点：
xi=2δrand（∗）+（centeri-δ），rand（∗）为随机数函数。若
，则令
；若
，则令
。
（5）计算各点的收入／吸引力f（xi）。
（6）记录最优值，记录最优点。
（7）人口流动次数l若小于预先指定的次数，则转步骤（4）。
（8）人口迁移：以吸引力最大的点（即最优记录点）为中心，按δ各分量的大小确定优惠区域。在该区域内均匀随机产生N点，替换原来的点。
（9）计算各点的收入／吸引力f（xi）。
（10）记录最优值，记录最优点。
（11）收缩优惠区域：δ=（1-Δ）δ，Δ为收缩系数，0＜Δ＜1。
（12）在优惠区域内进行人口流动且人口随经济重心转移：以吸引力最大的点（即最优记录点）为中心，按δ各分量的大小确定优惠区域。在该区域内均匀随机产生N点，替换原来的点。
（13）计算各点的收入／吸引力f（xi）。
（14）记录最优值，记录最优点。
（15）若maxδj＞α（α为人口压力参数，预先给定的正小量），转步骤（11）。
（16）报告结果。
（17）人口扩散：在搜索空间内均匀随机产生N点x1，x2，…，xN，替换原来的点。按步骤（1）的方法确定人口流动区域。
（18）计算各点的收入／吸引力f（xi）。
（19）记录最优值，记录最优点。
（20）迭代次数m加1，若迭代次数小于指定次数则转步骤（4）。
（21）结束。
人口迁移算法是一种概率型搜索算法。周永华等基于人口迁移算法的上述步骤，运用概率论有关定理对算法的收敛性及时间复杂性进行了分析，并给出了定理：PMA依概率收敛到全局最优解，并对该定理给出了证明（从略）和对收敛速度的估计。