Pietro S. Oliveto

Senior Lecturer
EPSRC Early Career Fellow

• Department of Computer Science,
• The University of Sheffield,
• Regent Court,
• Portobello
• Sheffield S1 4DP, UK.

• Phone: +44 114 222 1812
• Email: P.Oliveto@sheffield.ac.uk

(Last update: 14 September 2017)

Current Occupation

I am a Senior Lecturer and an EPSRC Early Career Fellow at The University of Sheffield in the Department of Computer Science.

My main research interests are in bio-inspired computation, randomised search heuristics and randomised algorithms in general, with strong emphasis on runtime analysis and computational complexity.

Team Members

I lead the Rigorous Research team based in the Algorithms group of the Department Computer Science.


• • Dogan Corus (Research Associate).
• • Andrei Lissovoi (Research Associate).
• • George Hall (PhD Student).
• • John Alasdair Warwicker (PhD Student).
• • Donya Yazdani (PhD Student).

Former Team Members

• • Andrea Mambrini (Research Associate).
A Fully funded PhD studentship in time complexity analysis of bio-inspired computation is available now . Enquiries by enthusiastic candidates can be sent to me by email. Applications will be accepted until the posts are filled. Further details are here. Applicants should apply using the online application form here (New)

News & Forthcoming Events

• • I will be co-Charing the 2017 Foundations of Computational Intelligence (IEEE FOCI 2017) Symposium as part of the 2017 Sysmposium Series on Computational Intelligence (IEEE SSCI 2017) held on November 27 - December 1, 2017, Honolulu, Hawaii, USA (Organised together with Leonardo Franco and Manuel Ojeda-Aciego).
  • FOCI 2017 Keynote talk announced: ''Parameterised analysis of bio-inspired computing" by Prof. Frank Neumann, University of Adelaide (Tuesday 28th at 10:45)
• • I am guest editing together with Andrew Sutton a Special Issue of the Theoretical Computer Science journal (Elsevier) on the theory of Bio-inspired computation.
• • I have recently joined the EPSRC Peer Review College.
• • Our COST Action CA15140: Improving Applicability of Nature-Inspired Optimisation by Joining Theory and Practice (ImAppNIO) has been approved.

Recent News & Events

• • I have Co-Chaired the 2016 Foundations of Computational Intelligence (IEEE FOCI 2016) Symposium
  • as part of the 2016 Sysmposium Series on Computational Intelligence (IEEE SSCI 2015) held on December 6 - 9, 2016, Athens, Greece (Organised together with Leonardo Franco and Manuel Ojeda-Aciego).
  • FOCI 2016 Special Sessions: "Emerging Techniques in Computational Intelligence'' (organised by S. Aggarwal) and "Unconventional Computing: From concepts to Prototypes'' (organised A. Adamatzky and G. Sirakoulis)
  • FOCI 2016 Keynote: Friday Dec 9th, From Complexity Theory to Better Algorithms by Prof. Benjamin Doerr.
• • 9th Workshop on Theory of Randomised Search Heuristics (ThRaSH 2015)
  • 11-12 September 2015 in Sheffield, UK. (Organising Committee )
• • I am guest co-editor (together with A. Sutton) of a Special Issue of the Evolutionary Computation Journal (ECJ) entitled Theory of Evolutionary Algorithms 2014 .
• • 7th Workshop on Theory of Randomised Search Heuristics (ThRaSH 2013)
  • 13-14 September 2013 in Aberystwyth, Wales. (Organising Committee )
• • I've given Runtime Analysis tutorials at CEC 2017 in Donostia - San Sebastian, Spain, at GECCO 2017 (with P. K. Lehre) in July in Berlin, Germany, at PPSN 2016 (with P. K. Lehre) in Edinburgh, UK, at GECCO 2016, Colorado, USA, GECCO 2015 (with P. K. Lehre), Madrid, Spain, (11 July 2015), at WCCI 2014, Beijing, china, (6 July 2014), at GECCO 2014, Vancouver, Canada, (13 July 2014), at CEC 2013, 20 June 2013, Cancun, Mexico (4 hour tutorial) , at GECCO 2013 (with P. K. Lehre), 6 July 2013, Amsterdam, The Netherlands (2 hour tutorial) and at IEEE WCCI 2012 (Download Slides), 10 June 2012, Brisbane, Australia (4 hour tutorial) .
• • Theoretical Foundations of Bio-inspired Computation (Chair)
  • IEEE CIS Task Force (Link)

Book Chapters

 
• • P.K. Lehre, P.S. Oliveto.
  • Theoretical Analysis of Stochastic Search Algorithms.
  • In Handbook of Heuristics.
  • Mauricio G.C. Resende, Rafael Marti and Panos M. Pardalos editors, Springer, (To appear). (Arxiv Version)
• • P.S. Oliveto, X. Yao.
  • Runtime Analysis of Evolutionary Algorithms for Discrete Optimization.
  • In Theory of Randomized Search Heuristics~Foundations and Recent Developments, pp. 21-52.
  • B. Doerr and A. Auger editors, World Scientific, February 2011. (World Scientific)
• • A. Athanasiou, M. De Felice, G. Oliveto, P. S. Oliveto.
  • Dynamical Modeling and Parameter Identification of Seismic Isolation Systems by Evolution Strategies.
  • In Computational Intelligence, Studies in Computational Intelligence series N.465, pp. 101-118.
  • K. Madani, A. Dourado, A. Rosa, J. Felipe (Eds), Springer-Verlag, 2013.

Refereed Journal Papers

• • P. S. Oliveto, T. Paixão, J. Pérez Heredia, D. Sudholt, B. Trubenová.
  • How to Escape Local Optima in Black Box Optimisation: When Non-Elitism Outperforms Elitism. [Download]
  • Algorithmica,
  • 2017.
• • D.Corus, P. S. Oliveto.
  • Standard Steady State Genetic Algorithms can Hillclimb Faster than Mutation-only Evolutionary Algorithms. (In press) [Download Arxiv Version]
  • IEEE Transactions on Evolutionary Computation,
  • 2017.
• • D.-C. Dang, T. Friedrich, T. Kötzing, M. S. Krejca, P. K. Lehre, P. S. Oliveto, D. Sudholt, A. M. Sutton.
  • Escaping Local Optima Using Crossover with Emergent Diversity. (In press) [Download Arxiv Version]
  • IEEE Transactions on Evolutionary Computation,
  • 2017.
• • D. Corus, J. He, T. Jansen, P. S. Oliveto, D. Sudholt, C. Zarges.
  • On Easiest Functions for Mutation Operators in Bio-Inspired Optimisation. [Download]
  • Algorithmica,
  • Vol. 78 (2), 714-740, 2017.
  • DOI: 10.1007/s00453-016-0201-4
• • P.S.Oliveto, C.Witt.
  • Improved Time Complexity Analysis of the Simple Genetic Algorithm.
  • Theoretical Computer Science, (Elsevier)
  • Vol. 605, 21-41, 2015.
  • DOI: 10.1016/j.tcs.2015.01.002
• • P.S.Oliveto, C.Zarges.
  • Analysis of Diversity Mechanisms for Optimisation in Dynamic Environments with Low Frequencies of Change.
  • Theoretical Computer Science (Elsevier),
  • Vol. 561, 37-56, 2015.
  • DOI: 10.1016/j.tcs.2014.10.028
• • P.S.Oliveto, C.Witt.
  • On the Runtime Analysis of the Simple Genetic Algorithm.
  • Theoretical Computer Science (Elsevier),
  • Vol. 545, 2-19, 2014.
  • DOI: 10.1016/j.tcs.2013.06.015
• • P.S.Oliveto, C.Witt.
  • Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation.
  • Algorithmica (Springer),
  • Vol. 59 (3), 369-386, 2011.
• • T.Friedrich, P.S.Oliveto, D.Sudholt, C.Witt.
  • Analysis of Diversity-Preserving Mechanisms for Global Exploration.
  • Evolutionary Computation, (ECJ),
  • Vol. 17 (4), 455-476, 2009.
• • P.S.Oliveto, J.He, X.Yao.
  • Analysis of the (1+1)-EA for Finding Approximate Solutions to Vertex Cover Problems.
  • IEEE Transactions on Evolutionary Computation (IEEE TEVC),
  • Vol. 13 (5), 1006-1029, 2009.
• • P.S.Oliveto, J.He, X.Yao.
  • Time Complexity of Evolutionary Algorithms for Combinatorial Optimization: A Decade of Results.
  • International Journal of Automation and Computing (IJAC)
  • Vol. 4 (3), 281-293, 2007.

Recent Refereed Conference Publications

• • A. Lissovoi, P. S. Oliveto, J.A. Warwicker
  • On the Runtime Analysis of Generalised Selection Hyper-heuristics for Pseudo-Boolean Optimisation. [Download]
  • In Proceedings of the 2017 Genetic and Evolutionary Computation Conference (GECCO '17),
  • Berlin, Germany, July 15-19, 2017.
• • D. Corus, P. S. Oliveto, D. Yazdani
  • On the Runtime Analysis of the Opt-IA Artificial Immune System. [Download]
  • In Proceedings of the 2017 Genetic and Evolutionary Computation Conference (GECCO '17),
  • Berlin, Germany, July 15-19, 2017.
• • S. Nallaperuma, P. S. Oliveto, J. Perez Heredia, D. Sudholt
  • When is it Beneficial to Reject Improvements? [Download]
  • In Proceedings of the 2017 Genetic and Evolutionary Computation Conference (GECCO '17),
  • Berlin, Germany, July 15-19, 2017.
• • D.-C. Dang, T. Friedrich, T. Kötzing, M. S. Krejca, P. K. Lehre, P. S. Oliveto, D. Sudholt, A. M. Sutton
  • Emergence of Diversity and its Benefits for Crossover in Genetic Algorithms. [Download]
  • In Proceedings of the 14th Parallel Problem solving from Nature Conference (PPSN 2016),
  • Edinburgh, Scotland, September 17-21, 2016. (Best paper nomination)
• • D.-C. Dang, T. Friedrich, T. Kötzing, M. S. Krejca, P. K. Lehre, P. S. Oliveto, D. Sudholt, A. M. Sutton
  • Escaping Local Optima with Diversity Mechanisms and Crossover. [Download]
  • In Proceedings of the 2016 Genetic and Evolutionary Computation Conference (GECCO '16),
  • Colorado, USA, July 20-24, 2016.
• • P. S. Oliveto, T. Paixão, J. Pérez Heredia, D. Sudholt, B. Trubenová
  • When Non-Elitism Outperforms Elitism for Crossing Fitness Valleys. [Download]
  • In Proceedings of the 2016 Genetic and Evolutionary Computation Conference (GECCO '16),
  • Colorado, USA, July 20-24, 2016.
• • A. Mambrini, P.S. Oliveto
  • On the Analysis of Simple Genetic Programming for Evolving Boolean Functions. [Download]
  • In Proceedings of the 2016 European Conference on Genetic Programming, (EuroGP '16), pp. 99-114,
  • Porto, Portugal, March 30-April 1, 2016.(Best paper nomination)
• • D. Corus, J. He, T. Jansen, P.S.Oliveto, D. Sudholt, C.Zarges
  • On Easiest Functions for Somatic Contiguous Hypermutations And Standard Bit Mutations.
  • In Proceedings of the 2015 Genetic and Evolutionary Computation Conference (GECCO '15),
  • Madrid, Spain, July 11-15, 2015.
• • P.S.Oliveto, D. Sudholt, C.Zarges
  • On the Runtime Analysis of Fitness Sharing Mechanisms.
  • In Proceedings of the 13th Parallel Problem solving from Nature Conference (PPSN 2014),
  • Ljubljana, Slovenia, September 13-17, 2014.
• • P.S.Oliveto, D. Sudholt.
  • On the Runtime Analysis of Stochastic Ageing Mechanisms.
  • In Proceedings of the 2014 Genetic and Evolutionary Computation Conference (GECCO '14),
  • Vancouver, Canada, July 12-16, 2014. (Best paper award)
• • P.S.Oliveto, C. Zarges.
  • Analysis of Diversity Mechanisms for Robust Optimisation in Dynamic Environments with Low Frequencies of Change.
  • In Proceedings of the 2013 Genetic and Evolutionary Computation Conference (GECCO'13),
  • Amsterdam, the Netherlands, July 6-10, 2013.
• • P.S.Oliveto, C. Witt.
  • Improved Runtime Analysis of the Simple Genetic Algorithm.
  • In Proceedings of the 2013 Genetic and Evolutionary Computation Conference (GECCO'13),
  • Amsterdam, the Netherlands, July 6-10, 2013.
• • T. Jansen, P.S.Oliveto, C. Zarges.
  • Approximating Vertex Cover Using Edge-Based Representations.
  • In Proceedings of Foundations of Genetic Algorithms XII (FOGA'13),
  • Adelaide, Australia, January 16-20, 2013.
• • P.S.Oliveto, C. Witt.
  • On the Runtime Analysis of the Simple Genetic Algorithm.
  • In Proceedings of the 2012 Genetic and Evolutionary Computation Conference (GECCO'12),
  • Philadelphia, USA, July 7-11, 2012.
• • A. Athanasiou, M. De Felice, G. Oliveto, P. S. Oliveto
  • Evolutionary Algorithms for the Identification of Structural Systems in Earthquake Engineering.
  • In Proceedings of the International Conference on Evolutionary Computation Theory and Applications (ECTA'11),
  • Paris, france, October 24-26, 2011.(Best paper nomination)
• • T. Jansen, P. S. Oliveto, C. Zarges
  • On the Analysis of the Immune Inspired B-Cell Algorithm for the Vertex Cover Problem.
  • In Proceedings of the 10th International Conference on Artificial Immune Systems (ICARIS'11),
  • Cambridge, UK, July 18-21, 2011. (Best paper award)
• • F. Neumann, P. S. Oliveto, G. Rudolph, D. Sudholt
  • On the Effectiveness of Crossover for Migration in Parallel Evolutionary Algorithms.
  • In Proceedings of the 2011 Genetic and Evolutionary Computation Conference (GECCO'11),
  • Dublin, Ireland, July 12-16, 2011.
• • S. Kratsch, P.K. Lehre, F. Neumann, P.S. Oliveto
  • Fixed Parameter Evolutionary Algorithms and Maximum Leaf Spanning Trees: A Matter of Mutation.
  • In Proceedings of the 11th Conference on Parallel Problem Solving from Nature (PPSN'10),
  • Krakow, Poland, September 11-15, 2010.
• • T. Kötzing, P. K. Lehre, F. Neumann, P. S. Oliveto.
  • Ant colony optimization and the minimum cut problem.
  • In Proceedings of the 2010 Genetic and Evolutionary Computation Conference (GECCO'10),
  • Portland, Oregon, July 7-11, 2010.
• • A. Chandra, P. S. Oliveto, X. Yao.
  • Co-evolution of Optimal Agents for the Alternating Offers Bargaining Game.
  • In Proceedings of the European Conference on the Applications of Evolutionary Computation (EvoApplications 2010),
  • Istanbul Technical University, Istanbul, Turkey, April 7-9, 2010.
• • F.Neumann, P.S.Oliveto, C. Witt.
  • Theoretical Analysis of Fitness-Proportional Selection - Landscapes and Efficiency.
  • In Proceedings of the 2009 Genetic and Evolutionary Computation Conference (GECCO'09),
  • Montreal, Canada, July 8-12, 2009.
• • P.S.Oliveto, P.K.Lehre, F.Neumann.
  • Theoretical Analysis of Rank-based Mutation - Combining Exploration and Exploitation.
  • In Proceedings of the IEEE Congress on Evolutionary Computation 2009(CEC'09),
  • Trondheim, Norway, May 18-21, 2009. (Best student paper nomination)
• • P.S.Oliveto, C.Witt.
  • Simplified Drift Analysis for Proving Lower Bounds in Evolutionary Computation.
  • In Proceedings of the Parallel Problem Solving from Nature (PPSN'08),
  • Dortmund, Germany, September 13-17, 2008.
• • T. Friedrich, P.S.Oliveto, D.Sudholt, C.Witt.
  • Theoretical Analysis of Diversity Mechanisms for Global Exploration.
  • In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'08),
  • Atlanta, Georgia, USA, July 12-16, 2008. (Best paper award)
• • P.S.Oliveto, J.He, X.Yao.
  • Analysis of Population-based Evolutionary Algorithms for the Vertex Cover Problem.
  • In Proceedings of the IEEE World Congress on Computational Intelligence (WCCI'08),
  • Hong Kong, June 1-6, 2008. Pictures
• • P.S.Oliveto, J.He, X.Yao.
  • Evolutionary Algorithms and the Vertex Cover Problem .
  • In Proceedings of the IEEE Congress on Evolutionary Computation (CEC'07),
  • Singapore, September 25-28, 2007. Pictures

• • Co-Chair of the 2015 IEEE Symposium on Foundations of Computational Intelligence (IEEE FOCI 2015) ,
  • December 7 - 10, 2015, Capetown, South Africa.

• Co-Chair of the IEEE WCCI 2016 Special Session on "Theoretical Foundations of Bio-inspired Computation"

• Co-Chair of the IEEE CEC 2015 Special Session on "Theoretical Foundations of Bio-inspired Computation"

• Co-Chair of the IEEE WCCI 2014 Special Session on "Theoretical Foundations of Bio-inspired Computation"

• Co-Chair of the IEEE CEC 2013 Special Session on "Theoretical Foundations of Bio-inspired Computation"

Programme Committees

• 24th International Joint Conference on Artificial Intelligence ( IJCAI'15).
• Genetic and Evolutionary Computation Conference (GECCO'08 ,GECCO'09, GECCO'10, GECCO'11, GECCO'12, GECCO'13, GECCO'14, GECCO'15, GECCO'16 ).
• IEEE Congress on Evolutionary Computation (CEC'07,WCCI'08,CEC'09,WCCI'10, CEC'11, CEC'13, WCCI'12)
• 2009 Foundations Of Genetic Algorithms (FOGA'09,FOGA'13, FOGA'15, FOGA'17).
• International Conference in Parallel Problem Solving from Nature (PPSN-X,PPSN-XI, PPSN-XIII, PPSN-XIV)
• IEEE Symposium on Foundations Of Computational Intelligence (First:FOCI'07,Second:FOCI'11,Third:FOCI'13, FOCI'14)
• Theory of Evolutionary Algorithms seminar, Schloss Dagstuhl, Germany, 27 January - 1 February, 2008. (Proceedings Collector)
• Workshop Italiano di Vita Artificiale e Computazione Evolutiva (WIVACE'07,WIVACE'08) (Italian Workshop of artificial life and evolutionary computation).
• 8th European Conference on Evolutionary Computation in Combinatorial Optimisation ( EVOCOP'08) (Reviewer).
• 10th International Conference on Artificial Immune Systems ( ICARIS'11).
• International Joint Conference on Computational Intelligence ( IJCCI'10, IJCCI'11).
• International Workshop on Nature Inspired Cooperative Strategies for Optimization (NICSO'07).

Organising Committees

• • 9th Workshop on Theory of Randomised Search Heuristics (ThRaSH 2015).
  • 11-12 September 2015, Sheffield, UK.
• • 7th Workshop on Theory of Randomised Search Heuristics (ThRaSH 2013).
  • 13-14 September 2013, Aberystwyth, Wales.
• • 27^th British Colloquium for Theoretical Computer Science (BCTCS'11)
  • 18-21 April 2011, Birmingham, UK.
• • Minisymposium on "Randomized Search Heuristics: Theoretical Aspects and Real World Applications" (Flyer)
  • at SIAM Conference on Optimization (SiamOPT11) 16-19 May 2011, Darmstadt, Germany.
• • 3rd Workshop on Theory of Randomised Search Heuristics (TRSH09).
  • 19-20 October 2009, Birmingham, UK.

Journal editing and reviewing

• Associate Editor of the IEEE Transactions on Evolutionary Computation (IEEE TEVC) journal.
• Guest Co-Editor of Journal of Computer Science and Technology (Springer), Special Issue on ''Evolutionary Computation''.
• Guest Co-Editor of the Evolutionary Computation Journal (ECJ-Mit Press), Special Issue on ''Theory of Evolutionary Computation 2014''.

• Theoretical Computer Science (Elsevier).
• Journal of Genetic Programming and Evolvable Machines (Springer).
• Algorithmica (Springer).
• IEEE Transactions on Neural Networks (IEEE-TNN).
• IEEE Transactions on Cybernetics
• Evolutionary Computation (MITpress).
• Information Sciences (Elsevier).
• IEEE Transactions on Evolutionary Computation (IEEE-TEVC).
• International Journal of Metaheuristics (Inderscience).
• Artificial Intelligence (Elsevier).
• Engineering Applications of Artificial Intelligence (Elsevier).
• Journal of Computer Science and Technology
• Natural Computing (Springer).
• Information Processing Letters (Elsevier).
• Soft Computing (Springer).
• Applied Mathematics and Computation (Elsevier).

Grants & Fellowships

• COST Action CA15140: Improving Applicability of Nature-Inspired Optimisation by Joining Theory and Practice (ImAppNIO)
• EPSRC Early Career Fellowship (2015-2020) Rigorous Runtime Analysis of Bio-inspired Computing ( EP/M004252/1 )
• Vice Chancellor Fellowship, University of Sheffield (2013-2016).
• EPSRC Postdoctoral Fellowship in Theoretical Computer Science grant (2010-2013), "Rigorous Runtime Analysis of Nature Inspired Meta-heuristics" ( EP/H028900/1 )
• EPSRC PhD+ Postdoctoral Fellowship grant (2009). ( EP/P502322/1)
• IEEE student travel grant for the CEC'09 conference attendance.
• IEEE student travel grant for the FOCI'07 conference attendance.

Workshops & Summer Schools

• Fifth Workshop on the Theory of Randomized Search Heuristics (ThRaSH'2011), Copenhagen, Denmark, 8-9 July 2011.
• Minisymposium on "Randomized Search Heuristics: Theoretical Aspects and Real World Applications" at SIAM Conference on Optimization (SiamOPT11) 16-19 May 2011, Darmstadt, Germany.
• 2011 Artificial Immune Systems seminar, Schloss Dagstuhl, Germany, 25 April - 29 April, 2011.
• 27th British Colloquium for Theoretical Computer Science (BCTCS2011), Birmingham, UK, 18-21 April 2011.
• 2010 Theory of Evolutionary Algorithms seminar, Schloss Dagstuhl, Germany,5 September - 10 September, 2010.
• Fourth Workshop on the Theory of Randomized Search Heuristics (ThRaSH'2010), Paris, France, 24-25 March 2010.
• Third Workshop on the Theory of Randomized Search Heuristics (TRSH3), Birmingham, UK, 19-20 October 2009.
• MOMiNE 2009 International Summer School (MOMINE'09), Cetraro, Cosenza, Italy, 1-11 September, 2009.
  (Tutorial on runtime analysis of EAs)
• Second Workshop on the Theory of Randomized Search Heuristics (TRSH2), Dortmund, Germany 13 September 2008.
• 2008 Theory of Evolutionary Algorithms seminar, Schloss Dagstuhl, Germany, 27 January - 1 February, 2008.
• First Workshop on the Theory of Randomized Search Heuristics (TRSH), Wroclaw, Poland 14-15 July 2007. Pictures
• Workshop on local Search, University Of Birmingham, Birmingham, Uk, July 2006.

Visiting Research

• Department of Algorithms and Logic (algolog) at Technical University of Denmark (DTU), Lyngby, Denmark, 24 June - 10 July 2011.
• Department of Civil and Environmental Engineering (DICA) at University of Catania(UNICT), Catania, Italy 2-10 May 2011.
• Department of Algorithms and Complexity (D1) at Max-Planck-Institut Fuer Informatik (MPI), Saarbruecken, Germany, 15-25 November 2010.
• At&t Research Labs (At&t), Florham Park, NJ,USA, May 2010 -- July 2010.
• Department of Algorithms and Logic (algolog) at Technical University of Denmark (DTU), Lyngby, Denmark, February 2010.
• Department of Algorithms and Complexity (D1) at Max-Planck-Institut Fuer Informatik (MPI), Saarbruecken, Germany, November 2009.
• Efficient Algorithms and Complexity Theory Institute (Lehrstuhl Informatik 2) at the Department of Computer Science (Facultaet Informatik) of the University of Dortmund (Techinsche Universitaet Dortmund) October 2007 - April 2008.