On easiest functions for mutation operators in bio-inspired optimisation

Corus, D, He, J ORCID: https://orcid.org/0000-0002-5616-4691, Jansen, T, Oliveto, PS, Sudholt, D and Zarges, C, 2017. On easiest functions for mutation operators in bio-inspired optimisation. Algorithmica, 78 (2), pp. 714-740. ISSN 0178-4617

Preview

Text 10587_He.pdf - Post-print Download (703kB) | Preview

Abstract

Understanding which function classes are easy and which are hard for a given algorithm is a fundamental question for the analysis and design of bio-inspired search heuristics. A natural starting point is to consider the easiest and hardest functions for an algorithm. For the (1+1) EA using standard bit mutation (SBM) it is well known that ONEMAX is an easiest function with unique optimum while Trap is a hardest. In this paper we extend the analysis of easiest function classes to the contiguous somatic hypermutation (CHM) operator used in artificial immune systems. We define a function MINBLOCKS and prove that it is an easiest function for the (1+1) EA using CHM, presenting both a runtime and a fixed budget analysis. Since MINBLOCKS is, up to a factor of 2, a hardest function for standard bit mutations, we consider the effects of combining both operators into a hybrid algorithm. We rigorously prove that by combining the advantages of k operators, several hybrid algorithmic schemes have optimal asymptotic performance on the easiest functions for each individual operator. In particular, the hybrid algorithms using CHM and SBM have optimal asymptotic performance on both ONEMAX and MINBLOCKS. We then investigate easiest functions for hybrid schemes and show that an easiest function for a hybrid algorithm is not just a trivial weighted combination of the respective easiest functions for each operator.

Item Type:	Journal article
Publication Title:	Algorithmica
Creators:	Corus, D., He, J., Jansen, T., Oliveto, P.S., Sudholt, D. and Zarges, C.
Publisher:	Springer New York
Date:	June 2017
Volume:	78
Number:	2
ISSN:	0178-4617
Identifiers:	Number Type 10.1007/s00453-016-0212-4 DOI 201 Publisher Item Identifier
Rights:	© the author(s) 2016. This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Divisions:	Schools > School of Science and Technology
Record created by:	Jonathan Gallacher
Date Added:	19 Mar 2018 15:48
Last Modified:	19 Mar 2018 15:48
URI:	https://irep.ntu.ac.uk/id/eprint/33031

Actions (login required)

Edit View

Statistics

Views

Downloads