Evolutionary Algorithms for Constrained Parameter Optimization Problems

Evolutionary Computation - Tập 4 Số 1 - Trang 1-32 - 1996
Zbigniew Michalewicz1, Marc Schoenauer2
1University of North Carolina, Charlotte
2Centre de Mathématiques Appliquées - Ecole Polytechnique

Tóm tắt

Evolutionary computation techniques have received a great deal of attention regarding their potential as optimization techniques for complex numerical functions. However, they have not produced a significant breakthrough in the area of nonlinear programming due to the fact that they have not addressed the issue of constraints in a systematic way. Only recently have several methods been proposed for handling nonlinear constraints by evolutionary algorithms for numerical optimization problems; however, these methods have several drawbacks, and the experimental results on many test cases have been disappointing. In this paper we (1) discuss difficulties connected with solving the general nonlinear programming problem; (2) survey several approaches that have emerged in the evolutionary computation community; and (3) provide a set of 11 interesting test cases that may serve as a handy reference for future methods.

Từ khóa


Tài liệu tham khảo

Back, T., Hoffmeister, F. & Schwefel, H.P. (199 1). A survey of evolution strategies. In R. K. Belew & L. B. Booker (Eds.), Pmceedizgs of the Fourth lntemational Conference on Genetic Algorithms (pp. 2-9). San Mateo, CA: Morgan Kaufmann.

Bean, J. C. & Hadj-Alouane, A. B. (1992). Adiialgeizeticalgoritbmforboll?zded integerprogr-ams. Technical Report T R 92-53, Ann Arbor, MI: University ofMichigan, Department of Industrial and Operations Engineering.

Bilchev, G. (1995). Private communication.

Bilchev, G. & Parmee, I. (1995). Ant colony search vs. genetic algorithms. Technical Report. Plymouth, UK: University of Plymouth, Plymouth Engineering Design Centre.

Colorni, A., Dorigo, M. & Maniezzo, V. (1991). Distributed optimization by ant colonies. In P. Bourgine & F. Varela (Eds.), Aaceedingsof the First European Coizference o n Artificial L i f . Cambridge, MA: M I T PresdBradford Books.

Davis, L. (1989). Adapting operator probabilities in genetic algorithms. In J. D. Schaffer (Ed.), Proccedivzgs of the Third Intematio2nl Conference on Genetic Algorithms (pp. 61-69). San Mateo, CA: Morgan Kaufmann.

Davis, L. (1995) Private communication.

De Jong, K. (1 975). The adysi.s ofthe bebanior- of a clnss ofgenetic adaptive systems. Doctoral dissertation, University of Michigan, Ann Arbor. L)i.rseitatim~ Abstl-acts htematiowal,6( lo), 5 140B. (University Microfilms No 76-9381).

Eiben, A., Raue, P.E. & Ruttkay, Z. (1994). Genetic algorithms with multi-parent recombination. In Y. Davidor, H.P. Schwefel, & R. MCnner (Eds.), Proceedings ojtbe Third Conference o n Paidlel Problem Solvingfi-om Napwe, Volume 866 of Lectwe Notes in Computer Science (pp. 78-87). Berlin: Springer-Verlag.

Eshelman, L. & Schaffer, J. D. (1993). Real-coded genetic algorithms and interval-schemata. In L. D. Whitley (Ed.), Foendntionr of Genetic Algovithms 2 (pp. 187-202). Los Altos, CA: Morgan Kaufmann. parameter spaces. In Paceediizgs of the Third Annual Confkreie on Euokitioizaiy Progrumviing (pp. 84-97). River Edge, NJ: World Scientific.

Michalewicz, Z. & Nazhiyath, G. (1995). Genocop 111: A co-evolutionary algorithm for numerical optimization problems with nonlinear constraints. In D. B. Fogel (Ed.), PF-oceedingsof the Second IEEE bzteinntional Coizfererice o?a Eziokitionaiy Compiitation (pp. 647-65 1). Piscataway, NJ: IEEE Press.

Michalewicz, Z., Nazhiyath, G. & Michalewicz, M. (1996). A note on usefulness of geometrical crossover for numerical optimization problems. In P. J. Angeline & T. Back (Eds.), Proceediizgs ofthe Ftfth A?zmal Conference on Eziohtionaiy Programming. Cambridge, MA: M I T Press. In press.

Muhlenbein, H. & Voigt, HI.M. (1995). Gene pool recombination for the breeder genetic algorithm. In Proceedings of the 1nteirr.ational Couference on i21etaheiiristicsfor Optimization (pp. 19-2 5 ) . ilordrecht, The Netherlands: Kluwer Publishing.

Myung, H., Kim, J.H. & Fogel, D. (1995). Preliminary investigation into a two-stage method of evolutionary optimization on constrained problems. in J. R. McDonnell, R. G. Reynolds, & D. B. Fogel (Eds.), Proceediugr of the Foirith Allllllal Coizference 011 Evoliitiomq Progr-amming (pp. 449-463). Cambridge, MA: M I T Press.

Orvosh, D. & Davis, L. (1993). Shall we repair? Genetic algorithms, combinatorial optimization, and feasibility constraints. In S. Forrest (Ed.), Proceedings ofthe Fifth Intei7zntio?zal Coi$erencr on Gemtic Algorithms (p. 650). San Mateo, CA: Morgan Kaufmann.

Paredis, J. ( I 994). Coevolutionary constraint satisfaction. In Y. Davidor, H.P. Schwefel, & R. Manner (Eds.), Proceedings of the Third Coi$ei.eizce on Parallel Problem SolzGngfi-om Nature (pp. 46-55). Berlin: Springer-Verlag.

Parrnee, I. & Purchase, G. (1994). The development of directed genetic search technique for heavily constrained design spaces. In Proceedings of the Collfel-ence on Adaptiue Computing ii7 Engineering Desig-17 mid Control (pp. 97-102). Plymouth, UK: University of Plymouth.

Powell, D. & Skolnick, M. M. (1993). Using genetic algorithms in engineering design optimization with non-linear constraints. In S. Forrest (Ed.), Proceedings of the Fifth bzteirzntional Coifereiice 077 Genetic Algorithms (pp. 424-430). San Mateo, CA: Morgan Kaufmann.

Renders, J.M. & Bersini, H. (1 994). Hybridizing genetic algorithms with hill-climbing methods for global optimization: Two possible ways. In 2. Michalewicz, J. D. Schaffer, 11.P. Schwefel, D. B. Fogel, & H . Kitano (Eds.), Pruceedi7gr of the Fiirt IEEE Inte?rzatio?znl Coifereme o n Evolritioizniy Compitutioiz (pp. 3 12-3 17). Piscataway, NJ: IFXE Press.

Keynolds R., 1994, Proceedings ofthe Third Amial Coizfererzce 011 Ezioliitionaty Programming (pp., 13, 1

Reynolds, R., Michalewicz, Z. & Cavaretta, M. (1995). Using cultural algorithms for constraint handling in Genocop. In J. R. McDonnell, R. G. Reynolds, & D. B. Fogel (Eds.), Proceedings ofthe Fourth Anma1 Coizfereizce on Evolutionary A-ogramming (pp. 298-305). Cambridge, MA: M I T Press.

Richardson, J. T, Palmer, M. R., Liepins, G. & Hilliard, M. (1989). Some guidelines for genetic algorithms with penalty functions. In J. D. Schaffer (Ed.), Proceedingr of the Third 17ztei7zatioiml Coizference 017 Genetic Algorithms (pp. 191-197). San Mateo, CA: Morgan Kaufmann.

Schaffer, D. (1985). Multiple objective optimization with vector evaluated genetic algorithms. In J. J. Grefenstette (Ed.), Proceedings of" the First Inteirzational Corzference on Genetic Algorithms. New York: Laurence Erlbaum Associates.

Schoenauer, M. & Michalewicz, Z. (1996). Evolutionary computation at the edge of feasibility. In W. Ebeling & H.M. Voigt (Eds.), Paceediizgs of the Foziith Corzfeiwzee on Parallel Problem Solvingfi-om Natzire. Berlin: Springer-Verlag.