SFL算法的流程图和算法

摘 要：本文主要介绍SFL算法的流程图和算法，并总结出SFL算法的易于理解、参数较少、收敛速度较快、寻优能力强、易于实现等优点。

关键词：SFL； 算法； 参数； 优点

中图分类号：M774 文献标识码：A 文章编号：1006-3315(2011)3-176-001

混合蛙跳算法（Shuffled Frog Leaping Algorithm, SFLA）是2000年由Eusuff等人提出的一种基于群体智能的后启发式计算技术。SFL作为一种生物进化算法, 它结合了基因进化的模因演算法(Memetic Algorithm)和群体行为的粒子群算法( Particle Swarm Optimization)两者的优点，具有概念易于理解、参数较少(比PSO算法更少的参数)、收敛速度快、全局寻优能力强、易于实现等优点。

一、SFL的编码和参数

1．frog的编码

在SFL算法中，frog的编码决定了解的形式和结果。和传统的GA算法相比，SFL算法最突出的特点是frog可以使用实值进行编码，frog的每一个基因都可以使用实值，减少了二进制转换时间。

2．SFL算法中的参数

2.1种群规模：种群中青蛙的个数，即解的个数。

2.2族群个数：族群个数决定了SFL算法的搜寻范围，族群个数越多，搜索范围越广，利于可行解的全局搜索。

2.3最大步长：当更新族群中的frog时，需要设定最大的更新步长，避免更新过快，找不到最优解。步长的设定决定了frog的局部搜索能力，步长越小，局部搜索能力越强，但时间也越长。

2.4阈值：用于控制算法挑出的参数。通常是残差、精度等数值。

二、SFL算法流程图和算法

在SFL算法执行过程中，当群体中的frog的适应度函数达到优化要求时，程序挑出、结束，否则继续执行算法，直到有可行解的出现。在SFL算法执行过程中使用了分组融合的概念，每次根据适应度值的不同，对整个群体进行分组，分组后进行组内更新，即每组中适应度函数最差的frog。经过若干次迭代后，合并所有组内的染色体，判断终止条件（有没有frog的适应度值达到设定条件），如不满足，则进行下一次迭代，如果满足，挑出程序。SFL算法流程图，如下图所示：

基本SFL算法如下：

算法分组后会更新组内适应度值最差的个体(Xw)，它的更新策略如下：

Xw位置的改变量（Di）=rand( )×（Xb-Xw），rand( )∈(0,1)（1）；

Xw新的位置=Xw当前位置+Di，-Dmax≤Di≤Dmax,Dmax表示最大更新步长。（2）

三、SFL算法的优缺点

SFL算法优点：

1．较少的参数

相对于其它算法，参数较少。

2．计算速度快

由于在SFL算法中采用了分组策略，每一组frog可以搜寻一个方向，并由一直带头frog指引方向（更新策略1），使得算法执行过程中能在局部快速找到最优解。

3．全局搜索

由于SFL算法执行中采用分组策略，每组进行局部搜索，多组进行全局搜索，并在执行一定次数的局部搜索后，进行全局的融合，再次分组，实现组间的信息交互，达到快速全局搜索的目的。

4．每次迭代过程中，所有的frog均可以多次选择参与进化

SFL算法缺点：和GA算法类似，SFL算法也存在着诸多进化算法的缺点，即算法执行过程中含有参数，算法时间复杂度较高，最优解不唯一等。

综上所述，SFL算法是一种寻优能力很强的算法，能够快速求解优化问题，避免了传统进化算法易陷入局部最优解的问题。

参考文献：

[1]E. Emad, H. Tarek, G. Donald. Comparison among five evolutionary-based optimizationalgorithms. Advanced Engineering Informatics, 2005, 19: 43–53.

[2]Wilson, D.L. Asymptotic properties of nearest neighbor rules using edited data. IEEE Transactions on Systems, Man, and Cybernetics, 1972, SMC-2(3):408–421.

[3]Fabrizio Angiulli. Fast Nearest Neighbor Condensation for Large Data Sets Classification. IEEE Transactions on Knowledge and Data Engineering, Nov 2007, Vol 19, No. 11. pp. 1450-1464.