Login | Sign up

Fully-funded PhD Research Studentship: Time complexity Analysis of Bio-Inspired Computation

About the Department The Department of Computer Science was established in 1982 and has since attained an international reputation for its research and teaching. In the very recent Research Excellence Framework, 45% of the research in the department was recognised as internationally excellent in terms of originality, significance and rigour, and another 47% as internationally world leading. These results place the department among the top 5 UK computer science departments for research excellence.


Bio-inspired meta-heuristics are general purpose algorithms that mimic powerful mechanisms from nature such as the natural evolution of species or the collective intelligence of animals with the goal of solving complex optimisation problems. Popular bio-inspired meta-heuristics are genetic algorithms, ant colony optimisation and artificial immune systems. They have been applied to a broad range of problems in various disciplines with remarkable success. They are particularly useful in settings where no knowledge on the problem is available (black-box optimisation) and evaluating candidate solutions is the only means of learning about the problem at hand. However, the reasons behind their success are often elusive: their performance often depends crucially, and unpredictably, on design choices and parameters. Furthermore, given a class of bio-inspired algorithms it is unclear on which kind of problems it performs well and on which it performs poorly. This lack of understanding represents a major obstacle for the wide-spread uptake and usage of bio-inspired computing techniques and for the development of more effective variants.

In recent years theoretical analyses have emerged that provide results about the performance of bio-inspired algorithms. They rigorously estimate the expected time required by the algorithms to find a satisfactory solution for various optimisation problems. Such analyses use mathematical techniques drawn and extended from the fields of randomised algorithms, probability theory and computational complexity. The results allow for insights into the working principles of bio-inspired meta-heuristics, enable the assessment of parameter choices and design aspects while contributing to the design of more powerful algorithms.

This studentship offers a valuable opportunity to work within this very active, challenging and exciting field of research at the intersection between computational complexity and bio-inspired computation. The successful applicant will also have the opportunity to further develop his/her research skills and expertise by collaborating with a wide range of top class researchers in bio-inspired computing who are partners of the EPSRC funded project. Project partners include, amongst others, research groups at the University of Birmingham, UK, at the Technical University of Denmark (DTU) in Lyngby, Denmark and at the University of Adelaide, Australia.

Research Topics

The successful applicant will perform high quality research in the area of time complexity analysis of bio-inspired computation. During the PhD studies, he/she will develop expertise in one or more promising research areas of his/her choice connected to the “Rigorous Runtime Analysis of Bio-inspired Computing” project at The University of Sheffield.

Possible topics include the performance analysis of:

a) Population-based metaheuristics, highlighting their advantages over single-trajectory algorithms; b) Parallel evolutionary algorithms, explaining how to exploit modern parallel architectures in bio-inspired computing; c) Genetic programming: how to evolve computer programs effectively; d) Black box complexity: what is the best possible performance of any bio-inspired algorithm for a given problem class; e) Fixed budget computation: what solution quality is achieved given limited resources, such as the available time.

The Candidate

Applicants must have at least a 2.1 or above degree in Computer Science. Outstanding applicants from Mathematics, Physics and Engineering will also be considered and are encouraged to apply. The successful applicant must have excellent analytical and computational skills. He/She must be an excellent team player who can work independently and communicate well with others. Since the project is theoretically challenging, strong mathematical and probability theory skills are required. Interest and enthusiasm for bio-inspired computing are essential while experience with modern meta-heuristics such as evolutionary algorithms and computational complexity analyses are desirable.

The Studentship

Duration: Three years full-time (subject to satisfactory progress).

Payments: The award covers tuition fees plus a living stipend at the standard UK research rate - currently £13,863 per annum. Funding is available for conference attendance and research visits to partner organisations.

Deadline: The position is available immediately and will be open until it is filled.

How to Apply

Applicants should apply using the online application form at:


For more information on the PhD Programme at The University of Sheffield:


For further information and informal enquiries contact Dr. Pietro Oliveto at


Dr. Pietro Oliveto's webpage: http://www.dcs.shef.ac.uk/people/P.Oliveto/

Duration/PeriodThree years full-time (subject to satisfactory progress).

Recover your password

Please, provide the email you used to register. We will send an email to that address with a link that will take you to the reset password page. After resetting your password you will be automatically logged in to the system.

Already a member?

If you had an account on the old website, please provide the email you used to register there. After resetting your password you will be automatically signed in to the system.

Already have an account? Log in