Dr. Per Kristian Lehre

Lecturer in The School of Computer Science at the University of Nottingham.

Contact

Per Kristian Lehre
ASAP Research Group
School of Computer Science (Office C42)
University of Nottingham
Jubilee Campus
Wollaton Road
Nottingham, NG8 1BB
United Kingdom

T: +44 0115 82 32825

Research Interests

My research interests are in the theoretical foundations of randomised search heuristics, in particular time-complexity analysis of evolutionary algorithms.

Current Activities

• Guest editing Special issue on Theoretical Foundations of Evolutionary Computation in IEEE Transactions on Evolutionary Computation.
• Giving tutorials about drift analysis at CEC 2013 and ThRaSH 2013.
• Joined the editorial board of Evolutionary Computation (MIT Press).
• Giving a tutorial about Runtime Analysis of Evolutionary Algorithms at GECCO 2013.
• The journal version of Black-box search by unbiased variation has been published in Algorithmica.
• Our special issue of Theoretical Computer Science on Theoretical Foundations of Evolutionary Computation has been printed.

Publications

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. Nominated for 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.