引用本文
屈迟文, 彭小宁. 信息共享的记忆被囊群算法. 模式识别与人工智能, 2021,34(7): 605-618
QU Chiwen, PENG Xiaoning. Memory Tunicate Swarm Algorithm with Information Sharing. PATTERN RECOGNITION AND ARTIFICIAL INTELLIGENCE, 2021,34(7): 605-618.  
Doi: 10.16451/j.cnki.issn1003-6059.202107003
Permissions
Copyright©2021, 《模式识别与人工智能》编辑部
《模式识别与人工智能》编辑部
信息共享的记忆被囊群算法
屈迟文1,2, 彭小宁1,3
1.湖南师范大学 数学与统计学院 长沙 410081
2.湖南师范大学 计算与随机数学教育部重点实验室 长沙 410081
3.湖南师范大学 医学院 长沙 410081
通讯作者:

彭小宁, 博士,教授,主要研究方向为遗传算法开发与运用、肿瘤基因组数据挖掘.E-mail: pxiaoning@hunnu.edu.cn.

作者简介:

屈迟文,博士研究生,副教授,主要研究方向为智能计算、统计学.E-mail: quchiwen@163.com.

收稿日期: 2021-01-13 修回日期: 2021-04-20 接受日期: 2021-04-20
资助项目: 国家自然科学基金项目(No.81472860)、湖南省重点研发计划项目(No.2020DK2002)资助
摘要

针对基本被囊群算法求解精度较低、收敛速度较慢、容易陷入局部最优的缺陷,提出信息共享的记忆被囊群算法.首先,将整个种群分为执行信息共享搜索和喷气推进搜索两个子群,引入动态自适应调整策略,用于平衡算法的全局开拓能力和局部开发能力.然后,在执行信息共享搜索模式时,部分个体向同伴所在领域相互获取信息,实现种群个体之间信息的充分交流与共享.另一部分个体引入历史最优位置,用于引导学习,增强算法搜索的有效性.在20个基准测试函数上的实验表明,文中算法的收敛速度、求解精度、鲁棒性等都较优.

关键词: 被囊群算法; 信息共享; 记忆搜索行为; 搜索精度
中图分类号:TP 182; TP 391
Memory Tunicate Swarm Algorithm with Information Sharing
QU Chiwen1,2, PENG Xiaoning1,3
1. School of Mathematics and Statistics, Hunan Normal University, Changsha 410081
2. Key Laboratory of Computing and Stochastic Mathematics, Ministry of Education, Hunan Normal University, Changsha 410081
3. School of Medicine, Hunan Normal University, Changsha 410081
Corresponding author:
PENG Xiaoning, Ph.D., professor. His research interests include development and application of genetic algorithm and data mining of tumor genome.

About Author:
QU Chiwen,Ph.D. candidate, associate professor. His research interests include intelligent computing and statistics.

Fund:National Natural Science Foundation of China(No.81472860), Key Research and Development Project of Hunan Province(No.2020DK2002)
Abstract

Aiming at the problems of low accuracy, slow convergence speed and easily falling into local optimum of the tunicate swarm algorithm(TSA), a memory tunicate swarm algorithm with information sharing is proposed. Firstly, a dynamic self-adaptive adjustment strategy is adopted to divide the population into two sub-groups dynamically, including information sharing search and jet propulsion search, to balance the global development capability and local development capability of TSA. Then, some tunicate individuals are selected randomly to acquire information from the peers to realize the sufficient information exchange and sharing among tunicate individuals in the information sharing search mode. For another group of individuals, historical optimal locations are introduced to guide learning and thus the effectiveness of the algorithm search is enhanced. Experimental results on 20 benchmark functions show that the proposed algorithm is evidently superior in convergence rate, solution accuracy and robustness.

Key words: Tunicate Swarm Algorithm; Information Sharing; Memory Search Behavior; Searching Precision

本文责任编委 何清

Recommended by Associate Editor HE Qing

优化问题一直是科学研究与工程实践、人工智能、管理决策等领域的研究热点.随着生产规模和科学技术的发展, 优化问题变得越来越复杂.传统精确求解法能求得问题域的精确解, 但算法的复杂度过大, 只适用于求解问题规模较小的领域.同时, 在解决优化问题时需要问题本身连续、可导, 对于多峰、强非线性和动态变化问题不具备全局优化的能力[1].

近年来, 基于生物系统的元启发式算法得到工业界和学术界的广泛关注.学者们从群体智能出发, 提出许多算法, 如粒子群算法(Particle Swarm Opti-mization, PSO)[2]、差分进化算法(Differential Evolu-tional, DE)[3]、布谷鸟算法(Cuckoo Search, CS)[4]、水波算法[5]等.之后, 学者们提出群体智能优化算法.例如, 根据乌鸦的智能行为提出的乌鸦搜索算法(Crow Search Algorithm, CSA)[6]、模拟灰狼群体捕猎行为的灰狼优化算法(Grey Wolf Optimization, GWO)[7]、教与学算法(Teaching-Learning-Based Optimization, TLBO)[8]、共生生物搜索算法[9]、鲸鱼优化算法[10]、原子搜索算法[11]、鹰栖优化算法[12]、樽海鞘群算法(Salp Swarm Algorithm, SSA)[13]等.

基于群体的智能算法具有深入探索搜索空间和返回全局最优解的能力, 在解决实际优化问题方面具有一定的优势.然而, 上述大多数算法的搜索机制相对较单一, 难以解决高维搜索问题.同时, 单一搜索模式具有很强的耦合性, 很难实现全局搜索和局部搜索间的有效协调.另外, 个体空间分布结构对系统整体计算具有调节作用, 这种单一模式的隐式结构关系不利于算法对计算过程的主动控制.因此, 此类架构的群体智能优化算法在求解复杂优化问题时容易出现过早收敛.

Kaur等[14]模拟被囊动物的群体觅食行为, 提出被囊群算法(Tunicate Swarm Algorithm, TSA).由于TSA基于无梯度的优化技术, 实现简单, 在寻优过程中具有较强的开发能力, 现已成功运用于求解函数优化问题及其它工程应用领域, 并取得良好效果.

TSA与其它智能优化算法一样, 单一模式的搜索方式使被囊动物的觅食活动缺乏机动性和灵活性, 难以跳出局部最优, 算法搜索精度不高.实际上, 自然界中的被囊动物通过自身周围的神经末梢感知水流的变化和同伴的发光, 实现极强的集群行为.TSA采用直接向全局最优值聚集的方式搜索食物, 导致算法的整体搜索不充分, 没有充分利用被囊动物在群体搜索食物时的共享信息, 降低算法的搜索精度和收敛速度.因此, 本文提出信息共享的记忆被囊群算法(Memory TSA with Information Sharing, IS-MTSA).被囊动物在搜索食物过程中通过相互学习, 实现被囊动物个体之间信息的充分交流与共享, 提高算法的全局开拓能力.同时, 通过引入个体的历史最优位置引导搜索, 增强算法搜索的有效性.采用动态自适应调整策略, 动态调节执行信息共享搜索和喷气推进搜索两种策略的个体数量比例, 使算法在迭代初期有较多的个体进行全局搜索, 加速算法收敛到全局最优位置区域.在迭代后期, 进入局部搜索的个体数量增多, 增强最优值附近的局部开发能力.多搜索策略使算法在求解高维复杂问题时具有更多的选择方案, 提高算法性能.

1 被囊群算法

被囊群算法[14]是一种元启发式算法, 模拟被囊动物的喷气推进行为和群体行为.喷气推进行为主要利用自身的重力、深海中的水流平流、个体之间的相互作用力, 实现个体之间搜索冲突避免, 同时, 也具有向最优个体移动的能力.喷气推进行为主要由3部分组成:搜索个体冲突避免, 保持接近最佳搜索个体, 向最佳个体的位置移动.群体行为主要为更新搜索个体最优解的位置, 通过被囊动物周围的神经感知水流的变化和同伴的发光确定同伴位置, 共同向目标食物源位置聚集, 达到群体觅食的目的.TSA采用喷气推进行为和群体行为这两种策略, 更真实地模拟海洋中被囊动物群体觅食行为, 达到算法实现简单、跳出局部最优能力强、寻优精度高的目的.TSA具体流程如图1所示.

图1 TSA流程图[14]Fig.1 Flowchart of TSA[14]

1.1 喷气推进行为

皮囊动物在进行喷气推进前, 需要避免搜索个体之间的冲突.为了避免个体冲突, 计算新的位置向量:

其中:G表示重力, 计算方式由文献[15]给出; M表示搜索个体之间的社会力量,

Pmin、Pmax为社交活动的最小值和最大值, c1为[0, 1]内的随机数.

在避免邻居之间的冲突后, 搜索个体朝着最佳邻居的方向发展, 此时需要计算搜索个体与食物源之间的距离.第t次迭代时第i个个体与食物来源之间的距离为

其中, rand为满足[0, 1]均匀分布的随机数, 为第t次迭代时种群食物来源位置, 即当前种群最优个体位置, 为第t次迭代时种群第i个皮囊个体位置.

搜索个体向最佳食物源位置移动, 即

其中, 为第t次迭代时种群食物来源位置, A为个体避免冲突计算的位置向量, 为当前第i个个体与食物来源之间的距离.

1.2 群体行为

在避免冲突、计算个体与食物源位置距离后, 皮囊个体采用群体行为向食物源聚集.为了从数学上模拟被囊动物的群体行为, 定义被囊动物的群体行为:

其中, 表示上一代被囊个体相对于食物源更新后的位置, c1表示[0, 1]内的随机数.

2 信息共享的记忆被囊群算法
2.1 信息共享搜索策略

TSA是仅依照被囊动物喷气推进与群体聚齐的生活习性而建立的群体智能搜索算法.在搜索食物过程中, 被囊动物个体以当前位置为中心, 在当前最优位置(食物源位置)与当前位置的差值构建的扇形区域内进行随机搜索, 未考虑被囊动物行为中的其它智能行为.此种单一模式的搜索方式使被囊动物的觅食活动缺乏机动性和灵活性, 难以跳出局部最优, 导致算法的搜索精度不高.实际上, 自然界中的被囊动物属于无脊椎动物, 相关研究表明, 该类动物除了表现为很强的集群行为以外, 还具有一定的免疫记忆能力与相互学习能力[16, 17].

TSA采用式(1)和式(2)的方式直接向全局最优值聚集, 导致算法的整体搜索不充分, 未充分利用被囊群体在合作搜索食物时的共享信息, 降低算法的搜索精度和收敛速度.本文采用信息共享搜索策略, 实现对领域信息的充分搜索.搜索方式为

其中:r是满足(0, 1)内均匀分布的随机数; J∈ [0, 1]表示基于概率的变量, 确定种群中的个体采用何种信息共享方式, 为了使种群中的个体能以同等概率选择每种领域搜索方式, J取值为1/3; α 表示领域学习系数; 表示点乘; levy(· )表示满足levy分布的随机数.由于levy分布积分较困难, 文献[16]证明可采用Mantegana算法实现等价计算, 即

其中, u、 μ 表示[0, 1]内的随机数, β 表示常数.

在式(3)的第1部分, 被囊动物的同伴自由搜索周边领域, 并引导个体向同伴方向搜索; 第2部分搜索个体充分探索自身周围的领域空间; 第3部分引导个体向共享区域进行搜索, 获得新解.该策略的核心思想是采用不同交流算子的个体之间进行信息交换以增加种群的多样性, 充分利用各自的领域信息.此外, 该共享策略使算法在整个优化搜索过程中展现更丰富的随机行为, 避免算法陷入局部最优.

图2为二维搜索空间中信息共享搜索模式的示意图.

图2 个体在二维空间中不同搜索模式的示意图
(a)同伴领域搜索模式 (b)自身领域空间搜索模式 (c)共享区域搜索模式Fig.2 Different search modes of individuals in 2D search space
(a)Peer domain search mode (b)Self-domain space search mode (c)Shared area search mode

2.2 记忆搜索策略

被囊动物在群体觅食过程中具有一定的记忆能力, 因此它们除了向领域中的个体学习以外, 还可以以一定的概率向其它个体历史最优位置领域进行搜索, 以加强对个体历史位置的充分搜索.搜索方式

其中, rand()表示[0, 1]内均匀分布的随机数, 表示个体j在第t次迭代时的记忆值.

2.3 子群数量的动态调节

在改进的被囊群优化算法中, 部分被囊个体执行喷气推进模式, 部分个体采用信息共享搜索模式, 如何做到合理分配、使种群中的个体执行相应的搜索模式是本文算法的一个关键问题.在迭代初期, 被囊群体中的大多数个体执行信息共享搜索方式, 提高算法的全局开拓能力, 避免陷入局部最优; 在迭代后期, 大多数个体执行喷气推进模式, 增强算法的局部搜索能力, 平衡算法局部开发与全局开拓能力.为了有效执行该方案, 本文引入动态自适应调节策略, 使种群中执行信息共享搜索模式的数量随迭代次数的增加自适应地减少, 而执行喷气推进模式的个体数量自适应地增加.设每次迭代中执行信息共享机制的数量

其中, t表示当前迭代次数, Tmax表示最大迭代次数, N表示种群数量, k∈ (0, 1)表示控制系数, 避免算法在迭代初期执行信息共享策略和迭代后期执行喷气推进模式的数量偏高、实现算法的局部开发和全局开拓能力的均衡.

selectnumber的取值在迭代过程中的动态变化如图3所示.由图可看出:在进化初期, selectnumber取值较大, 执行信息共享机制个体较多; 随着迭代次数的增大, selectnumber取值逐渐减小, 执行喷气推进模式的个体逐渐增多.因此, selectnumber取值确保本文算法在迭代前期能保持较好的全局开拓能力, 在迭代后期, 加强局部开拓能力, 在整体上提高算法的搜索精度和收敛速度.

图3 selectnumber在迭代过程中的取值Fig.3 Values of selectnumberin iterative process

2.4 算法步骤

算法 ISMTSA

初始化 种群x

参数设置 种群规模N, 最大迭代次数Tmax,

选择信息共享方式的控制参数J,

数量控制系数k等

计算种群中每个个体的适应度值fit(xi), 记录种群中最优个体位置positionsbest及其适应度值scorebest

记录每个个体的记忆位置memi=xi, fit(memi)=

fit(xi)

t=0

while t< Tmax

for i=1:N

对个体xi进行越界处理

计算个体更新后的适应度值fit(xi)

if fit(xi)< scorebest

scorebest=fit(xi)

positionsbest=xi

end if

if fit(xi)< fit(memi)

fit(memi)=fit(xi)

memi=xi

end if

end for

根据式(6)计算信息共享与记忆搜索的个体的数

量selectnum

for i=1:selectnum%执行信息共享与记忆搜索

p=rand(0, 1)

if rand()< 0.2 %执行记忆搜索策略

xit= xit+rand()· (me mjt- xit), j≠ i

else%执行信息共享搜索策略

if p< J

xit= xit+0.01( xjt⊗ levy(β )- xit)

else if p< (1-J)

xit= xit+α ( xjt- xit⊗ levy(β ))

else

xit= xit+α ( xjt- xit)⊗ levy(β )

end if

end if

end for

for i=selectnum+1:N %执行TSA

执行喷气推进行为

执行群体行为

end for

t=t+1

end while

输出最优被囊个体positionsbest, 适应度值scorebest

3 实验及结果分析
3.1 测试基准函数和测试平台

仿真实验在操作系统为windows 7, CPU为Intel(R) Core(TM)i5-7400(4核), 内存为8 GB, 主频为3.0 GHz的计算机上实现, 程序采用Matlab 2016b编写.

为了验证算法性能, 本文从文献[17]、文献[18]中选择20个基准测试函数作为实验对象.测试函数具体如下.

搜索区间为[-100, 100], 理论最优值为0.

搜索区间为[-10, 10], 理论最优值为0.

搜索区间为[-100, 100], 理论最优值为0.

搜索区间为[-30, 30], 理论最优值为0.

搜索区间为[-100, 100], 理论最优值为0.

搜索区间为[-1.28, 1.28], 理论最优值为0.

搜索区间为[-500, 500], 理论最优值为-418.9829n.

搜索区间为[-5.12, 5.12], 理论最优值为0.

搜索区间为[-32, 32], 理论最优值为0.

搜索区间为[-600, 600], 理论最优值为0.

搜索区间为[-50, 50], 理论最优值为0.

搜索区间为[-50, 50], 理论最优值为0.

搜索区间为[-5, 5], 理论最优值为0.000 307 5.

搜索区间为[-5, 5], 理论最优值为-1.031 629.

搜索区间为[-5, 10; 0, 15], 理论最优值为0.398.

搜索区间为[-2, 2], 理论最优值为3.

搜索区间为[0, 1], 理论最优值为-3.862 8.

搜索区间为[0, 1], 理论最优值为-3.32.

搜索区间为[0, 10], 理论最优值为-10.153 2.

搜索区间为[0, 10], 理论最优值为-10.402 9.

在这20个基准测试函数中: f1~f6为单峰高维函数, 用于测试算法的寻优精度; f7~f12为多峰高维函数, 具有多个局部极值点, 用于测试算法的全局搜索性能; f13~f20为多峰低维函数, 绝大多数函数具有强烈的震荡特征, 局部最优值的数量随函数维数的不同而不同.f1~f12的测试维度为30, 100, 200; f13、 f19、 f20的测试维度为4; f14~f16的测试维度为2; f17的测试维度为3; f18的测试维度为6.由于测试函数集具有代表性和多样性, 因此可客观、公平、全面地评价算法的寻优性能.

3.2 实验结果对比

为了对比算法性能, 选取如下对比算法:PSO[2]、DE[3]、CS[4]、CSA[6]、GWO[7]、TLBO[8]、SSA[13]、TSA.

为了对比的合理性和公平性, 各算法的种群规模N=30.对比算法的参数值来自于相应的参考文献.PSO的学习率c1=1.494 45, 学习率c2=1.494 45, 惯性权重 =0.729.DE的交叉概率pCR=0.2, 最小比例因子β min=0.2, 最大比例因子β max=0.8.CS中鸟窝被发现概率pa=0.25.CSA中记忆搜索AP=0.2, 飞行步长fl=2.TLBO中TF 值随机选择为1或2.TSA中社交活动的最小值Pmin=1, 最大值Pmax=4.在ISMTSA中, 确定种群中的个体采用何种信息共享方式的控制概率J=1/3, 执行信息共享策略子群数量的控制系数k =0.9, 社交活动的最小值Pmin=1, 最大值Pmax=4.

同时, 对于每个测试函数, 迭代次数为500次, 每种算法均独立运行30次.

单峰高维函数在30维时的测试结果如表1所示, 表中黑体数字为最优结果.由表可看出, ISMTSA的最优值、平均值和最差值都最优.此外, ISMTSA对6个函数获得的标准差最小, 说明算法的鲁棒性最强.

表1 各算法在f1f6函数上的测试结果 Table 1 Test results of different algorithms on f1f6

多峰高维函数在30维时的测试结果如表2所示, 表中黑体数字为最优结果.由表可看出, 对于f7f9、 f11f12 , ISMTSA在最优值、平均值、最差值和标准差上都达到最优值.对于f10, ISMTSA和TLBO都获得全局最优理想值.

表2 各算法在f7f12函数上的测试结果 Table 2 Test results of different algorithms on f7f12

多峰低维函数(D< 30)的测试结果如表3所示, 表中黑体数字为最优结果.由表可看出, 在最优值上, ISMTSA都搜索到理论最优值, 性能全面优于TSA.对于f13、 f19、 f20, ISMTSA在平均搜索精度、最差值、标准差上都达到最优值.对于f14~f17, ISMTSA的最优值、平均值和最差值都达到全局最优理想值.对于f18, ISMTSA的平均搜索精度仅次于DE, 说明DE适合于求解此类问题.

表3 各算法在f13f20函数上的测试结果 Table 3 Test results of different algorithms on f13f20

各算法求解部分函数的收敛曲线如图4所示.由图可看出, 相比其它方法, ISMTSA的收敛速度和精度都达到最优, 这进一步说明改进策略的有效性和可行性.

图4 各算法在12个函数上的收敛曲线对比Fig.4 Comparison of convergence curves of different algorithms on 12 functions

3.3 高维函数上的搜索性能

为了验证ISMTSA在高维情况下的搜索性能, 对f1~f12分别进行100维、200维的独立测试.对于每个测试函数, 各算法的参数与3.2节一致.每种算法均独立执行30次, 实验结果如表4和表5所示, 表中黑体数字表示最优结果.

表4 各算法在100维函数上的测试结果 Table 4 Text results of different algorithms on 100-dimensional functions
表5 各算法在200维函数上的测试结果 Table 5 Text results of different algorithms on 200-dimensional functions

由表4和表5可看出, 除f8和f10之外, 无论是求解100维还是200维问题, ISMTSA获得的最优值、平均值、最差值、方差都最优.对于f8和f10, ISMTSA和TLBO的搜索结果一致, 都获得全局最优理想值.同时, ISMTSA无论对低维函数(D≤ 100)的搜索, 还是对高维函数的搜索, 搜索结果都非常接近.这些都说明ISMTSA对于高维函数的寻优具有良好性能.

3.4 非参数统计分析

为了更好地评价算法, 确定ISMTSA与其它算法的寻优效果是否具有显著性, 在 0.05显著性水平下进行Wilcoxon非参数检验.低维(30维及以下)Wilcoxon检验结果如表6所示.

表6 各算法的Wilcoxon秩和检验的统计结果 Table 6 Statistical results of Wilcoxon rank sum test of different algorithms

在表6中, ★表示ISMTSA相对对比算法具有显著性, ◇表示ISMTSA相对对比算法无明显差异.

其中显著性水平p< 0.05被认为是针对零假设的充分证据.

由表6可看出, 对比DE、GWO、PSO、TSA, 所有函数的p< 0.05, 说明ISMTSA与这四种算法性能对比是显著的.对比CS、CSA、SSA、TLBO, 分别有19、19、17、18个函数的p< 0.05.从统计学的角度分析出ISMTSA的寻优性能显著优于对比算法的性能.

3.5 参数敏感性分析

在ISMTSA中, 执行信息共享搜索模式的数量随迭代次数的增加自适应减少, 而执行喷气推进模式的个体数量却自适应增加, 在算法的迭代前期能保持较好的全局开拓能力, 在迭代后期, 局部开拓能力加强, 从整体上提高算法的搜索精度和收敛速度.因此, 执行信息共享策略的子群数量的控制系数k对算法的搜索结果具有较大影响.

本文选取k=0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 分析k对算法性能的影响.其余参数与3.2节的ISMTSA参数保持一致.每个测试函数在k不同时独立运行30次.

k不同时ISMTSA求解各函数值的结果如表7所示, 表中黑体数字表示最优结果.

表7 k不同时ISMTSA解得的函数值 Table 7 Values of functions by ISMTSA with different k

由表7可看出, 当k=0.9时, 获得平均最优值的数量分别为15个, 多于取其它值的个数.因此, 本文取k=0.9较合理.

为了研究领域学习系数α 对算法的影响, 选取f4、 f6、 f7、 f8、 f11、 f13、 f14作为测试函数.这7个函数中单峰高维函数3个, 多峰高维函数2个, 多峰低维函数2个.实验中α =0.005, 0.01, 0.05, 0.1, 0.5.其余参数保持相同, 独立运行30次.α 不同时, ISMTSA求解函数值的结果如表8所示.

表8 α 不同时ISMTSA解得的函数值 Table 8 Values of functions by ISMTSA with different α

由表8可看出, 当α =0.01时, 获得平均最优值的数量分别为5个, 多于取其它值的个数.因此, 本文取α =0.01作为领域学习系数值.

3.6 时间复杂度分析

时间复杂度是反映算法性能的关键指标之一, 直接体现算法执行效果的优劣.在TSA中:设种群规模为N, 问题的维度为d, 产生一个随机数的时间为ω 1, 求解该测试函数的适应度值为f(d), 则TSA在初始化种群阶段的时间复杂度为

T1=O(N(dω 1+f(d)))=O(d+f(d)).

进入迭代阶段后, 总的迭代次数为Tmax, 在喷气推进阶段, 计算每维M、G、A和PD的时间分别设为ω 2、ω 3、ω 4、ω 5, 执行式(1)所需时间为ω 6, 则喷气推进的时间复杂度为

T2=O(Nd(ω 2+ω 3+ω 4+ω 5+ω 6))=O(d).

在群体行为阶段, 设执行式(2)所需要时间为ω 7, 则群体行为阶段的时间复杂度为

T3=O(Nd(ω 7))=O(d).

在边界处理和更新种群个体位置阶段, 设每维边界处理的时间为ω 8, 计算个体适应度值的时间为f(d), 替换最优个体的时间为ω 9, 则执行该阶段的时间复杂度为

T4=O(N(dω 8+dω 9+f(d))=O(d+f(d)).

综上所述, TSA总的时间复杂度为

T(d)=T1+Tmax(T2+T3+T4)=O(d+f(d)).

对于ISMTSA, 种群规模、求解问题的维度、适应度值的求解方式都与TSA一致, 因此, ISMTSA初始阶段的时间复杂度为

T1'=O(d+f(d)).

进入迭代阶段后, 设由式(6)计算信息共享与记忆搜索的个体数量selectnum的时间为σ 1.在执行信息共享与记忆搜索策略时, 按照式(4)计算每维满足levy分布的随机数时间为σ 2, 执行式(5)记忆搜索策略时间为σ 3, 执行式(3)记忆搜索策略时间为σ 4, 此阶段的时间复杂度为

T2'=O(σ 1+0.2selectnumσ 3d+ (1-0.2)selectnumd(σ 2+σ 4))=O(d).

剩余的N-selectnum个体执行TSA的喷气推进行为和群体行为操作相同, 时间复杂度为

T3'=O(d).

在边界处理和更新种群个体位置阶段时间复杂度与TSA一致, 因此, 执行该阶段的时间复杂度为

T4'=T4=O(d+f(d)).

综上所述, ISMTSA总的时间复杂度为

T'(d)=T1'+Tmax(T2'+T3'+T4')=O(d+f(d)).

ISMTSA与TSA的时间复杂度相同.为了更直观对比ISMTSA和TSA的时间复杂度, 采用ISMTSA和TSA, 在相同的测试环境下, 测试5个基准函数, 每个基准函数独立运行30次, 计算平均耗时, 结果如表9所示.

表9 各算法在不同维度时的平均耗时对比 Table 9 Comparison of average consumption time of different algorithms with different dimensions s

由表9可看出, 在测试规模较小的函数时, ISMTSA平均耗时长于TSA, 但随着测试维度的增加, 平均耗时与TSA逐渐保持一致.由于增加执行信息共享与记忆搜索策略时的个体数量的计算时间及产生levy分布的随机数的时间, 当求解问题规模较小时, 此部分耗时所占比例相对较高, 但随着测试维度的增加, 该部分耗时所占比例逐渐减少.由此进一步验证ISMTSA在求解大规模问题上的优势.

4 结束语

针对被囊群算法在喷气推进和群体游走环节对历史信息和领域信息探索不充分, 导致算法搜索精度较低、容易陷入局部最优的问题, 本文提出信息共享的记忆被囊群算法(ISMTSA), 通过被囊动物个体之间相互学习, 实现整个被囊个体之间信息的充分交流与共享.引入个体历史最优位置引导搜索, 充分利用整个群体内优势位置的优良基因, 增加算法搜索的有效性和收敛速度.动态自适应调节执行喷气推进模式和执行信息共享搜索模式的个体数量比例, 更好地平衡算法的全局开拓能力和局部开发能力.在20个基准测试函数上的对比分析表明, ISMT-SA在搜索精度、收敛速度和稳定性等方面都具有较强的竞争力和优越性.今后考虑将ISMTSA用于解决更多的实际问题, 特别是在多目标优化问题、图像匹配及聚类分析等领域.此外, 可将信息共享机制与其它元启发式算法结合, 进一步测试其性能.

参考文献
[1] MAO K, PAN Q K, PANG X F, et al. A Novel Lagrangian Relaxation Approach for a Hybrid Flowshop Scheduling Problem in the Steelmaking-Continuous Casting Process. European Journal of Ope-rational Research, 2014, 236(1): 51-60. [本文引用:1]
[2] LENNEDY J, EBERHART R. Particle Swarm Optimization // Proc of the International Conference on Neural Networks. Washington, USA: IEEE, 1995, IV: 1942-1948. [本文引用:2]
[3] STORN R, PRICE K. Differential Evolution-A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces. Journal of Global Optimization, 1997, 11(4): 341-359. [本文引用:2]
[4] RAJABIOUN R. Cuckoo Optimization Algorithm. Applied Soft Computing, 2011, 11(8): 5508-5518. [本文引用:2]
[5] ZHENG Y J. Water Wave Optimization: A New Nature-Inspired Metaheuristic. Computers and Operations Research, 2015, 55: 1-11. [本文引用:1]
[6] ASKARZADEH A. A Novel Metaheuristic Method for Solving Constrained Engineering Optimization Problems: Crow Search Algorithm. Computers and Structures, 2016, 169: 1-12. [本文引用:2]
[7] MIRJALILI S, MIRJALILI S M, LEWIS A. Grey Wolf Optimizer. Advances in Engineering Software, 2014, 69: 46-61. [本文引用:2]
[8] RAO R V, SAVSANI V J, VAKHARIA D P. Teaching-Learning-Based Optimization: An Optimization Method for Continuous Non-linear Large Scale Problems. Information Sciences, 2012, 183(1): 1-15. [本文引用:2]
[9] CHENG M Y, PRAYOGO D. Symbiotic Organisms Search: A New Metaheuristic Optimization Algorithm. Computers and Structures, 2014, 139: 98-112. [本文引用:1]
[10] MIRJALILI S, LEWIS A. The Whale Optimization Algorithm. Advances in Engineering Software, 2016, 95: 51-67. [本文引用:1]
[11] ZHAO W G, WANG L Y, ZHANG Z X. A Novel Atom Search Optimization for Dispersion Coefficient Estimation in Groundwater. Future Generation Computer Systems, 2019, 91: 601-610. [本文引用:1]
[12] KHAN A T, SENIOR S L, STANIMIROVIC P S, et al. Model-Free Optimization Using Eagle Perching Optimizer[C/OL]. [2020-12-26]. https://arxiv.org/pdf/1807.02754.pdf. [本文引用:1]
[13] MIRJALILI S, GANDOMI A H, MIRJALILI S Z, et al. Salp Swarm Algorithm: A Bio-inspired Optimizer for Engineering Design Problems. Advances in Engineering Software, 2017, 114: 163-191. [本文引用:2]
[14] KAUR S, AWASTHI L K, SANGAL A L, et al. Tunicate Swarm Algorithm: A New Bio-inspired Based Metaheuristic Paradigm for Global Optimization[C/OL]. [2020-12-26]. http://doi.org/10.1016/j.engappai.2020.103541. [本文引用:2]
[15] TSENG L Y, CHEN C. Multiple Trajectory Search for Large Scale Global Optimization // Proc of the IEEE Congress on Evolutionary Computation. Washington, USA: IEEE, 2008: 3052-3059. [本文引用:1]
[16] SUN J J, WANG L L, YANG C Y, et al. An Ancient BCR-Like Signaling Promotes ICP Production and Hemocyte Phagocytosis in Oyster. iScience, 2020. 23(2). DOI: DOI:10.1016/j.isci.2020.100834. [本文引用:2]
[17] YANG X S. Nature-Inspired Metaheuristic Algorithms. 2nd Edition. Beckington, UK: Luniver Press, 2010: 11-16. [本文引用:2]
[18] TANG K, YAO X, SUGANTHAN P N, et al. Benchmark Functions for the CEC'2008 Special Session and Competition on Large Scale Global Optimization[C/OL]. [2020-12-26]. https://sci2s.ugr.es/sites/default/files/files/TematicWebSites/EAMHCO/Tech.Report.CEC2008.LSGO.pdf. [本文引用:1]