Improving the efficiency of the extended compact genetic algorithm

ABSTRACT

Evolutionary Algorithms are largely used search and optimization procedures that, when properly designed, can solve intractable problems in tractable polynomial time. Efficiency enhancements are used to turn them from tractable to practical. In this paper we show preliminary results of two efficiency enhancements proposed for the Extended Compact Genetic Algorithm. First, a model building enhancement was used to reduce the complexity of the process from O($n^3$) to O($n^2$), speeding up the algorithm by 1000 times on a 4096 bits problem. Then, local-search hybridization was used to reduce the population size by at least 32 times, reducing the memory and running time required by the algorithm. These results draw the first steps toward a competent and efficient Genetic Algorithm.

REFERENCES

• 1: T. Duque, D. Goldberg, and K. Sastry. Enhancing the Efficiency of the ECGA. IlliGAL Report No. 2008006, Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL, 2008.
• 2: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 3: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 4: G. Harik, F. Lobo, and K. Sastry. Linkage Learning via Probabilistc Modeling in the Extended Compact Genetic Algorithm (ECGA). Scalable Optimization via Probabilistic Modeling, Studies in Computational Inteligence, pages 39--61, 2006. (Also Illigal Report No. 99010).
• 5: Kumara Sastry , David E. Goldberg , Xavier Llora, Towards billion-bit optimization via a parallel estimation of distribution algorithm, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277077]
• 6: K. Sastry, M. Pelikan, and D. Goldberg. Efficiency enhancement of estimation of distribution algorithms. Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, pages 161--185, 2006.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

General Terms:
Algorithms, Performance

Keywords:
ECGA, efficiency enhancement, estimation of distribution algorithms, model building