基于新颖二进制人工蜂群算法求解带权集合覆盖问题

Novel binary artificial bee colony algorithm for solving weighted set covering problem

带权集合覆盖问题(WSCP)是一个著名的NP-hard问题。为了利用人工蜂群算法(ABC)高效求解带权集合覆盖问题,提出了一个新颖二进制ABC(记作nBABC)。在nBABC中,首先提出了随机学习和继承性相结合的全局进化算子,以提高算法的全局勘探能力。其次,基于动态调整策略提出了自适应随机取反算子,以维持勘探与开发的平衡。在借鉴近似算法的思想提出处理WSCP不可行解的修复算法WSCP-GRA和优化算法WSCP-GOA的基础上,利用nBABC给出了求解WSCP的一个新方法。为了验证nBABC求解WSCP的高效性,利用它求解OR-Library中45个WSCP实例,与多个算法的比较表明:nBABC能够求得所有实例的最优值,比已有求解WSCP的算法更具竞争力。

The weighted set covering problem(WSCP)is a famous NP-hard problem.In order to solve the WSCP efficiently by using artificial bee colony algorithm(ABC),this paper proposed a novel binary ABC(nBABC).In nBABC,it proposed a global evolution operator which combined random learning and inheritance to improve the global exploration ability of the algorithm.Secondly,based on the dynamic adjustment strategy,it proposed an adaptive random inversion operator to maintain the balance between exploration and development.Based on the idea of approximate algorithm,it proposed the repair algorithm WSCP-GRA and optimization algorithm WSCP-GOA for dealing with the infeasible solution of WSCP,on the basis of which a new method for solving WSCP was given by using nBABC.In order to verify the efficiency of nBABC in solving WSCP,using it to solve 45 WSCP instances in OR-Library.The comparison with several algorithms shows that nBABC can obtain the optimal values of all instances,which is more competitive than the existing algorithms for solving WSCP.