【摘 要】由于原猴群算法中的参数过多且固定，若设置不准确，会丧失猴群多样性且易陷入局部最优值。针对这些不足，本文提出了一种新型的自适应猴群算法——基于高斯变异的自适应猴群算法（gama）。gama改变了原本固定的步长及视野，使其随着迭代次数的变化而变化，这样无论在算法的前期或者后期，都有较强的搜索能力。对于猴群算法容易陷入局部最优的缺点，本文采用高斯变异的方法，对数次迭代过程中未改变的局部最优值进行高斯变异，不仅使猴群能够有效摆脱局部极值的束缚，也加强了对局域再搜索能力。最后通过对多峰测试函数验证，结果表明gama算法无论在精度，稳定性，克服早熟及收敛速度方面都有显著提高。
　　【关键词】猴群算法；自适应；高斯变异
　　the self-adaptive monkey algorithm based on gaussian mutation
　　zhou zhi-peng xie jin-qiu chen bai-jian
　　（chaohu university，chaohu anhui 238000，china）
　　【abstract】due to so much fixed parametersof the monkey algorithm ， if the setting is not accurate， especially makes the loss of diversity，falling into the most superior con- ditions easily. aiming at this shortcoming， this paper proposes a novel adaptive monkey algorithm ——the self-adaptive monkey algorithm based on gaussian mutation （gama）， change the original fixed step length and the field of vision， make its changes with the change of the number of iterations， so no matter early or late in the algorithm， has a strong ability of search； especially for the algorithm easy to fall into local optimum of faults ， this paper uses the method of gauss-ian mutation did not change in the process of this method for several iterations gauss mutation localoptimal value， not only make monkeys can effectively get rid of the bondage of local extremum， but also strengthened the ability of local lan to search again. finally by using functions to exam， the resul- ts show that theopyimization precision， algorithm stability ，overcome the premature and convergence speed of gama algorithm are improved significantly.
　　【key words】monkey algorithm；self-adaptive；gaussian mutation
　　0 引言
　　在智能算法不断推陈出新的现在，猴群算法（monkey algorithm，ma）作为新兴智能优化算法，摆脱了以往启发式算法“维数灾难”[1-2]的困扰。该算法通过模拟大自然中猴群爬山行为，设计出爬、望和跳三个过程来求解多维、多峰函数[3-4]的优化问题。但由于ma中的参数过多、固定，使得算法后期的收敛速度减缓；并且算法的性能跟参数设置有很大的关系，如果参数设置不准确，就会丧失猴群多样性，易发生算法过早收敛，陷入局部最优的情况[5]，从而无法获得全局最优解。针对这个缺点，文献[6]通过引入欧氏距离来增强猴群的多样性，并加入和声算法中的随机扰动机制，以提高其全局搜索能力；文献[7]引入望过程参数递增机制，提高了算法后期的收敛速度；文献[8-9]引入混沌搜索，通用参数避免陷入局部最优，提高算法性能。但这些方法在搜索性能和寻优能力上都不同程度地存在一些不足，鉴于此，本文提出一种基于高斯变异的自适应猴群算法（简称gama）。
　　1 猴群算法的自适应改进过程
　　1.1 自适应步长[9]和视野
　　原猴群算法采用固定的步长和视野。算法初期具有较快的收敛速度，但在后期，算法的的收敛较慢。为了弥补这一不足，提出了如下改进：
　　1.1.1 步长衰减变化策略：step=step·θ，其中θ∈（0，1）为衰减因子，随着迭代的进程而自适应地减小步长大小；在算法前期，使用较大的步长，可以增强全局搜索能力；但随着迭代的进行，如果仍然采用初始步长，会使搜索的结果不精确，故自适应地减小步长，有利于在算法的后期增强局部的搜索能力。
　　1.1.2 视野递增变化策略：visual（new）=visual（old）+visual（old）·ρ，其中ρ为递增因子。因为猴群算法利用跳过程来摆脱局部最优的困扰，在算法前期，赋予一个较小的跳半径，使其能够保持搜索的精度；但在算法运行

期，如果跳的距离过短，就可能陷入局部最优值。 　即使猴群算法的跳过程从机制上来讲是为了跳出局部最优，但由于参数的人工初始化设置等原因，猴群算法也会陷入局部最优值。为此，本文进一步提出了以下改进。
　　1.2 猴群的高斯变异
　　什么是高斯变异[11]？高斯变异就是在原有个体的状态上加一个服从高斯分布的随机向量。高斯分布（gaussian distribution），也称作为正态分布（normal distribution），在数理统计及其概率论学科当中占有举足轻重的地位。同样，在数学、物理等诸多领域都有着重大的影响力。若随机变量x服从一个数学期望为μ、方差为σ2的高斯分布，记为n（μ，σ2）。其概率密度函数为：
　　f（x）=■exp-■
　　期望值μ决定了其位置，其标准差σ决定了分布的幅度。由于正态分布的特征和性质，在自然界中很多现象和随机因素均可近似地用正态分布描述。
　　针对猴群算法而言，在迭代过程中，处于最优位置上的猴子很容易陷入局部最优解，以至于在多次迭代过程中，“最优值”都不变。例如，函数f1（x）=■x■■，[-100，100]n，fmin=0。猴群算法（采用固定步长和固定视野）寻优就陷入了局部最优值69895.516361，出现的次数占总迭代次数的52.9%，并且实际寻得的最优解0.625722跟理论值0也相差很多。为了避免这一情况的出现，使猴群能够摆脱局部极值的束缚，较早的开始收敛，我们对猴群中的最优个体增加一个随机扰动项，该扰动项服从高斯分布。即对寻优过程得出的最优值在二十次迭代运算未发生改变的情况下，对最优猴位置采取gauss变异，表达式为xbest_new=xbest_old+gauss（0，1）·xbest_old，其中gauss（0，1）为标准正态分布。这样能够使算法较早跳出局部最优值，易实现全局收敛（详见第3节）。
　　2 改进的猴群算法
　　2.1 改进的猴群行为描述
　　2.1.1 猴群初始化过程
　　正整数m表示猴群的群体规模，猴群的个体位置由xi=（xi1+xi2，…，xin），i=1，2，…，m表示，x对应着优化问题中的决策变量，m对应着决策变量的个数。
　　2.1.2 （步长衰减）爬过程
　　（1）随机生成向量δxi=（δxi1，δxi2，…，δxin），满足：
　　■
　　其中α（α>0）为爬过程中的步长，k（k=1，2，…）表示爬的次数，即爬过程中的迭代次数。
　　（2）计算：
　　■其中向量■为目标函数在点xi的伪梯度；
　　（3）令■且y=（y1，y2，…，yn）；
　　（4）如果y满足函数条件，则用y来替换xi，否则xi不变；
　　（5）αk+1=θαk；k=k+1；
　　其中θ（0<θ<1）表示递减因子。可以看出每次迭代步长递减，这样有利于在算法的后期运行中，保证解得精确度，增强局部搜索能力。
　　重复步骤（1）至（5），当k满足条件时循环结束。
　　2.1.3 （视野递增）望过程
　　经过爬过程，目标函数达到了当前最优。之后，猴子开始眺望，观察周围领域是否存在比当前山峰更高的山峰，即是否存在更优解。如果存在，则跳到更高的山峰，更新当前的位置。望过程如下：
　　（1）随机从视野范围（xij-βiter，xij+βiter）内产生实数y=（y1，y2，…yn）。其中iter为当前的迭代次数；
　　（2）如果f（y）≥f（xi）时，并且y满足函数条件，则用y来替换xi；否则重复步骤（1）直到找到合适的y或者满足一定的运行次数为止；
　　（3）以y做为初始位置，重复爬过程。
　　2.1.4 （在视野范围内）跳过程
　　（1）由于经历过爬过程→望过程→爬过程后，我们假设猴子已经不能再其视野范围内找到更好的位置了，所以沿着指向支点pj= xij-xij的方向，跳到视野范围内的较优位置上，即x ，其中β是望过程中的视野参数；
　　（2）令yi=xij+θ（pj-xij），若y=（y1，y2，…，yn）可用，则令xi=y；否则重复步骤（1）（2）；
　　爬→望→爬→跳过程完成了一次迭代过程，在每次迭代过程中，视野β随迭代次数的增加而递增，即βiter+1=βiter+βiter·ρ，其中ρ为递增因子，这就是1.1.2节所讲的视野递增变化策略，其中iter为当前迭代次数，n为总迭代次数。
　　2.2 改进后算法的基本流程
　　改进后算法的基本流程如下：
　　（1）计算初始化过程，定义计算所需的初始条件，设置相关的参数；
　　（2）通过2.1节的猴群行为得出当前迭代下的最

优函数值；
　　（3）对该最优函数值进行判断，判断其在二十次迭代中都未发生变化，则跳转步骤5，进行高斯变异；否则，进入下一次循环迭代；
　　（4）判断是否达到最大循环迭代次数，若满足，则输出计算的结果；不满足，则返回步骤（2）；
　　（5）对处于最优位置的猴子进行gauss变异，生成的新猴群重复步骤（2）的操作；
　　（6）当总迭代次数达到最大设定次数时候终止。
　　说明：步骤（5）就是猴群的高斯变异。
　　3 gama性能测试
　　为测试改进后猴群算法的性能，这里采用以下五个经典验证函数对其进行验证：
　　ma和gama参数设置如表1所示。在microsoft visual c++平台上，通过c++编程算法，运行电脑配置为win7、intel core i3 m350 2.27ghz处理器、2g内存。寻优测试结果见表2。
　　表1 ma和gama参数设置 　　表2 ma和gama测试结果
　　对于测试函数f1～f5，ma和gama迭代对比过程见图1～图5。
　　图1 函数1 ma和gama迭代过程比较
　　图2 函数2 ma和gama迭代过程比较
　　图6 函数f1的ma和gama算法20次运算结果比较
　　对所有函数，算法连续运算20次。其中函数f1的寻优结果对比见图6。可见ma和gama算法运算20次最优值都不变，限于篇幅，其余函数的不同算法对比结果不再一一列出。
　　本文还将gama算法与遗传算法（ga）和粒子群算法（pso）做对比研究，对测试函数f1～f5的求解结果见表3。
　　表3 gama、ga、pso算法的测试结果统计
　　此外， gama算法还实现在不同维数下的寻优结果，见表4。
　　注：测试函数f4的维数为5时，迭代总次数设置为80次.
　　4 结果分析
　　4.1 gama和ma寻优性能比较
　　4.1.1 收敛精度
　　从表2的测试结果可以看出，针对测试函数1～5，gama算法找到的值0.004545、0.022183、-1566.646323、-3611.783171和0.004006都要比ma算法找到的最优值0.625722、0.686747、-1566.597321、-3472.150206、0.495808更加地接近理论最优解。尤其是对函数f1、f3、f5，在保留小数点后两位的情况下，我们可以认为gama算法成功找到了理论最优解。
　　但ma和gama算法对函数4的寻优结果-3611.783171、-3472.150206并不理想，与理论最优值-8379.658相差较远，这有待进一步改进。但无论如何，在精度方面gama算法都要优于ma算法。
　　4.1.2 收敛速度
　　从图1～图5可以看出，除了函数f4，针对其余函数gama在算法进行高斯变异后就开始收敛，虽然变异后值较大，但开始迭代的时间要快于ma算法。并且观察图1～图5中收敛的区域，可以发现，gama算法在收敛时，迭代图形的陡峭程度要比ma算法高。换言之，gama算法有着较快的收敛速度和“下坡能力”。但对于函数f4，ma和gama的收敛速度相当。
　　4.1.3 稳定性
　　将ma算法与gama算法对5个函数各运行20次，如f1的算法对比结果见图6（其他测试函数对比结果类似）。由图可见，对于20次运算结果，ma和gama都保持一致，不会出现偶尔一两次运算结果不一样的情况，这也足以说明gama算法较稳定。
　　4.2 gama与遗传算法（ga）和粒子群算法（pso）寻优结果比较分析
　　为了较全面地体现gama的特性，我们将gama算法与ga和pso算法进行比较，同样地对函数f1～f5进行寻优测试，结果如表3所示。可以看出，除了测试函数4，其余的测试函数gama算法在寻得结果的精度方面都很大程度地优于ga算法。pso算法一直以其实现容易、精度高、收敛快等优点著称，故在求解函数f1、f2时找到了理论最优值0和局部极值0.0142，要较优于gama算法寻得的结果0.004545和0.022183，误差仅在0.455%～0.80%之间；对于函数f1、f5，gama算法在精度方面的优势就有着较明显的体现，比pso寻得的结果更加接近理论值。
　　4.3 gama在不同维数下寻优结果分析
　　正如引言所述，一般的算法难以避免维数的灾难。基于此，我们选取不同的维数5、10、20、30、40、50、60来测试gama算法求解高维问题的能力及其稳定性。从表4可以看出，不同维数下的寻优结果，没有较大的波动。如函数f1，在不同维数下寻得的结果0、0、0.004545、0.012961、0.029157、0.047024、0.073767只有少许的增长幅度；对测试函数f3、f4的结果f（3）min=-78.33236n、f（4）min=-418.9829n跟维数有着直接的关系，所以寻得的结果会不同。但如果将最

优值除以各自的维数，那么不同维数下寻得的结果波动性很小。故gama算法与ma算法一样，对维数的敏感度较低（ma算法维数敏感度可参考文献[9]），不会陷入维数的灾难。
　　5 结束语
　　本文根据原猴群算法的特点，改变其原有的固定步长和视野，使其自适应增加或递减，有效地提高了猴群算法寻优的精度与收敛速度；并且引入高斯变异随机扰动机制，使很好地保持了猴群的多样性，同时也避免算法陷入局部极值和早熟现象。最后我们利用5个经典的多峰测试函数验证算法的性能，结果有力地表明了gama算法的优越性和有效性。
　　【参考文献】
　　[1]t.back，f.hoffmeister，and h.schwefel.a survey of evolution strategies[j].proceedings of the fourth international conference on genetic algorithms，132-139，san diego，academic press，1991.
　　[2]h.beye and h.schwefel.a comperhensive introdution ： evolution strategies[j].natural computing，2002，1（1）.
　　[3]张爱华，曹晓刚，钟守楠.求多峰函数全部全局最优解的改进遗传算法[j].数学杂志，2009（1）：56-60.
　　[4]朱葛俊.基于人工免疫的多峰函数优化算法研究[j].计算机仿真，2012，29（5）：239-243.
　　[5]y.leung and y.wang. an orthogonal genetic algorithm with quantization for global numerical optimization[j].ieee transactions on evolutionary computation，2001，5（1）：41-53.
　　[6]伊廷华，张旭东，李宏男.基于改进猴群算法的传感器优化布置方法研究[j].计算力学学报，2013，30（2）：218-223.
　　[7]王靖然，余贻鑫，曾沅.离散猴群算法及其在输电网扩展规划中的应用[j].天津大学学报， 2010（9）：798-803.
　　[8]骆晨钟，邵惠鹤.用混沌搜索求解非线性约束优化问题[j].系统工程理论与实践，2000（8）：54-58.
　　[9]郝士鹏.混沌猴群算法及其应用[d].天津大学：天津大学经济与管理学部，2010.
　　[10]欧阳喆，周永权.自适应步长萤火虫优化算法[j].计算机应用，2011，31（7）：1804-1807.
　　[11]陶杨，韩维，张磊.基于群体行为的自适应变异算子鱼群算法[j].中国电子科学研究院学报，2013，10（5）：491-495.
　　[责任编辑：汤静]