Gregory S. Hornby
ABSTRACT
To reduce the problem of premature convergence we define a new method for measuring an individual's age and propose the Age-Layered Population Structure (ALPS). This new measure of age measures how long the genetic material has been evolving in the population: offspring start with an age of 1 plus the age of their oldest parent instead of starting with an age of 0 as with traditional measures of age. ALPS differs from a typical evolutionary algorithm (EA) by segregating individuals into different age-layers by their age and by regularly introducing new, randomly generated individuals in the youngest layer. The introduction of randomly generated individuals at regular intervals results in an EA that is never completely converged and is always exploring new parts of the fitness landscape. By using age to restrict competition and breeding, younger individuals are able to develop without being dominated by older ones. Analysis of the search behavior of ALPS finds that the offspring of individuals that are randomly generated mid-way through a run are able to move the population out of mediocre local-optima to better parts of the fitness landscape. In comparison against a traditional EA, a multi-start EA and two other EAs with diversity maintenance schemes we find that ALPS produces significantly better designs with a higher reliability than the other EAs.
- J. E. Baker. Adaptive selection methods for genetic algorithms. In J. J. Grefenstette, editor, Proc. of the First Intl. Conf. on Genetic Algorithms, pages 101--111, 1985. Google Scholar
Digital Library
- G. J. Burke and A. J. Poggio. Numerical electromagnetics code NEC-method of moments. Technical Report UCID18834, Lawrence Livermore Lab, Jan 1981.Google Scholar
- D. J. Cavicchio. Adaptive Search using simulated evolution. PhD thesis, University of Michigan, Ann Arbor, 1970.Google Scholar
- G. Chakraborty and B. Chakraborty. Ideal marriage for fine tuning in GA. In Systems, Man, and Cybernetics Conference Proceedings, pages 631--636. IEEE Press, 1999.Google ScholarCross Ref
- H.-J. Cho, S.-Y. Oh, and D.-H. Choi. Fast evolutionary programming through search momentum and multiple offspring strategy. In Proceedings of the International Conference on Evolutionary Computation, pages 805--809. IEEE Press, 1998.Google Scholar
- K. A. DeJong. Analysis of the Behavior of a Class of Genetic Adaptive Systems. Dept. Computer and Communication Sciences, University of Michigan, Ann Arbor, 1975.Google Scholar
- D. E. Goldberg and J. Richardson. Genetic algorithms with sharing for multimodal function optimization. In J. J. Grefenstette, editor, Proc. of the Second Intl. Conf. on Genetic Algorithms, pages 41--49. Lawrence Erlbaum Associates, 1987. Google ScholarDigital Library
- D. E. Goldberg and P. Segrest. Finite markov chain analysis of genetic algorithms. In J. J. Grefenstette, editor, Proc. of the Second Intl. Conf. on Genetic Algorithms, pages 1--8. Lawrence Erlbaum Associates, 1987. Google ScholarDigital Library
- J. Hu and E. D. Goodman. The hierarchical fair competition HFC model for parallel evolutionary algorithms. In Proc. of the 2002 Congress on Evolutionary Computation, pages 49--54. IEEE Press, 2002. Google ScholarDigital Library
- J. Hu, E. D. Goodman, and K. Seo. Continuous hierarchical fair competition model for sustainable innovation in genetic programming. In R. L. Riolo and B. Worzel, editors, Genetic Programming Theory and Practice, pages 81--98, Ann Arbor, 2003. Kluwer.Google ScholarCross Ref
- J. Hu, E. D. Goodman, K. Seo, and M. Pei. Adaptive hierarchical fair competition AHFC model for parallel evolutionary algorithms. In Proc. of the Genetic and Evolutionary Computation Conference, pages 772--779. Morgan Kaufmann, 2002. Google ScholarDigital Library
- A. Huber and D. A. Mlynski. An age-controlled evolutionary algorithm for optimization problems in physical layout. In International Symposium on Circuits and Systems, pages 262--265. IEEE Press, 1998.Google ScholarCross Ref
- J.-H. Kim, J.-Y. Jeon, H.-K. Chae, and K. Koh. A novel evolutionary algorithm with fast convergence. In IEEE International Conference on Evolutionary Computation, pages 228--29. IEEE Press, 1995.Google Scholar
- N. Kubota, T. Fukuda, F. Arai, and K. Shimojima. Genetic algorithm with age structure and its application to self-organizing manufacturing system. In IEEE Symposium on Emerging Technologies and Factory Automation, pages 472--477. IEEE Press, 1994.Google ScholarCross Ref
- J. D. Lohn, G. S. Hornby, and D. S. Linden. Rapid re-evolution of an X-band antenna for NASA's space technology 5 mission. In T. Yu, R. L. Riolo, and B. Worzel, editors, Genetic Programming Theory and Practice III, volume 9 of Genetic Programming, chapter 5, pages 65--78. Springer, Ann Arbor, 2005.Google ScholarCross Ref
- S. J. Louis and G. J. E. Rawlins. Syntactic analysis of convergence in genetic algorithms. In L. D. Whitley, editor, Foundations of Genetic Algorithms 2, pages 141--151. Morgan Kaufmann, 1993.Google ScholarCross Ref
- S. W. Mahfoud. Crowding and preselection revisited. In R. Männer and B. Manderick, editors, Parallel Problem Solving from Nature, 2, pages 27--36. North-Holland, 1992.Google Scholar
- R. Tanese. Distributed genetic algorithms. In J. D. Schaffer, editor, Proc. of the Third Intl. Conf. on Genetic Algorithms, pages 434--439. Morgan Kaufmann, 1989. Google ScholarDigital Library
Index Terms
- ALPS: the age-layered population structure for reducing the problem of premature convergence
Recommendations
Age-fitness pareto optimization
GECCO '10: Proceedings of the 12th annual conference on Genetic and evolutionary computationWe propose a multi-objective method for avoiding premature convergence in evolutionary algorithms, and demonstrate a three-fold performance improvement over comparable methods. Previous research has shown that partitioning an evolving population into ...
Steady-state ALPS for real-valued problems
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computationThe objectives of this paper are to describe a steady-state version of the Age-Layered Population Structure (ALPS) Evolutionary Algorithm (EA) and to compare it against other GAs on real-valued problems. Motivation for this work comes from our previous ...
Review of phenotypic diversity formulations for diagnostic tool
Practitioners often rely on search results to learn about the performance of a particular optimizer as applied to a real-world problem. However, even the best fitness measure is often not precise enough to reveal the behavior of the optimizer's added ...
Comments