1. 嘉兴学院 机构 数理与信息工程学院,浙江,嘉兴,314001
2. 江西理工大学 机构 信息工程学院,江西,赣州,341000
3. 中山大学 数据科学与计算机学院,广东,广州,510006
纸质出版:2016
移动端阅览
夏小云, 周育人. 基于免疫B-Cell算法求解可满足性问题的性能分析[J]. 微电子学与计算机, 2016, 33(7): 5-10.
XIA Xiao-yun, ZHOU Yu-ren. Performance Analysis of Immune Inspired B-Cell Algorithm for the SAT Problem[J]. 2016, 33(7): 5-10.
可满足性问题(SAT) 是计算机科学和人工智能研究中的核心NP-完全问题.构造了两类SAT问题实例
易解和难解实例.从理论上分析了B-Cell算法求解该两个实例的运行时间
并证实了B-Cell算法在某些问题上有效而在一些问题上无效.进一步提出了一个简单的基于免疫的多目标优化算法(IBMO)
对于一个双目标的SAT问题
证明了IBMO能够有效地找到整个Pareto前沿.这些分析结果从理论上证实和说明了人工免疫系统的有效性.
The satisfiability problem is a basic core NP-complete problem in computer science and artificial intelligence. We construct two classes of SAT instances
and analyze the runtime of the B-Cell algorithm for these two instances. We proved that there exist situations where the BCA is efficient or inefficient. On the other hand
we develop a simple immune-based multi-objective optimizer (IBMO) and reveal that IBMO can find the whole Pareto front for a bi-objective sat problem in expected polynomial runtime. These analysis results exemplify and strengthen the usefulness of artificial immune systems from a theoretical perspective.
Jansen T, Oliveto P S, Zarges C. On the analysis of the immune-Inspired B-Cell algorithm for the vertex cover problem[C]//ICARIS 2011. Springer, Heidelberg, 2011: 117-131.
Garey M R, Johnson D S. Computers and intractability-a guide to the theory of NP-completeness[M]. New York, Freeman, 1979.
Baca Raton Dasgupta D, NIñO L F. Immunological computation: theory and applications[M]. Baca Raton: CRC Press, 2008.
Beame P, Kautz H, Sabharwa A. Towards understanding and harnessing the potential of clause learning[J]. Journal of Artificial Intelligence Research, 2004, 22(2): 319-335. DOI: 319
Cook S. The complexity of theorem-proving procedures[C]//Proc of the 3rd Ann. ACM Symp. on Theory of Computing, Assoc. Comput. Mach. New York, 1971: 151.
Neumann F, Witt C. Bioinspired computation in combinatorial optimization-algorithms and their computational complexity[M]. Series, Natural Computing Springer, 2010.
Jansen T, Zarges C. A theoretical analysis of immune inspired somatic contiguous hypermutations for function optimization[C]//Proc of the International Conference on Artificial Immune Systems, ICARIS. Berlin, Springer, 2009: 80-94.
Wegener I. Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions[C]//In Evolutionary Optimization. Norwell, USA, Kluwer Academic Publishers, 2002: 349-369.
Droste S, Jansen T, Tinnefeld K, et al. A new framework for the valuation of algorithms for black-box optimization[C]//Foundations of Genetic Algorithms 7 (FOGA). Morgan Kaufmann, San Francisco, CA, 2003: 253-270.
Kelsey J, Timmis J. Immune inspired somatic contiguous hypermutation for function optimization[C]//Genetic and Evolutionary Computation Conference. Heidelberg, Springer, 2003: 207-218.
HIirsch E A, Kojevnikov a. UnitWalk: A new SAT solver that uses local search guided by unit clause elimination[J]. Annals of Mathematics and Artificial Intelligence, 2005, 43(1): 91-111. DOI: 91
Jansen T, Zarges C. Computing longest common subsequences with the B-Cell algorithm[C]//Proc of the 11th International Conference on Artificial Immune Systems (ICARIS'12). Italy, Taormina, 2012: 111-124.
0
浏览量
11
下载量
0
CSCD
关联资源
相关文章
相关作者
相关机构
京公网安备11010602201714号