How long should we run in dynamic optimization?

ABSTRACT

The problem of measuring performance in dynamic optimization is still an open issue. The most popular procedure consists of choosing one measure from the standard evolutionary optimization domain, such as the best fitness in the current population, and averaging it across the number of generations (sometimes, the number of periods). Generally, it is assumed that the measure of our election has been sufficiently exposed to the changing landscape, although there is no way of actually checking whether this exposition has taken place or not. Our purpose is proposing here for the first time a way of determining how long we should run our experiments in order to get meaningful conclusions in a changing environment after a representative number of changes. The new stopping condition is based on the convergence of the chosen measure for the dynamic problem at hand, thus globally useful.

References

1. E. Alba and B. Sarasola. ABC, a new performance tool for algorithms solving dynamic optimization problems. In IEEE Congress on Evolutionary Computation, pages 1--7, 2010.
2. E. Alba and B. Sarasola. Measuring fitness degradation in dynamic optimization problems. In European Conference on the Applications of Evolutionary Computation, 2010.
3. J. Branke. Evolutionary optimization in dynamic environments. Kluwer Academic Publishers, 2002.
4. M. Cámara, J. Ortega, and F. de Toro. Performance measures for dynamic multi-objective optimization. Bio-Inspired Systems: Computational and Ambient Intelligence, I(5517):760--767, 2009.
5. H. G. Cobb and J. J. Grefenstette. Genetic algorithms for tracking changing environments. In 5th International Conference on Genetic Algorithms, pages 523--530, 1993.
6. C. Cruz, J. González, and D. Pelta. Optimization in dynamic environments: a survey on problems, methods and measures. Soft Computing - A Fusion of Foundations, Methodologies and Applications, 15:1427--1448, 2011.
7. J. J. Grefenstette. Genetic algorithms for changing environments. In Parallel Problem Solving from Nature, pages 139--146, 1992.
8. Y. Jin and J. Branke. Evolutionary optimization in uncertain environments-a survey. IEEE Trans. Evolutionary Computation, 9(3):303--317, 2005.
9. Y. Jin and B. Sendhoff. Constructing dynamic optimization test problems using the multi-objective optimization concept. In EvoWorkshops, volume 3005 of LNCS, pages 525--536. Springer, 2004.
10. N. Mori, S. Imanishi, H. Kita, and Y. Nishikawa. Adaptation to changing environments by means of the memory based thermodynamical genetic algorithm. In 7th International Conference on Genetic Algorithms, pages 299--306, 1997.
11. R. Morrison. Performance measurement in dynamic environments. In GECCO Workshop on Evolutionary Algorithms for Dynamic Optimization Problems, pages 5--8, 2003.
12. R. W. Morrison and K. A. D. Jong. Measurement of population diversity. In Selected Papers from the 5th European Conference on Artificial Evolution, pages 31--41, London, UK, 2002. Springer-Verlag.
13. I. Moser and R. Chiong. Dynamic function optimisation with hybridised extremal dynamics. Memetic Computing, 2(2):137--148, 2010. 10.1007/s12293-009-0027-6.
14. A. J. Nebro, J. J. Durillo, C. A. C. Coello, F. Luna, and E. Alba. A study of convergence speed in multi-objective metaheuristics. In Parallel Problem Solving from Nature, pages 763--772, 2008.
15. T. T. Nguyen and X. Yao. Continuous dynamic constrained optimisation - The challenges. IEEE Transactions on Evolutionary Computation, 2011.
16. W. Rand and R. Riolo. Measurements for understanding the behavior of the genetic algorithm in dynamic environments: a case study using the shaky ladder hyperplane-defined functions. In Workshops on Genetic and evolutionary computation, pages 32--38, 2005.
17. E. Tantar, A.-A. Tantar, and P. Bouvry. On dynamic multi-objective optimization, classification and performance measures. In IEEE Congress on Evolutionary Computation, pages 2759--2766, 2011.
18. K. Weicker. Performance measures for dynamic environments. In Parallel Problem Solving from Nature, volume 2439, pages 64--73. 2002.
19. M. Wineberg and F. Oppacher. Enhancing the ga's ability to cope with dynamic environments. In Genetic and Evolutionary Computation Conference, pages 3--10, 2000.
20. S. Yang. Genetic algorithms with memory- and elitism-based immigrants in dynamic environments. Evolutionary Computation, 16(3):385--416, 2008.
21. S. Yang and C. Li. A clustering particle swarm optimizer for locating and tracking multiple optima in dynamic environments. Evolutionary Computation, IEEE Transactions on, 14(6):959--974, dec. 2010.
22. S. Yang and R. Tinós. A hybrid immigrants scheme for genetic algorithms in dynamic environments. International Journal of Automation and Computing, pages 243--254, 2007.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Search methodologies

      • Heuristic function construction

• Mathematics of computing

  • Mathematical analysis

    • Mathematical optimization

• Theory of computation

  • Design and analysis of algorithms

    • Mathematical optimization