信息迁移多任务优化共生生物搜索算法

doi:10.11772/j.issn.1001-9081.2022060896

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (7): 2237-2247.DOI: 10.11772/j.issn.1001-9081.2022060896

• 先进计算 • 上一篇

信息迁移多任务优化共生生物搜索算法

程美英¹^,²(), 钱乾²^,³, 熊伟清⁴

^1.湖州师范学院经济管理学院, 浙江湖州 313000
^2.浙江省教育信息化评价与应用研究中心(湖州师范学院), 浙江湖州 313000
^3.湖州师范学院教师教育学院, 浙江湖州 313000
^4.宁波大学商学院, 浙江宁波 315211

收稿日期:2022-06-21 修回日期:2022-08-22 接受日期:2022-08-24 发布日期:2022-09-22 出版日期:2023-07-10
通讯作者: 程美英
作者简介:程美英（1983—），女，安徽黄山人，副教授，博士，主要研究方向：群体智能优化；
钱乾（1983—），男，安徽芜湖人，讲师，硕士，主要研究方向：进化计算；
熊伟清（1966—），男，安徽合肥人，教授，硕士，主要研究方向：人工智能。
基金资助:
浙江省高等教育“十三五”第二批教学改革项目(jg20190652);国家自然科学基金资助项目(62102148)

Symbiotic organisms search algorithm for information transfer multi-task optimization

Meiying CHENG¹^,²(), Qian QIAN²^,³, Weiqing XIONG⁴

^1.School of Economics and Management，Huzhou University，Huzhou Zhejiang 313000，China
^2.Research Center of Education Information Evaluation and Application of Zhejiang Province （Huzhou University），Huzhou Zhejiang 313000，China
^3.School of Teacher Education，Huzhou University，Huzhou Zhejiang 313000，China
^4.Business School，Ningbo University，Ningbo Zhejiang 315211，China

Received:2022-06-21 Revised:2022-08-22 Accepted:2022-08-24 Online:2022-09-22 Published:2023-07-10
Contact: Meiying CHENG
About author:CHENG Meiying， born in 1983， Ph. D.， associate professor. Her research interests include swarm intelligence optimization.
QIAN Qian， born in 1983， M. S.， lecturer. His research interests include evolutionary computation.
XIONG Weiqing， born in 1966， M. S.， professor. His research interests include artificial intelligence.
Supported by:
the Second Batch of Teaching Reform Project of Higher Education during “the 13th Five Year Plan” in Zhejiang Province(jg20190652);National Natural Science Foundation of China(62102148)

摘要/Abstract

摘要：

针对现有共生生物搜索（SOS）算法只能求解单个任务，以及信息负迁移影响多任务优化（MTO）性能这两个难题，提出一个信息迁移多任务优化共生生物搜索（ITMTSOS）算法。首先基于多种群演化MTO框架，根据任务个数设置相应数量种群；然后各种群独立运行基本SOS算法，当某一种群连续若干代停滞进化时，引入个体自身最优经验和邻域最优个体以形成知识模块并将该模块迁移至该种群个体进化过程中；最后对ITMTSOS算法时间和空间复杂度进行分析。仿真实验结果表明，ITMTSOS算法同时求解多个不同形态高维函数时均能快速收敛至全局极值解0，与单任务SOS算法相比，平均运行时间最多缩短约25.25%；而在同时求解多维0/1背包问题和师生匹配问题时，所提算法在测试集weing1和weing7上的最优适应值与目前测试集公布的最优结果相比分别提高了22 767和22 602，师生最优匹配差和平均匹配差的绝对值分别下降了26和33，平均运行时间约缩短了7.69%。

关键词: 共生生物搜索算法, 多任务优化, 信息迁移, 多任务高维函数优化, 多任务二元离散优化

Abstract:

Aiming at the problems that Symbiotic Organisms Search （SOS） algorithm only can solve single tasks and negative information transfer affects Multi-Task Optimization （MTO） performance， an Information Transfer Multi-Task SOS （ITMTSOS） algorithm was proposed. Firstly， based on multi-population evolution framework MTO， multiple populations were set according to the number of tasks. Secondly， each population ran basic SOS algorithm independently， and by introducing individual itself optimal experience and neighborhood optimal individuals， the knowledge module containing the above two was formed and transferred to the process of individual evolution when a population stagnated for several consecutive generations. Finally， the time and space complexity of ITMTSOS was analyzed. Simulation results show that ITMTSOS converges rapidly to the global optimal solution 0 when resolving a batch of different shape high-dimensional functions， and the average running time is reduced around 25.25% when compared with single task SOS； when solving the multi-dimensional 0/1 knapsack problems and the teacher-student matching problems concurrently， the optimal fitnesses on weing1 and weing7 test sets are increased by 22 767 and 22 602 respectively compared with the current published optimal results， the absolute values of the optimal and the average matching difference of teacher-student matching problem are decreased by 26 and 33 respectively， and the average running time is reduced around 7.69%.

Key words: Symbiotic Organisms Search (SOS) algorithm, Multi-Task Optimization (MTO), information transfer, multi-task high-dimensional function optimization, multi-task binary discrete optimization

中图分类号:

TP18

程美英, 钱乾, 熊伟清. 信息迁移多任务优化共生生物搜索算法[J]. 计算机应用, 2023, 43(7): 2237-2247.

Meiying CHENG, Qian QIAN, Weiqing XIONG. Symbiotic organisms search algorithm for information transfer multi-task optimization[J]. Journal of Computer Applications, 2023, 43(7): 2237-2247.

图/表 20

图1 ITMTSOS算法依托框架和搜索空间设置示意图

Fig. 1 Schematic diagram of supporting framework and search space setting of ITMTSOS

图2 ITMTSOS算法信息迁移策略示意图

Fig. 2 Schematic diagram of information transfer in ITMTSOS

表1 MTO基准测试函数

Tab. 1 MTO benchmark functions

名称	表达式	简写	特征
Sum of Different Powers function	$∑ j = 1 D x j j + 1$	SD	单模态
Sum Squares function	$∑ j = 1 D j ⋅ x j 2$	SSF	单模态
Zakharov function	$∑ j = 1 D x j 2 + ∑ j = 1 D 0.5 j ⋅ x j 2 + ∑ j = 1 D 0.5 j ⋅ x j 4$	Z	单模态
Sphere function	$∑ j = 1 D x j 2$	S	单模态
Quartic	$∑ j = 1 D j ⋅ x j 4 + r a n d [0,1]$	Q	单模态
Generalized Griewank	$1 4 000 ∑ j = 1 D x j 2 - ∏ j = 1 D c o s z j / j + 1$	G	多模态
Ackley function	$20 + e - 20 e x p - 0.2 1 D ∑ j = 1 D z j 2 - e x p 1 D ∑ j = 1 D c o s (2 π z j), z = M A (x - O A)$	A	多模态
Rastrigin function	$10 + ∑ j = 1 D x j 2 - 10 c o s (2 π x j)$	R	多模态

表1 MTO基准测试函数

Tab. 1 MTO benchmark functions

名称	表达式	简写	特征
Sum of Different Powers function	$∑ j = 1 D x j j + 1$	SD	单模态
Sum Squares function	$∑ j = 1 D j ⋅ x j 2$	SSF	单模态
Zakharov function	$∑ j = 1 D x j 2 + ∑ j = 1 D 0.5 j ⋅ x j 2 + ∑ j = 1 D 0.5 j ⋅ x j 4$	Z	单模态
Sphere function	$∑ j = 1 D x j 2$	S	单模态
Quartic	$∑ j = 1 D j ⋅ x j 4 + r a n d [0,1]$	Q	单模态
Generalized Griewank	$1 4 000 ∑ j = 1 D x j 2 - ∏ j = 1 D c o s z j / j + 1$	G	多模态
Ackley function	$20 + e - 20 e x p - 0.2 1 D ∑ j = 1 D z j 2 - e x p 1 D ∑ j = 1 D c o s (2 π z j), z = M A (x - O A)$	A	多模态
Rastrigin function	$10 + ∑ j = 1 D x j 2 - 10 c o s (2 π x j)$	R	多模态

表2 SOSSA和ITMTSOS算法求解不同形态高维函数优化问题实验结果

Tab. 2 Experimental results for different shape high-dimensional functions by SOSSA and ITMTSOS

多任务实例	最优适应值	平均适应值
30SD	5.45E-05	0.018 1
30SSF	0.003 3	1.210 1
30Z	0.088 4	20.974 2
30S	0.002 1	0.201 7
30Q	0.000 0	0.270 0
30G	0.001 7	0.047 2
30A	0.024 5	1.250 4
30R	1.305 3	5.969 4
50SD	0.064 7	0.375 7
50SSF	0.016 0	5.894 2
50Z	11.311 9	149.824 5
50S	0.519 7	0.594 5
50Q	0.000 0	0.586 7
50G	0.013 0	0.076 8
50A	1.180 1	2.339 4
50R	3.676 9	12.376 3
100SD	8.257 7	75.907 6
100SSF	21.634 6	35.425 1
100Z	62.847 5	420.281 0
100S	6.812 6	18.636 7
100Q	0.602 6	0.695 1
100G	0.236 6	0.358 5
100A	3.013 0	6.904 1
100R	7.833 7	72.890 5
（30SD， 30SSF， 30Z）	（0， 0， 0）	（1.85E-59， 1.82E-14， 6.01E-21）
（50SD， 50SSF， 50Z）	（0， 0， 0）	（7.83E-30， 1.44E-8， 6.41E-19）
（100SD， 100SSF， 100Z）	（0， 0， 0）	（2.91E-79， 2.93E-21， 6.87E-19）
（30S， 30Q， 30G）	（0， 0， 0）	（5.62E-19， 6.67E-2， 0）
（50S， 50Q， 50G）	（0， 0， 0）	（6.31E-14， 0.357 1， 0）
（100S， 100Q， 100G）	（0， 0， 0）	（3.54E-10， 0.622 9， 3.58E-11）
（30S， 30A， 30R）	（0， 0， 0）	（3.19E-19， 1.42E-10， 0）
（50S， 50A， 50R）	（0， 0， 0）	（6.10E-17， 2.59E-7， 0）
（100S， 100A， 100R）	（0， 5.89E-16， 0）	（1.36E-15， 2.43E-9， 0）

图3 SOSSA与ITMTSOS算法求解30维不同形态函数平均收敛曲线

Fig. 3 Average convergence curves for 30-dimensional different shape functions solved by SOSSA and ITMTSOS

图4 SOSSA与ITMTSOS算法求解50维不同形态函数平均收敛曲线

Fig. 4 Average convergence curves for 50-dimensional different shape functions solved by SOSSA and ITMTSOS

图5 SOSSA与ITMTSOS算法求解100维不同形态函数平均收敛曲线

Fig. 5 Average convergence curves for 100-dimensional different shape functions solved by SOSSA and ITMTSOS

图6 SOSSA算法和ITMTSOS算法求解不同维度（SD，SSF，Z）平均运行时间

Fig. 6 Average running time for different dimensional （SD，SSF，Z） by SOSSA and ITMTSOS

图7 SOSSA和ITMTSOS算法求解不同维度（S，G，Q）平均运行时间

Fig. 7 Average running time for different dimensional （S，G，Q） by SOSSA and ITMTSOS

图8 SOSSA和ITMTSOS算法求解不同维度（S，A，R）平均运行时间

Fig. 8 Average running time for different dimensional （S，A，R） by SOSSA and ITMTSOS

表3 不同多任务优化算法求解多任务高维函数优化问题平均适应值对比

Tab. 3 Average fitness comparison of different algorithms in solving multi-task high-dimensional functions

多任务实例	ITMTSOS算法	MT-CPSO算法^［24］	IEPSOM算法^［26］
（30SD， 30SSF， 30Z）	（1.85E-59， 1.82E-14， 6.01E-21）	（8.27E-15， 2.77E-5， 7.99E-7）	（4.19E-23， 1.33E-7， 0.001）
（50SD， 50SSF， 50Z）	（7.83E-30， 1.44E-8， 6.41E-19）	（1.66E-18， 5.72E-5， 0.004 1）	（8.31E-19， 3.05E-5， 0.006 9）
（100SD，100SSF， 100Z）	（2.91E-79， 2.93E-21， 6.87E-19）	（3.56E-14， 0.001 1， 0.051 9）	（1.84E-15， 0.001 9， 0.023 9）
（30S， 30Q， 30G）	（5.62E-19， 6.67E-2， 0）	（2.80E-6， 0， 0）	（1.56E-16， 0， 1.04E-11）
（50S， 50Q， 50G）	（6.31E-14， 0.357 1， 0）	（3.39E-7， 0， 3.42E-15）	（2.75E-6， 0， 1.45E-5）
（100S， 100Q， 100G）	（3.54E-10， 0.622 9， 3.58E-11）	（3.40E-6， 0， 4.85E-11）	（8.22E-6， 0， 5.37E-12）
（30S， 30A， 30R）	（3.19E-19， 1.42E-10， 0）	（3.49E-7， 1.75E-9， 0）	（6.33E-53， 1.48E-8， 1.14E-14）
（50S， 50A， 50R）	（6.10E-17， 2.59E-7， 0）	（2.50E-8， 1.06E-9， 0）	（4.15E-46， 8.89E-6， 3.36E-8）
（100S， 100A， 100R）	（1.36E-15， 2.43E-9， 0）	（5.19E-15， 4.71E-7， 2.40E-10）	（9.81E-11， 5.14E-9， 2.96E-7）

图9 OA不同偏移时30S、50S、30R、50R平均收敛曲线

Fig. 9 Average convergence curves of 30S， 50S， 30R， 50R with different OA shift

图10 MKP/TSM编码方法

Fig. 10 Coding methods of MKP/TSM

图11 非法个体处理示意图

Fig. 11 Schematic diagram of illegal individual handling

表4 SOSSA和ITMTSOS算法求解MKP和TSM实验结果

Tab. 4 Experimental results for MKP and TSM by SOSSA and ITMTSOS

多任务实例	最优适应值	平均适应值	测试集公布最优结果
weing1	163 935	160 728	141 278
weing7	1 102 872	1 102 836	1 095 445
TSM	107	141	—
（weing1， weing7， TSM）	（164 045，1 118 047，81）	（164 045，111 7611，108）	—

图12 SOSSA和ITMTSOS算法求解（weing1， weing7， TSM）平均收敛曲线

Fig. 12 Average convergences curves for （weing1， weing7， TSM） solved by single-task SOSSA and multi-task ITMTSOS

图13 SOSSA和ITMTSOS算法求解（weing1，weing7，TSM）平均运行时间

Fig. 13 Average running time for （weing1，weing7，TSM） by SOSSA and ITMTSOS

图14 weing1第1个和第2个背包对应的0/1序列

Fig. 14 Zero/one sequences corresponding to the first and the second knapsacks of weing1

图15 weing7 第1个和第2个背包对应的0/1序列

Fig. 15 Zero/one sequences corresponding to the first and the second knapsacks of weing7

图16 TSM中两个不同教师所对应0/1序列

Fig. 16 Zero/one sequences corresponding to two teachers in TSM

参考文献 29

1	CHENG M Y， PRAYOGO D. Symbiotic organisms search： a new metaheuristic optimization algorithm［J］. Computers and Structures， 2014， 139： 98-112. 10.1016/j.compstruc.2014.03.007
2	王艳娇，马壮. 基于子种群拉伸操作的精英共生生物搜索算法［J］. 控制与决策， 2019， 34 （7）： 1355-1364. 10.13195/j.kzyjc.2017.1747
	WANG Y J， MA Z. Elite symbiotic organisms search algorithm based on subpopulation stretching operation［J］. Control and Decision， 2019， 34 （7）： 1355- 1364. 10.13195/j.kzyjc.2017.1747
3	MIAO F H， YAO L， ZHAO X J. Symbiotic organisms search algorithm using random walk and adaptive Cauchy mutation on the feature selection of sleep staging［J］. Expert Systems with Applications， 2021， 176： No.114887. 10.1016/j.eswa.2021.114887
4	NGUYEN-VAN S， NGUYEN K T， LUONG V H， et al. A novel hybrid differential evolution and symbiotic organisms search algorithm for size and shape optimization of truss structure under multiple frequency constraints［J］. Expert Systems with Applications， 2021， 184： No.115534. 10.1016/j.eswa.2021.115534
5	CHAKRABORTY F， ROY P K， NANDI D. A novel chaotic symbiotic organisms search optimization in multilevel image segmentation［J］. Soft Computing， 2021， 25 （10）： 6973-6998. 10.1007/s00500-021-05611-w
6	DUMAN S， LI J， WU L， et al. Symbiotic organisms search algorithm-based security-constrained AC-DC OPF regarding uncertainty of wind， PV and PEV systems［J］. Soft Computing， 2021， 25 （14）： 9389-9426. 10.1007/s00500-021-05764-8
7	秦旋，房子涵，张赵鑫. 混合共生生物搜索算法求解置换流水车间调度问题［J］. 浙江大学学报（工学版）， 2020， 54 （4）： 712-721. 10.3785/j.issn.1008-973X.2020.04.010
	QIN X， FANG Z H， ZHANG Z X. Hybrid symbiotic organisms search algorithm for permutation flow shop scheduling problem［J］. Journal of Zhejiang University （Engineering Science）， 2020， 54 （4）： 712-721. 10.3785/j.issn.1008-973X.2020.04.010
8	CHAKRABORTY F， ROY P K， NANDI D. Symbiotic organisms search optimization for multilevel image thresholding［J］. International Journal of Swarm Intelligence， 2020， 11 （2）： 31-61. 10.4018/ijsir.2020040103
9	GUPTA A， ONG Y S， FENG L. Multifactorial evolution： toward evolutionary multitasking［J］. IEEE Transactions on Evolutionary Computation， 2016， 20 （3）： 343-357. 10.1109/tevc.2015.2458037
10	ONG Y S， GUPTA A. Evolutionary multitasking： a computer science view of cognitive multitasking［J］. Cognitive Computation， 2016， 8 （2）： 125-142. 10.1007/s12559-016-9395-7
11	BAI L， LIN W， GUPTA A， et al. From multitask gradient descent to gradient-free evolutionary multitasking： a proof of faster convergence［J］. IEEE Transaction on Cybernetics， 2022， 52 （8）： 8561-8573. 10.1109/tcyb.2021.3052509
12	GUPTA A， ZHOU L， ONG Y S， et al. Half a dozen real-world application of evolutionary multitasking and more［J］. IEEE Computational Intelligence Magazine， 2022， 17 （2）： 49-66. 10.1109/mci.2022.3155332
13	FENG L， ZHOU L， GUPTA A， et al. Solving generalized vehicle routing problem with occasional drivers via evolutionary multitasking［J］. IEEE Transactions on Cybernetics， 2021， 51 （6）： 3171-3184. 10.1109/tcyb.2019.2955599
14	FENG L， HUNAG Y X， ZHOU L， et al. Explicit evolutionary multitasking for combinatorial optimization： a case study on capacitated vehicle routing problem［J］. IEEE Transactions on Cybernetics， 2021， 51 （6）： 3143-3156. 10.1109/tcyb.2019.2962865
15	GUPTA A， ONG Y S， DA B S， et al. Landscape synergy in evolutionary multitasking ［C］// Proceedings of the 2016 IEEE Congress on Evolutionary Computation. Piscataway： IEEE， 2016： 3076-3083. 10.1109/cec.2016.7744178
16	DA B S， ONG Y S， FENG L， et al. Evolutionary multitasking for single-objective continuous optimization： benchmark problems， performance metric and baseline results［EB/OL］. （2017-06-12）［2022-04-23］. . 10.1109/cec.2016.7743992
17	ZHOU L， FENG L， ZHONG J H， et al. A study of similarity measure between tasks for multifactorial evolutionary algorithm ［C］// Proceedings of the 2018 Genetic and Evolutionary Computation Conference Companion. New York： ACM， 2018： 229-230. 10.1145/3205651.3205736
18	SHEN F， LIU J， WU K. Evolutionary multitasking network reconstruction from time series with online parameter estimation［J］. Knowledge-Based Systems， 2021， 222： No.107019. 10.1016/j.knosys.2021.107019
19	THANG T B， DAO T C， LONG N H， et al. Parameter adaptation in multifactorial evolutionary algorithm for many-task optimization［J］. Memetic Computing， 2021， 13 （4）： 433-446. 10.1007/s12293-021-00347-4
20	CAI Y Q， PENG D M， LIU P Z， et al. Evolutionary multi-task optimization with hybrid knowledge transfer strategy［J］. Information Sciences， 2021， 580： 874-896. 10.1016/j.ins.2021.09.021
21	程美英，钱乾，倪志伟，等. 信息筛选多任务优化自组织迁移算法［J］. 计算机应用， 2021， 41 （6）： 1748-1755. 10.11772/j.issn.1001-9081.2020091390
	CHENG M Y， QIAN Q， NI Z W， et al. Self-organized migrating algorithm for multi-task optimization with information filter［J］. Journal of Computer Applications， 2021， 41 （6）： 1748-1755. 10.11772/j.issn.1001-9081.2020091390
22	程美英，钱乾，倪志伟，等. 基于虚拟多任务二元粒子群算法和分形维数的雾霾天气预测方法［J］. 系统科学与数学， 2018， 38 （5）： 623-637. 10.12341/jssms13406
	CHENG M Y， QIAN Q， NI Z W， et al. Virtual multitasking binary particle swarm optimization and fractal dimension for haze forecast［J］. Journal of Systems Science and Mathematical Science， 2018， 38 （5）： 623-637. 10.12341/jssms13406
23	GUPTA A， ONG Y S， FENG L， et al. Insights on transfer optimization： because experience is the best teacher［J］. IEEE Transactions on Emerging Topics in Computational Intelligence， 2018， 2 （1）： 51-64. 10.1109/tetci.2017.2769104
24	CHENG M Y， GUPTA A， ONG Y S， et al. Coevolutionary multitasking for concurrent global optimization： with case studies in complex engineering design［J］. Engineering Applications of Artificial Intelligence， 2017， 64： 13-24. 10.1016/j.engappai.2017.05.008
25	TAN K C， FENG L， JINAG M. Evolutionary transfer optimization — a new frontier in evolutionary computation research［J］. IEEE Computational Intelligence Magazine， 2021， 16 （1）： 22-33. 10.1109/mci.2020.3039066
26	程美英，钱乾，倪志伟，等. 信息交互多任务粒子群算法［J］. 模式识别与人工智能， 2019， 32 （5）： 385-397. 10.16451/j.cnki.issn1003-6059.201905001
	CHENG M Y， QIAN Q， NI Z W， et al. Information exchange particle swarm optimization for multitasking［J］. Pattern Recognition and Artificial Intelligence， 2019， 32 （5）： 385-397. 10.16451/j.cnki.issn1003-6059.201905001
27	程美英，熊伟清，严彬，等. 求解多维0/1背包问题的二元粒子群算法［J］. 系统仿真学报， 2009， 21 （18）： 5735- 5743.
	CHENG M Y， XIONG W Q， YAN B， et al. Binary PSO algorithm for multiple 0/1 knapsack problem［J］. Journal of System Simulation， 2009， 21 （18）： 5735- 5743.
28	CLARK R E. Antagonism between achievement and enjoyment in ATI studies［J］. Educational Psychologist， 1982， 17 （2）： 92- 101. 10.1080/00461528209529247
29	JAMES W B， GARDNER D L. Learning styles： implications for distance learning［J］. New Directions for Adult and Continuing Education， 1995， 1995 （67）： 19-31. 10.1002/ace.36719956705

[1]	胡中波, 王旭鹏. 求解测试用例自动生成问题的多因子回溯搜索优化算法[J]. 《计算机应用》唯一官方网站, 2023, 43(4): 1214-1219.
[2]	程美英, 钱乾, 倪志伟, 朱旭辉. 信息筛选多任务优化自组织迁移算法[J]. 计算机应用, 2021, 41(6): 1748-1755.
[3]	贾鹤鸣, 李瑶, 姜子超, 孙康健. 基于改进共生生物搜索算法的林火图像多阈值分割[J]. 计算机应用, 2021, 41(5): 1465-1470.

信息迁移多任务优化共生生物搜索算法

Symbiotic organisms search algorithm for information transfer multi-task optimization

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 20

参考文献 29

相关文章 3

编辑推荐

Metrics