Runtime Analysis of Somatic Contiguous Hypermutation Operators in MOEA/D Framework

Abstract

Somatic contiguous hypermutation (CHM) operators are important variation operators in artificial immune systems. The few existing theoretical studies are only concerned with understanding the optimization behavior of CHM operators on solving single-objective optimization problems. The MOEA/D framework is one of the most popular strategies for solving multi-objective optimization problems (MOPs). In this paper, we present a runtime analysis of using two CHM operators in MOEA/D framework for solving five benchmark MOPs, including four bi-objective and one many-objective problems. Our analyses show that the expected runtimes of CHM operators on the four bi-objective problems are better than or as good as that of the well-studied standard bit mutation operator. Moreover, using CHM operators in MOEA/D framework can improve the best known upper bound on the many-objective problem by a factor of n. This paper provides insight into understanding the optimization behavior of CHM operators in the well-known MOEA/D framework, and indicates that using the CHM operator in MOEA/D framework is a promising method for handling MOPs.