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

Applications are invited for a fully-funded PhD studentship on the runtime analysis of bio-inspired computation techniques. The successful candidate will join the EPSRC funded project "Rigorous Runtime Analysis of Bio-inspired Computing" and will work alongside other researchers involved in the project at The University of Sheffield and at project partner organisations in UK, Europe and worldwide.

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:

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 positions are available immediately and will be open until they are filled.

For further information and informal enquiries contact Dr. Pietro Oliveto at p.oliveto@sheffield.ac.uk