基于多层次信息反馈的混合蛙跳算法

The Shuffled Frog Leaping Algorithm Bases on the Interation of Multi-Level Information

摘要: 基于多层次信息反馈的混合蛙跳算法(Shuffled Frog Leaping Algoriyhm based on the interation of Multi-level information, MSFLA)，吸收遗传算法的交叉算子及粒子群算法(PSO)的粒子进化方式，将整个优化过程划分为标准混合蛙跳优化层、青蛙进化与学习层、外部档案信息交换层。混合蛙跳优化层保证青蛙进行正常的局部搜索优化(蛙跳算法)；青蛙进化与学习层保证青蛙每次迭代结束时都能得到更好的自身位置(PSO粒子进化方式)；外部档案信息交换层可以保证青蛙种群获得最优解(交叉算子)。通过各层次之间的信息交流，提高算法的性能。从实验结果对比能够得出，改进后的MSFLA算法可以有效地改善早熟收敛问题，具有更好的收敛速度和更高的寻优精度。

Abstract: The Shuffled Frog Leaping Algorithm bases on the interation of multi-level information (MSFLA), which assimilates the Crossover of the Genetic Algorithm and the evolutional pattern of Particle Swarm Optimization (PSO). The whole optimization process includes three aspects—the optimizing layer of standardly blended frog leaping, the layer of flog evolution and learning, and the commutative layer of external file information. The first layer guarantees the frog to normally perform local optimal search (Fog Leaping Algorithm) and the second layer ensures that the frog can get a better self-position at the end of each iteration (the evolutional pattern of PSO). Moreover, the last layer can assure that the fog population gains the most optimal solution (the Crossover).Through the exchange of information between all levels, improve the performance of the algorithm. Experimental results show that the improved MSFLA can avoids premature convergence effectively, and has better convergence results, higher accuracy.

1. 引言

在实际应用中，非线性、非连续、不可微、多变量甚至混杂系统出现的越来越多，经典优化方法已经不可能有效求解，为寻找复杂优化问题的解决方案，20世纪90年代以来，学者们提出了一些新的迭代搜索算法——群智能优化算法。混合蛙跳算法(Shuffled Frog Leaping Algorithm, SFLA) [1] 就是其中一种，它是Eusuff等人在2003年提出的一种元启发式协同搜索群智能算法。

SFLA基于青蛙觅食的行为，结合遗传基因的模因演算算法和基于群体觅食行为的粒子群优化算法的优点，借鉴多种群混合进化的思想、将种群划分成若干个子群，所有子群独立地同时地进行局部模因进化，而后通过混合子群达到全局信息交换的目的，从而推进整个种群向最优的区域搜索。在局部迭代寻优的过程中，根据局部最优个体以及全局最优个体的差异对最差个体进行更新 [2] 。

2. 算法基本理论

2.1. 标准混合蛙跳算法

SFLA算法是一种受青蛙群体寻找食物时按子群分类进行信息交换过程得到启发而产生的仿生智能优化算法。

2.2. 标准混合蛙跳算法的数学模型

对于一个d维的函数优化问题：

$\{\begin{array}{l}\min f\left(x\right)\\ s.t.x\in \left[l,u\right]\end{array}$ (1)

其中 $\left[l,u\right]:=\left\{x\in {\Re }^d|l_k\le x_k\le u_k,k=1,2,\mathrm{...},d\right\}$ 。

利用SFLA算法求解此类问题时，主要有以下四个步骤：

1) 种群初始化：从可行域中随机生成F个青蛙作为初始种群，设第 $i$ 个青蛙表示为 $x\left(i\right)=\left(x_1^i,x_2^i,\mathrm{...},x_d^i\right)$ ，则每个 $x\left(i\right)$ 为问题的一个解。

2) 子群划分：计算每个解的目标函数值 $f\left(i\right)$ ，对目标函数值进行排序，记种群中目标函数值最优的解为 $X_g$ 。然后将整个种群分为m个子群。在每个子群中有n个解(即 $F=m\ast n$ )，记每个子群目标函数最好和最差的解分别为 $X_b$ 和 $X_w$ 。

3) 局部搜索：根据模因算法在各子群内部进行进化运算，每次迭代只改变子群中目标函数值最差的解 $X_w$ ，其更新公式为：

$D_i=rand\left(\right)\ast \left(x_b-x_w\right),i=1,2,\mathrm{...},m$ (2)

${x^{\prime }}_w=x_w+D_i,\left|D_i\right|\le D_{\max },i=1,2,\mathrm{...},m$ (3)

其中 $rand\left(\right)$ 是0到1之间的随机数， $D_i$ 为青蛙的移动步长， $D_{\max }$ 表示青蛙所允许改变位置的最大值。在经过更新后，如果得到的子群最差解 ${X^{\prime }}_w$ 优于原来的最差解 $X_w$ ，则用 ${X^{\prime }}_w$ 替换 $X_w$ ，如果 $X_w$ 没有得到改进，则用 $X_g$ 代替 $X_b$ 后利用公式(2)、(3)进行局部搜索，如仍没有改进，则随机生成一只新解直接替代 $X_w$ ，重复上述局部搜索直到达到子群迭代次数。

4) 全局混合：将所有子群内的蛙重新混合，更新整个种群中目标函数最优解 $X_g$ ，重新进行步骤2和3，直到达到指定的迭代次数或满足定义的收敛条件。

2.3. 标准SFLA的局限性

由以上4步骤可见，SFLA算法结合了局部进化更新和全局信息交换，在进行局部搜索的基础上更新全局最优解，具有参数少，全局寻优能力较强，且收敛速度较快等优点，故在实际中有很多的应用，可以用来优化各类连续或离散的问题 [3] [4] ，也可用于求组合优化和复杂函数的最优解 [5] 。

但由于标准SFLA更新方式较为单一，会造成种群多样性不强，收敛速度降低，而且容易陷入局部最优导致算法早熟的问题。并且在个体更新的过程中忽略了同组内其它个体，以及种群中其它个体的信息交流，可能会错过可能更优秀的解或组合 [6] 。

针对上述问题，本文通过引入粒子群算法(PSO) [7] 的粒子进化方式以及遗传算法 [8] 的交叉算子来改善。提出了基于多层次信息反馈的混合蛙跳算法(MSFLA)。

3. 基于多层次信息反馈的混合蛙跳算法

在MSFLA算法中，整个算法分为标准混合蛙跳优化层、青蛙进化与学习层、外部档案信息交换层三个层次。

在每次迭代优化初始阶段中，通过标准蛙跳算法更新位置的方法获得青蛙的新位置，并且判断青蛙新旧位置的优劣情况。如果青蛙新位置没有优于旧位置，则进入青蛙进化与学习层。

在MSFLA算法中，通过引入粒子群算法中的粒子进化方式 [9] 来实现青蛙进化和青蛙对全局最优的学习，获取更优的新位置，从而增加青蛙的多样性。同时，利用遗传算法中交叉算子的功能，建立外部档案信息交换层，将每一次得到的全局最优解(全局最小适应度)相关信息记录进外部档案信息中，在优化过程中，外部档案信息中的最优解以一定比例和优化层以及进化与学习层结合来产生新解，这样可以为青蛙寻优以及青蛙进化与学习提供更好的全局最优。

3.1. 青蛙进化与学习

蛙跳算法由于更新存在随机性，故对多模态等函数寻优时，往往使得SFLA后期搜索过程出现收敛速慢，解的精度较差等现象。我们将通过引入PSO算法中粒子的进化方式，用于改变这一现象。

在蛙群一次迭代完成后，判断青蛙的新位置P是否优于旧位置OP，如果没有，那么将此青蛙进行进化与学习，具体步骤如下：

Step1：将青蛙移动位置后得到的新位置P与旧位置OP进行交叉操作，得到位置P1。

Step2：计算青蛙位置P、P1的适应度，从中选出适应度更优的青蛙位置，记为P2。

Step3：比较青蛙位置P2与OP，如果P2优于OP，则取P2作为青蛙的新位置以促进算法的收敛，并转至Step7。否则，转至Step4进行青蛙旧位置OP对全局最小适应度(即最优解)的学习。

Step4：根据采取的交叉原则，将青蛙旧位置OP中的相应变量替换为全局最小适应度中的对应变量，得到青蛙位置P3。

Step5：计算青蛙位置P2与P3的适应度，从中选出适应度最优的青蛙位置，记为NP。

Step6：比较青蛙位置NP与OP，如果NP优于OP，则用NP作为青蛙的新位置，以促进算法的收敛；当NP和OP的适应度相等或无法比较时，NP也被保存作为青蛙的新位置，这样可以提高算法的多样性；如果NP劣于OP，则取OP作为青蛙的位置以防止最优解丢失。

Step7：青蛙进化和学习结束。

3.2. 外部档案信息交换

本文改进的SFLA算法采用遗传算法中交叉算子的功能用于实现外部档案信息交换。将全局最小适应度(即最优解)相关信息记录进外部档案信息中。在优化过程中，外部档案信息中的最优解以一定比例和混合蛙跳优化层以及青蛙进化与学习层结合以产生新解。外部档案信息交换层中的信息将在每次全局最小适应度更新后替换。具体交换方式有：

情形1：如青蛙 $i$ 的适应度比外部档案中记录最优解的适应度差，则以一定比例和混合蛙跳优化层以及青蛙进化与学习层结合以产生新解；

情形2：如适应度相等或无法比较，保留原青蛙位置；

情形3：如适应度优于最优解适应度，则保留此青蛙位置。

3.3. 算法伪代码

初始化参数

F←m*n;//产生初始青娃

for i1 = 1 to F

给所有青蛙赋初始值

end

//全局迭代寻优

While ii = 1 to G

for i2 = 1 to F

计算所有青蛙的适应度

end

for i3 = 1 to F

排序

end

xg←全局最好的青蛙

//局部搜索过程//混合蛙跳优化层，提供新位置

for i4 = 1 to m

for j = 1 to N//每组青蛙迭代次数

记录组内最优xb与组内最差的青蛙xw

使用rand.*(xb-xw)进行组内最优更新操作

if fun(temp) > fun(xw)

使用rand.*(xg-xw)进行采用全局最优更新操作

end

if fun(temp) > fun(xw)

使用pmax*rands(1,d)进行随机更新操作

end

记录最差的青蛙更新后的位置为P

If青蛙新位置p比旧位置op差

Then蛙群学习与进化

使用交叉算子对P和op进行交叉操作得到位置P1

计算P、P1的适应度并比较，选择适应度更优的青蛙位置，记为P2

If p2比op差

Then将记录的全局最优解xg记为P3

选择P2、p3中的最优位置，记为NP

If NP优于或者等于OP

Then保留Np作为青蛙新位置

Elseif保留op作为青蛙位置

Else保留p2为青蛙的新位置

End

Elseif青蛙新位置P优于旧位置

Then保留P

End

end //结束N

更新全局最优解

end //结束m

end//结束G

3.4. SFLA算法流程图

MSFLA算法流程图如下图1。

Figure 1. MSFLA algorithm flow chart

图1. MSFLA算法流程图

4. 仿真实验

为了验证MSFLA的收敛效果，根据文献 [10] 中的函数选择，选取了五个经典的测试函数进行仿真实验，将改进后的蛙跳算法与标准混合蛙跳算法进行对照实验。为了更好的进行MSFLA与SFLA算法的对比实验，本文进行实验时所有函数都采取一样的参数。参数设置如表1所示。

Table 1. Algorithm parameter settings

表1. 算法参数设置

表2列举了五个测试函数的表达式、范围、维数以及最优值。

Table 2. Test function

表2. 测试函数

在固定总迭代次数时，标准SFLA和MSFLA寻优精度的仿真结果如表3所示，从表中数值的对比结果可看出，在相同进化代数的前提下，MSFLA对于上述测试函数无论是最优值、最差值还是平均值的结果均优于标准的SFLA，故MSFLA可有效地提高算法的全局收敛性。

Table 3. Simulation results of optimization accuracy under fixed number of iterations

表3. 固定迭代次数下寻优精度的仿真结果

为了将MSFLA与标准SFLA进行对比，本文给出了两种算法下各测试函数的平均进化曲线图(图2~6)。

Figure 2. Sphere function

图2. Sphere函数

Figure 3. Rosenbrock function

图3. Rosenbrock函数

Figure 4. Rastrigin function

图4. Rastrigin函数

Figure 5. Griewank function

图5. Griewank函数

Figure 6. Schafferf7 function

图6. Schafferf7 函数

由上述图可见，在迭代次数相同的情形下，MSFLA相比于SFLA具有更高的寻优精度，在寻优精度相同的条件下，MSFLA比SFLA需要的迭代次数更少。

5. 结论

针对标准SFLA算法更新方式单一，收敛速度慢，易陷入局部最优而导致算法早熟等问题，本文提出的MSFLA融合算法在保留混合蛙跳算法的优点的基础上，溶入了粒子群算法的粒子进化和遗传算法的交叉算子。MSFLA算法通过粒子进化、学习和文件信息交换，提高了混合蛙跳算法的收敛性和多样性，通过新算法与SFLA算法的仿真实验可见，新算法在相比SFLA优化效果更好，具有更快的收敛速度、更高的寻优精度。

基金项目

江西省教育厅科学技术研究项目(编号：GJJ211329)。