基于环论的改进猴群算法求有界背包问题  

Ring Theory-Based Improved Monkey Algorithm for Bounded Knapsack Problem

作　　者：肖颜 潘大志[1,2] 冯世强[1] XIAO Yan;PAN Da-zhi;FENG Shi-qiang(College of Mathematics and Information,China West Normal University,Nanchong 637009,China;Institute of Computing Method and Application Software,China West Normal University,Nanchong 637009,China)

机构地区：[1]西华师范大学数学与信息学院,四川南充637009 [2]西华师范大学计算方法与应用研究所,四川南充637009

出　　处：《数学的实践与认识》2021年第13期166-174,共9页Mathematics in Practice and Theory

基　　金：国家自然科学基金(11871059);四川省教育厅自然科学基金(18ZA0469);西华师范大学英才科研基金(17YC385);西华师范大学校级科研团队(CXTD2015-4);西华师范大学校级创新创业训练计划项目(cxcy2020149)。

摘　　要：有界背包问题(bounded knapsack problem,BKP)是经典的NP-hard问题,为利用猴群算法(MA)求解此类背包问题,主要提出一种基于环论的改进猴群算法(Ring Theory-Based Improved Monkey Algorithm,RTIMA).该算法可减少计算过程中参数的调整,增强算法的稳定性.RTIMA针对BKP问题本身的结构特点,首先采用自然数编码方式对MA进行编码处理,并对不可行解进行修复与优化处理,以保证算法的求解效果,同时加快算法的收敛速度;然后将环理论应用到爬过程中,对爬过程进行改进,以减少参数的调整,降低时间复杂度;最后,将信息共享机制、扰动机制应用到翻过程中,确保猴群之间相互进行信息交流,以增加解的多样性,从而避免陷入局部最优的趋势.通过与其他算法的计算结果进行比较分析,RTIMA算法效果更好,性能更优.The bounded knapsack problem(BKP)is a classic NP-hard problem.In order to use the monkey algorithm(MA)to solve this type of knapsack problem,this paper mainly proposes an improved monkey algorithm based on ring theory(Ring Theory-Based Improved Monkey Algorithm,RTIMA).This algorithm can reduce the adjustment of parameters in the calculation process and enhance the stability of the algorithm.According to the structural characteristics of the BKP problem itself,RTIMA first uses the natural number encoding method to encode the MA and solves the infeasible solution.Perform repair and optimization processing to ensure the solution effect of the algorithm and accelerate the convergence speed of the algorithm;then apply the ring theory to the climbing process and improve the climbing process to reduce the adjustment of parameters and reduce the time complexity;finally,the information sharing mechanism and disturbance mechanism are applied to the translation process to ensure that the monkeys exchange information with each other to increase the diversity of solutions,thereby avoiding the tendency to fall into the local optimum.By comparing and analyzing the calculation results of other algorithms,RTIMA The algorithm is better and the performance is better.

关 键 词：猴群算法 环论 有界背包问题 信息共享机制 扰动机制 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]