Performance Analysis of Immune Inspired B-Cell Algorithm for the SAT Problem

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.