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

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.