改进的教与学优化算法求解集合联盟背包问题

摘要：

针对集合联盟背包问题(set-union knapsack problem,SUKP)难以使用确定性算法求解的情况,提出了一种快速求解SUKP问题的改进二进制教与学优化算法(modified binary teaching-learning-based optimization,MBTLBO).首先,给出了教与学优化算法的二进制编码方法;然后,针对求解SUKP问题中的候选解,提出改进的修复优化策略(modified SUKP greedy repairing and optimization algorithm,MS-GROA).该策略增加了修复后可行解的二次优化,从而提升了对SUKP问题的求解精度.另外为了克服教与学优化算法易早熟,求解精度低,后期收敛速度慢等弱点,在"教"阶段和"学"阶段引入差分算法的交叉算子,通过平衡算法的开发能力和勘探能力,避免算法过早陷入局部极值;在精英个体周围按正态分布进行自适应局部搜索,提高算法的收敛速度和求解精度.三类SUKP实例测试表明,MBTLBO算法具有较高的求解精度和更快的收敛速度,是有效求解SUKP问题的方法.

关键词：集合联盟背包问题(SUKP)、教与学优化算法(TLBO)、二进制编码、修复和优化策略、正态分布

所属期刊栏目：12

分类号：TP301.4(计算技术、计算机技术)

资助基金：The National Social Science Foundation of China under Grant No. 17BGL202;the Scientific Research Project of Colleges and Universities in Hebei Province under Grant No. ZD2016005;the Natural Sci-ence Foundation of Hebei Province under Grant No. F2016403055

在线出版日期：2019-01-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：2007-2020