License
When quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-14822
URL: http://drops.dagstuhl.de/opus/volltexte/2008/1482/
Go to the corresponding Portal


He, Jun ; Zhou, Yuren ; Yao, Xin

A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem

pdf-format:
Document 1.pdf (354 KB)


Abstract

Constraints exist in almost every optimization problem. Different constraint handling techniques have been incorporated with genetic algorithms (GAs), however most of current studies are based on computer experiments. An example is Michalewicz's comparison among GAs using different constraint handling techniques on the 0-1 knapsack problem. The following phenomena are observed in experiments: 1) the penalty method needs more generations to find a feasible solution to the restrictive capacity knapsack than the repair method; 2) the penalty method can find better solutions to the average capacity knapsack. Such observations need a theoretical explanation. This paper aims at providing a theoretical analysis of Michalewicz's experiments. The main result of the paper is that GAs using the repair method are more efficient than GAs using the penalty method on both restrictive capacity and average capacity knapsack problems. This result of the average capacity is a little different from Michalewicz's experimental results. So a supplemental experiment is implemented to support the theoretical claim. The results confirm the general principle pointed out by Coello: a better constraint-handling approach should tend to exploit specific domain knowledge.

BibTeX - Entry

@InProceedings{he_et_al:DSP:2008:1482,
  author =	{Jun He and Yuren Zhou and Xin Yao},
  title =	{A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem},
  booktitle =	{Theory of Evolutionary Algorithms},
  year =	{2008},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  number =	{08051},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1482},
  annote =	{Keywords: Genetic Algorithms, Constrained Optimization, Knapsack Problem, Computation Time, Performance Analysis}
}

Keywords: Genetic Algorithms, Constrained Optimization, Knapsack Problem, Computation Time, Performance Analysis
Seminar: 08051 - Theory of Evolutionary Algorithms
Issue Date: 2008
Date of publication: 06.05.2008


DROPS-Home | Fulltext Search | Imprint Published by LZI