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

中国机械工程 ›› 2015, Vol. 26 ›› Issue (7): 917-923.

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

朱传军1;曹静1;张超勇2;连坤雷2

1.湖北工业大学，武汉，430068
2.华中科技大学数字制造装备与技术国家重点实验室，武汉，430074

出版日期:2015-04-10 发布日期:2015-04-24
基金资助:
国家自然科学基金资助重点项目（51035001）；国家自然科学基金资助项目（51275190）；湖北省自然科学基金资助项目（2012FFB0063，2013CFB025）

Applying Modified Colonial Competitive Algorithm to Solve Minimal Hitting Set Problems

Zhu Chuanjun1;Cao Jing1;Zhang Chaoyong2;Lian Kunlei2

1.Hubei University of Technology, Wuhan, 430068
2.State Key Laboratory of Digital Manufacturing Equipment & Technology，Huazhong University of Science and Technology, Wuhan, 430074

Online:2015-04-10 Published:2015-04-24
Supported by:
National Natural Science Foundation of China（No. 51035001, 51275190）;Hubei Provincial Natural Science Foundation of China（No. 2012FFB0063，2013CFB025）

摘要/Abstract

摘要：

利用改进殖民竞争算法生成企业设备的最小候选集，其最小候选集就是企业设备的最小碰集。在对殖民竞争算法进行深入研究的基础上，引入自由国家的概念，同时对算法流程中帝国初始化阶段和帝国内同化及更新阶段进行改进，提高了算法效率。与DMDSE-Tree算法进行了对比，在计算90%的最小碰集时，改进殖民竞争算法具有良好的效率。最后，通过某企业实例对算法的有效性进行了验证。实验结果表明，该方法能有效应用于企业设备选择组合优化问题的求解。

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

Abstract:

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 initialization, 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 example. 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 better efficiency. Finally, the experimental results of certain system verify the effectiveness of the algorithm,which proves that this method can be applied in solving the minimal hitting set of combinatorial optimization problems for selection of equipment effectively.

Key words: business planning, colonial competitive algorithm(CCA), minimal hitting set, equipment selection

中图分类号:

TB114.1

朱传军, 曹静, 张超勇, 连坤雷. 基于改进殖民竞争算法的最小碰集求解[J]. 中国机械工程, 2015, 26(7): 917-923.

Zhu Chuanjun, Cao Jing, Zhang Chaoyong, Lian Kunlei. Applying Modified Colonial Competitive Algorithm to Solve Minimal Hitting Set Problems[J]. China Mechanical Engineering, 2015, 26(7): 917-923.

参考文献

[1]Reiter R.A Theory of Diagnosis from First Principles [J].Artificial Intelligence,1987,32(1):57-96.
[2]Greiner R,Smith B A,Wilkerson R W.A Correction to the Algorithm in Reiter’s Theory of Diagnosis(Research Note)[J]. Artificial Intelligence, 1989, 41(1):79-88.
[3]陈晓梅，孟晓风，乔仁晓.基于BNB-HSSE计算全体碰集的方法[J].仪器仪表学报，2010，31(1)：605-608.
Chen Xiaomei,Meng Xiaofeng,Qiao Renxiao.Method of Computing All Minimal Hitting Set Based on BNB-HSSE [J].Chinese Journal of Scientific Instrument,2010,31(1):605-608.
[4]Wang Ziling, Xu Aiqiang, Wang Dingguo,et al.Research on a New Combined Algorithm for Computing Minimal Hitting Sets[C]//Proceedings of the 2010 International Conference on Measuring Technology and Mechatronics Automation. Changsha, 2010: 14-17.
[5]Feng Wenquan, Du Min, Zhao Qi, et al.A Method of Combining HSSE-tree and Binary Label to Compute All Minimal Hitting Sets[C]//2011 Fourth International Symposium on Computational Intelligence and Design.Hangzhou,2011:14-17.
[6]Shi Lei,Cai Xuan.An Exact Fast Algorithm for Minimum Hitting Set[C]//2010 Third International Joint Conference on Computational Science and Optimization.Huangshan, 2010: 64-67.
[7]张立明,欧阳丹彤,曾海林.基于动态极大度的极小碰集求解方法[J].计算机研究与发展,2011,48(2)：209-215.
Zhang Liming, Ouyang Dantong,Zeng Hailin.Computing the Minimal Hitting Sets Based on Dynamic Maximum Degree[J].Journal of Computer Research and Development,2011,48( 2):209-215.
[8]蒋荣华,田书林,龙兵.基于DPSO的最小碰集算法的掩盖故障识别[J].系统工程与电子技术,2009,31(4):997-1001.
Jiang Ronghua,Tian Shulin,Long Bing.Minimal Hitting Sets Algorithm of Identifying Masking False Failure Sets Based on DPSO[J]. Systems Engineering and Electronics,2009,31(4):997-1001.
[9]吕晓明，黄考利，连光耀.基于BPSO的多故障最小候选集生成技术[J].系统工程与电子技术, 2012,34(5):961-965.
Lü Xiaoming, Huang Kaoli, Lian Guangyao.Generation of Minimal Candidate Set for Multiple Fault Diagnosis Based on Binary Particle Swarm Optimization[J]. Systems Engineering and Electronics,2012,34(5):961-965.
[10]Abreu R,van Gemund A J C.A Low-cost Approximate Minimal Hitting Set Algorithm and Its Application to Model-Based Diagnosis[C]//Proceedings of the 8th Symposium on Abstraction,Reformulation and Approximation.Lake Arrowhead,2009:2-8.
[11]Atashpaz-Gargari E,Lucas C.Imperialist Competitive Algorithm: an Algorithm for Optimization Inspired by Imperialistic Competition[C]//IEEE Congress on Evolutionary Computation.Singapore,2007:4661-4667.
[12]Forouharfard S, Zandieh M.An Imperialist Competitive Algorithm to Schedule of Receiving and Shipping Trucks in Cross-docking Systems[J].The International Journal of Advanced Manufacturing Technology,2010,51(9):1179-1193.
[13]Kaveh A,Talatahari S.Optimum Design of Skeletal Structures Using Imperialist Competitive Algorithm[J]. Computers & Structures, 2010, 88 (21/22):1220-1229.
[14]Nazari-Shirkouhi S,Eivazy H,Ghodsi R,et al.Solving the Integrated Product Mix-outsourcing Problem Using the Imperialist Competitive Algorithm[J].Expert Systems with Applications,2010,37(12):7615-7626.
[15]Sarayloo F,Tavakkoli-Moghaddam R.Imperialistic Competitive Algorithm for Solving a Dynamic Cell Formation Problem with Production Planning[J].Advanced Intelligent Computing Theories and Applications,2010,6215:266-276.
[16]Hadji M M,Vahidi B.A Solution to the Unit Commitment Problem Using Imperialistic Competition Algorithm[J].IEEE Transactions on Power Systems, 2011, 27(1):117-124.
[17]Bagher M,Zandieh M,Farsijani H.Balancing of Stochastic U-type Assembly Lines:an Imperialist Competitive Algorithm[J].The International Journal of Advanced Manufacturing Technology,2011,54(1/4):271-285.
[18]Niknam T,Fard E T,Pourjafarian N,et al.An Efficient Hybrid Algorithm Based on Modified Imperialist Competitive Algorithm and K-means for Data Clustering[J].Engineering Applications of Artificial Intelligence,2011,24 (2):306-317.