More Web Proxy on the site http://driver.im/

research-article

Runtime analysis of convex evolutionary search

Authors:

Alberto Moraglio,

Dirk SudholtAuthors Info & Claims

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

Pages 649 - 656

https://doi.org/10.1145/2330163.2330255

Published: 07 July 2012 Publication History

Abstract

Geometric crossover formalises the notion of crossover operator across representations. In previous work, it was shown that all evolutionary algorithms with geometric crossover (but with no mutation) do a generalised form of convex search. Furthermore, it was suggested that these search algorithms could perform well on concave and approximately concave fitness landscapes. In this paper, we study the runtime of a generalised form of convex search on concave fitness landscapes. This is a first step towards linking a geometric theory of representations and runtime analysis in the attempt to (i) set the basis for a more general/unified approach for the runtime analysis of evolutionary algorithms across representations, and (ii) identify the essential matching features of evolutionary search behaviour and landscape topography that cause polynomial performance. Our convex search algorithm optimises LeadingOnes in O(n log n) fitness evaluations, which is faster than all unbiased unary black-box algorithms.

References

[1]

A. Auger and B. Doerr, editors. Theory of Randomized Search Heuristics -- Foundations and Recent Developments. World Scientific, 2011.

Digital Library

[2]

B. Doerr, E. Happ, and C. Klein. Crossover can provably be useful in evolutionary computation. Theoretical Computer Science, 425(0):17--33, 2012.

Digital Library

[3]

B. Doerr, D. Johannsen, T. Kötzing, P. K. Lehre, M. Wagner, and C. Winzen. Faster black-box algorithms through higher arity operators. In Proc. of FOGA '11, pages 163--172. ACM Press, 2011.

Digital Library

[4]

T. Jansen and I. Wegener. On the analysis of evolutionary algorithms--a proof that crossover really can help. Algorithmica, 34(1):47--66, 2002.

Digital Library

[5]

T. Jansen and I. Wegener. Real royal road functions--where crossover provably is essential. Discrete Applied Mathematics, 149:111--125, 2005.

Digital Library

[6]

T. Kötzing, D. Sudholt, and M. Theile. How crossover helps in pseudo-Boolean optimization. In Proc. of GECCO '11, pages 989--996. ACM Press, 2011.

Digital Library

[7]

J. Lassig and D. Sudholt. General scheme for analyzing running times of parallel evolutionary algorithms. In Parallel Problem Solving from Nature (PPSN 2010), pages 234--243. Springer, 2010.

Digital Library

[8]

P. K. Lehre and C. Witt. Black box search by unbiased variation. In Proc. of GECCO '10, pages 1441--1448, 2010.

Digital Library

[9]

A. Moraglio. Towards a Geometric Unification of Evolutionary Algorithms. PhD thesis, University of Essex, 2007.

[10]

A. Moraglio. Abstract convex evolutionary search. In Proc. of FOGA '11, pages 151--162. ACM Press, 2011.

Digital Library

[11]

A. Moraglio and R. Poli. Topological interpretation of crossover. In Proc. of GECCO '04, pages 1377--1388. Springer, 2004.

[12]

A. Moraglio and R. Poli. Product geometric crossover. In Parallel Problem Solving from Nature (PPSN 2006), pages 1018--1027. Springer, 2006.

Digital Library

[13]

R. Motwani and P. Raghavan. Randomized Algorithms. Cambridge University Press, 1995.

Digital Library

[14]

F. Neumann and C. Witt. Bioinspired Computation in Combinatorial Optimization -- Algorithms and Their Computational Complexity. Springer, 2010.

Digital Library

[15]

N. R. Patel, R. L. Smith, and Z. B. Zabinsky. Pure adaptive search in Monte Carlo optimization. Mathematical Programming, 4:317--328, 1988.

Digital Library

[16]

D. Sudholt. Crossover is provably essential for the Ising model on trees. In Proc. of GECCO '05, pages 1161--1167. ACM Press, 2005.

Digital Library

[17]

D. Sudholt. General lower bounds for the running time of evolutionary algorithms. In Parallel Problem Solving from Nature (PPSN 2010), pages 124--133. Springer, 2010.

Digital Library

[18]

D. Sudholt and C. Zarges. Analysis of an iterated local search algorithm for vertex coloring. In Proc. of ISAAC '10, pages 340--352. Springer, 2010.

[19]

I. Wegener. Methods for the analysis of evolutionary algorithms on pseudo-Boolean functions. In R. Sarker, X. Yao, and M. Mohammadian, editors, Evolutionary Optimization, pages 349--369. Kluwer, 2002.

[20]

D. H. Wolpert and W. G. Macready. No free lunch theorems for optimization. IEEE Transaction on Evolutionary Computation, 1(1):67--82, 1996.

Digital Library

[21]

Z. B. Zabinsky. Stochastic Adaptive Search for Global Optimization. Kluwer Academic, 2003.

Cited By

Moraglio ASudholt D(2017)Principled design and runtime analysis of abstract convex evolutionary searchEvolutionary Computation10.1162/EVCO_a_0016925:2(205-236)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1162/EVCO_a_00169
Dang DFriedrich TKötzing TKrejca MLehre POliveto PSudholt DSutton ANeumann FSutton A(2016)Escaping Local Optima with Diversity Mechanisms and CrossoverProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908956(645-652)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908956
Goldman BSudholt DNeumann FSutton A(2016)Runtime Analysis for the Parameter-less Population PyramidProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908846(669-676)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908846
Show More Cited By

Index Terms

Runtime analysis of convex evolutionary search
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Abstract convex evolutionary search
FOGA '11: Proceedings of the 11th workshop proceedings on Foundations of genetic algorithms

Geometric crossover is a formal class of crossovers which includes many well-known recombination operators across representations. In this paper, we present a general result showing that all evolutionary algorithms using geometric crossover with no ...
Principled design and runtime analysis of abstract convex evolutionary search

Geometric crossover is a formal class of crossovers that includes many well-known recombination operators across representations. In previous work, it was shown that all evolutionary algorithms with geometric crossover but no mutation do the same form ...
A Unifying View on Recombination Spaces and Abstract Convex Evolutionary Search
Evolutionary Computation in Combinatorial Optimization
Abstract
Previous work proposed to unify an algebraic theory of fitness landscapes and a geometric framework of evolutionary algorithms (EAs). One of the main goals behind this unification is to develop an analytical method that verifies if a problem’s ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '12: Proceedings of the 14th annual conference on Genetic and evolutionary computation

July 2012

1396 pages

ISBN:9781450311779

DOI:10.1145/2330163

Editor:
Terence Soule
University of Idaho, USA
,
General Chair:
Jason H. Moore
Dartmouth College, USA

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 July 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '12

Sponsor:

SIGEVO

GECCO '12: Genetic and Evolutionary Computation Conference

July 7 - 11, 2012

Pennsylvania, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
132
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Moraglio ASudholt D(2017)Principled design and runtime analysis of abstract convex evolutionary searchEvolutionary Computation10.1162/EVCO_a_0016925:2(205-236)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1162/EVCO_a_00169
Dang DFriedrich TKötzing TKrejca MLehre POliveto PSudholt DSutton ANeumann FSutton A(2016)Escaping Local Optima with Diversity Mechanisms and CrossoverProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908956(645-652)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908956
Goldman BSudholt DNeumann FSutton A(2016)Runtime Analysis for the Parameter-less Population PyramidProceedings of the Genetic and Evolutionary Computation Conference 201610.1145/2908812.2908846(669-676)Online publication date: 20-Jul-2016
https://dl.acm.org/doi/10.1145/2908812.2908846
Pawlak TKrawiec K(2016)Progress properties and fitness bounds for geometric semantic search operatorsGenetic Programming and Evolvable Machines10.1007/s10710-015-9252-617:1(5-23)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1007/s10710-015-9252-6
Pawlak TKrawiec K(2016)Semantic Geometric InitializationGenetic Programming10.1007/978-3-319-30668-1_17(261-277)Online publication date: 24-Mar-2016
https://doi.org/10.1007/978-3-319-30668-1_17
Paixão TBadkobeh GBarton NÇörüş DDang DFriedrich TLehre PSudholt DSutton ATrubenová B(2015)Toward a unifying framework for evolutionary processesJournal of Theoretical Biology10.1016/j.jtbi.2015.07.011383(28-43)Online publication date: Oct-2015
https://doi.org/10.1016/j.jtbi.2015.07.011
Pawlak TWieloch BKrawiec K(2015)Review and comparative analysis of geometric semantic crossoversGenetic Programming and Evolvable Machines10.1007/s10710-014-9239-816:3(351-386)Online publication date: 1-Sep-2015
https://dl.acm.org/doi/10.1007/s10710-014-9239-8

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten