Dr. Per Kristian Lehre
Tweets by @pklehreProfessor in School of Computer Science at the University of Birmingham and Turing AI Acceleration Fellow.
Contact and Office Hours
Per Kristian Lehre
School of Computer Science (Office 207)
University of Birmingham
Edgbaston
B15 2TT, United Kingdom
Email:
Phone: +44 (0)121 414 8560
Office hours (by appointment) (Zoom).
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.
Current Activities and News
- 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.
- Co-organising with Benjamin Doerr the 2021 ThRaSh Seminar series.
- GECCO Theory Track 2018 special issue of Algorithmica guest-edited with Anne Auger has appeared online.
- Giving IEEE CIS Webinar on Self-adaptation
- Giving an tutorial on Runtime Analysis of Evolutionary Algorithms at GECCO 2021 with Pietro S. Oliveto.
- Chairing the GECCO 2019 Theory Track with Johannes Lengler.
- Giving keynote on "Algorithmic Perspectives on Evolution" at the OPTA 2018 conference in Omsk, Russia.
- Paper on level-based analysis accepted for publication in IEEE Transactions on Evolutionary Computation
- I joined the School of Computer Science at the University of Birmingham as a Senior Lecturer from January 2017.
PostDocs and PhD Students
- Mario Hevia Fajardo (PostDoc, started Feb 2022)
- Shishen Lin (PhD student, first supervisor, since Sept 2021)
- Efstratios Palias (PhD student, second supervisor, since Sept 2020)
- Xiaoyu Qin (PhD student, first supervisor, since Jan 2020)
- Phan Trung Hai Nguyen (PhD student, first supervisor, completed May 2021)
- Daniel Herring (PhD student, second supervisor)
- Xunzhao Yu (PhD student, second supervisor)
- Fawaz Alanazi (PhD student, first supervisor, completed Feb 16th 2017)
- Haneen Algethami (PhD student, second supervisor, completed Feb 2017)
- Dogan Corus (PhD student, first supervisor, completed Dec 15th 2016)
- Duc-Cuong Dang (PostDoc, completed Dec 2016)
- Shahriar Asta (PhD student, second supervisor, completed)
Publications
2022
- Per Kristian Lehre and Xiaoyu Qin, More Precise Runtime Analyses of Non-elitist Evolutionary Algorithms in Uncertain Environments, Algorithmica, 2022.
- 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
- Per Kristian Lehre, Runtime Analysis of Competitive co-Evolutionary Algorithms for Maximin Optimisation of a Bilinear Function. To appear in Proceedings of Genetic and Evolutionary Computation Conference (GECCO '22).
- Per Kristian Lehre and Xioayu Qin, Self-adaptation via Multi-objectivisation: A Theoretical Study To appear in Proceedings of Genetic and Evolutionary Computation Conference (GECCO '22). Implementation in C of MOSA-EA.
- Duc-Cuong Dang, Anton Eremeev, Per Kristian Lehre, and Xiaoyu Qin, Fast Non-elitist Evolutionary Algorithms with Power-law Ranking Selection. To appear in Proceedings of Genetic and Evolutionary Computation Conference (GECCO '22).
2021
- Per Kristian Lehre and Phan Trung Hai Nguyen, Runtime Analyses of Population-Based Univariate Estimation of Distribution Algorithms on LeadingOnes, Algorithmica, 83(10), 3238-3280 (2021).
- Duc-Cuong Dang, Anton Eremeev, and Per Kristian Lehre, Non-elitist Evolutionary Algorithms excel in Fitness Landscapes with Sparse Deceptive Regions and Dense Valleys, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2021), 1133-1141, ACM video corrigendum
- Per Kristian Lehre and Xiaoyu Qin, More Precise Runtime Analysis of Non-elitist EAs in Uncertain Environments, In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2021), 1160-1168, ACM
- Duc-Cuong Dang, Anton Eremeev, and Per Kristian Lehre, Escaping Local Optima with Non-Elitist Evolutionary Algorithms, In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 2021), Vol 35, No 14, Technical Tracks 14. video simulation
2020
- Per Kristian Lehre and Carsten Witt, Tail Bounds on Hitting Times of Randomized Search Heuristics Using Variable Drift Analysis, Combinatorics, Probability & Computing, Cambridge University Press
- 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.2985450 arXiv:2004.00327. slides video erratum
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
- Barbora Trubenova, Martin S. Krejca, Per Kristian Lehre, and Timo Kötzing, Surfing on the seascape: Adaptation in a changing environment, to appear in Evolution, Wiley.
2018
- Duc-Cuong Dang, Per Kristian Lehre, and Phan Trun Hai Nguyen, Level-based Runtime Analysis of the Univariate Marginal Distribution Algorithm To appear in Algorithmica. DOI
- 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
2017
- Dogan Corus and Per Kristian Lehre, Theory Driven Design of Efficient Genetic Algorithms for a Classical Graph Problem, In: Amodeo L., Talbi EG., Yalaoui F. (eds) Recent Developments in Metaheuristics. Operations Research/Computer Science Interfaces Series, vol 62. Springer, Cham
- Dogan Corus, Duc-Cuong Dang, Anton Eremeev and Per Kristian Lehre, Level-Based Analysis of Genetic Algorithms and Other Search Processes, To appear in IEEE Transactions on Evolutionary Computation. DOI: 10.1109/TEVC.2017.2753538
- 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 Thomas Jansen and Per Kristian Lehre, Populations can be essential in tracking dynamic optima. Algorithmica (2017) 78(2) pp 660-680.
- Per Kristian Lehre and Phan Trung Hai Nguyen, Improved Runtime Bounds for the Univariate Marginal Distribution Algorithm via Anti-Concentration. In GECCO '17, Proceedings of Genetic and Evolutionary Computation Conference Pages 1383-1390, Berlin, Germany. DOI: 10.1145/3071178.3071317
2016
- 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.05551 Interactive 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.
- Duc-Cuong Dang and Per Kristian Lehre, Runtime Analysis of Non-elitist Populations: From Classical Optimisation to Partial Information. To appear in Algorithmica. (eprint)
2015
- 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 Ender Özcan, A runtime analysis of simple hyper- heuristics: To mix or not to mix operators, Proceedings of the 12th Workshop on Foundations of Genetic Algorithms (FOGA 2013), January 16-20, Adelaide, Australia. Pages 97-104, ACM New York, NY, USA.
2012
- Per Kristian Lehre and Carsten Witt, Black-box search by unbiased variation, Algorithmica December 2012, Volume 64, Issue 4, pp 623-642
- Per Kristian Lehre and Xin Yao, On the Impact of Mutation-Selection Balance on the Runtime of Evolutionary Algorithms, IEEE Transactions on Evolutionary Computation 16(2):225-241 (2012), (Preprint: arXiv:1012.3098.)
2011
- 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)
- Stefan Kratsch, Per Kristian Lehre, Frank Neumann, Pietro Simone Oliveto, Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutations, In Proceedings of 11th International Conference on Parallel Problem Solving From Nature (PPSN XI), LNCS 6238/2011, pages 204-213, 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.
- Oliver Giel and Per Kristian Lehre, On The Effect of Populations in Evolutionary Multi-objective Optimisation, Evolutionary Computation, Vol. 18, No. 3: 357-381. 2010 MIT Press
- Per Kristian Lehre and Xin Yao, Runtime Analysis of the (1+1) EA on Computing Unique Input Output Sequences, Information Sciences, Elsevier, In Press, DOI: 10.1016/j.ins.2010.01.031.
- Per Kristian Lehre and Xin Yao, Crossover can be constructive when computing unique input-output sequences, Soft Computing, Springer, In Press, DOI: 10.1007/s00500-010-0610-2.
2009
- Per Kristian Lehre and Xin Yao. On the Impact of the Mutation-Selection Balance on the Runtime of Evolutionary Algorithms. In Proceedings of Foundations of Genetic Algorithms (FOGA 2009), Orlando, Florida, USA, January 9-11, 2009. An extended version is available as Per Kristian Lehre and Xin Yao, Technical Report CSR-09-07, The University of Birmingham, School of Computer Science, August 2009. (slides).
- Philipp Rohlfshagen, Per Kristian Lehre and Xin Yao. Dynamic Evolutionary Optimisation: An Analysis of Frequency and Magnitude of Change. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2009), pages 1713-1720, Montreal, Canada, July 8-12, 2009. Best paper award.
- Per Kristian Lehre and Xin Yao. Runtime analysis of search heuristics on software engineering problems. Frontiers of Computer Science in China, 3(1):64-72, Higher Education Press/Springer-Verlag GmbH, 2009.
- Tianshi Chen, Per Kristian Lehre, Ke Tang, and Xin Yao. When is an estimation of distribution algorithm better than an evolutionary algorithm? In Proceedings of the 2009 IEEE Congress on Evolutionary Computation (CEC 2009), Trondheim, Norway, May 18-21, 2009.
- 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.
2008
- Per Kristian Lehre and Xin Yao - Crossover can be constructive when computing unique input output sequences, In Proceedings of the 7th International Conference on Simulated Evolution and Learning, pages 595-604, Melbourne, Australia, Dec 7-10 (2008).
- Andrea Arcuri, Per Kristian Lehre, and Xin Yao - Theoretical runtime analyses of search algorithms on the test data generation for the triangle classification problem In Proceedings of the International Workshop on Search-Based Software Testing, Lillehammer, Norway, Apr. 9-11 (2008). Best PhD student paper award.
2007
- Per Kristian Lehre and Xin Yao - Runtime Analysis of (1+1) EA on Computing Unique Input Output Sequences, In Proceedings of 2007 IEEE Congress on Evolutionary Computation, pages 1882-1889, Singapore, Sept. 25-28, (2007).
- Morten Hartmann, Pauline Haddow and Per Kristian Lehre - The genotypic complexity of evolved fault-tolerant and noise-robust circuits Biosystems, 87:2-3, pages 224-232 (2007).
- Per Kristian Lehre and Pauline Haddow - Phenotypic complexity and local variations in neutral degree Biosystems, 87:2-3, pages 233-242 (2007).
2006
- Per Kristian Lehre - Complexity and Geometry in Artificial Development PhD thesis, Norwegian University of Science and Technology, ISBN 82-471-8046-4, (2006)
- 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
- Vidar Beisvag, Per Kristian Lehre, Herman Midelfart, Halfdan Aass, Odd Geiran, Arne Kristian Sandvik, Astrid Lægreid, Jan Komorowski and Øyvind Ellingsen - Aetiology-specific patterns in end-stage heart failure patients identified by functional annotation and classification of microarray data. European Journal of Heart Failure Volume 8, Issue 4, June 2006, Pages 381-389.
- Oliver Giel and Per Kristian Lehre - On the Effect of Populations in Evolutionary Multi-objective Optimization. In Proceedings of Genetic and Evolutionary Computation Conference 2006 (GECCO 2006). Seattle, USA, July 8-12, pages 651-658 (Vol. 1), 2006. Technical Report CI-202/06, Universität Dortmund. (Slides.) Best Paper Award.
2005
- Per Kristian Lehre and Pauline C. Haddow - Accessibility between Neutral Networks in Indirect Genotype-Phenotype Mappings. In proceedings of IEEE Congress on Evolutionary Computation (CEC2005), Edinburgh, UK, Sept 2 - 5, pp 419-426 (Vol. 1), 2005. (Erratum, Slides.)
- 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.
- Per Kristian Lehre and Pauline C. Haddow - Phenotypic Complexity and Local Variations in Neutral Degree, Sixth International Workshop on Information Processing in Cells and Tissues (IPCAT2005), York, UK, Aug. 30 - Sept. 1, 2005. (Slides.)
- 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.
2004
- Per Kristian Lehre and Morten Hartmann - Development and complexity-based fitness function modifiers. Workshop on Regeneration and Learning in Developmental Systems, Seattle, USA, June 27, (2004).
2003
- 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.