License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.08051.3
URN: urn:nbn:de:0030-drops-14822
URL: http://dagstuhl.sunsite.rwth-aachen.de/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:
08051.HeJun.Paper.1482.pdf (0.3 MB)

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:DagSemProc.08051.3,
  author =	{He, Jun and Zhou, Yuren and Yao, Xin},
  title =	{{A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem}},
  booktitle =	{Theory of Evolutionary Algorithms},
  pages =	{1--39},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8051},
  editor =	{Dirk V. Arnold and Anne Auger and Jonathan E. Rowe and Carsten Witt},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2008/1482},
  URN =		{urn:nbn:de:0030-drops-14822},
  doi =		{10.4230/DagSemProc.08051.3},
  annote =	{Keywords: Genetic Algorithms, Constrained Optimization, Knapsack Problem, Computation Time, Performance Analysis}
}

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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI