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

research-article

An analysis on recombination in multi-objective evolutionary optimization

Authors:

Zhi-Hua ZhouAuthors Info & Claims

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

Pages 2051 - 2058

https://doi.org/10.1145/2001576.2001852

Published: 12 July 2011 Publication History

Abstract

Recombination (or called crossover) operators are a kind of characterizing feature of evolutionary algorithms (EAs). The usefulness of recombination operators has been verified empirically in many practical applications, and has also been theoretically studied in single-objective optimization. For multi-objective optimization, however, there lacks strong evidence on whether the recombination operators can lead to a better running time. In this paper, we establish some theoretical support to the use of recombination in multi-objective optimization. We analyze the running time of REMO, a simple multi-objective EA with a recombination operator, on two well-studied bi-objective problems, i.e., the LOTZ and the COCZ problems. Our analysis results disclose that the average running time of REMO on LOTZ and COCZ is Θ(n²) and Θ(n log n), respectively, improved from Θ(n³) and Θ(n²) as when the recombination operator is turned off, respectively. These results imply that the recombination operator is crucial for the efficiency of REMO on these two problems. The analysis also suggests that, generally, recombination operators can be helpful to multi-objective optimization as they may accelerate the filling of the Pareto front through recombining diverse solutions.

References

[1]

T. Bäck. Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, Oxford, UK, 1996.

Digital Library

[2]

M. Dietzfelbinger, B. Naudts, C. Van Hoyweghen, and I. Wegener. The analysis of a recombinative hill-climber on H-IFF. IEEE Transactions on Evolutionary Computation, 7(5):417--423, 2003.

Digital Library

[3]

B. Doerr, E. Happ, and C. Klein. Crossover can provably be useful in evolutionary computation. In Proceedings of the 10th ACM Annual Conference on Genetic and Evolutionary Computation (GECCO'08), pages 539--546, Atlanta, GA, 2008.

Digital Library

[4]

B. Doerr, D. Johannsen, T. Kötzing, F. Neumann, and M. Theile. More effective crossover operators for the all-pairs shortest path problem. In Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN'10), pages 184--193, Krakow, Poland, 2010.

Digital Library

[5]

B. Doerr and M. Theile. Improved analysis methods for crossover-based algorithms. In Proceedings of the 11th ACM Annual Conference on Genetic and Evolutionary Computation (GECCO'09), pages 247--254, Montreal, Canada, 2009.

Digital Library

[6]

S. Droste, T. Jansen, and I. Wegener. On the analysis of the (1+1) evolutionary algorithm. Theoretical Computer Science, 276(1--2):51--81, 2002.

Digital Library

[7]

A.-E. Eiben, P.-E. Raué, and Z. Ruttkay. Genetic algorithms with multi-parent recombination. In Proceedings of the 3rd International Conference on Parallel Problem Solving from Nature (PPSN'94), pages 78--87, Jerusalem, Israel, 1994.

Digital Library

[8]

S. Fischer and I. Wegener. The one-dimensional Ising model: Mutation versus recombination. Theoretical Computer Science, 344(2--3):208--225, 2005.

Digital Library

[9]

T. Friedrich, J. He, N. Hebbinghaus, F. Neumann, and C. Witt. Approximating covering problems by randomized search heuristics using multi-objective models. In Proceedings of the 9th ACM Annual Conference on Genetic and Evolutionary Computation (GECCO'07), pages 797--804, London, UK, 2007.

Digital Library

[10]

O. Giel. Expected runtimes of a simple multi-objective evolutionary algorithm. In Proceedings of the 2003 IEEE Congress on Evolutionary Computation (CEC'03), pages 1918--1925, Canberra, Australia, 2003.

[11]

T. Hanne. On the convergence of multiobjective evolutionary algorithms. European Journal of Operational Research, 117(3):553--564, 1999.

[12]

T. Hanne. Global multiobjective optimization with evolutionary algorithms: Selection mechanisms and mutation control. In Proceedings of the 1st International Conference on Evolutionary Multi-Criterion Optimization (EMO'01), pages 197--212, Zurich, Switzerland, 2001.

Digital Library

[13]

J. He and X. Yao. Drift analysis and average time complexity of evolutionary algorithms. Artificial Intelligence, 127(1):57--85, 2001.

Digital Library

[14]

C. Horoba and F. Neumann. Additive approximations of pareto-optimal sets by evolutionary multi-objective algorithms. In Proceedings of the 10th International Workshop on Foundations of Genetic Algorithms (FOGA'09), pages 79--86, Orlando, FL, 2009.

Digital Library

[15]

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

Digital Library

[16]

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

Digital Library

[17]

M. Laumanns, L. Thiele, and E. Zitzler. Running time analysis of multiobjective evolutionary algorithms on pseudo-boolean functions. IEEE Transactions on Evolutionary Computation, 8(2):170--182, 2004.

Digital Library

[18]

M. Laumanns, L. Thiele, E. Zitzler, E. Welzl, and K. Deb. Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem. In Proceedings of the 7th International Conference on Parallel Problem Solving from Nature (PPSN'02), pages 44--53, Birmingham, UK, 2002.

Digital Library

[19]

P. K. Lehre and X. Yao. Crossover can be constructive when computing unique input output sequences. In Proceedings of the 7th International Conference on Simulated Evolution and Learning (SEAL'08), pages 595--604, Melbourne, Australia, 2008.

Digital Library

[20]

G. Lin and X. Yao. Analysing crossover operators by search step size. In Proceedings of the 1997 IEEE Congress on Evolutionary Computation (CEC'97), pages 107--110, Indianapolis, IN, 1997.

[21]

T. Murata and H. Ishibuchi. MOGA: Multi-objective genetic algorithms. In Proceedings of the 1995 IEEE Congress on Evolutionary Computation (CEC'95), pages 289--294, Perth, Australia, 1995.

[22]

F. Neumann. Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. European Journal of Operational Research, 181(3):1620--1629, 2007.

[23]

F. Neumann and J. Reichel. Approximating minimum multicuts by evolutionary multi-objective algorithms. In Proceedings of the 10th International Conference on Parallel Problem Solving from Nature (PPSN'08), pages 72--81, Dortmund, Germany, 2008.

Digital Library

[24]

F. Neumann and M. Theile. How crossover speeds up evolutionary algorithms for the multi-criteria all-pairs-shortest-path problem. In Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN'10), pages 667--676, Krakow, Poland, 2010.

Digital Library

[25]

F. Neumann and I. Wegener. Minimum spanning trees made easier via multi-objective optimization. Natural Computing, 5(3):305--319, 2006.

Digital Library

[26]

P. Oliveto, J. He, and X. Yao. Analysis of population-based evolutionary algorithms for the vertex cover problem. In Proceedings of the 2008 IEEE Congress on Evolutionary Computation (CEC'08), pages 1563--1570, Hong Kong, China, 2008.

[27]

J. Richter, A. Wright, and J. Paxton. Ignoble trails-where crossover is provably harmful. In Proceedings of the 10th International Conference on Parallel Problem Solving from Nature (PPSN'08), pages 92--101, Dortmund, Germany, 2008.

Digital Library

[28]

O. Rudenko and M. Schoenauer. Dominance based crossover operator for evolutionary multi-objective algorithms. In Proceedings of the 8th International Conference on Parallel Problem Solving from Nature (PPSN'04), pages 812--821, Birmingham, UK, 2004.

[29]

G. Rudolph. Evolutionary search for minimal elements in partially ordered sets. In Proceedings of the 7th International Conference on Evolutionary Programming (EP'98), pages 345--353, San Diego, CA, 1998.

Digital Library

[30]

G. Rudolph. On a multi-objective evolutionary algorithm and its convergence to the pareto set. In Proceedings of the 1998 IEEE Congress on Evolutionary Computation (CEC'98), pages 511--516, Piscataway, NJ, 1998.

[31]

G. Rudolph and A. Agapie. Convergence properties of some multi-objective evolutionary algorithms. In Proceedings of the 2000 IEEE Congress on Evolutionary Computation (CEC'00), pages 1010--1016, Piscataway, NJ, 2000.

[32]

W. Spears. Evolutionary Algorithms: The Role of Mutation and Recombination. Springer Verlag, Berlin, Germany, 2000.

Digital Library

[33]

D. Sudholt. Crossover is provably essential for the ising model on trees. In Proceedings of the 7th ACM Annual Conference on Genetic and Evolutionary Computation (GECCO'05), pages 1161--1167, Washington DC, 2005.

Digital Library

[34]

R. A. Watson. Analysis of recombinative algorithms on a non-separable building block problem. In Proceedings of the 6th International Workshop on Foundations of Genetic Algorithms (FOGA'00), pages 69--89. San Mateo, CA, 2000.

[35]

Y. Yu, C. Qian, and Z.-H. Zhou. Towards analyzing recombination operators in evolutionary search. In Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN'10), pages 144--153, Krakow, Poland, 2010.

Digital Library

[36]

Y. Yu and Z.-H. Zhou. A new approach to estimating the expected first hitting time of evolutionary algorithms. Artificial Intelligence, 172(15):1809--1832, 2008.

Digital Library

Cited By

Dang DOpris ASudholt D(2024)Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective OptimisationArtificial Intelligence10.1016/j.artint.2024.104098(104098)Online publication date: Feb-2024
https://doi.org/10.1016/j.artint.2024.104098
Antipov DKötzing TRadhakrishnan A(2024)Greedy Versus Curious Parent Selection for Multi-objective Evolutionary AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_6(86-101)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_6
Ren SBian CLi MQian C(2024)A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2)Parallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_19(295-312)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_19
Show More Cited By

Index Terms

An analysis on recombination in multi-objective evolutionary optimization
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On the effect of populations in evolutionary multi-objective optimization
GECCO '06: Proceedings of the 8th annual conference on Genetic and evolutionary computation

Multi-objective evolutionary algorithms (MOEAs) have become increasingly popular as multi-objective problem solving techniques. An important open problem is to understand the role of populations in MOEAs. We present a simple bi-objective problem which ...
An analysis on recombination in multi-objective evolutionary optimization

Evolutionary algorithms (EAs) are increasingly popular approaches to multi-objective optimization. One of their significant advantages is that they can directly optimize the Pareto front by evolving a population of solutions, where the recombination (...
Evolutionary Algorithms for Multi-Objective Optimization: Performance Assessments and Comparisons

Evolutionary techniques for multi-objective (MO) optimization are currently gaining significant attention from researchers in various fields due to their effectiveness and robustness in searching for a set of trade-off solutions. Unlike conventional methods ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '11: Proceedings of the 13th annual conference on Genetic and evolutionary computation

July 2011

2140 pages

ISBN:9781450305570

DOI:10.1145/2001576

Editor:
Natalio Krasnogor
University of Nottingham, UK
,
General Chair:
Pier Luca Lanzi
Politecnico di Milano, Italy

Copyright © 2011 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: 12 July 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '11

Sponsor:

SIGEVO

GECCO '11: Genetic and Evolutionary Computation Conference

July 12 - 16, 2011

Dublin, Ireland

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
190
Total Downloads

Downloads (Last 12 months)16
Downloads (Last 6 weeks)4

Reflects downloads up to 13 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Dang DOpris ASudholt D(2024)Crossover Can Guarantee Exponential Speed-Ups in Evolutionary Multi-Objective OptimisationArtificial Intelligence10.1016/j.artint.2024.104098(104098)Online publication date: Feb-2024
https://doi.org/10.1016/j.artint.2024.104098
Antipov DKötzing TRadhakrishnan A(2024)Greedy Versus Curious Parent Selection for Multi-objective Evolutionary AlgorithmsParallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_6(86-101)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_6
Ren SBian CLi MQian C(2024)A First Running Time Analysis of the Strength Pareto Evolutionary Algorithm 2 (SPEA2)Parallel Problem Solving from Nature – PPSN XVIII10.1007/978-3-031-70071-2_19(295-312)Online publication date: 7-Sep-2024
https://doi.org/10.1007/978-3-031-70071-2_19
Pliszka ZUnold O(2015)On the Ability of the One-Point Crossover Operator to Search the Space in Genetic AlgorithmsArtificial Intelligence and Soft Computing10.1007/978-3-319-19324-3_33(361-369)Online publication date: 2015
https://doi.org/10.1007/978-3-319-19324-3_33
Dinneen MWei K(2013)A (1+1) Adaptive Memetic Algorithm for the Maximum Clique Problem2013 IEEE Congress on Evolutionary Computation10.1109/CEC.2013.6557756(1626-1634)Online publication date: Jun-2013
https://doi.org/10.1109/CEC.2013.6557756
Doerr BKodric BVoigt M(2013)Lower bounds for the runtime of a global multi-objective evolutionary algorithm2013 IEEE Congress on Evolutionary Computation10.1109/CEC.2013.6557601(432-439)Online publication date: Jun-2013
https://doi.org/10.1109/CEC.2013.6557601
Zafra AVentura S(2012)Multi-objective approach based on grammar-guided genetic programming for solving multiple instance problemsSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-011-0794-016:6(955-977)Online publication date: 1-Jun-2012
https://dl.acm.org/doi/10.1007/s00500-011-0794-0

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.

Media

Figures

Other

Tables

View Table of Contents