Maximal age in randomized search heuristics with aging

ABSTRACT

The concept of aging has been introduced and applied in many different variants in many different randomized search heuristics. The most important parameter is the maximal age of search points. Considering static pure aging known from artificial immune systems in the context of simple evolutionary algorithms, it is demonstrated that the choice of this parameter is both, crucial for the performance and difficult to set appropriately. The results are derived in a rigorous fashion and given as theorems with formal proofs. An additional contribution is the presentation of a general method to combine fitness functions into a function with stronger properties than its components. By application of this method we combine a function where the maximal age needs to be sufficiently large with a function where the maximal age needs to be sufficiently small. This yields a function where an appropriate age lies within a very narrow range.

REFERENCES

• 1: M. Castrogiovanni, G. Nicosia, and R. Rascuna. Experimental analysis of the aging operator for static and dynamic optimisation problems. In Knowledge-Based Intelligent Information and Engineering Systems, pages 804--811. Springer, 2007.
• 2: D.-H. Choi. Cooperative mutation based evolutionary programming for continuous function optimization. Operations Research Letters, 30(3):195--201, 2002.
• 3: V. Cutello, G. Nicosia, and M. Pavone. Exploring the capability of immune algorithms: A characterization of hypermutation operators. In International Conference on Artificial Immune Systems (ICARIS), pages 263--276. Springer, 2004.
• 4: V. Cutello, G. Nicosia, M. Pavone, and J. Timmis. An immune algorithm for protein structure prediction on lattice models. IEEE Transactions on Evolutionary Computation, 11(1):101--117, 2007.
• 5: V. Cutello, G. Nicosia, M. Romeo, and P. S. Oliveto. On the convergence of immune algorithms. In IEEE Symposium on Foundations of Computational Intelligence (FOCI), pages 409--415. IEEE Press, 2007.
• 6: Leandro R. de Castro , Jonathan Timmis, Artificial Immune Systems: A New Computational Intelligence Paradigm, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 7: Stefan Droste , Thomas Jansen , Ingo Wegener, On the analysis of the (1+ 1) evolutionary algorithm, Theoretical Computer Science, v.276 n.1-2, p.51-81, April 6, 2002 [doi>10.1016/S0304-3975(01)00182-7]
• 8: A. Ghosh, S. Tsutsui, and H. Tanaka. Individual aging in genetic algorithms. In Australian New Zealand Conference on Intelligent Information Systems, pages 276--279. IEEE Press, 1996.
• 9: Jeffrey Horn , David E. Goldberg , Kalyanmoy Deb, Long Path Problems, Proceedings of the International Conference on Evolutionary Computation. The Third Conference on Parallel Problem Solving from Nature: Parallel Problem Solving from Nature, p.149-158, October 09-14, 1994
• 10: Thomas Jansen, On the Analysis of Dynamic Restart Strategies for Evolutionary Algorithms, Proceedings of the 7th International Conference on Parallel Problem Solving from Nature, p.33-43, September 07-11, 2002
• 11: N. Kubota and T. Fukuda. Genetic algorithms with age structure. Soft Computing, 1(4):155--161, 1997.
• 12: R. J. Quick , Victor J. Rayward-Smith , G. D. Smith, Fitness Distance Correlation and Ridge Functions, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.77-86, September 27-30, 1998
• 13: Günter Rudolph, How mutation and selection solve long-path problems in polynomial expected time, Evolutionary Computation, v.4 n.2, p.195-205, Summer 1996 [doi>10.1162/evco.1996.4.2.195]
• 14: Hans-Paul Schwefel , Günter Rudolph, Contemporary Evolution Strategies, Proceedings of the Third European Conference on Advances in Artificial Life, p.893-907, June 04-06, 1995
• 15: D. Sudholt. Computational Complexity of Evolutionary Algorithms, Hybridizations, and Swarm Intelligence. PhD thesis, Technische Universität Dortmund, 2008.
• 16: J. Timmis , A. Hone , T. Stibor , E. Clark, Theoretical advances in artificial immune systems, Theoretical Computer Science, v.403 n.1, p.11-32, August, 2008 [doi>10.1016/j.tcs.2008.02.011]
• 17: Carsten Witt, Runtime Analysis of the (μ+1) EA on Simple Pseudo-Boolean Functions, Evolutionary Computation, v.14 n.1, p.65-86, March 2006 [doi>10.1162/106365606776022751]
• 18: Christine Zarges, Rigorous Runtime Analysis of Inversely Fitness Proportional Mutation Rates, Proceedings of the 10th international conference on Parallel Problem Solving from Nature: PPSN X, September 13-17, 2008, Dortmund, Germany [doi>10.1007/978-3-540-87700-4_12]
• 19: Christine Zarges, On the utility of the population size for inversely fitness proportional mutation rates, Proceedings of the tenth ACM SIGEVO workshop on Foundations of genetic algorithms, January 09-11, 2009, Orlando, Florida, USA [doi>10.1145/1527125.1527132]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
aging, evolutionary algorithms, genetic algorithms, immune algorithms, runtime analysis