多维背包问题的新型人类学习优化算法  

Novel human learning optimization algorithm for multidimensional knapsack problem

作　　者：张翼鹏 刘勇[1] 马良[1] Zhang Yipeng;Liu Yong;Ma Liang(Management School,University of Shanghai for Science&Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机应用研究》2024年第12期3689-3700,共12页Application Research of Computers

基　　金：教育部人文社会科学研究青年基金资助项目(21YJC630087);上海市哲学社会科学规划课题(2019BGL014)。

摘　　要：针对目前算法求解多维背包时精度低、稳定性差、特别是无法有效求解超大规模算例等问题,提出一种新型人类学习优化算法。首先,基于认知心理学中的记忆理论,在基本人类学习算法中采用哈希函数表示人类在学习过程中的记忆行为,避免重复搜索,提高算法搜索群体多样性;其次,采用认知心理学中的对比认知理论对学习算子选择策略进行自适应调整;最后,采用变邻域搜索操作提升算法局部搜索能力。采用小规模、中等规模、大规模、超大规模共76个多维背包问题的标准测试数据集进行数值实验,并将新算法和二进制粒子群算法、遗传算法、人类学习算法以及融合学习心理学的人类学习算法进行比较。结果表明新算法能够有效求解四种规模算例。与其他算法相比,新算法具有更高的寻优精度和更好的稳定性。此外,对提出的三种优化策略进行分析,测试其对提高算法搜索性能的有效性。Aiming at the problems of low accuracy and poor stability of the current algorithms in solving multi-dimensional knapsacks,especially the inability to effectively solve super-large-scale arithmetic cases,this paper proposed a new type of human learning optimization algorithm.Firstly,the noval human learning algorithm used a hash function based on the memory theory in cognitive psychology to represent the memory behaviour of human beings in the learning process,avoiding repeated searches and improving the algorithm’s search group diversity.Secondly,the algorithm used the contrastive cognition theory from cognitive psychology to adaptively adjust the learning operator selection strategy.Finally,the algorithm used a variable neighborhood search operation to enhance the algorithm’s local search capability.This paper conducted numerical experiments using a standardized test dataset of a total of 76 multidimensional knapsack problems that covered small,medium,large,and very large scales.Experiments compared the new algorithm with binary particle swarm algorithms,genetic algorithms,human learning algorithms,and human learning algorithms that incorporated the psychology of learning.The results show that the new algorithm is able to solve the four scale instances efficiently.Compared with other algorithms,the new algorithm has higher accuracy in finding the optimum and better stability.In addition,this paper analyzed three proposed optimization strategies to test their effectiveness in improving the algorithm’s search performance.

关 键 词：人类学习优化算法 认知心理学 哈希函数 学习算子选择策略 多维背包问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]