具有振荡搜索和自适应突变的教与学优化算法

Improved TLBO with Oscillation Search and Adaptive Mutation

摘要: 为了克服标准教与学优化(TLBO)算法在求解高维问题中表现出的后期收敛速度慢、容易早熟的问题，提出了一种具有振荡搜索和自适应突变的改进教与学优化算法(ITLBOA)。该算法首先在“教”算子中引入二阶振荡搜索策略，期望在早期抑制粒子向最优粒子的过快收敛，而在后期使其具有较强的勘探能力，提高算法的解精度。其次，引入自适应突变，随着迭代的进行逐渐提高粒子的突变概率，并随机选择部分维度变异，赋予算法摆脱局部最优约束的能力。在5个标准Benchmark函数上的测试，结果表明该算法具有较好的全局搜索能力和解精度。选择8个UCI数据集上进行特征选择问题求解，ITLBOA获得的有效特征数目比TLBO平均减少了1.35个，最优适应度值下降了15.91个百分点。一系列的实验表明，ITLBOA不仅适合求解较高维度的函数优化问题，同样也能够高效求解组合优化问题。

Abstract: To overcome the weakness of slow convergence and easy precocity of teaching and learning based optimization (TLBO) in solving higher dimensional problems, an improved teaching and learning optimization algorithm with oscillatory search and adaptive mutation (ITLBOA) was proposed. Firstly, the second-order oscillation search strategy is introduced into the “teach” operator, which is expected to restrain the rapid convergence of individuals to the optimal individuals in the early stage, and make it have strong exploration ability and improve the solution accuracy of the algorithm in the later stage. Secondly, adaptive mutation is introduced to gradually improve the mutation probability of individuals with the progress of iteration, and some dimensional mutation is randomly selected to give the algorithm the ability to escape from local optimal in the later stage. Testing on 8 standard benchmark functions showed that ITLBOA has better global search ability and higer accuracy than TLBO. It was applied to the experiment of feature selection on 11 UCI data sets. The results showed that the number of effective features obtained by ITLBOA was reduced by 1.35 compared with TLBO, and the optimal fitness value was reduced by 15.91%. A series of experiments showed that ITLBOA is not only suitable for solving higher dimensional function optimization problems, but also can efficiently solve combinatorial optimization problems.

1. 引言

群智能 [1] [2] 算法利用种群内的协作及特定的进化机制，实现待求解问题解空间的启发式搜索。教与学优化(Teaching & Learning based optimization, TLBO) [3] [4] [5] 算法诞生于2010年，通过模拟教学班中的“教”和“学”两种行为，实现对问题的求解，是群智能算法中优秀代表之一。算法原理简单，参数较少且易实现，在多个领域得到了应用 [6] [7] [8] [9] [10] 。

由于TLBO的数学基础薄弱，在求解较高维度的问题时，后期往往容易陷入局部最优，收敛速度降低等问题 [4] 。为了克服这些弱点，提高算法的性能和效率，研究者们从不同的角度提出了各种策略对算法进行改进。文献 [11] 提出了一种相对精英教与学优化算法(OETLBO)该算法能够提高搜索全局最优解的效率，在算法后期能够较好地保持种群多样性。于坤杰等人 [12] 针对种群多样性下降过快的问题，提出了一种基于反馈的精英教与学优化算法(FETLBO)，该算法在“学”算子中增加了一种差生向教师反馈的机制，通过这种反馈来调整种群的多样性。文献 [13] 采用自适应教学因子并通过调节教师人数的方式提升TLBO的全局搜索能力，提高算法的性能。文献 [14] 提出了一种自主学习行为的教与学优化算法(SDTLBO)，在执行完标准TLBO算法之后，通过计算当前粒子与最优、最差粒子的距离自主完成学习，最后通过高斯搜索实现全局搜索以避免种群陷入局部最优的约束。针对TLBO在求解高维问题中出现的解精度低、收敛速度慢和容易陷入局部最优解的弱点，文献 [15] 提出了一种融合头脑风暴思想的改进教与学优化算法(ITLBOBSO)。在执行“教”算子中当前粒子与优秀粒子进行头脑风暴式学习，同时在该算子中引入柯西变异和一个与迭代次数关联的随机参数提高对新解的开发能力。

为了提高算法的性能，提出了一种引入二阶振荡搜索和粒子自适应突变的改进教与学优化算法。将当前粒子向教师粒子的学习曲线视为信号的振荡变化，将“教”算子修改为二阶振荡搜索。基于迭代次数产生概率，以此为基础使当前粒子或者部分维度突变，或者执行标准“学”算子。

2. 改进教与学优化算法

此处限于篇幅，TLBO算法的原理和执行流程不再给出，请参见文献 [3] 等。为了一致性，文中以X_i(t)标记种群内的粒子，X_g(t)标记当前最佳粒子，不再使用教师个体、学生个体的说法。

2.1. 算法早熟分析

由算法原理可知，TLBO采用优胜劣汰策略更新自身的状态，以保持较快的收敛速度。因为TLBO算法是一种模拟自然现象的智能算法，缺少严密的数学理论支持，所以还无法从数学的角度严格解释算法收敛性和收敛能力。基于马尔科夫链全局收敛证明的前提是算法种群数量足够多和进化时间足够长(甚至是无限长)的理想状态，所以说TLBO的设计本身存在一定缺陷的。任何一种改进机制只能是针对算法的收敛性进行改善，而并非保证算法的全局收敛。

影响算法提前早熟的主要原因之一是所求解问题的解空间分布。由于TLBO算法中种群的粒子数量有限，它们在解空间内的分布随机，对于较复杂的问题而言，当前优质解的前进方向不一定就是全局最优解的收敛方向。在单峰问题中下面两种情况就容易发生提前收敛。第一，最优解区域附近种群粒子适应度跨度变化较大；第二，代表最优解的粒子和次优解的粒子适应度相差较小。而在多峰问题中，如果解与解之间相距较远，也难以保证种群搜索能够扩展到全部最优区域。

在求解问题时，为了加快运算速度，采用的种群规模有限。随机生成粒子的初始状态，故种群对解空间的覆盖具有不确定性。在初始种群难以覆盖到全局最优解的情况下，有限迭代次数内，如果无法检索到最优解区域，则算法早熟是难以避免的。所以，为了改善算法的收敛性，通常采用提高种群的多样性和增加变异等机制使粒子跳出局部最优的约束，保持算法勘探和开发之间的平衡。

2.2. 引入二阶振荡的“教”算子

粒子X_i通过“教”算子向最优粒子X_g周围靠近，从而达到实现搜索解空间的目的。但是，标准“教”算子使粒子向最优个体周围收敛的速度较快，在单峰问题中表现较好，但是在多峰问题中，则容易使非最优粒子跳过可能存在新解的空间。将算法中粒子的搜索视为控制系统中的信号振荡，在“教”算子中引入一种二阶振荡因子 [16] ，抑制学生个体的过快收敛，实现对解空间的稳定搜索，新“教”算子如公式(1)所示。

$X_i\left(t+1\right)=\delta \times X_i\left(t\right)+ran{d}_1\times \left(X_g\left(t\right)-\beta \times X_m\left(t\right)\right)$ (1)

式中， $\beta =round\left(1+ran{d}_1\right)$ ，X_m为种群的平均值，rand1是(0,1)内服从正态分布的随机值。

$\delta =\{\begin{array}{l}\frac{\left(2\sqrt{ran{d}_2}-1\right)\times \left(1+ran{d}_2\right)}{ran{d}_2},t\le T_{\max }/2\\ \frac{\left(2\sqrt{ran{d}_2-1}\right)\times ran{d}_2}{ran{d}_2},t>T_{\max }/2\end{array}$

T_max为最大迭代次数，rand₂代表(0,1)内均匀分布的随机值。由式(1)可以看出，引入的参数δ可控制粒子自身状态对其下一代进化的影响。在早期，可加速粒子向最优粒子的靠近。而在后期，则较好的减缓靠近速度，维持种群的多样性。

2.3. 自适应部分维度突变

标准TLBO中，“学”算子赋予粒子一定的变异能力，期望维持种群多样性。但是，算法迭代后期，由于种群中的大部分粒子已经聚集在最优粒子的周围，状态非常相近，“学”算子已经很难将当前个体跳出当前解的约束。本文引入一种自适应非线性参数来控制当前粒子的突变概率和突变范围，以扩展该算法的开发新解的能力，突变概率由公式(2)计算获得。

$p=e^{5\times \left(t-MaxG\right)/t}/2$ (2)

该公式中，MaxG是最大迭代次数，t为当前迭代次数。可以看出，算法在进入迭代后期，该概率值将会上升，而在早期则具有较小的概率。

将“学”算子设定为，如果rand(0,1) < P，则随机选择当前个体 $X_i\left(t\right)$ 的多个维度进行重新初始化，待初始化的维度为 $L=\max \left\{1,\lceil D\times P\rceil \right\}$ (D为问题的维度)，否则执行标准“学”算子，即在种群内随机选择两个粒子，标记其中状态优的粒子为 $X_k\left(t\right)$ ，执行公式(3)。

$X_i\left(t+1\right)=X_i\left(t\right)+rand\times \left(X_k\left(t\right)-X_i\left(t\right)\right)$ (3)

2.4. 算法描述

算法1. 改进的教与学优化算法(Improved TLBO algorithm, ITLBOA)

输入：种群规模n，最大迭代次数等参数；

输出：最优粒子 $X_g\left(t\right)$ ；

步骤1. 在解空间内随机初始化种群POP；

步骤2. 计算个体的适应度值；

步骤3. 挑选当前迭代次数的最优粒子 $X_g\left(t\right)$ ；

步骤4. 当前粒子 $X_t\left(t\right)$ 依据公式(1)执行“教”算子；

步骤5. 根据公式(2)计算 $X_i\left(t\right)$ 的概率p。如果 $rand\in \left(0,1\right)<p$ 则随机选择其 $L=\max \left\{1,\lceil D\times P\rceil \right\}$ 个维度初始化，否则执行标准“学”算子。

步骤6. 满足结束条件，则算法终止。否则，goto步骤2。

3. 仿真实验1

为了验证ITLBOA算法的性能，基于python3.8编程，实验环境的硬件为cpu：intel i7，内存：16 G。测试函数列于表1，问题维度D = 50。挑选几个经典改进算法如：ETLBO [11] 、FETLBO [12] 、TLBO-RLS [13] 等参与对比。全部算法的种群规模设为30，迭代次数3000，算法其它参数参考相关文献。为了消除随机性的影响，所有算法均独立运行30次，然后对比适应度均值(mean)、方差(Std)和成功收敛时的迭代次数(iter)，数据列于表2。

Table 1. Benchmark functions

表1. 无约束测试函数

对表2进行分析可知，ITLBOA算法在函数f1、f2、f3上表现出的求解能力良好，无论是均值还是方差均优于参与对比的其它算法，且需要的迭代次数也是最少的。在函数f4的表现，ITLBOA在均值和解方差仅仅低于FETLBO算法，但也并非相差较多，而迭代次数的对比上则是所有算法中最少的。f5函数的解空间为多峰，搜索算法容易陷入局部最优，ITLBOA算法同样表现优秀，在参与对比的算法中表现优秀，仅仅在解均值项上劣于FETLBO。通过本实验表明，在连续型无约束函数上，ITLBOA算法是值得信赖的，收敛速度比较快，表现出了较好的解精度和稳定性。

Table 2. Comparison of results on unconstrained benchmark functions

表2. 无约束测试函数上的对比

4. 仿真实验2

将ITLBOA算法应用解决特征选择问题，以测试其求解约束优化问题的能力。将粒子X_i应用Sigmoid函数离散化处理。设 $X_i^j$ 代表i粒子的第j维向量，首先以式(4)计算Sigmoid值。

$sig\left(X_i^j\right)=1/\left(1+e^{-X_i^j}\right)$ (4)

依据式(5)将得到的sig值转换为对应的向量值。

$X_i^j=\{\begin{array}{l}1\\ 0\end{array}\begin{array}{c}\\ \end{array}\begin{array}{c},\\ ,\end{array}\begin{array}{c}rand\left(0,1\right)<sig\left(X_i^j\right)\\ otherwise\end{array}$ (5)

参考文献 [17] 的处理方法，应用基于特征聚类信息种群初始化策略，以提高TLBO特征选择时的性能。设置阈值λ，如果个体的某维大于或等于该阈值，则选择该维所对应的特征，否则，该特征被舍弃。根据公式(6) [17] [18] 对算法进行评价。

$ErrorRate=\frac{FP+FN}{TP+TN+FP+FN}$ (6)

其中，FP表示负样本被预测成正样本的个数，FN表示正样本被预测成负样本的个数，TP表示正样本被预测成正样本的个数，TN表述负样本被预测成负样本的个数。将ITLBOA算法与Relief、ReliefF、RF-MI [19] 、TLBO等方法在8个数据集上进行对比。ITLBOA的种群大小设为30，阈值λ = 0.4，所有算法的迭代次数均为200，8个UCI数据集信息列于表3，所有的算法均独立运行30次。

Table 3. Information of datasets

表3. 数据集信息

Table 4. Evaluation of average error rate and average characteristic number

表4. 算法的平均错误率和平均特征数

(a) wine 数据集 (b) WBCD数据集 (c) Libras数据集(d) VST数据集(e) Muskl数据集 (f) Spectf数据集

Figure 1. Convergence curve of the alogrithms on 6 datasets

图1. 算法在数据集上的收敛曲线

表4列出了参与对比的四个算法在多个数据集上的平均错误率和平均特征数。从表4中的数据可以看出，在所有的数据集上，本文提出的ITLBOA算法的平均错误率均是最小的，说明该算法在求解特征选择问题时，具有较高的解精度。在分析寻找的平均特征数上，获得的特征数明显比其它方法所得到的有效特征数少。在Wine、Muskl、WBCD、Spectf几个数据集上的表现与RF-MI基本上旗鼓相当，略优于该方法，但是要明显好于其它算法。在Libras数据集上，ITLBOA要劣于RF-MI方法，但是同样优于其它算法。

图1绘制了五个算法在6个数据集上的收敛曲线，X轴表示迭代次数，Y轴坐标表示适应度函数值。从图1中折线图趋势可以看出，随着迭代次数的增加，所有算法的适应度值均在逐渐降低，其中ITLBOA算法表现更为优秀。ITLBOA在6个数据集上搜索到相比于其他三种算法更优质的解。从图中可以看出，ITLBOA能够经过非常少的迭代次数就迅速收敛，收敛速度明显优于其它的算法。实验验证了ITLBOA在求解约束组合优化问题时，亦具有较高的解精度和摆脱局部最优的束缚能力。

5. 结论

提出了一种具有二阶振荡搜索和自适应突变的教与学优化算法。在“教”算子中引入二阶振荡机制，抑制个体向最优个体所在空间的收敛速度，加强其发现新解的能力。同时，结合自适应的突变机制，赋予个体在后期较强的变异概率，以摆脱局部最优的约束。最后一系列的实验表明，所提出的算法具有较好的解精度和鲁棒性，适合求解较高维度的组合优化优化和函数优化问题。教与学优化算法原理简单，参数较少，进一步将针对其收敛性能进行分析。结合传统演化算法原理，开拓新的应用领域也是主要的研究方向之一。

基金项目

河北省高等学校科学技术研究项目：网络舆情数值建模及其演化路径发掘关键技术研究(ZD2020344)。

NOTES

^*通讯作者。