Advertisement

The Significance of the Evaluation Function in Evolutionary Algorithms

  • Zbigniew Michalewicz
Chapter
Part of the The IMA Volumes in Mathematics and its Applications book series (IMA, volume 111)

Abstract

The major component of any evolutionary algorithm is its evaluation function, which serves as a major link between the algorithm and the problem being solved. The evaluation function is used to distinguish between better and worse individuals in the population, hence it provides an important feedback for the search process. In this paper we survey a few typical methods for constructing an evaluation function for constrained optimization problems.

Key words

Constrained optimization evolutionary algorithms evaluation function infeasible individuals 

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. [1]
    Bean, J.C. and Hadj-Alouane, A.B. (1992), A Dual Genetic Algorithm for Bounded Integer Programs, Department of Industrial and Operations Engineering, The University of Michigan, TR 92–53.Google Scholar
  2. [2]
    Davis, L. (1987), Genetic Algorithms and Simulated Annealing, Morgan Kaufmann Publishers, Los Altos, CA, 1987.Google Scholar
  3. [3]
    Davis, L. (1991), Handbook of Genetic Algorithms, New York, Van Nostrand Reinhold.Google Scholar
  4. [4]
    Davis, L. (1997), Private communication. Google Scholar
  5. [5]
    De Jong, K.A. (1975), An Analysis of the Behavior of a Class of Genetic Adaptive Systems, Doctoral dissertation, University of Michigan, Dissertation Abstract International, 36(10), 5140В, (University Microfilms No 76–9381).Google Scholar
  6. [6]
    De Jong K.A. and W.M. Spears (1989), Using Genetic Algorithms to Solve NP-Complete Problems, In Proceedings of the Third International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, 124–132.Google Scholar
  7. [7]
    Falkenauer, E. (1994), A New Representation and Operators for GAs Applied to Grouping Problems, Evolutionary Computation, Vol. 2, No.2, 123–144.CrossRefGoogle Scholar
  8. [8]
    Fogel, L.J., A.J. Owens and M.J. Walsh (1966), Artificial Intelligence through Simulated Evolution, New York, Wiley.Google Scholar
  9. [9]
    Glover, F. (1977), Heuristics for Integer Programming Using Surrogate Constraints, Decision Sciences, Vol.8, No.1, 156–166.CrossRefGoogle Scholar
  10. [10]
    Glover, F. (1995), Tabu Search Fundamentals and Uses, Graduate School of Business, University of Colorado.Google Scholar
  11. [11]
    Homaifar, A., S. H.-Y. Lai and X. Qi (1994), Constrained Optimization via Genetic Algorithms, Simulation, Vol.62, 242–254.CrossRefGoogle Scholar
  12. [12]
    Joines, J.A. and C.R. Houck (1994), On the Use of Non-Stationary Penalty Functions to Solve Nonlinear Constrained Optimization Problems With GAs, In Proceedings of the Evolutionary Computation Conference-Poster Sessions, part of the IEEE World Congress on Computational Intelligence, Orlando, 27–29, June 1994, 579–584.Google Scholar
  13. [13]
    Koza, J. R. (1992), Genetic Programming, Cambridge, MA, MIT Press.Google Scholar
  14. [14]
    Le Riche, R., C. Vayssade, R. T. Haftka (1995), A Segregated Genetic Algorithm for Constrained Optimization in Structural Mechanics, Technical Report, Universite de Technologie de Compiegne, France.Google Scholar
  15. [15]
    Michalewicz, Z. (1996), Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag, 3rd edition, New York.zbMATHGoogle Scholar
  16. [16]
    Michalewicz, Z. and N. Attia (1994), In Evolutionary Optimization of Constrained Problems, Proceedings of the 3rd Annual Conference on Evolutionary Programming, eds. A. V. Sebald and L. J. Fogel, River Edge, NJ, World Scientific Publishing, 98–108.Google Scholar
  17. [17]
    Michalewicz, Z. and C. Janixow (1991), Handling Constraints in Genetic Algorithms, In Proceedings of the Fourth International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, 151–157.Google Scholar
  18. [18]
    Michalewtcz, Z. and Nazhiyath, G. (1995), Genocop III: A Co-evolutionary Algorithm for Numerical Optimization Problems with Nonlinear Constraints, In Proceedings of the 2nd IEEE International Conference on Evolutionary Computation, Perth, 29 November - 1 December 1995.Google Scholar
  19. [19]
    Michalewicz, Z., Nazhiyath, G., and Michalewicz, M. (1996), A Note on Usefulness of Geometrical Crossover for Numerical Optimization Problems, In Proceedings of the 5th Annual Conference on Evolutionary Programming, L. J. Fogel, P. J. Angeline, and T. Baeck (eds.), MIT Press, Cambridge, MA, 1996, 305–312.Google Scholar
  20. [20]
    Michalewicz, Z., G.A. Vignaux, and M. Hobbs (1991), A Non-Standard Genetic Algorithm for the Nonlinear Transportation Problem, ORSA Journal on Computing, Vol.3, No. 4, 1991, 307–316.CrossRefGoogle Scholar
  21. [21]
    Michalewicz, Z. and J. Xiao (1995), Evaluation of Paths in Evolutionary Planner/ Navigator, In Proceedings of the 1995 International Workshop on Biologically Inspired Evolutionary Systems, Tokyo, Japan, May 30–31, 1995, 45–52.Google Scholar
  22. [22]
    Orvosh, D. and L. Davis (1993), Shall We Repair? Genetic Algorithms, Combinatorial Optimization, and Feasibility Constraints, In Proceedings of the Fifth International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, 650.Google Scholar
  23. [23]
    Paechter, B., A. Cumminc, H. Luchian, and M. Petriuc (1994), Two Solutions to the General Timetable Problem Using Evolutionary Methods, In Proceedings of the IEEE International Conference on Evolutionary Computation, 27–29 June 1994, 300–305.Google Scholar
  24. [24]
    Palmer, C. C. and A. Kershenbaum (1994), Representing Trees in Genetic Algorithms, In Proceedings of the IEEE International Conference on Evolutionary Computation, 27–29 June 1994, 379–384.Google Scholar
  25. [25]
    Pardalos, P. (1994), On the Passage from Local to Global in Optimization, In Mathematical Programming, J.R. Birge and K.G. Murty (Editors), The University of Michigan, 1994.Google Scholar
  26. [26]
    Powell, D. and M.M. Skolnick (1993), Using Genetic Algorithms in Engineering Design Optimization with Non-linear Constraints, In Proceedings of the Fifth International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, 424–430.Google Scholar
  27. [27]
    Richardson, J. T., M. R. Palmer, G. Liepins and M. Hilliard (1989), Some Guidelines for Genetic Algorithms with Penalty Functions, In Proceedings of the Third International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, 191–197.Google Scholar
  28. [28]
    Schoenauer, M. and Michalewicz, Z. (1996), Evolutionary Computation at the Edge of Feasibility, In Proceedings of the 4th Parallel Problem Solving from Nature, H. M. Voigt, W. Ebeling, I. Rechenberg, and H. P. Schwefel (Editors), Berlin, September 22–27, 1996, Springer-Verlag, Lecture Notes in Computer Science, Vol. 1141, 245–254.CrossRefGoogle Scholar
  29. [29]
    Schoenauer, M. and Michalewicz, Z. (1997), Boundary Operators for Constrained Parameter Optimization Problems, In Proceedings of the 7th International Conference on Genetic Algorithms, East Lansing, Michigan, July 19–23, 1997.Google Scholar
  30. [30]
    Siedleciu, W. and J. Sklanski (1989), Constrained Genetic Optimization via Dynamic Reward-Penalty Balancing and Its Use in Pattern Recognition, In Proceedings of the Third International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, 141–150.Google Scholar
  31. [31]
    Smith, A.E. and D.M. Tate (1993), Genetic Optimization Using a Penalty Function, In Proceedings of the Fifth International Conference on Genetic Algorithms, 499–503, Urbana-Champaign, CA: Morgan Kaufmann.Google Scholar
  32. [32]
    Whitley, D., V.S. Gordon, and K. Mathias (1994), Lamarckian Evolution, the Baldwin Effect and function Optimization, In Proceedings of the Parallel Problem Solving from Nature, 3, Springer-Verlag, New York, 6–15.Google Scholar

Copyright information

© Springer Science+Business Media New York 1999

Authors and Affiliations

  • Zbigniew Michalewicz
    • 1
    • 2
  1. 1.Department of Computer ScienceUniversity of North CarolinaCharlotteUSA
  2. 2.Institute of Computer SciencePolish Academy of SciencesWarsawPoland

Personalised recommendations