基于改进殖民竞争算法的最小碰集求解  

Applying Modified Colonial Competitive Algorithm to Solve Minimal Hitting Set Problems

作　　者：朱传军[1] 曹静[1] 张超勇[2] 连坤雷[2] 

机构地区：[1]湖北工业大学,武汉430068 [2]华中科技大学数字制造装备与技术国家重点实验室,武汉430074

出　　处：《中国机械工程》2015年第7期917-923,共7页China Mechanical Engineering

基　　金：国家自然科学基金资助重点项目(51035001);国家自然科学基金资助项目(51275190);湖北省自然科学基金资助项目(2012FFB0063;2013CFB025)

摘　　要：利用改进殖民竞争算法生成企业设备的最小候选集,其最小候选集就是企业设备的最小碰集。在对殖民竞争算法进行深入研究的基础上,引入自由国家的概念,同时对算法流程中帝国初始化阶段和帝国内同化及更新阶段进行改进,提高了算法效率。与DMDSE-Tree算法进行了对比,在计算90%的最小碰集时,改进殖民竞争算法具有良好的效率。最后,通过某企业实例对算法的有效性进行了验证。实验结果表明,该方法能有效应用于企业设备选择组合优化问题的求解。A CCA was developed and modified to solve the problem of minimal candidates set. The minimal candidate set was a minimal hitting set. The modified CCA improved performance in initial- ization, assimilation and rebirth of original CCA by introducing a third type of country, independent country,to the population of countries maintained by CCA. Implementation details of the proposed CCA and modified colonial competitive algorithm（MCCA） were elaborated using an illustrative exam- ple. The performance of the algorithms was analyzed, and the results by the MCCA were compared with DMDSE-Tree algorithm. When 90 % of the minimal hitting sets are obtained, the MCCA has bet- ter efficiency. Finally, the experimental results of certain system verify the effectiveness of the algo- rithm, which proves that this method can be applied in solving the minimal hitting set of combinatorial optimization problems for selection of equipment effectively.

关 键 词：企业规划 殖民竞争算法 最小碰集 设备选择 

分 类 号：TB114.1[理学—运筹学与控制论]