融合差异进化的混合算法求解多选择背包问题

Hybrid Algorithm Based on Individual Differential Evolution for Solving Multiple-choice Knapsack Problem

针对典型的组合优化问题——多选择背包问题(MCKP),提出了一种融合差异进化的混合算法(IDEHA)。算法按照适应度值将个体分为3个阶级,实施差异进化;通过设计一种有效的随机贪心修复策略,引入精英库进行协同寻优来加速算法收敛。通过对典型的多选择背包算例的求解并与其他算法的对比分析,基于融合差异进化的混合算法具有收敛速度快、求解精度高、稳定性和鲁棒性强等优点。

The multiple-choice knapsack problem(MCKP)is a kind of typical multi-constraint combinatorial optimization problem.In order to solve this kind of problem,a hybrid algorithm integrating differential evolution,named IDEHA,is proposed and designed.According to their fitness values,the proposed algorithm divides all the individuals into three classes to implement dif⁃ferential evolution.Through designing an effective random greedy repair strategy and introducing the elite database for collaborative optimization,the convergence of the proposed algorithm is speeded up.In comparison with the other algorithms through typical multi-choice knapsack examples,it is demonstrated that the proposed algorithm has the advantages of fast convergence speed,high solution accuracy,strong stability and robustness.