Projects per year
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 bioinspired 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 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 show that an easiest function for the hybrid algorithm is not just a trivial weighted combination of the respective easiest functions for each operator. Nevertheless, by combining the advantages of both operators, the hybrid algorithm has optimal asymptotic performance on both OneMax and MinBlocks.
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 show that an easiest function for the hybrid algorithm is not just a trivial weighted combination of the respective easiest functions for each operator. Nevertheless, by combining the advantages of both operators, the hybrid algorithm has optimal asymptotic performance on both OneMax and MinBlocks.
Original language  English 

Title of host publication  GECCO 2015  Proceedings of the 2015 Genetic and Evolutionary Computation Conference 
Editors  Sara Silva 
Place of Publication  New York 
Publisher  Association for Computing Machinery 
Pages  13991406 
Number of pages  8 
ISBN (Electronic)  9781450334723 
ISBN (Print)  9781450334723 
DOIs  
Publication status  Published  11 Jul 2015 
Publication series
Name  GECCO 2015  Proceedings of the 2015 Genetic and Evolutionary Computation Conference 

Keywords
 Artificial immune systems
 Evolutionary algorithms
 Hybridisation
 Running time analysis
 Theory
Fingerprint
Dive into the research topics of 'On easiest functions for somatic contiguous hypermutations and standard bit mutations'. Together they form a unique fingerprint.Projects
 1 Finished

Evolutionary Approximation Algorithms for Optimization: Algorithm design and Complexity Analysis
He, J. (PI)
Engineering and Physical Sciences Research Council
01 May 2011 → 31 Oct 2015
Project: Externally funded research