×

Constraint handling in genetic algorithms using a gradient-based repair method. (English) Zbl 1086.90058

Summary: Constraint handling is one of the major concerns when applying genetic algorithms (GAs) to solve constrained optimization problems. This paper proposes to use the gradient information derived from the constraint set to systematically repair infeasible solutions. The proposed repair procedure is embedded into a simple GA as a special operator. Experiments using 11 benchmark problems are presented and compared with the best known solutions reported in the literature. Our results are competitive, if not better, compared to the results reported using the homomorphous mapping method, the stochastic ranking method, and the self-adaptive fitness formulation method.

MSC:

90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Goldberg, D., Genetic algorithms in search, optimization, and machine learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056
[2] Liu, B., Theory and practice of uncertain programming (2002), Physica-Verlag, Springer: Physica-Verlag, Springer Wurzburg, Berlin · Zbl 1029.90084
[3] Coello Coello, C. A., Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art, Computer Methods in Applied Mechanics and Engineering, 191, 11, 1245-1287 (2002) · Zbl 1026.74056
[4] Koziel, S.; Michaelwicz, Z., Evolutionary algorithms, homomorphous mappings, and constrained parameter optimization, Evolutionary Computation, 7, 1, 19-44 (1999)
[5] Joines J, Houck C. On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GAs. Proceedings of the first IEEE conference on evolutionary computation; 1994. p. 579-84.; Joines J, Houck C. On the use of non-stationary penalty functions to solve nonlinear constrained optimization problems with GAs. Proceedings of the first IEEE conference on evolutionary computation; 1994. p. 579-84.
[6] Coello, C. A., Use of a self-adaptive penalty approach for engineering optimization problem, Computers in Industry, 41, 2, 113-127 (2000)
[7] Homaifar, A.; Qi, C. X.; Lai, S. H., Constrained optimization via genetic algorithms, Simulation, 62, 4, 242-253 (1994)
[8] Runarsson, T. P.; Yao, X., Stochastic ranking for constrained evolutionary optimization, IEEE Transactions on Evolutionary Computation, 4, 3, 284-294 (2000)
[9] Farmani, R.; Wright, J. A., Self-adaptive fitness formulation for constrained optimization, IEEE Transactions on Evolutionary Computation, 7, 5, 445-455 (2003)
[10] Orvosh D, Davis L. Using a genetic algorithm to optimize problem with feasibility constraints. Proceedings of the first IEEE conference on evolutionary computation; 1994. p. 548-53.; Orvosh D, Davis L. Using a genetic algorithm to optimize problem with feasibility constraints. Proceedings of the first IEEE conference on evolutionary computation; 1994. p. 548-53.
[11] Chu, P. C.; Beasley, J. E., Constraint handling in genetic algorithm: the set partitioning problem, Journal of Heuristics, 11, 323-357 (1998) · Zbl 1071.90573
[12] Kim, J.-H.; Myung, H., Evolutionary programming techniques for constrained optimization problems, IEEE Transactions on Evolutionary Computation, 1, 2, 129-140 (1997)
[13] Adeli, H.; Cheng, N.-T., Augmented Lagrangian genetic algorithm for structural optimization, Journal of Aerospace Engineering, 7, 1, 104-118 (1994)
[14] Van Le T. A fuzzy evolutionary approach to constrained optimization problems. Proceedings of the second IEEE conference on evolutionary computation; 1995. p. 274-8.; Van Le T. A fuzzy evolutionary approach to constrained optimization problems. Proceedings of the second IEEE conference on evolutionary computation; 1995. p. 274-8.
[15] Surry PD, Radcliffe NJ, Boyd ID. A multi-objective approach to constrained optimization of gas supply network: the COMOGA method. In: Fogarty TC, editor. Evolutionary computing. AISB workshop, Selected papers, Lecture notes in computer science; 1995. p. 166-80.; Surry PD, Radcliffe NJ, Boyd ID. A multi-objective approach to constrained optimization of gas supply network: the COMOGA method. In: Fogarty TC, editor. Evolutionary computing. AISB workshop, Selected papers, Lecture notes in computer science; 1995. p. 166-80.
[16] Ray T, Kang T, Chye SK. An evolutionary algorithm for constrained optimization. Proceedings of the genetic and evolutionary computation conference; 2000. p. 771-7.; Ray T, Kang T, Chye SK. An evolutionary algorithm for constrained optimization. Proceedings of the genetic and evolutionary computation conference; 2000. p. 771-7.
[17] Griewank, A.; Corliss, G. F., Automatic differentiation of algorithms: theory, implementation, and application (1991), SIAM: SIAM Philadelphia
[18] Campbell, S. L.; Meyer, C. D., Generalized inverses of linear transformations (1991), Dover Press: Dover Press New York · Zbl 0732.15003
[19] Michaelwicz, Z.; Schoenauer, M., Evolutionary computation for constrained parameter optimization problems, Evolutionary Computation, 4, 1, 1-32 (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.