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

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