• 理论与算法 •

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

1. 1. 河北地质大学 信息工程学院，石家庄 050031
2. 全北国立大学 电子信息工程学院，韩国 全州 54896
• 出版日期:2018-12-01 发布日期:2018-12-07

### Solving Set-Union Knapsack Problem by Modified Teaching-Learning-Based Optimization Algorithm

WU Congcong, HE Yichao, ZHAO Jianli

1. 1. College of Information Engineering, Hebei GEO University, Shijiazhuang 050031, China
2. School of Electronics & Information Engineering, ChonBuk National University, Jeonju 54896, Korea
• Online:2018-12-01 Published:2018-12-07

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.