Populations Can Be Essential in Tracking Dynamic Optima

Article, Preprint English OPEN
Dang, Duc-Cuong ; Jansen, Thomas ; Lehre, Per Kristian (2016)
  • Publisher: Springer US
  • Journal: Algorithmica, volume 78, issue 2, pages 660-680 (issn: 0178-4617, eissn: 1432-0541)
  • Related identifiers: doi: 10.1007/s00453-016-0187-y, doi: 10.13039/501100004963, pmc: PMC5479466
  • Subject: Applied Mathematics | Computer Science - Artificial Intelligence | Quantitative Biology - Populations and Evolution | Computer Science(all) | Population-based algorithm | Dynamic optimisation | Computer Science Applications | Runtime analysis | Computer Science - Neural and Evolutionary Computing | Article

Real-world optimisation problems are often dynamic. Previously good solutions must be updated or replaced due to changes in objectives and constraints. It is often claimed that evolutionary algorithms are particularly suitable for dynamic optimisation because a large population can contain different solutions that may be useful in the future. However, rigorous theoretical demonstrations for how populations in dynamic optimisation can be essential are sparse and restricted to special cases.\ud \ud This paper provides theoretical explanations of how populations can be essential in evolutionary dynamic optimisation in a general and natural setting. We describe a natural class of dynamic optimisation problems where a sufficiently large population is necessary to keep track of moving optima reliably. We establish a relationship between the population-size and the probability that the algorithm loses track of the optimum.
  • References (22)
    22 references, page 1 of 3

    1.Branke, J., Wang, W.: Theoretical analysis of simple evolution strategies in quickly changing environments. In: Proceedings of the 5th Annual Conference on Genetic and Evolutionary Computation, GECCO’03, pp. 537–548. (2003)

    2.Dang, D.-C., Jansen, T., Lehre, P.K.: Populations can be essential in dynamic optimisation. In: Proceedings of the 17th Annual Conference on Genetic and Evolutionary Computation Conference, GECCO’15, pp. 1407–1414. ACM (2015)

    Dang, D-C, Lehre, PK. Runtime analysis of non-elitist populations: from classical optimisation to partial information. Algorithmica. 2016; 75 (3): 428-461

    4.Droste, S.: Analysis of the (1+1) EA for a dynamically bitwise changing OneMax. In: Proceedings of the 2003 International Conference on Genetic and Evolution ary Computation, GECCO’03, pp. 909–921. Springer (2003)

    Droste, S, Jansen, T, Wegener, I. On the analysis of the (1+1) Evolutionary Algorithm. Theor. Comput. Sci.. 2002; 276: 51-81

    Droste, S, Jansen, T, Wegener, I. Upper and lower bounds for randomized search heuristics in black-box optimization. Theory Comput. Syst.. 2006; 39 (4): 525-544

    7.Fu, H., Lewis, P.R., Sendhoff, B., Tang, K., Yao, X.: What are dynamic optimization problems?. In: Proceedings of the IEEE Congress on Evolutionary Computation, vol. 2014, pp. 1550–1557. (2014)

    8.Goldberg, D.E., Deb, K.: A comparative analysis of selection schemes used in genetic algorithms. In: Proceedings of the First Workshop on Foundations of Genetic Algorithms, FOGA 1991, pp. 69–93. Morgan Kaufmann (1991)

    9.Jansen, T., Schellbach, U.: Theoretical analysis of a mutation-based evolutionary algorithm for a tracking problem in the lattice. In: Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation, GECCO’05, pp. 841–848. ACM (2005)

    10.Jansen, T., Zarges, C.: Evolutionary algorithms and artificial immune systems on a bi-stable dynamic optimisation problem. In: Proceedings of the 16th Annual Conference on Genetic and Evolutionary Computation Conference, GECCO’14, pp. 975–982. ACM (2014)

  • Metrics
    No metrics available
Share - Bookmark