融合涡流搜索和差分策略的教学优化算法

李子扬，刘宗堡

(东北石油大学 地球科学学院，黑龙江 大庆 163318)

0 引 言

优化技术是一种以数学为基础，用于求解各种工程问题最优解或满意解的应用技术。美国工程院院士何毓琦教授指出：“任何控制与决策问题本质上均可归结为优化问题，优化是一个光彩夺目的研究领域”。对于很多工程优化问题，由于目标函数的特殊性质(如高维、多峰、不可微分)，精确的解析方法往往是不可行的。因此各种群智能、仿生智能、进化计算等优化模型应运而生并得以快速发展。然而各种智能优化算法都有其自身的优势和局限性，任何优化算法都不可能适用于所有优化问题。一般而言，待优化的问题不同，算法的参数设置也不相同，优化算法的控制参数越多，就越不便于使用。

因此，面对实际问题时算法参数的具体选择，是各类智能优化算法都面临的一个问题。2011年，通过模拟教师授课的教学行为，文献[1-2]提出了教学优化算法(teaching-learning-based optimization，TLBO)。该算法是目前少数没有自身个性参数的优化模型(种群规模、变量个数等共性参数除外)之一，自提出之后即受到了国内外学者的广泛关注，同时在各类工程优化中也获得了成功应用。

在TLBO的改进方面，文献[3]提出了基于可变种群的寻优方案，目的是减少原始TLBO的计算成本。文献[4]提出了融合全局交叉策略的改进方案，可有效改善探索和开发之间的平衡。文献[5]提出了一种融合模糊推理的TLBO，该方案可在全局探索和局部开发之间自适应选择。文献[6]提出了一种称为动态对立学习的TLBO，它采用一种新的动态对立学习策略来克服早熟收敛。文献[7]提出了采用多个种群的TLBO，在教师阶段，将种群划分为几个子种群，子群平均位置和全局最优位置之间的方向信息将引导相应子种群向着高质量区域移动，不同子群之间的信息交换可有效阻止早熟收敛。

为降低早熟收敛，文献[8]引入了交叉概率，此外，在教师阶段和学生阶段分别引入了八种和四种新的变异策略，以增强算法的探索和开发能力。文献[9]在TLBO中引入了两个新阶段，即自我反馈学习阶段以及变异和交叉阶段，使算法保持良好的探索和开发能力。文献[10]利用自适应指数分布的惯性权重，改变位置更新方程；此外，应用logistic映射生成一个均匀分布的种群，以提高初始种群的质量。TLBO已广泛用于医学诊断、优化调度、车间调度、系统辨识、工程设计、图像处理等众多领域。

在TLBO现有的改进方案中，融合其他经典策略的改进方案相对较少，然而这类融合其他经典策略的改进方案可以实现优势互补。

鉴于此，该文提出一种融合涡流搜索、差分进化策略的改进方案，其中涡流搜索用于教师个体的自寻优，而差分策略用于教师阶段和学生阶段所有个体的调整更新。改进后的算法没有增加个性参数，从而使算法仍然具有很好的适用性。复杂函数极值优化的仿真结果表明，改进后的算法不仅明显优于原算法，也优于其他同类对比算法。

1 改进方案涉及的优化算法

1.1 教学优化算法

教学优化算法的灵感来源于教师向学生传授知识的教学过程。不失一般性，以极小值优化为例，教学优化算法包括以下两个阶段。

(1)教师阶段。

设为第

t

步迭代种群平均值，为第

t

步迭代最优个体(教师)，将

T

看作全班学生新的均值，可得两均值之差，如式(1)：Difference_Mean=

r

(-

T

)

(1)

其中，

T

=round[1+rand(0,1)]∈{1,2}，

r

是区间(0,1)内均匀分布的随机数。按式(2)计算与对应的new,。若new,优于，则=new,，否则保持不变。new,=+Difference_Mean

(2)

(2)学生阶段。

每个学生个体随机选择学习目标。假设个体随机选择个体≠，首先按式(3)计算新解new,，然后按贪婪选择决定是否保留该解。最后，若满足终止条件则终止，否则返回教师阶段。

(3)

1.2 涡流搜索算法

(1)产生初始解。

在涡流搜索算法(vortex search，VS)中，通过以搜索空间中心点为中心的球型高斯分布随机产生初始解(0)={,,…,}。球形高斯分布的初始标准差可按下式计算。

(4)

其中，upperlimit和lowerlimit分别为搜索空间的上下边界，

σ

可看作涡流外环初始半径。

(2)当前解的更新。

用最好的候选解∈(0)替换初始解，并将其作为半径

σ

的内环中心，产生新的候选解集(1)，若最好解∈(1)好于迄今为止的最好解，则更新最好解。再将最好解作为缩减半径后的第三个环中心，重复上述过程直至满足终止条件，如图1所示。

图1 涡流算法的搜索过程

(3)半径缩减方法。

在涡流算法中，每步迭代按如下逆不完全伽马函数缩减半径的值。

(5)

其中，

λ

>0

.

1为随机变量，

a

>0为分辨率参数。

每步迭代涡流半径按式(6)缩减。

σ

=

σ

λ

γ

(

λ

,

a

-

t/

MaxItr)

(6)

其中，

a

=1，

t

为当前步数，MaxItr为限定步数。

1.3 差分进化算法

目前，差分进化(differential evolution，DE)算法中的变异方案存在多种版本，下面以文献[20]中提出的DE/rand/1/bin方案为例，给出DE的实施步骤。

(1)参数及种群初始化。

DE的控制参数包括：种群规模NP，变量个数

D

及范围，缩放因子

F

，交叉概率CR。所有个体均初始化为搜索空间内均匀分布的随机数，置当前代数为

t

=1。

(2)生成变异向量。

计算所有个体目标函数值，根据式(7)为每个个体生成变异向量。

(

t

+1)=(

t

)+

F

[(

t

)-(

t

)]

(7)

其中，

i

,

r

,

r

,

r

∈{1,2,…,NP}为随机选择且互不相同的个体序号。

(3)交叉操作。

对变异向量(

t

+1)，生成试探向量(

t

+1)=[(

t

+1),…,(

t

+1)]，其中：

(8)

其中，rand为在(0,1)均匀分布的随机数，rand{1,2,…,}为按均匀分布在{1,2,…,

D

}中随机选取的一个整数。

(4)选择操作。

比较(

t

+1)和(

t

)的目标函数值，按贪婪选择方法替换当前个体。(

t

+1)=

(9)

若满足终止条件则终止；否则置

t

=

t

+1，转(2)。

2 改进的教学优化算法

2.1 实施改进的基本思路

关于TLBO的两个核心阶段，在教师阶段，学生向教师学习，而教师自身不能进行有效的学习；在学生阶段，学生之间采用偏向式学习(即先对比两个体优劣，再使劣者向优者学习)，这种学习方式容易降低种群多样性，从而使算法有早熟收敛的倾向。

在TLBO中，作为当前最优解的教师具有优化路标的作用，有必要增加“教师自学”环节使其实施自寻优。而对于单解寻优，涡流搜索显然是一种可行方案。因此，在TLBO中融合VS，将其应用于教师的自寻优，是该文采用的第一种改进策略。在TLBO的教师阶段和学生阶段，将体现不同个体之间信息共享的差分策略融合到个体的更新中，同时在学生阶段采用轮盘赌策略，以便增加优良个体的更新机会，是该文采用的第二种改进策略。综上，改进后的TLBO每步迭代分为三个阶段：教师自学；向教师学；学生互学。

2.2 改进算法的实现方法

为便于描述，将改进后的教学优化算法简称为ITLBO(improved TLBO)，其实现方法如下所述。

(1)种群规模设置及初始化。

改进后的算法没有增加新的个性控制参数，但对于共性参数，增加了1个用于涡流搜索的候选解数。换言之，ITLBO包括两个种群；用于教师自学(涡流搜索)的种群NP，用于教学阶段的种群NP。为增强算法的实用性，经过多次重复实验，该文建议NP=2NP。实际使用时，令种群规模为NP，则NP=NP/3，NP=2NP/3。因此，与TLBO比较，ITLBO的控制参数没有增加，且初始化时，只需要随机初始化种群NP。对于初始化后的种群(0)={,,…,NP}，计算目标函数值，确定最优个体。

(2)教师自学阶段。

令涡流中心=，以为中心，按高斯分布产生NP个候选解。高斯分布的一般形式如式(10)：

(10)

(3)向教师学阶段。

该阶段在标准TLBO教师阶段的基础上，增加了差分策略，同时为降低计算复杂度，对于每个候选解，只随机更新1个维度。

对于个体(

i

=1,2,…,NP)，设为第

t

步迭代种群NP的平均值，=为第

t

步迭代最优个体(教师)，将看作种群NP的新均值，先置new,=，再按式(11)修正new,。new,(

d

)=(

d

)+rand((

d

)-(

d

))+rands(

X

(

d

)-

X

(

d

))

(11)

其中，

T

∈{1,2}；rand∈(0,1),rands∈(-1,1)为均匀分布的随机数；

j

∈{1,2,…,NP}且

j

≠

i

；

d

∈{1,2,…,

D

}。个体

j

和维度

d

均随机产生。最后，按贪婪选择策略实现当前个体的更新。

(4)学生互学阶段。

该阶段也将在个体的更新式中融入差分变异策略。为降低计算复杂度，对于每个候选解，也只随机更新1个维度。同时，为提高优良个体的更新机会，本阶段采用了轮盘赌策略。以极小值优化为例，根据目标函数构造的适应度函数如式(12)：

Fitness=(1+

F

)

(12)

其中，

F

为目标函数值。按式(13)构造种群中每个候选解的选择概率。

(13)

首先，依概率选择个体，然后实施更新，直到选出并更新NP个个体为止。具体方法如下：对所选个体(

i

=1,2,…,NP)，首先置new,=，在集合{1,…,

i

-1,

i

+1,…, NP}中随机选择

j

,

k

且

j

≠

k

，然后按式(14)计算

X

new,。

(14)

其中，rand∈(0,1),rands∈(-1,1)为均匀分布的随机数；

d

∈{1,2,…,

D

}为随机产生的整数。最后，按贪婪选择策略实现当前个体的更新。

(5)算法终止条件。

终止条件通常可以设置为精度阈值或目标函数计算次数。对于精度阈值，当最优解的目标值达到预先设置的某种精度要求后，终止算法的运行；对于目标函数计算次数，当且仅当目标函数计算次数小于预先设定的最大次数时，算法继续运行，否则不论优化结果是否满足精度要求，都将终止运行。该文选择目标函数计算次数作为终止条件。

不选择迭代步数作为终止条件的原因是，不同优化算法在1步迭代内个体的寻优次数一般会有不同，因此，单纯考察相同迭代步数下的寻优结果有失公平。然而每次寻优都会通过计算目标函数值来考察其效果，因此，考察相同目标函数计算次数下的优化结果才是相对公平的。

3 对比实验

为充分展示ITLBO的优势，本节将针对标准函数极值优化问题设计实验，同时与普通TLBO、自适应差分进化(adaptive DE，ADE)、人工蜂群(artificial bee colony，ABC)、粒子群(particle swarm optimization，PSO)、涡流搜索VS五种算法进行综合对比。所有实验均在64 位操作系统，主频2.40 GHz，内存8.0 GB的笔记本电脑上采用Matlab2017B实现。

3.1 测试函数

采用文献[24]提供的10个测试函数为仿真对象，它们均通过若干基本函数复合而成，基本特性如表1所示。所有函数均为极小值优化。

表1 10个测试函数的基本特性

对于函数

F

～

F

，

F

～

F

，变量个数分别取

D

=5, 10, 15, 20；对于函数

F

，

F

，变量个数分别取

D

=10, 15, 20。所有函数的变量取值范围均为[-100, 100]。由于不同算法在一次迭代中目标函数的计算次数可能不同，因此对比相同迭代步数下的优化结果有失公平，而对比相同目标函数计算次数下的优化结果更为合理。根据文献[24]，当

D

=5, 10, 15, 20时，限定目标函数的计算次数分别为5×10,10,3×10,10。

3.2 参数设置

种群规模：在种群规模NP的每步迭代中，关于目标函数计算次数，TLBO为2NP次，ITLBO为NP/3+4NP/3=5NP/3次，ADE、ABC、PSO、VS均为NP次。为保证ITLBO和TLBO每步迭代与其他算法有相同的目标函数计算次数，该文将ITLBO和TLBO的种群规模分别设置为0.6NP和0

.

5NP，此时ITLBO和TLBO的目标函数计算次数均为NP。该文取NP=100。其他参数：ABC的观察阈值limit=100，采蜜蜂和跟踪蜂均为0

.

5NP。ADE的缩放因子

F

随迭代步数从0

.

2线性增加到0

.

9，交叉概率CR根据种群方差自适应确定。PSO的

c

=

c

=2，惯性因子从0

.

9随迭代步数线性下降到0

.

4。VS没有需要设置的个性参数。

3.3 优化结果对比

对于表1中的10个函数，考虑到不同维度的情况，共有38种组合。对于每种组合分别采用6种算法独立优化30次，然后对比30次优化结果的平均误差。具体结果如表2所示。

表2 30次优化结果的平均误差对比

续表2

从实验结果可以看出，没有一种算法适合所有类型(单峰、基本、混合、复合)的函数。以ITLBO获得最好结果的函数为例，当

D

=5时为3个基本函数(

F

、

F

、

F

)，1个复合函数(

F

)；当

D

=10时为1个基本函数(

F

)，2个复合函数(

F

、

F

)；当

D

=15时为1个基本函数(

F

)，1个混合函数(

F

)，3个复合函数(

F

、

F

、

F

)；当

D

=20时为2个基本函数(

F

、

F

)，2个复合函数(

F

、

F

)，如表2中粗体数字所示。总体看来，对于不同类型和维度的38种组合，ITLBO获得最好结果的组合数是最多的。

3.4 实验结果分析

综合以上实验结果，ITLBO的整体优化性能不仅明显高于TLBO，同时也高于其他对比算法，从而验证了改进方案的有效性及可行性。对于实验结果，给出如下分析：

第一，ITLBO在原始TLBO的算法结构中，通过增加最优个体自寻优策略，突出了最优个体的“路标”指引作用。对于最优个体而言，其自寻优过程应侧重于局部开发，这恰好是寻优后期涡流搜索的长处。因此该策略有助于提升算法的性能，这与表2中的实验结果是一致的。

第二，ITLBO在原始TLBO的教学阶段中，通过引入差分和轮盘赌策略，实现了经典算法的优势互补。在个体更新中引入差分策略，可以通过融入随机选取的候选解的差分向量，实现信息共享，并提高种群的多样性，抑制早熟收敛。而引入轮盘赌策略可以提升高质量候选解获得进化的机会。这是使ITLBO获得高性能的重要原因。从算法结构看，ITLBO与ABC有相似之处，其阶段2(向教师学)相当于ABC的采蜜蜂搜索，而阶段3(学生互学)相当于ABC的跟踪蜂搜索。这就是对比实验结果中ITLBO和ABC的搜索性能较为相似的原因。

第三，ITLBO在提升优化性能的同时，由于引入了其他算子，提高了算法的计算复杂度。对于绝大多数群智能优化算法，优化性能和优化效率二者是不能兼得的。性能的提升一般都会伴随着计算效率的降低，这与“无免费午餐定理”的结论是一致的。

4 结束语

提出了一种改进的教学优化算法，改进算法增加了基于涡流搜索的最优个体自寻优过程，同时在个体更新中增加了差分策略和轮盘赌选择机制，目的在于通过优势互补提升原算法的优化性能。采用不同维度的10个标准测试函数考察了改进算法的优化性能，通过与原始教学优化算法及其他同类算法的优化结果对比，验证了改进算法的优势。仿真实验及实际应用结果揭示出该改进方案能够有效提升目前教学优化算法的寻优能力。