20 November 2021

Fast Immune System-Inspired Hypermutation Operators for Combinatorial Optimization

Pietro Oliveto profile photo


Dogan Corus, Kadir Has University, Istanbul, Turkey

Piertro S. Oliveto, University of Sheffield

Donya Yazdani, Advanced Reasoning Group, Aberystwyth University, Aberystwyth, U.K

Read the full paper

What is this paper about?

Immune systems differ from Darwinian natural evolution by using considerably higher mutation rates (i.e., hypermutations) when evolving antibodies to fight pathogens. In immune system inspired search heuristics for solving combinatorial optimisation problems the higher mutation rates allow the algorithm to escape from locally optimal solutions faster than evolutionary algorithms (EAs) which use lower mutation rates. This, however, comes at the expense of the artificial immune systems being slower during the exploitation phases of the optimisation process compared to EAs. The paper provides new hypermutation operators which provably speed up the exploitation phases while still allowing to escape local optima more efficiently than EAs.

Why is the research important and/or novel?

The paper fixes several drawbacks of previous artificial immune systems for combinatorial optimisation proposed in the literature. In particular, it introduces hypermutation operators which allow for lower expected times to escape from local optima while at the same time being fast during the exploitation phase when the global or local optima have to be identified.

Flagship institutes

The University’s four flagship institutes bring together our key strengths to tackle global issues, turning interdisciplinary and translational research into real-world solutions.