Per Kristian Lehre
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Per Kristian Lehre has a total of 101 co-authors. Here are the top co-authors by number of shared publications:
- Xin Yao
Lingnan University
12 shared publications - Pietro Simone Oliveto
Southern University of Science and Technology
9 shared publications - Frank Neumann
Adelaide University
7 shared publications - Mario Alejandro Hevia Fajardo
University of Birmingham, Birmingham, United Kingdom
7 shared publications - Duc-Cuong Dang
University of Nottingham
6 shared publications - Shishen Lin
School of Computer Science, University of Birmingham, Birmingham, United Kingdom
5 shared publications
Latest Publications
- Open Access
- 13 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 1862-1882
Theory of Competitive Co-evolutionary Algorithms
- 13 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 1862-1882
Open AccessTheory of Competitive Co-evolutionary Algorithms
- Open Access
- 10 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 1340-1348
A Generic Framework for Optimisation under Uncertainty with Recourse: Theory and Examples
- 10 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 1340-1348
Open AccessA Generic Framework for Optimisation under Uncertainty with Recourse: Theory and Examples
- Open Access
- 10 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 1313-1322
Analysis of the Impact of Tournament Size on Coevolutionary Search
- 10 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 1313-1322
Open AccessAnalysis of the Impact of Tournament Size on Coevolutionary Search
- Open Access
- 27 August 2025
- Published by Association for Computing Machinery (ACM)
- p. 85-95
Runtime Bounds for a Coevolutionary Algorithm on Classes of Potential Games
- 27 August 2025
- Published by Association for Computing Machinery (ACM)
- p. 85-95
Open AccessRuntime Bounds for a Coevolutionary Algorithm on Classes of Potential Games
- Open Access
- 14 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 37-38
Hot off the Press: No Free Lunch Theorem and Black-Box Complexity Analysis for Adversarial Optimisation
- 14 July 2025
- Published by Association for Computing Machinery (ACM)
- p. 37-38
Open AccessHot off the Press: No Free Lunch Theorem and Black-Box Complexity Analysis for Adversarial Optimisation
- 7 September 2024
- Published by Springer Nature
- p. 117-132
Overcoming Binary Adversarial Optimisation with Competitive Coevolution
- 7 September 2024
- Published by Springer Nature
- p. 117-132
Overcoming Binary Adversarial Optimisation with Competitive Coevolution
- 7 September 2024
- Published by Springer Nature
- p. 213-229
Ranking Diversity Benefits Coevolutionary Algorithms on an Intransitive Game
- 7 September 2024
- Published by Springer Nature
- p. 213-229
Ranking Diversity Benefits Coevolutionary Algorithms on an Intransitive Game
- Open Access
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 903-927
Runtime Analysis of Population-based Evolutionary Algorithms
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 903-927
Open AccessRuntime Analysis of Population-based Evolutionary Algorithms
- Open Access
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1551-1559
The SLO Hierarchy of pseudo-Boolean Functions and Runtime of Evolutionary Algorithms
While some common fitness landscape characteristics are critical when determining the runtime of evolutionary algorithms (EAs), the relationship between fitness landscape structure and the runtime of EAs is poorly understood. Recently, Dang et al. (2021) introduced a classification of pseudo-Boolean problems showing that "sparsity" of local optima and the "density" of fitness valleys can be crucial characteristics when determining the runtime of EAs. However, their approach could only classify some classes of pseudo-Boolean functions and thus defined an incomplete hierarchy. We generalise the previous work to a complete hierarchy for all pseudo-Boolean functions. The hierarchy is consistent with existing results for the runtime of EAs. The hardest part of the hierarchy consists of problems satisfying the No Free Lunch theorem. The easiest part contains well-known theoretical benchmark problems, easy for EAs. The intermediary parts contain instances of NP-hard problems. Problem classes where local optima sparsity exceed fitness valley density are shown to have exponential black-box complexity. We study how random perturbations of a function can change its classification. E.g, randomly perturbing search points in OneMax with constant probability leads to a problem class that can still be optimised efficiently with appropriately tuned non-elitist EAs.
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1551-1559
Open AccessThe SLO Hierarchy of pseudo-Boolean Functions and Runtime of Evolutionary Algorithms
While some common fitness landscape characteristics are critical when determining the runtime of evolutionary algorithms (EAs), the relationship between fitness landscape structure and the runtime of EAs is poorly understood. Recently, Dang et al. (2021) introduced a classification of pseudo-Boolean problems showing that "sparsity" of local optima and the "density" of fitness valleys can be crucial characteristics when determining the runtime of EAs. However, their approach could only classify some classes of pseudo-Boolean functions and thus defined an incomplete hierarchy. We generalise the previous work to a complete hierarchy for all pseudo-Boolean functions. The hierarchy is consistent with existing results for the runtime of EAs. The hardest part of the hierarchy consists of problems satisfying the No Free Lunch theorem. The easiest part contains well-known theoretical benchmark problems, easy for EAs. The intermediary parts contain instances of NP-hard problems. Problem classes where local optima sparsity exceed fitness valley density are shown to have exponential black-box complexity. We study how random perturbations of a function can change its classification. E.g, randomly perturbing search points in OneMax with constant probability leads to a problem class that can still be optimised efficiently with appropriately tuned non-elitist EAs.
- Open Access
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1542-1550
Runtime Analysis of Coevolutionary Algorithms on a Class of Symmetric Zero-Sum Games
A standard aim in game theory is to find a pure or mixed Nash equilibrium. For strategy spaces too large for a Nash equilibrium to be computed classically, this can instead be approached using a co-evolutionary algorithm. How to design coevolutionary algorithms which avoid pathological behaviours (such as cycling or forgetting) on challenging games is then a crucial open problem. We argue that runtime analysis can provide insight and inform the design of more powerful and reliable algorithms for this purpose. To this end, we consider a class of symmetric zero-sum games for which the role of population diversity is pivotal to an algorithm's success. We prove that a broad class of algorithms which do not utilise a population have superpolynomial runtime for this class. In the other direction we prove that, with high probability, a coevolutionary instance of the univariate marginal distribution algorithm finds the unique Nash equilibrium in time O(n(log n)2). Together, these results demonstrate the importance of generating diverse search points for evolving better strategies. The corresponding proofs develop several techniques that may benefit future analysis of estimation of distribution and coevolutionary algorithms.
- 14 July 2024
- Published by Association for Computing Machinery (ACM)
- p. 1542-1550
Open AccessRuntime Analysis of Coevolutionary Algorithms on a Class of Symmetric Zero-Sum Games
A standard aim in game theory is to find a pure or mixed Nash equilibrium. For strategy spaces too large for a Nash equilibrium to be computed classically, this can instead be approached using a co-evolutionary algorithm. How to design coevolutionary algorithms which avoid pathological behaviours (such as cycling or forgetting) on challenging games is then a crucial open problem. We argue that runtime analysis can provide insight and inform the design of more powerful and reliable algorithms for this purpose. To this end, we consider a class of symmetric zero-sum games for which the role of population diversity is pivotal to an algorithm's success. We prove that a broad class of algorithms which do not utilise a population have superpolynomial runtime for this class. In the other direction we prove that, with high probability, a coevolutionary instance of the univariate marginal distribution algorithm finds the unique Nash equilibrium in time O(n(log n)2). Together, these results demonstrate the importance of generating diverse search points for evolving better strategies. The corresponding proofs develop several techniques that may benefit future analysis of estimation of distribution and coevolutionary algorithms.