On the effectiveness of immune inspired mutation operators in some discrete optimization problems

Artificial immune systems have been widely applied to a variety of complex real-world problems. However, theoretical studies on artificial immune system are still limited and there is a strong need for building a rigorous theoretical foundation to better understand these heuristics. This paper contributes to a theoretical runtime analysis of immune inspired hypermutations on some discrete optimization problems. In particular, we are interested in the performance comparison among somatic contiguous hypermutations (CHM), standard bit mutations (SBM) and local mutation. We reveal that the immune inspired hypermutations can significantly outperform the standard bit mutation most often used in evolutionary algorithms on some well-known pseudo-Boolean functions including Trap and Hierarchical-if-and-only-if functions and instances of two combinatorial optimization problems, namely the Max-Cut problem and the Minimum s-t-cut problem. The proofs give some insights into the relationships between the problem characteristics and algorithmic features. The results of the analysis help strengthen the usefulness of Artificial immune systems.