Email: P.K.Lehre@bham.ac.uk (please do not use my previous School
of CS email address)
Phone: +44 (0)121 414 8560
Office hours Fridays 11-12 (office 207). For all Zoom meetings with
me, (please use this link).
Teaching
(I currently have no teaching and admin duties as my time
over the next years is bought out by my Turing AI fellowship.)
Neural Computation (Autumn 2020, co-taught with Jinming Duan,
Yunwen Lei and Shan He)
Nature Inspired Search and Optimisation (Spring 2020, co-taught with Shan He)
Research Interests
My research interests are in theory of evolutionary computation,
population genetics, randomised algorithms and related topics.
Open PhD Scholarship
We are currently looking for one PhD student to be associated
with my Turing AI Acceleration fellowship project on
co-evolution. If you are interested in theory of evolutionary
computation, particularly runtime analysis, please get in
touch with me or apply directly here.
ROAR-NET Short-term Scientific Missions
Funding is available for research visits within the ROAR-NET
COST action. Members of Working Group 4 offer to host visitors
working on a range of topics related to Optimisation under
Uncertainty. See here for more information and list of hosts.
Current Activities and News
Joining COST Action ROAR-NET as work group leader on optimisation under uncertainty.
Giving tutorial on runtime analysis of population-based evolutionary algorithms
at GECCO 2023.
Alistair Benford joined the group as a Research Fellow in
February 2023. He is funded by the Turing AI Acceleration
Fellowship. He was previously a PhD student in the Probability and
Combinatorics group in Birmingham
Our group presented four papers and one tutorial at the GECCO 2022 conference in
Boston.
Mario Hevia Fajardo joined the group as a Research
Fellow in February 2022. He is funded by the Turing AI Acceleration Fellowship.. He was previously a PhD student at the University of Sheffield.
Mario Alejandro Hevia Fajardo and Per Kristian Lehre,
Ranking Diversity Benefits Coevolutionary Algorithms on an
Intransitive Game,
In Proceedings of 18th International Conference on Parallel
Problem Solving from Nature (PPSN 2024).
Per Kristian Lehre and Shishen Lin,
Overcome Binary Adversarial Optimisation: From (1,λ) Evolutionary Algorithm to (1,λ) Co-evolutionary Algorithm,
In Proceedings of 18th International Conference on Parallel
Problem Solving from Nature (PPSN 2024).
Per Kristian Lehre and Shishen Lin,
Concentration Tail-Bound Analysis of Coevolutionary and Bandit
Learning Algorithms,
In Proceedings of The 33rd International Joint Conference on Artificial Intelligence (IJCAI-24)
Alistair Benford and Per Kristian Lehre,
Runtime Analysis of Coevolutionary Algorithms on a Class of Symmetric
Zero-Sum Games,
In Proceedings of Genetic and Evolutionary Computation Conference
(GECCO '24).
Alistair Benford, Markus Olhofer, Tobias Rodemann, and Per Kristian Lehre,
Bicriteria optimisation of average and worst-case performance using coevolutionary algorithms,
In Proceedings of IEEE Congress on Evolutionary Computation (IEEE CEC) 2024
Mario Hevia Fajardo, Per Kristian Lehre, Jamal Toutouh, Erik
Hemberg, Una-May O'Reilly,
Analysis of a Pairwise Dominance Coevolutionary Algorithm with
Spatial Topology,
Genetic Programming Theory and Practice XX, (2004).
Mario Alejandro Hevia Fajardo, Erik Hemberg, Jamal Toutouh,
Una-May O'Reilly, Per Kristian Lehre,
Self-adaptive Co-Evolutionary Algorithms
In Proceedings of Genetic and Evolutionary Computation Conference
(GECCO '24).
Duc-Cuong Dang and Per Kristian Lehre,
The SLO Hierarchy of pseudo-Boolean Functions and Runtime of
Evolutionary Algorithms,
In Proceedings of Genetic and Evolutionary Computation Conference
(GECCO '24).
2023
Mario Alejandro Hevia Fajardo, Per Kristian Lehre, and Shishen Lin,
Runtime Analysis of a Co-Evolutionary Algorithm: Overcoming
Negative Drift in Maximin-Optimisation,
In Proceedings of 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA '23).
Per Kristian Lehre and Xiaoyu Qin,
Self-adaptation Can Improve the Noise-tolerance of Evolutionary
Algorithms,
In Proceedings of 17th ACM/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA '23).
Per Kristian Lehre, Mario Hevia Fajardo, Erik Hemberg, Una-May
O'Reilly, and Jamal Toutouh,
Analysis of a Pairwise Dominance Coevolutionary Algorithm And DefendIt,
To appear in Proceedings of Genetic and Evolutionary Computation
Conference (GECCO '23)
Per Kristian Lehre and Andrew M. Sutton,
Runtime Analysis with Variable Cost,
To appear in Proceedings of Genetic and Evolutionary Computation
Conference (GECCO '23)
Mario Hevia Fajardo and Per Kristian Lehre,
How Fitness Aggregation Methods Affect the Performance of Competitive CoEAs on Bilinear Problems
To appear in Proceedings of Genetic and Evolutionary Computation
Conference (GECCO '23)
Per Kristian Lehre and Xiaoyu Qin,
Self-adaptation Can Help Evolutionary Algorithms Track Dynamic Optima,
To appear in Proceedings of Genetic and Evolutionary Computation
Conference (GECCO '23)
Per Kristian Lehre and Shishen Lin,
Is CC-(1+1) EA more efficient than (1+1) EA on either separable or inseparable problems?
To appear in Proceedings of IEEE 2023 Congress on Evolutionary
Computation, (CEC '23)
Per Kristian Lehre and Xioayu Qin,
Self-adaptation via Multi-objectivisation: An Empirical Study.
To appear in Proceedings of Parallel Problem Solving from Nature
(PPSN '22). code on github
Brendan Case and Per Kristian Lehre,
Self-adaptation in non-Elitist Evolutionary Algorithms on Discrete Problems with Unknown Structure,
IEEE Transactions on Evolutionary Computation, Vol 24, Issue 4,
Aug. 2020
DOI 10.1109/TEVC.2020.2985450arXiv:2004.00327.
slidesvideoerratum
2019
Per Kristian Lehre and Dirk Sudholt,
Parallel Black-Box Complexity with Tail Bounds,
IEEE Transactions on Evolutionary Computation, 24(6):1010-1024,
December
2020. DOI: 10.1109/TEVC.2019.2954234
Per Kristian Lehre and Phan Trung Hai Nguyen,
On the Limitations of the Univariate Marginal Distribution Algorithm to Deception and Where Bivariate EDAs might help,
To appear in Proceedings of 15th ACM/SIGEVO Workshop on Foundations of Genetic Algorithms (FOGA XV), Berlin, Germany.
Per Kristian Lehre and Phan Trung Hai Nguyen,
Runtime Analysis of the UMDA under Low Selective Pressure and Prior Noise,
To appear in
Proceedings of Genetic and Evolutionary Computation Conference
(GECCO '19), July 13-17, 2019, Prague, Czech Republic.
arXiv:1904.09239
Per Kristian Lehre and Phan Trun Hai Nguyen,
Level-Based Analysis of the Population-Based Incremental Learning Algorithm,
to appear in Proceedings of Parallell Problem Solving from Nature
(PPSN XV), Coimbra, Portugal.
2018. arXiv:1806.01710
Per Kristian Lehre and Pietro S. Oliveto, (2018). Handbook of
Heuristics, chapter Theoretical Analysis of Stochastic Search Algorithms, pages
1--36. Springer International Publishing. DOI: 10.1007/978-3-319-07153-4_35-1
Duc-Cuong Dang,
Tobias Friedrich,
Timo Kötzing,
Martin Krejca,
Per Kristian Lehre,
Pietro Oliveto,
Dirk Sudholt, and
Andrew Sutton,
Escaping Local Optima Using Crossover with Emergent Diversity,
To appear in IEEE Transactions on Evolutionary Computation.
Duc-Cuong Dang and Per Kristian Lehre,
Self-adaptation of Mutation Rates in Non-elitist Populations,
to appear in Proceedings of 14th International Conference on
Parallel Problem Solving from Nature (PPSN) 2016.
arXiv:1606.05551Interactive visualisation of result.
Duc-Cuong Dang, Tobias Friedrich, Timo Koetzing,
Martin S. Krejca,
Per Kristian Lehre,
Pietro S. Oliveto, Dirk Sudholt,
Andrew M. Sutton,
Emergence of Diversity and its Benefits for Crossover in Genetic
Algorithms,
to appear in Proceedings of 14th International Conference on
Parallel Problem Solving from Nature (PPSN) 2016.
Nominated for best paper award.arXiv:1608.03123
Duc-Cuong Dang, Tobias Friedrich, Timo Kotzing, Martin Krejca,
Per Kristian Lehre, Pietro Oliveto, Dirk Sudholt, and Andrew Sutton,
Escaping Local Optima with Diversity Mechanisms and Crossover,
To appear in Proceedings of Genetic and Evolutionary Computation
Conference (GECCO 2016), Denver, Colorado, USA 2016.
Fawaz Alanazi and Per Kristian Lehre,
Limits to Learning in Reinforcement Learning Hyper-heuristics,
To appear in Proceedings of 16th European Conference on
Evolutionary Computation in Combinatorial Optimisation (EvoCOP),
Porto, Portugal, 30 March-1 April 2016.
Tiago Paixão, Golnaz Badkobeh, Nick H Barton, Dogan Corus, Duc-Cuong Dang,
Tobias Friedrich, Per Kristian Lehre, Dirk Sudholt, Andrew Sutton,
Barbora Trubenova:
Toward a unifying framework for evolutionary processes,
To appear in Journal of Theoretical Biology, 2015. (PDF)
Duc-Cuong Dang, Thomas Jansen, and Per Kristian Lehre:
Populations can be essential in Dynamic Optimisation,
To appear in Proceedings of the 17th annual Genetic and
Evolutionary Computation Conference (GECCO 2015), Madrid,
Spain, July 11-15, 2015.
Duc-Cuong Dang and Per Kristian Lehre:
Simplified Runtime Analysis of Estimation of Distribution Algorithms,
To appear in Proceedings of the 17th annual Genetic and
Evolutionary Computation Conference (GECCO 2015), Madrid,
Spain, July 11-15, 2015. (slides)
Dogan Corus and Per Kristian Lehre: Theory-driven Design of
efficient Genetic Algorithms for a classical Graph Problem.
To appear in Proceedings of the 11th Metaheuristics International
Conference (MIC 2015), June 7-10th 2015, Agadir, Morocco.
Dogan Corus, Per Kristian Lehre, Frank Neumann, Mojgan Pourhassan: A
Parameterised Complexity Analysis of Bi-level Optimisation with
Evolutionary Algorithms. To appear in Evolutionary Computation
Journal, MIT Press. (2015)
Duc-Cuong Dang, Per Kristian Lehre: Efficient Optimisation of Noisy
Fitness Functions with Population-based Evolutionary Algorithms.
In Proceedings of Foundations of Genetic Algorithms (FOGA
2015), Aberystwyth, January 2015.
Golnaz Badkobeh, Per Kristian Lehre, Dirk Sudholt: Black-box
Complexity of Parallel Search with Distributed Populations.
To appear in Proceedings of Foundations of Genetic Algorithms (FOGA
2015), Aberystwyth, January 2015.
2014
Per Kristian Lehre and Carsten Witt,
Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift,
to appear in Proceedings of The 25th International Symposium on
Algorithms and Computation (ISAAC 2014), Jeonju, Korea.
Best Paper Award
Dogan Corus, Duc-Cuong Dang, Anton V. Eremeev and Per Kristian Lehre,
Level-based Analysis of Genetic Algorithms and other Search Processes,
to appear in Proceedings of
13th International Conference on Parallel Problem Solving from Nature
(PPSN 2014),
Ljubljana, Slovenia.
Nominated for best paper award.
Golnaz Badkobeh, Per Kristian Lehre and Dirk Sudholt,
Unbiased Black-Box Complexity of Parallel Search,
to appear in Proceedings of
13th International Conference on Parallel Problem Solving from Nature
(PPSN 2014),
Ljubljana, Slovenia.
Fawaz Alanazi and Per Kristian Lehre,
Runtime Analysis of Selection Hyper-heuristics with Various Learning
Mechanisms,
to appear in Proceedings of 2014 IEEE Congress on Evolutionary
Computation (CEC), Beijing, China.
Duc-Cuong Dang and P. K. Lehre. Refined upper bounds on
the expected runtime of non-elitist populations from
fitness-levels. In Proceedings of the 16th Annual
Conference on Genetic and Evolutionary
Computation, (GECCO 2014), pages 1367-1374, New
York, NY, USA, 2014. ACM.
Duc-Cuong Dang and Per Kristian Lehre. Evolution under partial
information. In Proceedings of the 16th Annual Conference on
Genetic and Evolutionary Computation, (GECCO 2014), pages
1359-1366, New York, NY, USA, 2014. ACM.
Nominated for best paper award.
2013
Philipp Rohlfshagen, Per Kristian Lehre, and Xin Yao.
Theoretical advances in evolutionary dynamic optimization
. In Shengxiang Yang and
Xin Yao, editors, Evolutionary Computation for Dynamic Optimization
Problems, volume 490 of Studies in Computational Intelligence, pages
221-240. Springer Berlin Heidelberg, 2013.
Dogan Corus, Per Kristian Lehre, and Frank Neumann, The Generalized
Minimum Spanning Tree Problem: A Parameterized Complexity Analysis of
Bi-level Optimisation, To appear in Proceedings of the Genetic and
Evolutionary Computation Conference (GECCO 2013), July 06-10, 2013,
Amsterdam, The Netherlands. Best paper award.
Per Kristian Lehre and Carsten Witt,
Finite First Hitting Time versus Stochastic Convergence
in Particle Swarm Optimisation,
To appear in Proceedings of the 9th
Metaheuristic International Conference (MIC 2011),
July 25-28, 2011, Udine, Italy.
(Preprint: arXiv:1105.5540)
Per Kristian Lehre,
Fitness-Levels for Non-Elitist Populations,
In Proceedings of the
Genetic and Evolutionary Computation Conference (GECCO 2011),
July 12-16, 2011, Dublin, Ireland.
Pages 2075-2082, ACM New York, NY, USA.
(slides)
Stephan Cathabard, Per Kristian Lehre and Xin Yao,
Non-uniform Mutation Rates for Problems with Unknown Solution Lengths,
In Proceedings of the 11th workshop proceedings on Foundations of
genetic algorithms, (FOGA 2011), pages 173-180, New York, NY, USA, 2011. ACM.
Benjamin Doerr, Daniel Johannsen, Timo Kötzing, Per Kristian Lehre, Markus Wagner, and Carola Winzen,
Faster Black-Box Algorithms Through Higher Arity Operators,
In Proceedings of the 11th workshop proceedings on
Foundations of genetic algorithms, (FOGA 2011), pages 163-172, New York,
NY, USA, 2011. ACM.
2010
Per Kristian Lehre,
Negative Drift in Populations,
In Proceedings of
11th International Conference on
Parallel Problem Solving From Nature (PPSN XI),
LNCS 6238/2011, pages 244-253,
September 11-15, 2010 Krakow, Poland.
(DOI,
BiBTeX)
Per Kristian Lehre and Carsten Witt,
Black Box Search by Unbiased Variation,
In Proceedings of the
Genetic and Evolutionary Computation Conference (GECCO 2010),
pages 1441-1449,
July 7-11, 2010 Portland, Oregon, USA.
Best paper award.ECCC TR10-102
Timo Kötzing, Per Kristian Lehre, Frank Neumann and Pietro Oliveto,
Ant Colony Optimization and the Minimum Cut Problem,
In Proceedings of
the Genetic and Evolutionary Computation Conference (GECCO 2010),
pages 1393-1400,
July 7-11, 2010 Portland, Oregon, USA.
Pietro S. Oliveto, Per Kristian Lehre, and Frank Neumann. Theoretical
analysis of rank-based mutation - combining exploration and
exploitation. In Proceedings of the 2009 IEEE Congress on Evolutionary
Computation (CEC 2009),
pages 1455-1462,
Trondheim, Norway, May 18-21, 2009.
Nominated for best paper award.
Per Kristian Lehre and Pauline C. Haddow -
Accessibility and Runtime between Convex Neutral Networks.
In Proceedings of the 6th International Conference on
Simulated Evolution and Learning, Hefei, China, Oct. 15-18,
LNCS 4247, pages 734-741, Springer (2006). xkcd
Morten Hartman, Pauline C. Haddow and Per Kristian Lehre -
The Genotypic complexity of Evolved Fault-tolerant and Noise-robust Circuits,
Sixth International Workshop on Information Processing in Cells and Tissues (IPCAT2005),
York, UK, Aug. 30 - Sept. 1, 2005.
Morten Hartman, Pauline C. Haddow and Per Kristian Lehre -
Evolved Digital Circuits and Genome Complexity,
In Proceedings of The 2005 NASA/DoD Conference on Evolvable Hardware,
Washington DC, USA, Jun 29 - Jul 1, 2005.
Per Kristian Lehre and Pauline C. Haddow -
Developmental Mappings and Phenotypic Complexity. In proceedings of
IEEE Congress on Evolutionary Computation (CEC2003), Canberra,
Australia, Dec 8 - 12, pp 62-68, (Vol. 1), 2003.
Tweets by @pklehre