Potential Topics for PhD Theses in the Area of Theory Randomised Search Heuristics Including Two Concrete Project Proposals

Supervisor Thomas Jansen, Department of Computer Science, Aberystwyth University
t.jansen@aber.ac.uk
http://users.aber.ac.uk/thj10

Keywords evolutionary algorithms, artificial immune systems, simulated annealing,
random local search, ant colony optimisation, estimation of distribution
algorithms, black-box complexity, runtime analysis

Randomised search heuristics are a huge and diverse class of algorithms that are often used in practice to solve hard optimisation problems when no good problem-specific algorithm is available. Fairly complex and often nature-inspired search heuristics like evolutionary algorithms, artificial immune systems, and ant colony optimisation belong to this class as well as much simpler approaches like simulated annealing and random local search. A growing body of theoretical work improves our understanding of these heuristics, explains when they should and should not be used, and guides us in designing more effective and efficient randomised search heuristics.

Starting in the area of evolutionary algorithms a number of analytical tools and techniques to facilitate the analysis of randomised search heuristics have been developed in the last 20 years [3]. There is also an appropriate notion of complexity to categorise the hardness of problems for randomised search heuristics, called black-box complexity [2]. The field is sufficiently matured to allow to tackle exciting and relevant problems now. It is a major goal to develop theoretical results that are of direct significance for practical applications. There is the potential for a number of PhD projects in this area. Below are two suggestions. I am always happy to discuss other ideas in this area. Work in the area requires basic knowledge of algorithms and programming, a good understanding of algorithm analysis and complexity, and the ability or willingness to learn to analyse randomised algorithms and random processes.

fixed budget computations: Traditionally, analysis of randomised search heuristics concentrates on the runtime,i.e., the time needed on average to find a solution of a pre-specified quality. This perspective is not well aligned with practical applications when often the algorithms are stopped after some time. Recently, a novel perspective more in line with this way of applying randomised search heuristics has been suggested, analysing the average solution quality after a pre-specified number of steps [6]. Currently, only results for the most simple randomised search heuristics and the most simple example functions are available. It is a challenging and important topic to extend the analysis to match the current scope of runtime analysis with respect to both, algorithms and problems. Moreover, modifications of the model to make it match the situation in practice even more closely should be explored.

modules in randomised search heuristics: From a software engineering point of view, randomised search heuristics can be described as being algorithmically simple frameworks employing a small number of generic modules like selection and variation. Concrete instantiations of these modules define the specific type of randomised search heuristic. In principle, these modules can be combined in arbitrary ways allowing for a systematic design of novel randomised search heuristic. The hope is to be able to come to a principled design of randomised search heuristics that are custom-tailored towards a specific applications leading to more effective and efficient algorithms. While by now there is a good understanding of different mutation operators [1,4,5] it is an open problem to develop or more general understanding of the other operators and, most importantly, their interplay.

REFERENCES

[1] B. Doerr, T. Jansen, and C. Klein (2008):
Comparing global and local mutations on bit strings.
In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2008).
ACM Press, New York, pages 929-936.
http://dx.doi.org/10.1145/1389095.1389274

[2] S. Droste, T. Jansen, and I. Wegener (2006):
Upper and lower bounds for randomized search heuristics in black-box optimization.
Theory of Computing Systems 39(4):525-544.
http://dx.doi.org/10.1007/s00224-004-1177-z

[3] T. Jansen (2013):
Analyzing Evolutionary Algorithms. The Computer Science Perspective.
Springer.
http://link.springer.com/book/10.1007/978-3-642-17339-4

[4] T. Jansen and D. Sudholt (2010):
Analysis of an asymmetric mutation operator.
Evolutionary Computation 18(1):1-26.
http://dx.doi.org/10.1162/evco.2010.18.1.18101

[5] T. Jansen and C. Zarges (2011):
Analyzing different variants of immune inspired somatic contiguous hypermutations.
Theoretical Computer Science 412(6):517-533.
http://dx.doi.org/10.1016/j.tcs.2010.09.027

[6] T. Jansen and C. Zarges (2012):
Fixed budget computations: A different perspective on run time analysis.
In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012).
ACM Press, New York, pages 1325-1332.
http://dx.doi.org/10.1145/2330163.2330347

-----------------------------------------

Potential Topic for a PhD Thesis in the Area of Randomised Search Heuristics
Supervisor Thomas Jansen, Department of Computer Science, Aberystwyth University
t.jansen@aber.ac.uk
http://users.aber.ac.uk/thj10

Keywords evolutionary algorithms, artificial immune systems, simulated annealing,
random local search, combinatorial optimisation

Randomised search heuristics are a huge and diverse class of algorithms that are often used in practice to solve hard optimisation problems when no good problem-specific algorithm is available. Fairly complex and often nature-inspired search heuristics like evolutionary algorithms, artificial immune systems, and ant colony optimisation belong to this class as well as much simpler approaches like simulated annealing and random local search. A growing body of theoretical work improves our understanding of these heuristics, explains when they should and should not be used, and guides us in designing more effective and efficient randomised search heuristics.

Starting in the area of evolutionary algorithms a number of analytical tools and techniques to facilitate the analysis of randomised search heuristics have been developed in the last 20 years [1]. The field is sufficiently matured to allow to tackle exciting and relevant problems now. One of the most notorious problems in the field of randomised search heuristics is the large gap between theory and practice. Reasons for this gap have been pointed out [6,7] and the wish to bridge this gap has been voiced more than once [5].

More recently, the performance of randomised search heuristics for combinatorial optimisation problems has come into focus [9]. Recent results hint at combinatorial optimisation problems where specific kinds of randomised search heuristics may perform particularly well [2,3,4,8]. It is an open problem to rigorously compare such theoretically motivated randomised search heuristics with the best problem-specific algorithms, describe for what problems, what optimisation goals, and what classes of instances randomised search heuristics actually excel. Based on such an empirical investigation improved randomised search heuristics should be developed to demonstrate how existing theory-based insights help to derive the best performing algorithms in practice. Work in the area requires excellent knowledge of algorithms and programming, some knowledge of algorithm analysis, and an appreciation of theoretical run time analysis of randomised search heuristics.

REFERENCES

[1] T. Jansen (2013):
Analyzing Evolutionary Algorithms. The Computer Science Perspective.
Springer.
http://dx.doi.org/10.1007/978-3-642-17339-4

[2] T. Jansen, P.S. Oliveto, and C. Zarges (2011):
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 2011).
LNCS 6825, Springer. Pages 117-131.
http://dx.doi.org/10.1007/978-3-642-22371-6_13

[3] T. Jansen, P.S. Oliveto, and C. Zarges (2013):
Approximating vertex cover using edge-based representations.
In Proceedings of the 12th Workshop Proceedings on Foundations of Genetic Algorithms (FOGA 2013).
ACM. To appear.

[4] T. Jansen and D. Sudholt (2010):
Analysis of an asymmetric mutation operator.
Evolutionary Computation 18(1):1-26.
http://dx.doi.org/10.1162/evco.2010.18.1.18101

[5] T. Jansen and R.P. Wiegand (2004):
Bridging the gap between theory and practice.
In Proceedings of the 8th International Conference on Parallel Problem Solving From Nature (PPSN VIII).
LNCS 3242, Springer. Pages 61-71.
http://dx.doi.org/10.1007/978-3-540-30217-9_7

[6] T. Jansen and C. Zarges (2011):
Analysis of evolutionary algorithms: from computational complexity analysis to algorithm engineering.
In Proceedings of the 11th Workshop Proceedings on Foundations of Genetic Algorithms (FOGA 2011).
ACM. Pages 1-14.
http://dx.doi.org/10.1016/10.1145/1967654.1967656

[7] T. Jansen and C. Zarges (2012):
Fixed budget computations: A different perspective on run time analysis.
In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2012).
ACM Press, New York, pages 1325-1332.
http://dx.doi.org/10.1145/2330163.2330347

[8] T. Jansen and C. Zarges (2012):
Computing longest common subsequences with the B-Cell algorithm.
In Proceedings of the 12th International Conference on Artificial Immune Systems (ICARIS 2012).
LNCS 7595, Springer. Pages 111-124.
http://dx.doi.org/10.1007/978-3-642-33757-4_9

[9] F. Neumann and C. Witt (2010):
Bioinspired Computation in Combinatorial Optimization.
Springer.
http://dx.doi.org/10.1007/978-3-642-16544-3