Published on Wed Apr 04 2018

When Hypermutations and Ageing Enable Artificial Immune Systems to Outperform Evolutionary Algorithms

Dogan Corus, Pietro S. Oliveto, Donya Yazdani

We present a time complexity analysis of the Opt-IA artificial immune system. We show that ageing combined with local mutations can help escape local optima on a dynamic optimisation benchmark function. We prove that algorithms using hypermutations can be considerably faster than EAs at escaping local optima.

0
0
0
Abstract

We present a time complexity analysis of the Opt-IA artificial immune system (AIS). We first highlight the power and limitations of its distinguishing operators (i.e., hypermutations with mutation potential and ageing) by analysing them in isolation. Recent work has shown that ageing combined with local mutations can help escape local optima on a dynamic optimisation benchmark function. We generalise this result by rigorously proving that, compared to evolutionary algorithms (EAs), ageing leads to impressive speed-ups on the standard Cliff benchmark function both when using local and global mutations. Unless the stop at first constructive mutation (FCM) mechanism is applied, we show that hypermutations require exponential expected runtime to optimise any function with a polynomial number of optima. If instead FCM is used, the expected runtime is at most a linear factor larger than the upper bound achieved for any random local search algorithm using the artificial fitness levels method. Nevertheless, we prove that algorithms using hypermutations can be considerably faster than EAs at escaping local optima. An analysis of the complete Opt-IA reveals that it is efficient on the previously considered functions and highlights problems where the use of the full algorithm is crucial. We complete the picture by presenting a class of functions for which Opt-IA fails with overwhelming probability while standard EAs are efficient.

Wed Mar 27 2019
Neural Networks
On Inversely Proportional Hypermutations with Mutation Potential
Artificial Immune Systems (AIS) employing hypermutations with linear static mutation potential have been shown to be very effective at escaping local optima of combinatorial optimisation problems. The aim of the AIS is to approximate the ideal behaviour of the inversely proportional mutation potential.
0
0
0
Fri Jun 01 2018
Neural Networks
Fast Artificial Immune Systems
Hypermutations and ageing can be very efficient at escaping local optima. This efficiency comes at the expense of considerably slower runtimes during the exploitation phase. We propose modifications to traditional `hypermutations with mutation potential' (HMP) that allow them to be efficient at exploitation.
0
0
0
Tue Sep 01 2020
Neural Networks
Fast Immune System Inspired Hypermutation Operators for Combinatorial Optimisation
We show that immune system inspired hypermutation (AIS) can allow artificial immune systems to be very efficient at escaping local optima of multimodal optimisation problems. However, this efficiency comes at the expense of considerably slower runtimes during the exploitation phase compared to standard evolutionary algorithms. We propose modifications to the traditional `hypermutations with mutation potential'
0
0
0
Thu Apr 23 2015
Neural Networks
First Steps Towards a Runtime Comparison of Natural and Artificial Evolution
Strong Selection Weak Mutation (SSWM) evolutionary regime. Time between occurrence of new mutations is much longer than time it takes for a new beneficial mutation to take over the population. SSWM can have a moderate advantage over the (1+1)EA at crossing fitness valleys.
0
0
0
Mon Jul 09 2018
Neural Networks
Optimal Parameter Choices via Precise Black-Box Analysis
We prove that the unary unbiased black-box complexity of the OneMax benchmark function class is $n \ln(n) - cn \pm o(n), which is between and $ 0.2665. This runtime can be achieved with a
0
0
0
Fri Nov 30 2018
Neural Networks
Runtime Analysis for Self-adaptive Mutation Rates
The current mutation rate is part of the individual and thus also subject to mutation. A simple local mutation scheme for the rate leads to an expected optimization time. The paper contributes new tools for the analysis of two-dimensional drift processes.
0
0
0