基本信息

猴群算法是于2008年由Zhao和Tang[8]提出的一种新的用于求解大规模、多峰优化问题的智能优化算法.其思想在于通过模拟自然界中猴群爬山过程中爬、望和跳的几个动作,设计了三个搜索过程：爬过程主要用来搜索当前所在位置的局部最优解；望过程主要通过眺望来搜索邻近领域比当前位置更优的解,以便加速最优解的搜寻过程；跳过程的目的在于由当前搜索区域转移到其它区域,以避免搜索过程陷入局部最优.在猴群算法中,其花费的CPU时间主要在于寻找局部最优位置的爬过程.爬过程中每次迭代的计算量主要集中在目标函数伪梯度的计算,其只涉及到当前位置的两个临近位置的目标函数值而与决策向量的维数无关.这一特征显著地提高了算法的性能,尤其针对高维优化问题时效果更为明显.另外,跳过程迫使猴群由当前区域转移到新的区域,从而避免算法陷于局部最优.

作为一种智能算法, MA能够有效地求解高维的、非线性不可微的函数优化问题.此外, MA需要调整的参数也少,这使得MA易于实现.尽管猴群算法在求解高维数优化问题时有了较大的突破,但其也存在一些不足.首先,对于不同的优化问题,在利用MA求解时需要设置不同的参数,并且这些参数对猴群算法来说很重要,一旦设置的不准确,即便是优化问题的近似最优解也很难找到.另外,猴群算法求解优化问题时耗费的CPU时间也较长,在优化效率方面仍具有很大的提高空间.基于以上分析,本文结合了猴群算法和混沌搜索技术提出了一种改进的猴群算法,称为混沌混群算法CMA.混沌描述的是一种非线性状态,它同时具有确定性、随机性和遍历性.基于混沌的遍历性及不重复性而提出的混沌搜索技术比传统的随机搜索技术速度更快,质量更高.将混沌搜索技术引入到MA中非常必要,这样在很大程度上避免了猴群算法陷入局部最优.此外,本文采用了变参数的方法设计了一组设用于各种优化问题的混沌猴群算法通用参数,在提高了算法性能同时也为算法的使用者提供了便利.

一般来说,在优化问题中如果目标函数是一个多峰函数,局部最优点的数量将随着决策向量维数的增加而急剧增长.一方面,在求解高维优化问题时,常用算法如遗传算法、蚁群算法、粒子群算法等容易陷入局部最优；另一方面,由于需要大量的计算,这些算法所消耗的CPU时间也会大大增长.而在MA中,跳过程的目的恰恰是迫使猴群由当前区域转移到新的区域,从而避免算法陷于局部最优.另外, MA花费的CPU时间主要在于寻找局部最优位置的爬过程.而在爬过程中每次迭代的计算量主要集中在目标函数伪梯度的计算,其只涉及到当前位置的两个临近位置的目标函数值而与决策向量的维数无关.这一特征显著地提高了算法的性能,尤其针对高维优化问题时效果更为明显.

优化模型

大部分优化问题的数学表达形式是最大化（或者最小化）某一些目标函数.不失一般性,本文将只讨论最大化的情况,因为任意的极小化问题都可以通过改变目标函数的符号而转化成最大化问题.全局优化问题的一般化模型可表示为：

其中为上的决策向量,为优化问题的目标函数,为约束函数.

考虑由Koziel和Michalewicz提出的优化问题

(2.1)

图2.1描述了模型(2.1)的目标函数f(x1,x2)在区间[0, 10]×[0, 10]的轮廓图形,从中可以看出f(x1, x2)是一个多峰函数.

图2-1模型中目标函数的图像

2.2． 猴群算法(MA)

MA由初始化、爬过程、望过程和跳过程等部分组成,这几部分分别介绍如下.首先,令正整数M表示猴群的群体规模,第i猴子的当前位置用向量xi=(xi1, xi2, . . . , xin), i = 1, 2, . . . , M表示,每只猴子的位置实际上对应着优化问题的一个决策向量.例如,在例1中,令M = 5 ,即5只猴子组成一个群体.对于第i只猴子的位置,用向量xi= (xi1, xi2), i = 1, 2, . . . , 5表示,它又表示模型(2.1)的一个决策向量.

2.2.1初始化

给每一只猴子初始产生一个位置,可用产生随机变量的方法生成.例如,在求解模型(2.1)时,可用以下随机方法给产生初始位置.

#include "stdlib.h"

for i =1 to M

Mark :

for j=1 to 2