## 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 CLIFF_{d} problem with this feature and prove that conditional on an event that happens with Ω(1) probability, the (1+1) EA reaches the optimum in expected O(nlnn) iterations. It is much better than the expected runtime of Θ(n^{d}) for the original 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 CLIFF_{d} problem with this feature, and also prove an expected runtime of O(nlnn) (conditional on an event happening with Ω(1) probability), compared with the expected runtime of Ω(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.

Original language | English |
---|---|

Title of host publication | Parallel Problem Solving from Nature – PPSN XVIII: 18th International Conference, PPSN 2024, Hagenberg, Austria, September 14-18, 2024, Proceedings, Part III |

Editors | Michael AFFENZELLER, Stephan M. WINKLER, Anna V. KONONOVA, Thomas BÄCK, Heike TRAUTMANN, Tea TUŠAR, Penousal MACHADO |

Publisher | Springer Science and Business Media Deutschland GmbH |

Pages | 280-294 |

Number of pages | 15 |

ISBN (Electronic) | 9783031700712 |

ISBN (Print) | 9783031700705 |

DOIs | |

Publication status | Published - 2024 |

Event | 18th International Conference on Parallel Problem Solving from Nature, PPSN 2024 - Hagenberg, Austria Duration: 14 Sept 2024 → 18 Sept 2024 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 15150 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 18th International Conference on Parallel Problem Solving from Nature, PPSN 2024 |
---|---|

Country/Territory | Austria |

City | Hagenberg |

Period | 14/09/24 → 18/09/24 |

### Bibliographical note

Publisher Copyright:© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.

## Keywords

- Evolutionary algorithms
- Time-linkage property