A splicing/decomposable encoding and its novel operators for genetic algorithms

ABSTRACT

In this paper, we introduce a new genetic representation --- a splicing/decomposable (S/D) binary encoding, which was proposed based on some theoretical guidance and existing recommendations for designing efficient genetic representations. Our theoretical and empirical investigations reveal that the S/D binary representation is more proper than other existing binary encodings for searching of genetic algorithms (GAs). Moreover, we define a new genotypic distance on the S/D binary space, which is equivalent to the Euclidean distance on the real-valued space during GAs convergence. Based on the new genotypic distance, GAs can reliably and predictably solve problems of bounded complexity and the methods depended on the Euclidean distance for solving different kinds of optimization problems can be directly used on the S/D binary space.

REFERENCES

• 1: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 2: Richard W. Hamming, Coding and Information Theory, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 3: K. H. Han, and J. H. Kim, Genetic quantum algorithm and its application to combinatorial optimization problem, Proceeding of Congress on Evolutionary Computation 2000, 1: 1354--1360, 2000
• 4: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 5: B. A. Julstrom, Redundant genetic encodings may not be harmful, Proceedings of the Genetic and Evolutionary Computation Conference 1999, 1: 791, San Francisco, CA: Morgan Kaufmann Publishers, 1999
• 6: K. S. Leung, J. Y. Sun, and Z. B. Xu, Efficiency speed-up strategies for evolutionary computation: an adaptive implementation, Engineering Computations, 19 (3): 272--304, 2002
• 7: G. E. Liepins, and M. D. Vose, Representational issues in genetic optimization, Journal of Experimental and Theoretical Artificial Intelligence, 2: 101--115, 1990
• 8: Samir W. Mahfoud, Niching methods for genetic algorithms, University of Illinois at Urbana-Champaign, Champaign, IL, 1996
• 9: Franz Rothlauf , David E. Goldberg, Representations for Genetic and Evolutionary Algorithms, Physica-Verlag, 2002
• 10: J. David Schaffer , Rich Caruana , Larry J. Eshelman , Rajarshi Das, A Study of Control Parameters Affecting Online Performance of Genetic Algorithms for Function Optimization, Proceedings of the 3rd International Conference on Genetic Algorithms, p.51-60, June 01, 1989
• 11: D. Thierens, Analysis and Design of Genetic Algorithms, Leuven, Belgium: Katholieke Universiteit Leuven, 1990
• 12: D. Whitley, Local search and high precision gray codes: Convergence results and neighborhoods. In Martin, W., & Spears, W. (Eds.), Foundations of Genetic Algorithms 6, San Francisco, California: Morgan Kaufmann Publishers, Inc., 2000
• 13: Zong-Ben Xu , Kwong-Sak Leung , Yong Liang , Yee Leung, Efficiency speed-up strategies for evolutionary computation: fundamentals and fast-GAs, Applied Mathematics and Computation, v.142 n.2-3, p.341-388, 10 October 2003 [doi>10.1016/S0096-3003(02)00309-0]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms

Keywords:
genetic algorithm, genetic representation