一种基于粒子群和鱼群的混合优化算法

李玉毛，于志远

（1.赤峰学院 数学与统计学院，内蒙古 赤峰 024000；2.赤峰学院 附属医院，内蒙古 赤峰 024000）

1 引言

从二十世纪九十年代就产生了通过模拟生物群体行为来解决优化问题的演化计算技术，称为群体智能[1].在1995年，美国学者Kennedy和Eberhart提出了粒子群优化算法(Particle Swarm Optimization)，就是通过对鸟群的某些行为的观察研究，提出的一种新颖而有效的进化算法[2].李晓磊等在2002年提出的人工鱼群算法(Artificial Fish)则是通过模拟人工鱼的觅食行为来处理优化问题.但两个算法都存在不足，鉴于二者的关系，结合二者的优点，提出了一种混合优化算法，可有效地提高算法的寻优能力.

2 关于粒子群算法和人工鱼群算法的基本原理及其存在的问题

2.1 粒子群优化算法原理

PSO算法的基本原理是通过个体间的协作与竞争，实现复杂空间中的最优解的搜索.首先，在D维可行解空间中初始化一群粒子(设有N个)，对应于优化问题在D维空间中的N个潜在的解，然后根据下面两个值来确定它的下次迭代的速度和位置：一个是每个粒子目前搜索到的最优位置，称为个体最优极值；另一个是整个群体迄今为止搜索到的最优位置，称为全局极值.根据这两个值来进行迭代，直到找到满意的解为止[3].

基本的PSO的迭代模型如下：

2.2 人工鱼群算法的基本原理

在一片水域中，鱼往往能自行或尾随其他鱼找到食物多的地方，因而鱼生存多的地方就是食物多的地方，人工鱼群算法就是根据这一特点，通过构造人工鱼来模仿鱼群的觅食、聚群及追尾行为，从而实现寻优.人工鱼群算法[4]具体行为描述如下：

设x=(x1,x2,…,xN)为人工鱼当前状态，对应优化函数中的N个潜在解(其中N表示人工鱼的个数)，yi=f(xi)(i=1,2,…,N)表示人工鱼当前的食物浓度，对应优化函数中的N个函数值，dij=||xi-xj||表示人工鱼个体之间的距离，Visual表示人工鱼视野范围，Step表示移动的最大步长，σ表示拥挤度因子.

(1)觅食行为：人工鱼群当前状态为xi(i=1,2,…,N)野范围内随机选择一个状态xj，当该环境的状态优于原来的状态时，则向该方向前进一步；反之，则重新选择随机状态xj，判断是否满足前进条件；如此反复Try number次后，如果仍不满足，则随机移动一步.

(2)聚群行为：人工鱼群当前状态为xi(i=1,2,…,N)，其视野范围内伙伴数为nf，如果(nf/N)

每条人工鱼搜索当前所处环境的状态，按照“进步最快的原则”或者“进步即可的原则”从中选择一个合适的行为，使得各人工鱼不断向最优化方向前进，并且在公告板上记录其每次搜索到的最值，最终全部人工鱼集结在几个局部极值的周围，且较优的极值区域周围能集结较多的人工鱼.

根据以上对粒子群和人工鱼群的叙述可以看出，二者均属于种群优化算法，由于二者概念简单，需要调整的参数少，易于编程，本身没有类似求导等复杂的数学操作，且在搜索的过程中是多个粒子同时展开搜索，具有隐含并行性，在处理优化问题尤其是复杂问题时，已经相对于传统的优化算法显示出了明显的优势，因而受到人们广泛的关注和青睐，近几年已成功应用于多个领域.

2.3 两个算法存在的问题

粒子群算法和人工鱼群算法都有各自的优缺点，对于粒子群算法它的优点是收敛速度快，缺点是由于在算法初期各粒子很快地向最优值聚拢，也就是在最优值附近粒子群表现出强烈的“趋同性”，算法容易陷入局部最优但收敛速度快，最终收敛到某一局部极值，即出现“早熟”现象，尤其是当解空间是非凸集时，更易陷入局部收敛.人工鱼群算法由于其引入了拥挤度因子[5]，从而能够很好地跳出局部极值，并尽可能地搜索到其他的极值，最终向全局极值靠拢，却在接近最优值时往往停滞不前，而且算法对初值和各种参数的选择也不很敏感，但是当寻优域较大或处于变化平坦的区域时，一部分人工鱼将处于无目的的随机游动中，这就影响了寻优的效率.

3 基于粒子群算法和人工鱼群算法的一种新的混合算法

本文结合鱼群算法和粒子群算法两者的优点，提出了一种新的混合优化算法.由于算法是粒子群和鱼群混合算法，而粒子群算法隐含了鱼群算法中的追尾行为，故为了减少计算量将鱼群算法中的追尾行为去掉，去掉追尾行为的鱼群算法我们称之为简单粒子群算法(SAF).首先初始化一群体，从同一种群出发分别用SAF算法和PSO算法进行搜索，各自的迭代次数由各自目前找到的最优值和上次的最优值的偏差决定，不妨设SAF当前找到的最优值为BBp(p为当前迭代次数)，PSO算法当前的最优值为Bq(q为当前迭代次数)，即当|BBp-BBp-1|

3.1 混合优化算法流程：

Step1：初始化有关参数

设置群体大小N及终止条件，初始化粒子群算法的参数 c1，c2，w和简单鱼群算法的参数 nf，Try number，σ 等.

Setp2：群体初始化

在解空间范围内随机产生N个个体作为初始解，计算N个个体的适应值，将最优值记入公告板.

Step3：简单鱼群迭代

进行一次鱼群搜索得到的最优值记为BBp，若|BBp-BBp-1|

Step4：粒子群迭代

进行一次粒子群搜索得到的最优值记为 Bq，若|Bq-Bq-1|

Step5：比较

若(BBp

Step6：检验公告板的值

若算法达到终止条件的要求，则停止迭代，输出公告板的值，否则，转入Step3.

3.2 混合优化算法性能分析

为了验证新的混合优化算法的性能，本文选择四个经典函数用于优化试验，将混合优化算法和标准粒子群算法、标准鱼群算法、文献[6]结果比较.

以上测试函数均取维数D=30，种群大小N=100，设优化函数各维数的上、下限分别为a、b，根据经验值对算法中的参数如下设置，σ＝0.382，Visual=(b-a)/5，Step=(b-a)/10，Try number=N/5，c1=c2=2，w=0.8，停止条件为最大迭代次数为200次，其中混合优化算法(PSO-AF)的迭代次数规定为粒子群迭代次数和简单鱼群算法迭代次数的一半之和，将本文算法和标准粒子群算法(BPSO)，标准鱼群算法(BAF)，改进的基本粒子群算法(MPSO)[6]算法分别进行10次独立的试验，四种算法运行平均最优值如表1所示.

从表1可以看出，混合优化算法的每个测试函数的收敛精度明显优于其他三种算法，而且它的稳定性也有很大幅度的提高.

表1 四种算法运行平均最优值

4 结束语

本文提出基于粒子群算法和人工鱼群算法的一种新的混合算法(PSO-AF)，解决了两种算法：基本粒子群算法容易陷入局部最优但收敛速度快，鱼群算法全局收敛能力好却在接近最优值时往往停滞不前经过仿真测试，我们提出的混合优化算法能够很好地跳出全局最优并很快向极值靠拢，是一种比较可行的优化算法，但不足的是文中很多参数只能凭借经验取定，其理论值还有待于通过分析算法的收敛性而进一步确定.

〔1〕Kennedy J,Eberhart R C.Shi Y.Swarm Intelligence[M].San Francisco:Morgan Kaufman Publishers,2001.

〔2〕Kennedy J,Eberhart R C.Particle Swarm Optim ization[R].Proc.IEEE Int,Ioont.On Nerual Networds.IEBE Service Center,Piscataway,NJ,1995(4):1942-1948.

〔3〕徐宗本.计算智能（第一册）-模拟进化计算.北京:高等教育出版社,2004.114-116.

〔4〕李晓磊,邵之江,钱积新.一种基于动物自治体的寻优模式:鱼群算法[J].系统工程理论实践.2002(22):32-38.

〔5〕修春晓,张雨虹.基于蚁群与鱼群的混合优化算法[J].计算机工程，2008（4）.

〔6〕王晓英,邢志栋,黄瑞平.改进的粒子群优化算法[J].计算机应用与软件，2008（3）.