event
Thursday 09 Nov 2017: Sexual Reproduction Can Speed Up Optimisation
Dr. Pietro S. Oliveto - University of Sheffield
Harrison 170 14:30-15:30
Despite reproduction via recombination being at the centre stage in life and much more successful than asexual reproduction in natural evolution, most optimisation heuristics widely recognised to be successful in practice rely on variation operators that resemble or are inspired by asexual evolution. Examples of such heuristics include local search, simulated annealing and mutation-based evolutionary algorithms. We present an analysis of the performance of a standard steady state genetic algorithm (GA) for the Mastermind problem with two colours, also known as OneMax. We prove that the GA can identify the solution to the problem using fewer guesses than asexual evolution heuristics. By providing bounds on the optimisation time that decrease with the population size, we give an indication of the benefits of evolving a population of solutions via recombination, mutation and selection.
Bio:
Pietro S. Oliveto is a Senior Lecturer and an EPSRC Early Career Fellow at the University of Sheffield, UK. He received the Laurea degree in computer science from the University of Catania, Italy in 2005 and the PhD degree from the University of Birmingham,UK in 2009. He has been EPSRC PhD+ Fellow (2009-2010) and EPSRC Postdoctoral Fellow (2010-2013) at Birmingham and Vice-Chancellor’s Fellow at Sheffield (2013-2016). His main research interest is the performance analysis of bio-inspired computation techniques including evolutionary algorithms, genetic programming, artificial immune systems and hyperheuristics. He has won best paper awards at GECCO 2008, ICARIS 2011 and GECCO 2014. He is part of the Steering Committee of the annual workshop on Theory of Randomized Search Heuristics (ThRaSH), Associate Editor of the IEEE Transactions on Evolutionary Computation, Chair of the IEEE CIS Task Force on Theoretical Foundations of Bio-inspired Computation, Leader of the ImAppNIO Cost Action Working Group on Benchmarking and member of the EPSRC Peer Review College. Dr. Oliveto has given tutorials on the runtime complexity analysis of EAs regularly at CEC, GECCO, WCCI, SSCI and PPSN since 2012.
