融合随机森林决策的海鸥优化算法

A Seagull Optimization Algorithm Incorporating Random Forest Decision Making

摘要: 针对海鸥优化算法(SOA)在求解优化问题时容易早熟、算法性能过于依赖参数以及解的精确度较低等问题，提出了一种融合随机森林决策的海鸥优化算法(RFSOA)。首先，在海鸥前期迁徙阶段，引入非线性递减参数A对海鸥位置进行改变，调整算法的全局寻优能力，避免在迭代过程前期算法便会陷入局部最优的情况；其次，在海鸥攻击阶段，引入机器学习中随机森林思想，将每个海鸥个体位置看作任一决策树的分支，利用其构造决策树进行海鸥位置的改变，位置变化时采取螺旋状位置更新策略或最优高斯游走策略，增加海鸥位置改变的随机性，并利用贪心策略保留优质个体，从而提高寻优精度。选择Benchmark测试函数及0-1背包问题部分算例进行算法性能测试，结果显示RFSOA具有寻优能力强、精确度高的优点，更适合求解较高维度的连续函数优化问题及带有约束的实际应用问题。

Abstract: A seagull optimization algorithm (RFSOA) that incorporates random forest decision making is pro-posed to address the problems that the seagull optimization algorithm (SOA) tends to be premature in solving optimization problems, the performance of the algorithm is too dependent on parame-ters, and the accuracy of the solution is low. Firstly, in the premigration stage of the seagull, a non-linear decreasing parameter A is introduced to change the position of the seagull to adjust the global optimization capability of the algorithm and avoid the situation that the algorithm will fall into the local optimum at the early stage of the iterative process; secondly, in the attack stage of the seagull, the random forest idea in machine learning is introduced to consider each individual position of the seagull as a branch of any decision tree and use it to construct a decision tree to change the position of the seagull. The spiral position update strategy or optimal Gaussian wandering strategy is adopted when the position changes to increase the randomness of the gull position change, and the greedy strategy is used to retain the high quality individuals, so as to improve the optimization seeking accuracy. Benchmark test function and some examples of 0-1 knapsack problem are selected to test the performance of the algorithm. The results show that RFSOA is more suitable for solving continuous function optimization problems with higher dimensionality and practical application problems with constraints.

1. 引言

受自然界生物群体行为的启发，诸多群智能算法被提出并用于求解优化问题，如粒子群优化算法(Particle Swarm Optimization, PSO) [1] 、鲸鱼优化算法(Whale Optimization algorithm, WOA) [2] 、哈里斯鹰优化算法(Harris Hawks Optimization, HHO) [3] 、黑猩猩优化算法(Chimp Optimization Algorithm, ChOA) [4] 、海洋捕食者算法(Marine Predators Algorithm, MPA) [5] 等。

海鸥优化算法(Seagull Optimization Algorithm, SOA) [6] 是由Dhiman和Kumar教授在2019年提出的一种新的元启发式算法，海鸥优化算法参数较为简单容易实现，目前常被用于求解较大规模的优化类问题，但是在迭代寻优过程中也存在倾向于局部最优、算法性能依靠参数以及寻优的精确度低等缺陷。为了解决海鸥优化算法存在的缺陷，提高算法性能，诸多学者在海鸥优化算法的基础上提出改进策略。

毛清华等 [7] 提出一种融合改进Logistics混沌和正弦余弦算子的自适应t分布海鸥算法(ISOA)，采用Logistics混沌映射对种群进行初始化，并引入正弦余弦算子以及非线性参数A来对算法的全局搜索和局部搜索进行协调，从而加快算法收敛速度，在最优解位置利用自适应t分布变异策略进行扰动产生新解，增强了算法跳出局部最优的能力。秦维娜 [8] 等提出一种基于惯性权重的海鸥优化算法，该算法使用非线性递减的惯性权重对海鸥的位置进行调整，并使用莱维飞行和随机指数值增加海鸥飞行的随机性，从而提高算法寻找最佳方案的全局能力。He [9] 等提出的基于反向的海鸥优化算法(OSOA)，将特征选择技术与SOA相结合，其总体由基于反向的学习(OBL)算法确定，测试结果证明该算法具有更高的精度和计算效率。Jia H [10] 等提出了一种特征选择混合海鸥优化算法，将海鸥优化算法与热交换优化(TEO)算法进行混合，采用TEO算法的热交换公式来改进SOA的海鸥攻击模式，从而有效的提高了SOA的开发能力。

为了进一步提升海鸥优化算法的性能，本文提出一种融合随机森林决策的海鸥优化算法(RFSOA)。该算法在迁徙阶段，引入非线性参数A，从而提高算法对于搜索空间全局及局部的平衡性；在攻击阶段利用随机森林思想，利用决策树计算海鸥个体的待攻击位置，位置变化过程采取螺旋更新或高斯随机游走策略，增加海鸥位置改变的随机性，最后利用贪心策略保留最优个体，从而提高算法寻优精度。

2. 标准海鸥优化算法

海鸥是遍布全球的候鸟，主要以群居式生活，擅长利用智慧来寻找和攻击猎物。

其最重要的运动行为是迁徙和攻击，迁徙通常被定义为动物为了搜寻更为丰富的食物来源从而获得充足的能量而从一个区域移动到另一个区域的生理需要。在迁移期间，动物呈集群式出行。在进行迁徙时，每只海鸥所处的飞行位置都不同，以避免相互之间发生碰撞。在一个群体中，会有一个最佳位置方向，每个海鸥都会朝着这个方向移动，从而导致自身所在的位置发生改变。海鸥经常会攻击候鸟，在这种情况下，运动群体的位置会围绕螺旋形轨迹发生变化 [11] 。

2.1. 迁徙(全局搜索)

在进行迁移时，算法模拟处于集群中的海鸥个体如何从一个位置移动到另一个位置。在这一过程中，海鸥应该满足三个条件：

1) 避免碰撞：为了避免与邻居(其他海鸥)碰撞，该算法使用一个额外的变量A来进行对于海鸥新位置的计算。

$C_s\left(t\right)=A\times P_s\left(t\right)$ (1)

$C_s\left(t\right)$ 表示不会和其他海鸥发生位置冲突从而导致碰撞的新位置， $P_s\left(t\right)$ 表示海鸥目前所在的位置，t表示当前迭代，A表示海鸥在特定搜索空间中移动时的行为。

$A=f_c-t\times \left(f_c/Ma{x}_{iteration}\right)$ (2)

$f_c$ 可以控制变量A随迭代次数的改变而发生改变，它的值从2线性降低到0。

2) 最佳位置方向：在避免了与群体中的其他海鸥个体发生位置碰撞冲突之后，海鸥会寻找一个目前相对个体最佳的位置方向，然后朝着其所处的方向移动。

$M_s\left(t\right)=B\times \left(P_{bs}\left(t\right)-P_s\left(t\right)\right)$ (3)

$M_s\left(t\right)$ 表示需要朝着其移动的最佳位置所在的方向，B是负责平衡全局和局部搜索的随机数。

$B=2\times A^2\times r_d$ (4)

$r_d$ 是[0, 1]范围内的随机数。

3) 靠近最佳位置：当海鸥移动到不与其他海鸥发生位置冲突的位置并且寻找到最佳位置方向之后，就会朝着该方向进行移动，从而使其位置发生改变。

$D_s\left(t\right)=\left|C_s\left(t\right)+M_s\left(t\right)\right|$ (5)

$D_s\left(t\right)$ 是海鸥在整个迁移改变位置过程中的位移。

2.2. 攻击(局部搜索)

海鸥在迁徙过程中用翅膀和重量保持高度，攻击角度和速度会不断发生改变。当进行对猎物的攻击时，它们就在空中整体的运动轨迹呈螺旋形状变化。利用x、y和z平面描述的运动行为如下：

$\{\begin{array}{l}x=r\times \cos \left(\theta \right)\\ y=r\times \sin \left(\theta \right)\\ z=r\times \theta \\ r=u\times {\text{e}}^{\theta v}\end{array}$ (6)

其中r是每个螺旋的半径，θ是[0, 2π]范围内的随机角度值。u和v是螺旋形状的相关常数，e是自然对数的底数。

$P_s\left(t\right)=P_{bs}\left(t\right)+D_s\left(t\right)\times x\times y\times z$ (7)

$P_s\left(t\right)$ 是海鸥的攻击位置。

综上所述，进行位置变换之后的海鸥粒子位置如下所示：

$P_s\left(t\right)=P_{bs}\left(t\right)+\left|B\times P_{bs}\left(t\right)-\left(B-A\right)\times P_s\left(t\right)\right|\times x\times y\times z$ (8)

3. 融合随机森林决策的海鸥优化算法

3.1. 非线性参数A

标准海鸥优化算法中引入辅助变量A作为避免海鸥发生位置碰撞的变量，A的值随着 $f_c$ 发生变化，A的取值从2线性下降到0，导致对于解空间的搜索呈线性收敛。经过测试发现，呈线性收敛的A并不适合算法对于非线性空间中解的有效搜索。为了进一步提高算法对于解的全局及局部搜索的平衡能力，将A设置成非线性参数，由公式(9)描述：

$A=\frac{A_{\text{start}}-A_{\text{final}}}{1+{\text{e}}^{\frac{2t-T_{\max }}{T_{\max }}\ast 5}}$ (9)

t代表当前迭代， $T_{\max }$ 代表最大迭代次数。

如图1所示，改进后的参数A呈非线性下降，在算法迭代前期，A的值较大，因此算法具有较好的全局搜索能力；在迭代后期，A的值迅速下降，使得算法具有较强的局部搜索能力。相比于标准SOA中线性下降的参数A，改进后的A有效平衡了算法的全局及局部搜索，理论上可以有效提升算法性能。

Figure 1. Variation curve of parameter A with the number of iterations

图1. 参数A随迭代次数的变化曲线

3.2. 基于随机森林的位置更新

随机森林算法中采用的bootstrap重采样技术是一种有放回的随机采样，从原始的训练样本集中随机有放回地抽取与其等数量的样本组成1个采样集，重复n轮得到n个相互独立的采样集；然后利用每个采样集分别生成决策树，n个决策树连接形成“森林” [12] 。

将该机制引入海鸥优化算法的种群更新，应用随机森林构建多个决策树同时进行决策，最终取最优结果。

设种群内有个体数量n，利用 $P=\left(P_1,P_2,\cdots ,P_n\right)$ 表示种群个体。随机且有放回的取其中n个个体构成数据集1，利用 $T{P}_1=\left(T{P}_{11},T{P}_{12},\cdots ,T{P}_{1n}\right)$ 表示，记其中不重复的个体数量为 $r_1$ ；数据集2同理，利用 $T{P}_2=\left(T{P}_{21},T{P}_{22},\cdots ,T{P}_{2n}\right)$ 表示，其中不重复的个体数量为 $r_2$ ；数据集3中包含的个体为种群P除 $T{P}_1,T{P}_2$ 以外剩余的个体，个体数量为 $n-r_1-r_2$ 。分别将数据集1、数据集2及数据集3的个体视为其对应决策树的分支。对第一棵决策树包含的 $r_1$ 个个体选择第一种位置更新策略，即公式(10)螺旋状更新策略；对第二棵决策树包含的 $r_2$ 个个体选择第二种位置更新策略，即公式(11)高斯随机游走策略；对第三棵决策树包含的个体进行随机概率取值，每个个体对应一个随机数 $\rho$ ， $\rho \in \left(0,1\right)$ ，若 $0<\rho \le 0.5$ ，则该个体采用公式(10)进行位置更新；若 $0.5<\rho <1$ ，则利用公式(11)进行位置更新。三棵决策树共同进行决策，判断个体位置变化后适应值优劣，并利用贪心策略保留适应值优越的个体。

3.2.1. 位置更新策略

a) 按照标准SOA中螺旋状位置更新进行。

$P_s\left(t\right)=P_{bs}\left(t\right)+\left|B\times P_{bs}\left(t\right)-\left(B-A\right)\times P_s\left(t\right)\right|\times x\times y\times z$ (10)

b) 采用最优高斯游走策略进行位置更新。

高斯随机游走模型是最具有代表性的随机游走模型之一，具有较高的探索能力。因此，以当前的最优个体作为引导，利用高斯随机游走的特点，产生新的个体，可以平衡算法在进行探索与开发时的能力。下式为基于当前最优个体的高斯随机游走策略：

$P_s\left(t\right)=Gaussian\left(P_{bs}\left(t\right),\tau \right)+\left|B\times P_{bs}\left(t\right)-\left(B-A\right)\times P_s\left(t\right)\right|$ (11)

步长τ表示为

$\tau =\frac{\log \left(t\right)}{t}\left(p_s\left(t\right)-p_{bs}\left(t\right)\right)$ (12)

通过当前最优个体的引导，种群会产生接近最优个体的新个体，从而使算法较快的发生收敛；同时，利用高斯分布的方差 $\tau$ 对给定空间中的搜索进行自适应控制，在算法迭代初期，t的值偏小， $\tau$ 的值较大，因此算法具有较强的全局探索能力；进入到迭代后期之后，随着迭代次数的不断增加， $\tau$ 的值逐渐减小，从而算法具有了较强的局部开发能力。

3.2.2. 贪心策略保留优质个体

利用式(13)贪心策略对每次迭代进行位置变换之后的海鸥个体进行选择保留，具有较高适应值的个体将被保留下来，避免了标准SOA中位置更新之后产生并保留劣质个体的情况，从而使得迭代过程可以拥有相对较高的平均适应值，同时个体分布更加广泛，有助于提高寻找整体最优值的效率，降低了过早地发生局部收敛而无法跳出的概率。

$P_s\left(t+1\right)=\{\begin{array}{l}{P}_s\left(t\right)\text{if}fit\left(P_s\left(t\right)\right)>fit\left(P_s\left(t+1\right)\right)\\ P_s\left(t+1\right)\text{else}\end{array}$ (13)

3.3. 算法描述

算法1. 融合随机森林决策的海鸥优化算法(RFSOA)：

输入：种群规模n，迭代次数Maxiter

输出：最优解 $X_{best}$

步骤1. 初始化算法问题参数、迭代次数以及种群规模；

步骤2. 随机生成初始化种群，产生初始个体编码与海鸥位置编码；

步骤3. 计算种群个体适应值，获得当前种群中最优个体位置 $P_{best}\left(t\right)$ ；

步骤4. 利用公式(9)计算参数A，公式(1)~(5)计算海鸥迁移最佳位置方向 $M_s\left(t\right)$ 以及 $D_s\left(t\right)$ ；

步骤5. 采用随机森林策略，利用公式(10)以及(11)进行海鸥攻击位置变化，得到 $P_s\left(t\right)$ ；计算 $P_s\left(t\right)$ 适应值，利用式(13)保留适应值较高的个体；

步骤6. 判断是否到达迭代停止条件，如果未到达，则返回执行步骤3~5；

步骤7. 停止迭代，输出最优适应值以及其对应最优解 $X_{best}$ 。

以上步骤对应具体流程如图2所示。

Figure 2. RFSOA specific process

图2. RFSOA具体流程

4. 实验与结果分析

4.1. 无约束函数测试

仿真实验的计算机环境为：Windows11，CPU 2.70GHz处理器，8 GB内存，应用python对算法编码。

为了验证RFSOA的性能优劣，选择7个Benchmark基准测试函数 来测试算法的性能，其中f1~f4为单峰函数，f5~f7为多峰函数，具体信息列于表1中。以粒子群算法PSO，遗传算法GA，基于非线性惯性权重的海鸥优化算法I-SOA作为对比算法。RFSOA的种群规模设置40，问题维度为30，算法的迭代次数为500。将所有算法均独立运行30次，以消除偶然因素的影响，取解均值及标准差进行对比，如表2所示。

Table 1. Benchmark functions

表1. Benchmark基准测试函数

Table 2. Comparison with other algorithm tests

表2. 与其他算法测试对比

由表2数据可以得到，在维度30的情况下，RFSOA在对7个Benchmark函数的测试中展示出来的总体效果较好。相比于标准SOA，改进后的RFSOA所寻得的最优解及稳定性均有较大提升，更加接近理论最优。同时由测试结果可以看出，RFSOA针对测试函数所展示出来的效果也明显优于参与对比的PSO、GA及I-SOA。因此证明了改进后的RFSOA针对无约束优化函数的求解的确具有更好的效果。

4.2. 0-1背包问题测试

背包问题(Knapsack Problem, KP) [13] [14] 是由Markel和Hellman提出的一个经典的组合优化问题。0-1背包问题(0-1 knapsack problem, 0-1 KP)可以描述为：给定一个背包和n种物品，每个物品都有两个参数：重量和价值，背包有自己的限重，选择部分物品将其装入背包中，在满足背包限重的条件下，使得装入的物品价值最高。

设共有n种物品， $i\left(1\le i\le n\right)$ 号物品的价值与重量分别为 $v_i$ 和 $w_i$ ，背包的重量限制为C，其中， $v_i$ 、 $w_i$ 与C均为正数。令 $X=\left[x_1,x_2,\cdots ,x_n\right]\in {\left\{0,1\right\}}^n$ 表示0-1背包问题的一个潜在解向量，其中，当 $x_i=1$ 时，表示i号物品被装入背包中；当 $x_i=0$ 时，表示i号物品不装入背包。0-1KP的数学模型为：

$\max f\left(X\right)=\max {\displaystyle \underset{x=1}{\overset{n}{\sum }}{v}_i{x}_i}$ (14)

$\text{s}\text{.t}\text{.}{\displaystyle \underset{i=1}{\overset{n}{\sum }}{w}_i{x}_i}\le C$ (15)

在上述模型中，任意一个n维的0-1向量都是0-1KP的一个潜在解，当其满足约束条件(15)式时，才能称为0-1KP的一个可行解。

利用引入随机森林思想的海鸥优化算法(RFSOA)对0-1KP进行求解，测试数据以及对比数据均来源于文献 [15] ，同样将算法的种群规模设置为30，最大迭代次数设置为200，算法独立运行次数为20。

由表3测试结果可以看出，RFSOA针对0-1KP问题具有较好的求解效果，针对文献所给测试数据，其寻优效果达到100%。对于较高维度的kp4、kp5以及kp6三组数据，RFSOA获得的最优解相比于BSOA以及BCSA也展示出了较明显的优势，相比于标准SOA，其最优解及平均解提升最高达到了16.1%和20.6%。因此证明RFSOA针对带有约束的优化问题求解也具有一定提升效果。

Table 3. Comparison of test results of algorithms on 0-1KP problems

表3. 算法在0-1KP问题上测试结果对比

5. 结束语

为了克服标准SOA存在的容易早熟、算法性能过于依赖参数以及解的精确度较低等缺陷，本文提出了一种融合随机森林策略的海鸥优化算法(RFSOA)，通过引入非线性参数、随机森林策略以及高斯随机游走策略对SOA进行改进，从而更好的平衡算法对于搜索空间全局及局部的探索。针对Benchmark函数以及0-1KP的一系列测试实验表明，改进后的RFSOA在对函数以及实际应用问题进行求解时，可以有效地解决算法过早陷入局部最优值的缺陷，从而找到更具有优越性的解，同时算法鲁棒性得到了很大提升，证明了RFSOA的有效性。

在未来的工作中，仍需进一步提升SOA的性能，并利用SOA对更为复杂的实际应用进行研究，扩展其应用范围。