License
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-2394
URL: http://drops.dagstuhl.de/opus/volltexte/2005/239/

Ishibuchi, Hisao

Effects of Crossover Operations on the Performance of EMO Algorithms

pdf-format:
Dokument 1.pdf (249 KB)


Abstract

This paper visually demonstrates the effect of crossover operations on the performance of EMO algorithms through computational experiments on multi-objective 0/1 knapsack problems. In our computational experiments, we use the NSGA-II algorithm as a representative EMO algorithm. First we compare the performance of the NSGA-II algorithm between two cases: NSGA-II with/without crossover. Experimental results show that the crossover operation has a positive effect on the convergence of solutions to the Pareto front and a negative effect on the diversity of solutions. That is, the crossover operation decreases the diversity of solutions while it improves the convergence of solutions to the Pareto front. Next we examine the effects of recombining similar or dissimilar parents using a similarity-based mating scheme. Experimental results show that the performance of the NSGA-II algorithm is improved by recombining similar parents and degraded by recombining dissimilar ones. Finally we show that the recombination of extreme and similar parents using the similarity-based mating scheme drastically improves the diversity of obtained non-dominated solutions without severely degrading their convergence to the Pareto front. An idea of dynamically controlling the selection pressure toward extreme and similar parents is also illustrated through computational experiments.

BibTeX - Entry

@InProceedings{ishibuchi:DSP:2005:239,
  author =	{Hisao Ishibuchi},
  title =	{Effects of Crossover Operations on the Performance of EMO Algorithms},
  booktitle =	{Practical Approaches to Multi-Objective Optimization},
  year =	{2005},
  editor =	{J{\"u}rgen Branke and Kalyanmoy Deb and Kaisa Miettinen and Ralph E. Steuer},
  number =	{04461},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2005/239},
  annote =	{Keywords: Evolutionary Multiobjective Optimization, Multiobjective 0/1 Knapsack Problems, Crossover Operations, Mating Restriction}
}

Keywords: Evolutionary Multiobjective Optimization, Multiobjective 0/1 Knapsack Problems, Crossover Operations, Mating Restriction
Seminar: 04461 - Practical Approaches to Multi-Objective Optimization
Issue date: 2005
Date of publication: 10.08.2005


DROPS-Home | Fulltext Search | Imprint Published by LZI