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

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