2026-07-22T22:18:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:1482 2024-03-06T11:07:55Z ddc:004 open_access

A Comparison of GAs Penalizing Infeasible Solutions and Repairing Infeasible Solutions on the 0-1 Knapsack Problem He, Jun Zhou, Yuren Yao, Xin Genetic Algorithms Constrained Optimization Knapsack Problem Computation Time Performance Analysis 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jun He and Yuren Zhou and Xin Yao 2008 Is Part Of Dagstuhl Seminar Proceedings, Volume 8051, Theory of Evolutionary Algorithms (2008) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.08051.3 urn:nbn:de:0030-drops-14822 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08051.3 eng https://creativecommons.org/licenses/by/4.0/legalcode