zbMATH — the first resource for mathematics

An efficient constraint handling method for genetic algorithms. (English) Zbl 1028.90533
Summary: 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.

MSC:
 90C30 Nonlinear programming 90C59 Approximation methods and heuristics in mathematical programming
Full Text:
References:
 [1] Deb, K., Optimization for engineering design: algorithms and examples, (1995), Prentice-Hall New Delhi [2] Reklaitis, G.V.; Ravindran, A.; Ragsdell, K.M., Engineering optimization methods and applications, (1983), Wiley New York [3] Homaifar, A.; Lai, S.H.-V.; Qi, X., Constrained optimization via genetic algorithms, Simulation, 62, 4, 242-254, (1994) [4] J.A. Joines, C.R. Houck, On the use of nonstationary penalty functions to solve nonlinear constrained optimization problems with GAs, in: Z. Michalewicz (Ed.), Proceedings of the International Conference on Evolutionary Computation, IEEE Press, Piscataway, 1994, pp. 579-584 [5] Z. Michalewicz, N. Attia, Evolutionary optimization of constrained problems, in: A.V. Sebald, L.J. Fogel (Eds.), Proceedings of the Third Annual Conference on Evolutionary Programming, World Scientific, Singapore, 1994, pp. 98-108 [6] Z. Michalewicz, Genetic algorithms, numerical optimization, and constraints, in: L. Eshelman (Ed.), Proceedings of the Sixth International Conference on Genetic Algorithms, Morgan Kauffman, San Mateo, 1995, pp. 151-158 [7] Michalewicz, Z.; Schoenauer, M., Evolutionary algorithms for constrained parameter optimization problems, Evolutionary computation, 4, 1, 1-32, (1996) [8] D. Powell, M.M. Skolnick, Using genetic algorithms in engineering design optimization with nonlinear constraints, in: S. Forrest (Ed.), Proceedings of the Fifth International Conference on Genetic Algorithms, Morgan Kauffman, San Mateo, 1993, pp. 424-430 [9] Deb, K., Optimal design of a welded beam structure via genetic algorithms, AIAA journal, 29, 11, 2013-2015, (1991) [10] Kim, J-H.; Myung, H., Evolutionary programming techniques for constraint optimization problems, IEEE transcations on evolutionary computation, 1, 2, 129-140, (1997) [11] D.E. Goldberg, Personal communication, September 1992 [12] J.T. Richardson, M.R. Palmer, G. Liepins, M. Hilliard, Some guidelines for genetic algorithms with penalty functions, in: J.D. Schaffer (Ed.), Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kauffman, San Mateo, 1989, pp. 191-197 [13] Z. Michalewicz, Personal communication, June 1998 [14] Deb, K.; Agrawal, R.B., Simulated binary crossover for continuous search space, Complex systems, 9, 115-148, (1995) · Zbl 0843.68023 [15] Deb, K.; Goyal, M., A combined genetic adaptive search (geneas) for engineering design, Computer science and informatics, 26, 4, 30-45, (1996) [16] K. Deb, D.E. Goldberg, An investigation of niche and species formation in genetic function optimization, in: J.D. Schaffer (Ed.), Proceedings of the Third International Conference on Genetic Algorithms, Morgan Kauffman, San mateo, 1989, pp. 42-50 [17] Goldberg, D.E., Genetic algorithms in search, optimization, and machine learning, (1989), Addison-Wesley Reading, MA · Zbl 0721.68056 [18] Rechenberg, I., Evolutionsstrategie: optimierung technischer systeme nach prinzipien der biologischen evolution, (1973), Frommann-Holzboog Verlag Stuttgart [19] Schwefel, H.-P., Numerical optimization of computer models, (1983), Wiley New York [20] Deb, K.; Kumar, A., Real-coded genetic algorithms with simulated binary crossover: studies on multimodal and multiobjective problems, Complex systems, 9, 6, 431-454, (1995) [21] Goldberg, D.E.; Deb, K.; Clark, J.H., Genetic algorithms, noise, and the sizing of populations, Complex systems, 6, 333-362, (1992) · Zbl 0800.68600 [22] G. Harik, E. Cantu-Paz, D.E. Goldberg, B.L. Miller, The gambler’s ruin problem, genetic algorithms, and the sizing of populations, in: T. Bäck, Z. Michalewicz, X. Yao (Eds.), Proceedings of the 1997 IEEE International Conference on Evolutionary Computation, IEEE Press, Piscataway, 1997, pp. 7-12 [23] Himmelblau, D.M., Applied nonlinear programming, (1972), McGraw-Hill New York · Zbl 0521.93057 [24] W. Hock, K. Schittkowski, Test Examples for Nonlinear Programming Code, Lecture Notes on Economics and Mathematical Systems, vol. 187, Springer-Verlag, Berlin, 1981 · Zbl 0452.90038
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.