An Investigation of GA Performance Results for Different Cardinality Alphabets

  • Jackie Rees
  • Gary J. Koehler
Part of the The IMA Volumes in Mathematics and its Applications book series (IMA, volume 111)


Theoretical and empirical results give mixed advice for choosing the cardinality for GA representation. Using GA models that capture the exact expected behavior of both the binary and higher cardinality cases, the determination of which representation is best for a given GA can be made. De Jong et al. and Spears and De Jong presented how the exact model for the binary genetic algorithm can give important insights to transient GA behavior. This paper uses a similar approach to study the impact of different cardinalities using the Koehler-Bhattacharyya-Vose general cardinality model.


Genetic Algorithm Crossover Rate String Length Simple Genetic Algorithm Expected Wait Time 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. [1]
    Antonisse, J., A New Interpretation of Schema Notation that Overturns the Binary Encoding Constraint, Proceedings of the Third International Conference on Genetic Algorithms, Ed. J.D. Schaffer, Morgan Kaufmann, San Francisco, 1989, pp. 86–97.Google Scholar
  2. [2]
    Bhaacaryya, S. and G.J. Koehler, An Analysis of Genetic Algorithms of Cardinality 2v, Complex Systems, 8, 1994, pp. 227–256.MathSciNetGoogle Scholar
  3. [3]
    Davis, L., Handbook of Genetic Algorithms, 1991, Van Nostrand Reinhold, New York.Google Scholar
  4. [4]
    Davis, T., Toward an Extrapolation of the Simulated Annealing Convergence Theory onto the Simple Genetic Algorithm, 1991, Dissertation, University of Florida.Google Scholar
  5. [5]
    De Jong, K., An analysis of the Behavior of a Class of Genetic Adaptive Sytems, PhD Thesis, 1975, University of Michigan, Department of Computer and Communication Sciences, Ann Arbor, MI.Google Scholar
  6. [6]
    De Jong, K.A., W.M. Spears and D.F. Gordon, Using Markov Chains to Analyze GAFOs, in Foundations of Genetic Algorithms, 3, 1995, Morgan Kaufmann, San Francisco, pp. 115–137.Google Scholar
  7. [7]
    Deb, K. and D.E. Goldberg, Analyzing Deception in Trap Functions, Foundations of Genetic Algorithms 2, Ed. L. Darrell Whitley, 1993, Morgan Kaufman, San Francisco, pp. 93–108.Google Scholar
  8. [8]
    Holland, J.H.,Adaptationin Natural and Artificial Systems, University of Michigan Press, Ann Arbor, 1975.Google Scholar
  9. [9]
    Koehler, G.J., Computing Simple GA Expected Waiting Times, in review, January, 1997, College of Business, BUS 351, University of Florida, Gainesville, FL 32611.Google Scholar
  10. [10]
    Koeuler, G.J., S. Bhattacharyya, and M. Vose, General Cardinality Genetic Algorithms, in review, No. 95–06–101, College of Business, BUS 351, University of Florida, Gainesville, FL 32611.Google Scholar
  11. [11]
    Mason, A.J.,Partition Coefficients Static Deception and Deceptive Problems for Non-Binary Alphabets, Proceedings of the Fourth International Conference on Genetic Algorithms, Ed. R.K. Belew and L.B. Booker, Morgan Kaufmann, San Francisco, 1991, pp. 210–214.Google Scholar
  12. [12]
    Nix, A. and M.D. Vose, Modeling Genetic Algorithms with Markov Chains, Annals of Mathematics and Artificial Intelligence, 5, 1992, pp. 79–88.MathSciNetzbMATHCrossRefGoogle Scholar
  13. [13]
    Shaffer, J.D., Some Experiments in Machine Learning using Vector Evaluated Genetic Algorithms, Dissertation, 1984, CS Department, Vanderbilt University, Nashville, TN.Google Scholar
  14. [14]
    Spears, W.M. and K.A. de Jong, Analyzing GAs using Markov Models with Semantically Ordered and Lumped States, forthcoming Foundations of Genetic Algorithms 4, 1996.Google Scholar
  15. [15]
    Vose, M.D., Formalizing Genetic Algorithms, Proceedings of the IEEE Workshop on Genetic Algorithms, Neural Networks, and Simulated Annealing Applied to Signal and Image Processing, Glasgow, Scotland, May, 1990.Google Scholar
  16. [16]
    Vone, M.D., The Simple Genetic Algorithm: Foundations and Theory, forthcoming, MIT Press, Cambridge, MA.Google Scholar
  17. [17]
    Vose, M.D. and G.E. Liepins, Punctuated Equilibria in Genetic Search, Complex Systems, 5, 1991, pp. 31–44.MathSciNetzbMATHGoogle Scholar

Copyright information

© Springer Science+Business Media New York 1999

Authors and Affiliations

  • Jackie Rees
    • 1
  • Gary J. Koehler
    • 1
  1. 1.Decision and Information SciencesUniversity of FloridaGainesvilleUSA

Personalised recommendations