引入高斯变异和最速下降算子的人口迁移算法(1)

《引入高斯变异和最速下降算子的人口迁移算法(1)》由会员分享，可在线阅读，更多相关《引入高斯变异和最速下降算子的人口迁移算法(1)（5页珍藏版）》请在金锄头文库上搜索。

1、2009，45（20）1引言人口迁移算法 （Population Migration Algorithm，PMA）是由我国学者周永华、毛宗源等人提出的一类模拟人口迁移机理的全局优化算法1。 人口迁移算法模拟的是社会领域中人口随经济重心而转移、随人口压力增加而扩散的机制，即模拟的是人往高处走、人往富处流，当某个优惠地区的相对人口过剩，人口压力增加时，人们就会迁出该优惠地区去寻找更好更适合自己的优惠地区的这样一种规律。前者促使算法选择较好的区域搜索，后者可在一定程度上避免陷入局部最优点，搜索过程呈现交替进行集中搜索和分散搜索的特点。这体现了人口迁移过程中人口不断聚集和扩散的矛盾运动的特点。后来由我

2、国学者徐宗本给出了改进的形式2。概括地说，人口移动主要可分为人口流动、人口迁移与人口扩散三种基本形式。人口流动是在常居地周围自发而无确定整体规则的移动； 人口迁移是跨越较大范围的选择性移动，基本规则是趋上性 （ 即 “ 人往高处走，人往富处流，随经济中心而转移”）； 人口扩散是从优惠地区向非优惠地区的选择性移动，基本规律是开拓性 （ 随人口压力增加而扩散，反映人的开拓进取精神）。2人口迁移算法考虑如下无约束单目标优化问题：min f（x）s.t. xS（1）其中f：SR为一实值映射，xRn，S=ni=1仪ai，bi为搜索空间，且ai（t） （ 即未超过人口压力警戒），则继续人口流动，即对于B（

3、Y（i）best（t），（t）：=B（Z（i）best（t），（t），转步（2.3.3），否则转 （2.3.6）。（2.3.6）报告最好的N个优势个体Zbest（t）=（Z（1）best（t），Z（2）best（t），Z（N）best（t）（2.4）人口扩散：（2.4.1）保留Zbest（t）中的最好个体 （ 例如设为Z（0）best（t）。（2.4.2）将Zbest（t）Z（0）best（t）中的N-1个个体用（t）c中随机抽取的N-1个新个体替代 （ 这里（t）c表示（t） 在可行域中的余集）。（2.4.3）定义新一代种群X（t+1）=（X（1）（t+1），X（N-1）（t+1），Z（0）

4、best（t）步骤3终止性检验：如果X（t+1）中已经包含符合条件的近似解，则停机并输出X（t+1）中的最好解，否则以适当方式缩小（t）、（t），并置t：=t+1转步骤2。3改进的人口迁移算法 （IPMA） 3.1高斯变异算子高斯变异来源于高斯分布 （ 也叫正态分布），所谓高斯变异（Gaussian Mutation）操作是指进行变异操作时，用符合均值为方差为2的正态分布的一个随机数来替代原有的基因值。由正态分布的特性可知，高斯变异也是重点搜索原个体附近的某个局部区域。具体实现高斯变异时， 符合正态分布的随机数Q可由一些符合0，1均匀分布的随机数ri（i=1，2，12） 来产生3，则符合N（，

5、2）的正态分布的一个随机数Q可由此求得：Q=+（12i=1ri-6）。在进行由个体X（i）=（X1（i），X2（i），Xk（i），Xn（i）向X（i）=（X1（i），X2（i），Xk（i），Xn（i） 的高斯变异操作时，若变异点Xk（i）处的基因值取值范围为ak，bk，并假设=ak+bk 2，=bk-ak 6，则新的点Xk（i）由下式确定：Xk（i）芊ak+bk 2+bk-ak 6（12i=1ri-6）在文献3-4已经证明高斯分布有较好的局部搜索能力，对于大量局部极小点的优化问题，使得算法能够高效高精度地找到全局极小点，并且也可以提高算法的鲁棒性。 3.2最速下降算法最速下降算法是数值优化方法

6、中较早的方法， 它直观、简单、不需要求解函数的二阶导数Hessen矩阵，而许多有效的数值优化方法却是在它的启发下获得的。最速下降法的计算步骤如下：步骤1给定初始点X（0）Rn，置k：=1。步骤2计算d（k）=-f（X（k），进行一维线性搜索确定步长k，使得f（X（k）+kd（k）=min0（X（k）+d（k）。步骤3如果满足终止条件，则停止；否则，令X（k+1）=X（k）+kd（k），置k：=k+1，转步骤2。3.3改进的人口迁移算法在改进的算法中，把原来的人口迁移算法步骤 （2.3.3）改进为在每一优惠地区作人口流动：（1）在B（Y（i）best（t），（t）中随机产生li个个体，li按与Y

7、（i）best的 适应值成比例的方式确定；（2） 对 （1） 中每个个体Y（i）j（j=1，2，li） 进行一次高斯变异，得到新的个体Yj（i）（j=1，2，li）；（3）对高斯变异后所得到的个体Yj（i）（j=1，2，li）再进行一次最速下降运算：求dj=-f（Yj（i），进行一维搜索确定步长j，使f（Yj（i）+jdj）=min0（Yj（i）+dj），得到新个体Yj（i）=Yj（i）+jdj（j=1，2，li）；（4）然后从Yj（i）（j=1，2，li）中找出最佳个体Z（i）best（t）。其余步骤和上面叙述的人口迁移算法相同。4改进人口迁移算法收敛性分析这里采用公理化模型对改进人口迁移算

8、法的收敛性进行分析和证明。定义12（ 选择算子）一个选择算子是一个随机映射S：HNLHML， 其中HNL=HLHLHL N称为N阶种群空间，HL称为个体空间，满足：（1） 对任何XHNL，SXiX，i=1，2，N，其中SXi表示 种群SX中的第i个个体。（2）对任何满足B（X） B（X）0582009，45（20）其中B（X） 表示X中的适应度最大个体的全体，B（X） 表示B（X）所含个体的数目。 条件 （1）是说被选择的个体应该是被选择种群的一部分；而 （2）是说除了选择后个体与种群个体数目差异外，只要被选择种群不是齐次种群，选择算子作用后应该有可能增加种群中最优个体的数目。定义22（ 繁殖

9、算子） 一个随机映射E：HMLHNL称为是一个繁殖算子，如果对任意种群X，它满足PE（X）Be（X）覫0（2）其中Be（X）=XHL：F（X）F（Xe）为X的满意集，Xe是最优个体。上述定义是说，一个繁殖算子是这样的一个操作：它作用在当前种群X上生成新的种群E（X），而新的种群E（X） 中可能含有比旧种群X中个体更满意的个体， 否则产生退化。 式（2）刻画的是E作为繁殖算子的最基本要求。定义32（ 变异算子） 一个随机映射M：HNLHML称为是一个变异算子，如果对任意种群XHNL，有PM（X）B*覫0（3）其中B*是最小的满意集。由于对任何满意集B2HL有B*哿B，条件 （3）蕴含PM（X）B

10、覫0，坌B2HL（4）这推出变异算子也是繁殖算子，而注意到：条件 （4）等价于下列两个条件：（1）PM（X）B=覫|XB覫0条件 （1）是说，如果当前种群含有满意个体，则变异后的种群不应该不含有满意个体；条件 （2）是说，如果当前种群不含有满意个体，则变异后的种群一定有可能包含满意个体。条件 （2）同样蕴含式 （2），故变异算子是具有更好进化性质的繁殖算子。变异算子的作用方式是： 独立地分别作用于种群X中的每一个个体Xi，以某种概率方式生成变异后的个体MXi，从而MX=（MX1，MX2，MXN）。在 改进的 人 口 迁 移 算 法 中 ，令L0：HNLHNlL，L0（X）=（X（1），X（1）

11、 l，X（N），X（N） l），坌X=（X（1），X（2），X（N）HNL表示扩展算子；Mt：HNlLHNlL为均匀变异，Mt（Y）=（Mt（Y）（1），Mt（Y）（2），Mt（Y）（Nl），坌Y=（Y（1），Y（2），Y（Nl）HNlL，从而算子MtL0：HNLHNlL表示步骤 （2.2）中的人口流动操作；让S1：HNlLHNL表示步骤 （2.3.1）中的从Y（t） 中选择出N个最佳个体的操作，E2：HNLHNL表示由Ybest（t）经步骤 （2.3.2）（2.3.6）最终输出Zbest（t） 的操作，E1：HNLHNL表示由Zbest（t） 经过步骤3生成X（t+1）的操作，则改进的人口迁

12、移算法可表示为：X（t+1）=E1莓E2莓S1莓Mt莓L0X（t），t=0，1，2，（5）令S=S1：HNlLHNL，E=Mt莓L0莓E1莓E2：HNLHNlL，并且Y（t）=MtL0 X（t），t=0，1，2，则对式 （5） 两边作用Mt+1莓L0可得，Y（t+1）=E莓SY（t）。一个一般的模拟进化算法可抽象表示为如下随机过程：X（t+1）=Et莓StX（t） （t=1，2，），这里Et和St是一系列繁殖算子和选择算子。引理1改进的人口迁移算法中的S是选择算子。 证明参见文献5。引理2改进的人口迁移算法中的E是繁殖算子。 证明参见文献5。由引理1和引理2可推出定理1。定理1改进的人口迁移算

13、法是一种模拟进化算法 （SEA）。引理35（IPMA中择优选择算子的特征数）S的选择压PS=1，选择强度S=1。在改进的人口迁移算法中的步骤 （2.3.3） 的选择一直采用择优选择。根据文献2中选择压与选择强度的定义来计算S的特征数，其具体证明过程可参见文献5。引理4（IPMA中繁殖算子的特征数） 设E：HNLHNl+NL，则繁殖算子的吸收率5和散射率5分别满足下面的估计式：AENlt（1-（Ct+1）n+1）N-1（C（）n）1-t（C（） Ct+1）nl-1，SKE=0其中=C（）（为搜索空间的半径）为最优解集B*的半径，t为折算系数：若B*包含于（t+1）中的某个划分区域，则t=1；否则

14、，t为B*与某个划分区域相交的交集的体积与B*的体积之比，因此0t1。 证明参见文献5。定理2（ 择优选择IPMA的收敛性） 假定改进的人口迁移算法所有采取的选择算子族St中均为择优选择算子，繁殖算子族Et如Y（t+1）=E莓SY（t）所定义，且满足以下条件：（1）Ct+1=O（1/t）1/n）（2）t=O（1/t）或t=O（Ct+1）n）则改进的人口迁移算法依概率弱收敛到最优解集。证明 由以上的引理可知，PS（t）=1，且S（t）=1，AENlt（1-（Ct+1）n+1）N-1（C（）n）1-t（C（） Ct+1）nl-1，当给定以后，C（）也随之固定。 由条件 （1）可知lim t（Ct+

15、1）n+1）N-1=1，又由条件 （2）可知t与 （Ct+1）n同阶，因此lim t1-t（C（） Ct+1）nl-10。 又t=O（1/t），因此，AENlt（1-（Ct+1）n+1）N-1（C（）n）1-t（C（） Ct+1）nl-1=O（1/t）根据调和级数的发散性，从而有t=1AE（t）=，由引理4知SE1=0，因为S（t）=1，于是limt1-（1-SE（t）1）S（t） AE（t）=0，满足文献5中的SEA的概率收敛性定理中的条件，故此定理成立。综上述可知， 改进的人口迁移算法依概率弱收敛到最优解集。5数值实验为了检验IPMA的全局优化能力，用下列典型测试函数对它进行测试：（1）max f1（x）=（1-2sin20（3x）+sin20（20x）20，0x1王晓慧，刘雪英，白梅花：引入高斯变异和最速下降算子的人口迁移算法592009，45（20）Computer Engineering and Applications计算机工程与应用函数12345678k10101010101055N33333333l10101010101010100.10.10.10.10.1