Quality-time analysis of multi-objective evolutionary algorithms

Jian Hung Chen*, Shinn-Ying Ho, David E. Goldberg

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A quality-time analysis of multi-objective evolutionary algorithms (MOEAs) based on schema theorem and building blocks hypothesis is developed. A bicriteria OneMax problem, a hypothesis of niche and species, and a definition of dissimilar schemata are introduced for the analysis. In this paper, the convergence time, the first and last hitting time models are constructed for analyzing the performance of MOEAs. Population sizing model is constructed for determining appropriate population sizes. The models are verified using the bicriteria OneMax problem. The theoretical results indicate how the convergence time and population size of a MOEA scale up with the problem size, the dissimilarity of Pareto-optimal solutions, and the number of Pareto-optimal solutions of a multi-objective optimization problem.

Original languageEnglish
Title of host publicationGECCO 2005 - Genetic and Evolutionary Computation Conference
EditorsH.G. Beyer, U.M. O'Reilly, D. Arnold, W. Banzhaf, C. Blum, E.W. Bonabeau, E. Cantu-Paz, D. Dasgupta, K. Deb, al et al
Pages1455-1462
Number of pages8
DOIs
StatePublished - 1 Dec 2005
EventGECCO 2005 - Genetic and Evolutionary Computation Conference - Washington, D.C., United States
Duration: 25 Jun 200529 Jun 2005

Publication series

NameGECCO 2005 - Genetic and Evolutionary Computation Conference

Conference

ConferenceGECCO 2005 - Genetic and Evolutionary Computation Conference
CountryUnited States
CityWashington, D.C.
Period25/06/0529/06/05

Keywords

  • Convergence
  • Dissimilar schemata
  • Multi-objective evolutionary algorithms
  • Population sizing

Fingerprint Dive into the research topics of 'Quality-time analysis of multi-objective evolutionary algorithms'. Together they form a unique fingerprint.

  • Cite this

    Chen, J. H., Ho, S-Y., & Goldberg, D. E. (2005). Quality-time analysis of multi-objective evolutionary algorithms. In H. G. Beyer, U. M. O'Reilly, D. Arnold, W. Banzhaf, C. Blum, E. W. Bonabeau, E. Cantu-Paz, D. Dasgupta, K. Deb, & A. et al (Eds.), GECCO 2005 - Genetic and Evolutionary Computation Conference (pp. 1455-1462). (GECCO 2005 - Genetic and Evolutionary Computation Conference). https://doi.org/10.1145/1068009.1068240