While for single-objective evolutionary algorithms many sharp run-time analyses exist, there are only few for multi-objective evolutionary algorithms (MOEAs), and even fewer for global MOEAs, that is, MOEAs using standard bit mutation (instead of 1-bit mutation, which is easier to analyze, but less common in practice). For example, there is not a single lower bound result for the runtime of the classic 'global simple evolutionary multiobjective optimizer' (GSEMO) on the bi-objective test function LeadingOnesTrailingZeros (LOTZ). An upper bound of O(n2/p), where p ≤ 1/n is the mutation probability, for this runtime was proven ten years ago by Giel (CEC 2003). In this work, we show that this bound is sharp for small values of p, namely p < n -7/4. © 2013 IEEE.

Lower bounds for the runtime of a global multi-objective evolutionary algorithm

Kodric B.;
2013-01-01

Abstract

While for single-objective evolutionary algorithms many sharp run-time analyses exist, there are only few for multi-objective evolutionary algorithms (MOEAs), and even fewer for global MOEAs, that is, MOEAs using standard bit mutation (instead of 1-bit mutation, which is easier to analyze, but less common in practice). For example, there is not a single lower bound result for the runtime of the classic 'global simple evolutionary multiobjective optimizer' (GSEMO) on the bi-objective test function LeadingOnesTrailingZeros (LOTZ). An upper bound of O(n2/p), where p ≤ 1/n is the mutation probability, for this runtime was proven ten years ago by Giel (CEC 2003). In this work, we show that this bound is sharp for small values of p, namely p < n -7/4. © 2013 IEEE.
2013
2013 IEEE Congress on Evolutionary Computation, CEC 2013
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in ARCA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10278/5035730
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? ND
social impact