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

摘要

针对集合联盟背包问题(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问题的方法.