On easiest functions for somatic contiguous hypermutations and standard bit mutations

Dogan Corus, Jun He, Thomas Jansen, Pietro Oliveto, Dirk Sudholt, Christine Zarges

Allbwn ymchwil: Pennod mewn Llyfr/Adroddiad/Trafodion CynhadleddTrafodion Cynhadledd (Nid-Cyfnodolyn fathau)

6 Dyfyniadau (Scopus)

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 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 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.
Iaith wreiddiolSaesneg
TeitlGECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference
GolygyddionSara Silva
Man cyhoeddiNew York
CyhoeddwrAssociation for Computing Machinery
Tudalennau1399-1406
Nifer y tudalennau8
ISBN (Electronig)9781450334723
ISBN (Argraffiad)978-1-4503-3472-3
Dynodwyr Gwrthrych Digidol (DOIs)
StatwsCyhoeddwyd - 11 Gorff 2015

Cyfres gyhoeddiadau

EnwGECCO 2015 - Proceedings of the 2015 Genetic and Evolutionary Computation Conference

Ôl bys

Gweld gwybodaeth am bynciau ymchwil 'On easiest functions for somatic contiguous hypermutations and standard bit mutations'. Gyda’i gilydd, maen nhw’n ffurfio ôl bys unigryw.

Dyfynnu hyn