自组织迁移算法149030018张硕

1自组织迁移算法149030018张硕摘要：自组织迁移算法（SOMA）是一种新型的群体智能算法。与其他群体智能算法如粒子群算法类似，其基本思想是基于社会环境下群体的自组织行为，如社会性的合作觅食行为。SOMA算法所需要调整的参数也比较少，易于并行化，是一类较有潜力的新型进化算法。关键字：优化；进化算法；自组织迁移算法；变异Self-organizingmigratingalgorithm149030018zhangshuo【Abstract】Self-OrganizingMigratingAlgorithm（SOMA）isakindofnewswarmintelligentalgorithm.SimilarwithotherSwarmintelligencealgorithmsuchasswarmoptimizationalgorithm,thebasicideaisbasedontheself-organizingbehaviorundersocialenvironmentgroups,suchassocialcooperativeforagingbehavior.SOMAalgorithmparameterstobeadjustedisrelativelysmallandeasytoparallelize.Itisakindofthemorepromisingevolutionaryalgorithms.【Keywords】optimization;evolutionaryalgorithm;self-organizingmigratingalgorithm;mutation1引言2000年，Zelinka和Lampinen共同发展了一下名叫自组织迁移算法（Self-OrganizingMigratingAlgorithm，简称SOMA）[1]的新型演化算法。与多数演化算法一样，SOMA也是一种基于群体的随机优化算法，它将位于解空间中的粒子看成个体，所有个体形成一个群体，通过模仿社会性动物觅食过程中的竞争合作关系，逐步收敛直至得到最优解或近似最优解。但相比于传统的群体智能算法，SOMA具有描述简单、参数设置少、智能性强、收敛快的特点；它可对离散或连续问题进行优化，具有潜在并行性[2]，是一种较为有潜力的算法。但是，SOMA在寻优过程中，很大程度上受早期发现的较好解的影响，这些较好解以极大的概率引导SOMA走向局部最优解。2自组织迁移算法自组织迁移算法的主要思想在于模拟社会性动物觅食过程中的竞争与合作关系。一群动物在寻找食物过程中，如果某个个体找到食物，就会成为领导者（Leader），而其他个体则向该领导者靠拢，在靠拢过程中如果又有个体找到更多食物，就成为新的领导者，使得群体改变移动方向，向新的领导者靠拢。SOMA解空间中的粒子相当于群体中的个体，最优解相当于领导者，个体2在每一代都向当前最优解靠拢，每次迭代结束后就更新当前最优解，如此反复，直到迭代结束。SOMA在不停的循环中工作，这个循环叫做迁移循环（Migrationloops，简称ML）。在SOMA运行过程进行之前，先产生一群个体。在每一次迁移的循环中，最好的个体被选择出来，叫做领导者（Leader）。在群中的其他个体都在解空间中朝向这个领导者运动，运动采用小步跳跃（Step）的形式，步长参数Step向领先者跳跃，每跳跃一步都根据目标函数对当前位置进行评价并重新生成PRTVector向量，从而形成一条由个体i当前位置指向领先者位置的搜索轨迹。跳跃一直持续到PathLength（最大迁移路径长度）所限定的位置。在整个运动结束后，个体把在运动中遇到的最好的位置选择出来，如果这个最好的位置比个体的原来位置好，则个体就迁移到新位置，否则个体原地不动。在所有的个体都移动以后，新的领导者被选出来，然后进行下一次的迁移。2.1问题描述与编码为简单起见，这里只考虑如下函数优化问题：min(𝑓(𝑥))𝑥∈𝐷（1）其中，X={x1,x2,…,xn}T∈Rn，D={X∈Rn|li≤Xi≤ui,i=1,2…,n}，𝑓(𝑥)为目标函数。SOMA采用浮点数编码，对于维数为Nd的问题，个体编码为一个大小为Nd的向量X={x1,x2,…,xNd}。2.2群体初始化与其他群体智能算法一样，首先对群体进行随机初始化，方法如下：Xi,j=lj+(uj−lj)×Rand（2）其中i=1,2…,Nc，j=1,2…,Nd，Nc为群体的大小，Nd为问题的维数，Rand是一个在[0,1]区间内均匀分布的随机数，且每次使用前都要重新抽样。2.3迭代过程不同于其他群体智能算法，SOMA的迭代是由迁移循环（MigrationLoop，ML）组成的。在每次迭代开始时，首先找到群体中的最优个体XbestML，即领导者（Leader），然后对其他每个个体进行一次迁移循环。一次迁移循环过程如下：先利用随机抽样生成一个扰动向量PRTVector，然后由PRTVector决定个体如何以小步跳跃的形式向领导者前进，每次前进的步长为Step，并在前进的同时记录遇到的最佳点Xbest；若步长总和超过最大迁移路径长度PathLength，就结束该次迁移循环，并比较Xbest的适应度与起始点XstartML的适应度，如果Xbest优于XstartML，个体就迁移到新的位置，否则原地不动。当所有个体都完成一次迁移循环，就结束该次迭代。以下是一次迁移循环过程的形式化语言描述：t=0;whiletPathLength;%生成PRTVector向量j=0;WhilejNd;IfPRTVector[j]==13𝑋𝑡𝑒𝑚𝑝=𝑋𝑗,𝑠𝑡𝑎𝑟𝑡𝑀𝐿+(𝑋𝑖,𝑏𝑒𝑠𝑡𝑀𝐿−𝑋𝑖,𝑠𝑡𝑎𝑟𝑡𝑀𝐿)×𝑡;End;j=j+1;End;If𝑓(𝑋𝑏𝑒𝑠𝑡)𝑓(𝑋𝑡𝑒𝑚𝑝)𝑋𝑏𝑒𝑠𝑡=𝑋𝑡𝑒𝑚𝑝;End;t=t+Step;End;其中，PRTVector是一个长度为Nd的0-1向量，用于在迁移循环过程中决定个体的前进方向。PRTVector的产生由位于区间[0,1]的扰动（Perturbation）参数PRT和一个随机数共同决定，以下是PRTVector产生策略的形式化语言描述：j=0;WhilejNd;IfRandPRTPRTVector[j]=1;ElsePRTVector[j]=0;End;j=j+1;End;2.4SOMA基本流程原始SOMA的流程如下：（1）参数设置。需要设置的参数主要有群体规模（Np）、评价次数（counter）、小步跳跃的幅度（Step）、最大迁移路径长度（PathLength）、扰动参数（PRT）等。（2）群体初始化。对群体的所有Np个个体进行随机初始化，并用目标函数评价每一个个体的适应度。（3）迭代过程。求出群体当前的最优个体，当作领导者，然后对所有个体进行一次上面所描述的迁移循环，更新个体位置与适应度。（4）判断迭代是否结束。根据预先给出的结束条件判断迭代是否结束，若未结束则转到步骤（3），否则执行下一步。（5）算法结束。返回最好个体的值，或者根据情况返回所有个体的值。2.5参数选择SOMA基本参数的分析和设置可以见参考文献[3,4]。对SOMA性能产生影响的参数主要有群体规模（Np）、小步跳跃幅度（Step）、最大迁移路径长度（PathLength）和扰动参数（PRT）44个，文献[5]给出了它们的取值范围及建议值（见表1）。表1参数取值范围与建议值参数名称取值范围建议值Np至少大于10问题维数的0.2倍至0.5倍Step0.11，PathLength0.11PathLength1.1，3.03.00PRT0.10.103仿真结果为了验证和比较算法的性能，选择了一组标准测试函数进行仿真实验，其函数基本特征见表2，基本SOMA的策略参数设置如下：PRT=0.10，PathLength=3，Step=0.11，NP=50，ML=500，MinDiv=0.000001。表2测试函数F1—F5函数名称函数表达式（求最小值）维数变量范围最优值Spheref(X)=∑xi2ni=130[-100,100]n0Griewankf(X)=14000∑xi2ni=1−∏cos[xi√i]ni=1+130[-600,600]n0Rastriginf(X)=∑(xi2ni=1−10cos(2πxi)+10)30[-5.12,5.12]n0Rosenbrockf(X)=0.5+sin2√x12+x22−0.5[1+0.001[x12+x22]]22[-100,100]n0Ackleyf(X)=20+e−20e−1√1∑xi2ni=1n5−e−1∑cos(2πxi)ni=1n100[-30,30]n0表3SOMA优化结果函数SOMASphere0.001784Rosenbrock60.286698Griewank0.029761Ackley0.044183Rastrigin3.9776445图1Sphere函数寻优动态曲线图2Rosenbrock函数寻优动态曲线图3Griewank函数寻优动态曲线图4Ackley函数寻优动态曲线4结论通过对经典数值优化问题的测试，显示出了SOMA算法的优异性能,。其算法具有描述简单，易于应用的特点。SOMA能应用到所有整数、离散和连续变量函数的优化，同时也能优化带有多个非平凡约束的非线性目标函数。此外，SOMA算法所需要调整的参数也比较少，易于并行化，是一类较有潜力的新型进化算法。参考文献[1]PawlakZ.Roughsets[J].InternationalJournalofComputerandInformationScience，1982，11：341-356.[2]PawlakZ.Roughsets：theoreticalaspectsofreasoningaboutdata[M].Boston：KluwerAcademicPublishers，1991.[3]OplatkováZ,ZelinkaI.InvestigationOnShannon-KotelnikThe-oremImpactOnSomaAlgorithmPerformance[A].Richardzobel：Procee-dings19thEuropeanConferenceonModellingandSimulation.YuriMerkuryev，20056[4]柯晶，李歧强，乔谊正.采用随机变异步长的改进自组织迁移算法.计算机工程与应用[J].2006，35：41-44.[5]蔡永泉，杜秋玲.一种CA密钥安全管理方案[J].电子学报，2005，33（8）：1407-1410.