An efficient constraint handling method for genetic algorithms
K. Deb. Computer Methods in Applied Mechanics and Engineering, 186 (2-4):
311--338(June 2000)
Abstract
Many real-world search and optimization problems involve inequality
and/or equality constraints and are thus posed as constrained optimization
problems. In trying to solve constrained optimization problems using
genetic algorithms (GAs) or classical optimization methods, penalty
function methods have been the most popular approach, because of
their simplicity and ease of implementation. However, since the penalty
function approach is generic and applicable to any type of constraint
(linear or nonlinear), their performance is not always satisfactory.
Thus, researchers have developed sophisticated penalty functions
specific to the problem at hand and the search algorithm used for
optimization. However, the most difficult aspect of the penalty function
approach is to find appropriate penalty parameters needed to guide
the search towards the constrained optimum. In this paper, GA's population-based
approach and ability to make pair-wise comparison in tournament selection
operator are exploited to devise a penalty function approach that
does not require any penalty parameter. Careful comparisons among
feasible and infeasible solutions are made so as to provide a search
direction towards the feasible region. Once sufficient feasible solutions
are found, a niching method (along with a controlled mutation operator)
is used to maintain diversity among feasible solutions. This allows
a real-parameter GA's crossover operator to continuously find better
feasible solutions, gradually leading the search near the true optimum
solution. GAs with this constraint handling approach have been tested
on nine problems commonly used in the literature, including an engineering
design problem. In all cases, the proposed approach has been able
to repeatedly find solutions closer to the true optimum solution
than that reported earlier.
%0 Journal Article
%1 DebK_00_eff
%A Deb, Kalyanmoy
%D 2000
%J Computer Methods in Applied Mechanics and Engineering
%K constrained, genetic-algorithms, optimization
%N 2-4
%P 311--338
%T An efficient constraint handling method for genetic algorithms
%U http://www.sciencedirect.com/science/article/B6V29-40CRYKF-B/2/d6ddd61a547493fbb99a7b9f25405d85
%V 186
%X Many real-world search and optimization problems involve inequality
and/or equality constraints and are thus posed as constrained optimization
problems. In trying to solve constrained optimization problems using
genetic algorithms (GAs) or classical optimization methods, penalty
function methods have been the most popular approach, because of
their simplicity and ease of implementation. However, since the penalty
function approach is generic and applicable to any type of constraint
(linear or nonlinear), their performance is not always satisfactory.
Thus, researchers have developed sophisticated penalty functions
specific to the problem at hand and the search algorithm used for
optimization. However, the most difficult aspect of the penalty function
approach is to find appropriate penalty parameters needed to guide
the search towards the constrained optimum. In this paper, GA's population-based
approach and ability to make pair-wise comparison in tournament selection
operator are exploited to devise a penalty function approach that
does not require any penalty parameter. Careful comparisons among
feasible and infeasible solutions are made so as to provide a search
direction towards the feasible region. Once sufficient feasible solutions
are found, a niching method (along with a controlled mutation operator)
is used to maintain diversity among feasible solutions. This allows
a real-parameter GA's crossover operator to continuously find better
feasible solutions, gradually leading the search near the true optimum
solution. GAs with this constraint handling approach have been tested
on nine problems commonly used in the literature, including an engineering
design problem. In all cases, the proposed approach has been able
to repeatedly find solutions closer to the true optimum solution
than that reported earlier.
@article{DebK_00_eff,
abstract = {Many real-world search and optimization problems involve inequality
and/or equality constraints and are thus posed as constrained optimization
problems. In trying to solve constrained optimization problems using
genetic algorithms (GAs) or classical optimization methods, penalty
function methods have been the most popular approach, because of
their simplicity and ease of implementation. However, since the penalty
function approach is generic and applicable to any type of constraint
(linear or nonlinear), their performance is not always satisfactory.
Thus, researchers have developed sophisticated penalty functions
specific to the problem at hand and the search algorithm used for
optimization. However, the most difficult aspect of the penalty function
approach is to find appropriate penalty parameters needed to guide
the search towards the constrained optimum. In this paper, GA's population-based
approach and ability to make pair-wise comparison in tournament selection
operator are exploited to devise a penalty function approach that
does not require any penalty parameter. Careful comparisons among
feasible and infeasible solutions are made so as to provide a search
direction towards the feasible region. Once sufficient feasible solutions
are found, a niching method (along with a controlled mutation operator)
is used to maintain diversity among feasible solutions. This allows
a real-parameter GA's crossover operator to continuously find better
feasible solutions, gradually leading the search near the true optimum
solution. GAs with this constraint handling approach have been tested
on nine problems commonly used in the literature, including an engineering
design problem. In all cases, the proposed approach has been able
to repeatedly find solutions closer to the true optimum solution
than that reported earlier.},
added-at = {2008-06-26T18:58:40.000+0200},
author = {Deb, Kalyanmoy},
biburl = {https://www.bibsonomy.org/bibtex/24d4ad6f162911b30d58cc1da37f61886/jacquenot},
citeulike-article-id = {1284746},
folder = {Theory/Optimization_methods/Evolutionary_Algorithms/Genetic_Algorithms},
interhash = {adbf305052bbfee9ebfdb412e869e9a3},
intrahash = {4d4ad6f162911b30d58cc1da37f61886},
journal = {Computer Methods in Applied Mechanics and Engineering},
keywords = {constrained, genetic-algorithms, optimization},
month = {June},
number = {2-4},
owner = {jacquenot},
pages = {311--338},
timestamp = {2008-06-26T18:58:41.000+0200},
title = {An efficient constraint handling method for genetic algorithms},
url = {http://www.sciencedirect.com/science/article/B6V29-40CRYKF-B/2/d6ddd61a547493fbb99a7b9f25405d85},
volume = 186,
year = 2000
}