Crynodeb
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 (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 an hybrid algorithm is not just a trivial weighted combination of the respective easiest functions for each operator.
Iaith wreiddiol  Saesneg 

Tudalennau (oi)  714–740 
Cyfnodolyn  Algorithmica 
Cyfrol  78 
Rhif cyhoeddi  2 
Dyddiad arlein cynnar  18 Awst 2016 
Dynodwyr Gwrthrych Digidol (DOIs)  
Statws  Cyhoeddwyd  01 Meh 2017 
Ôl bys
Gweld gwybodaeth am bynciau ymchwil 'On Easiest Functions for Mutation Operators in BioInspired Optimisation'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.Proffiliau

Thomas Jansen
 Cyfadran Busnes a’r Gwyddorau Ffisegol, Cyfrifiadureg  Reader, Head of Department (Computer Science)
Unigolyn: Dysgu ac Ymchwil, Arall

Christine Zarges
 Cyfadran Busnes a’r Gwyddorau Ffisegol, Cyfrifiadureg  Senior Lecturer
Unigolyn: Dysgu ac Ymchwil