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

来源：计算机科学与探索杂志2018年第12期北京时间：

作者：吴聪聪，贺毅朝，赵建立

单位：1. 河北地质大学 信息工程学院，石家庄 0500312. 全北国立大学 电子信息工程学院，韩国 全州 54896

摘要：针对集合联盟背包问题（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）,二进制编码,修复和优化策略,正态分布