Tools
Tools
Corus, D., He, J. 
ORCID: 0000-0002-5616-4691, Jansen, T., Oliveto, P.S., 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
|
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: |
|
||||||
| 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 |
Views
Views per month over past year
Downloads
Downloads per month over past year
