Abstract:

Aiming at the set-union knapsack problem (SUKP) which is difficult to be solved by a deterministic algorithm, a modified binary teaching-learning-based optimization (MBTLBO) algorithm is proposed to quickly solve SUKP problems. First, a binary encoding method of teaching-learning-based optimization algorithm is presented. Second, for candidate solutions in solving SUKP, an improved repairing and optimization strategy MS-GROA (modified SUKP greedy repairing and optimization algorithm) is proposed, which can improve the accuracy of solving SUKP by the second optimization of the feasible solutions. Third, to balance global search and local exploration capabilities of the binary teaching-learning-based optimization algorithm, the crossover operator is introduced in the teaching phase and learning phase. Finally, local search around the elite individuals on the normal distribution is adopted to enhance the convergence speed and solution accuracy of MBTLBO. The experimental results in three kinds of SUKP instances show that the MBTLBO algorithm has a higher solution accuracy and faster convergence speed, which is an effective method for solving SUKP.

Key words: set-union knapsack problem (SUKP), teaching-learning-based optimization (TLBO), binary coding, repairing and optimization strategy, normal distribution

摘要：

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