基于免疫B-Cell算法求解可满足性问题的性能分析
Performance Analysis of Immune Inspired B-Cell Algorithm for the SAT Problem
-
摘要: 可满足性问题(SAT) 是计算机科学和人工智能研究中的核心NP-完全问题.构造了两类SAT问题实例, 易解和难解实例.从理论上分析了B-Cell算法求解该两个实例的运行时间, 并证实了B-Cell算法在某些问题上有效而在一些问题上无效.进一步提出了一个简单的基于免疫的多目标优化算法(IBMO), 对于一个双目标的SAT问题, 证明了IBMO能够有效地找到整个Pareto前沿.这些分析结果从理论上证实和说明了人工免疫系统的有效性.Abstract: 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.