Publications

Overcoming Binary Adversarial Optimisation with Competitive Coevolution

Published in 18th International Conference on Parallel Problem Solving From Nature (PPSN), 2024

Abstract: Co-evolutionary algorithms (CoEAs), which pair candidate designs with test cases, are frequently used in adversarial optimisation, particularly for binary test-based problems where designs and tests yield binary outcomes. The effectiveness of designs is determined by their performance against tests, and the value of tests is based on their ability to identify failing designs, often leading to more sophisticated tests and improved designs. However, CoEAs can exhibit complex, sometimes pathological behaviours like disengagement. Through runtime analysis, we aim to rigorously analyse whether CoEAs can efficiently solve test-based adversarial optimisation problems in an expected polynomial runtime.

Recommended citation: Per Kristian Lehre, and Shishen Lin. (2024). " Overcoming Binary Adversarial Optimisation with Competitive Coevolution." 18th International Conference on Parallel Problem Solving From Nature (PPSN). 14 pages, Hagenberg, Austria, 2024. to appear. https://arxiv.org/pdf/2407.17875

Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms

Published in Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI), 2024

Abstract: Runtime analysis, as a branch of the theory of AI, studies how the number of iterations algorithms take before finding a solution (its runtime) depends on the design of the algorithm and the problem structure. Drift analysis is a state-of-the-art tool for estimating the runtime of randomised algorithms, such as bandit and evolutionary algorithms. Drift refers roughly to the expected progress towards the optimum per iteration. This paper considers the problem of deriving concentration tail-bounds on the runtime of algorithms. It provides a novel drift theorem that gives precise exponential tail-bounds given positive, weak, zero and even negative drift. Previously, such exponential tail bounds were missing in the case of weak, zero, or negative drift.

Recommended citation: Per Kristian Lehre, and Shishen Lin. (2024). "Concentration Tail-Bound Analysis of Coevolutionary and Bandit Learning Algorithms." Proceedings of the 33rd International Joint Conference on Artificial Intelligence (IJCAI). 7 pages, Jeju, South Korea, 2024. https://www.ijcai.org/proceedings/2024/0767.pdf

Runtime Analysis of a Co-Evolutionary Algorithm: Overcoming Negative Drift in Maximin-Optimisation

Published in Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA), 2023

Abstract: This paper is about a mathematically rigorous method to analyze co-evolutionary algorithms, successfully obtaining Maximin-solutions with improved runtime analysis and new mathematical tools.

Recommended citation: Mario Alejandro Hevia Fajardo, Per Kristian Lehre, and Shishen Lin. (2023). "Runtime analysis of a Co-Evolutionary Algorithm: Overcoming Negative Drift in Maximin-Optimisation." Proceedings of the 16th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA). 11 pages, Potsdam, Germany, 2023. https://dl.acm.org/doi/10.1145/3594805.3607132

Is CC-(1+1) EA more efficient than (1+1) EA on either separable or inseparable problems?

Published in IEEE Congress on Evolutionary Computation (CEC), 2023

Abstract: This paper is about the cooperative co-evolutionary algorithms. This paper investigates cooperative co-evolutionary algorithms (CoEAs) for large-scale optimization problems, focusing on the runtime analysis to understand their behavior. By proving that the basic cooperative co-evolutionary (1+1) EA has an expected optimization time of Θ(n log n) on linear functions, it solves an open conjecture. Empirical analysis on NK-LANDSCAPE and k-MAXSAT problems shows that performance can be optimized by adjusting block length, providing more precise runtime bounds and insights on more complicated inseparable problems.

Recommended citation: Per Kristian Lehre, Shishen Lin. (2023). "Is CC-(1+1) EA more efficient than (1+1) EA on either separable or inseparable problems?" IEEE Congress on Evolutionary Computation (CEC). 8 pages, Chicago, USA, 2023. https://ieeexplore.ieee.org/document/10254149