Abstract
Recent theoretical works show that the time-linkage property challenges evolutionary algorithms to optimize. Here we consider three positive circumstances and give the first runtime analyses to show that the time-linkage property can also help the optimization of evolutionary algorithms. The problem is easier to optimize if the time-linkage property changes the optimal function value to an easy-to-reach one. We construct a time-linkage variant of the \(\textsc {Cliff}_{d}\) problem with this feature and prove that conditional on an event that happens with \(\varOmega (1)\) probability, the \((1 + 1)\) EA reaches the optimum in expected \(O(n \ln n)\) iterations. It is much better than the expected runtime of \(\varTheta (n^d)\) for the original \(\textsc {Cliff}_{d}\). If the time-linkage property does not change the optimal function value but enlarges the optimal solution set, the problem is also possible to be easier to optimize. We construct another time-linkage variant of the \(\textsc {Cliff}_{d}\) problem with this feature, and also prove an expected runtime of \(O(n\ln n)\) (conditional on an event happening with \(\varOmega (1)\) probability), compared with the expected runtime of \(\varOmega (n^{d-2})\) for the corresponding problem without the time-linkage property. Even if the time-linkage property neither changes the optimal function value nor the optimal solution set, it is still possible to ease this problem if the intermediate solution, from which the optimum is easier to reach, is more prone to be maintained. We construct a time-linkage variant of the Jump problem, and proved that the expected runtime is reduced from \(O(n^k)\) to \(O(n^{k-1})\). Our experiments also verify the above theoretical findings.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bian, C., Zhou, Y., Li, M., Qian, C.: Stochastic population update can provably be helpful in multi-objective evolutionary algorithms. In: International Joint Conference on Artificial Intelligence, IJCAI 2023, pp. 5513–5521. ijcai.org (2023)
Bosman, P.A.: Learning, anticipation and time-deception in evolutionary online dynamic optimization. In: Genetic and Evolutionary Computation Conference Workshop, GECCO 2005 Workshop, pp. 39–47. ACM (2005)
Doerr, B.: Probabilistic tools for the analysis of randomized optimization heuristics. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 1–87. Springer, Cham (2020). https://arxiv.org/abs/1801.06733
Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. In: Genetic and Evolutionary Computation Conference, GECCO 2010, pp. 1449–1456. ACM (2010)
Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 777–784. ACM (2017)
Droste, S., Jansen, T., Wegener, I.: On the analysis of the (1+1) evolutionary algorithm. Theoret. Comput. Sci. 276, 51–81 (2002)
Jägersküpper, J., Storch, T.: When the plus strategy outperforms the comma strategy and when not. In: Foundations of Computational Intelligence, FOCI 2007, pp. 25–32. IEEE (2007)
Jansen, T., Wegener, I.: The analysis of evolutionary algorithms - a proof that crossover really can help. Algorithmica 34, 47–66 (2002)
Paixao, T., Pérez Heredia, J., Sudholt, D., Trubenova, B.: First steps towards a runtime comparison of natural and artificial evolution. In: Genetic and Evolutionary Computation Conference, GECCO 2015, pp. 1455–1462. ACM (2015)
Rajabi, A., Witt, C.: Self-adjusting evolutionary algorithms for multimodal optimization. Algorithmica 84, 1694–1723 (2022)
Sudholt, D.: Crossover speeds up building-block assembly. In: Genetic and Evolutionary Computation Conference, GECCO 2012, pp. 689–702. ACM (2012)
Witt, C.: Tight bounds on the optimization time of a randomized search heuristic on linear functions. Comb. Probab. Comput. 22, 294–318 (2013)
Witt, C.: How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys. Theoret. Comput. Sci. 940, 18–42 (2023)
Yang, T., Zhou, Y.: Analysis of multi-objective evolutionary algorithms on fitness function with time-linkage property. IEEE Trans. Evol. Comput. 28, 837–843 (2024)
Zheng, W., Chen, H., Yao, X.: Analysis of evolutionary algorithms on fitness function with time-linkage property. IEEE Trans. Evol. Comput. 25, 696–709 (2021)
Zheng, W., Doerr, B.: Theoretical analyses of multiobjective evolutionary algorithms on multimodal objectives. Evol. Comput. 31, 337–373 (2023)
Zheng, W., Doerr, B.: Runtime analysis of the SMS-EMOA for many-objective optimization. In: Conference on Artificial Intelligence, AAAI 2024, pp. 20874–20882. AAAI Press (2024)
Zheng, W., Zhang, Q., Chen, H., Yao, X.: When non-elitism meets time-linkage problems. In: Genetic and Evolutionary Computation Conference, GECCO 2021, pp. 741–749. ACM (2021)
Acknowledgments
This work was supported by National Natural Science Foundation of China (Grant No. 62350710797, 62306086, 62250710682), Science, Technology and Innovation Commission of Shenzhen Municipality (Grant No. GXWD20220818191018001), and Guangdong Basic and Applied Basic Research Foundation (Grant No. 2019A1515110177).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Ethics declarations
Disclosure of Interests
The authors have no competing interests to declare that are relevant to the content of this article.
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Li, M., Zheng, W., Xie, W., Sun, A., Yao, X. (2024). When Does the Time-Linkage Property Help Optimization by Evolutionary Algorithms?. In: Affenzeller, M., et al. Parallel Problem Solving from Nature – PPSN XVIII. PPSN 2024. Lecture Notes in Computer Science, vol 15150. Springer, Cham. https://doi.org/10.1007/978-3-031-70071-2_18
Download citation
DOI: https://doi.org/10.1007/978-3-031-70071-2_18
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-70070-5
Online ISBN: 978-3-031-70071-2
eBook Packages: Computer ScienceComputer Science (R0)