How can we automatically design algorithms for a given problem domain? The aim of this tutorial is to demonstrate how we can use genetic programming to improve human-written programs. The resulting algorithms are therefore part man-made part machine-made.
While there are often many algorithms suitable for a specific task (e.g. the Lin-Kernighan for the travelling salesman problem) there is often an over-arching structure which defines their functionality. There are commonalities between these algorithms (that define their purpose) and the differences (which give different performance).
The invariant parts of a family of algorithms can be extracted by examining existing algorithms, and variations of the algorithm can be generated using genetic programming resulting in novel behaviour but with a predefined purpose. Therefore we have a method of mass-producing tailor-made algorithms for specific purposes. This is perhaps best illustrated by the following example; typically a travelling salesman algorithm is developed by hand and when executed returns a solution to a specific instance of the problem (i.e. an ordered list of cities). What we are advocating is a method that automatically generates travelling salesman algorithms in this example. An additional yet centrally important advantage of this approach is that the resulting algorithm is “unique” and bespoke to the specific set of problem instances used to train the algorithm. Continuing the travelling salesman example, two logistics companies will have two different probability distributions of customers and therefore require two different algorithms if they are to achieve better performance compared to using a standard off-the-shelf travelling salesman problem algorithm.
This method has been applied to a rapidly increasing number of domains including; data mining/machine learning, combinatorial problems including bin packing (on and off line), traveling salesman problems, Boolean satiability, job shop scheduling, exam timetabling, image recognition, black-box function optimization, layout of wind farms, and components of metaheuristics themselves. A step-by-step guide will be given, taking the novice through the distinct stages of the process of automatic design and a number of examples will be given to illustrate and reinforce the method in practice.
John Woodward is a lecturer at the University of Stirling, within the CHORDS group (http://chords.cs.stir.ac.uk/) and is employed on the DAASE project (http://daase.cs.ucl.ac.uk/), and for the previous four years was a lecturer with the University of Nottingham (China). He holds a BSc in Theoretical Physics, an MSc in Cognitive Science and a PhD in Computer Science, all from the University of Birmingham. His research interests include Automated Software Engineering, particularly Search Based Software Engineering, Artificial Intelligence/Machine Learning and particularly Genetic Programming. He has over 50 publications in Computer Science, Operations Research and Engineering which include both theoretical and empirical contributions, and given over 50 talks at International Conferences and as an invited speaker at Universities. He has worked in industrial, military, educational and academic setting, and been employed by EDS, CERN and RAF and three UK Universities.
Before entering academia, Jerry Swan spent 20 years in industry as a systems architect and software company owner. He obtained his PhD in Computational Group Theory from the University of Nottingham in 2006. His research interests include software engineering, computer algebra, formal methods and their application to meta- and hyper-heuristics, symbolic computation and machine learning. He has published in international journals and conferences and serves as a reviewer for numerous journals and program committees. Jerry's research has been presented worldwide and since 2011 has been a presenter and co-organizer of various GECCO Workshops concerned with the automation of the heuristic design process.
Michael G. Epitropakis received his B.S., M.S., and Ph.D. degrees from the Department of Mathematics, University of Patras, Greece. He is currently a post-doctoral research assistant at the Computational-Heuristics, Operations Research and Decision-Support (CHORDS) research group, at the Department of Computing Science and Mathematics, University of Stirling, Scotland. His current research interests include computational intelligence, evolutionary computation, swarm intelligence, automatic design of algorithms, machine learning and search-based software engineering. He has published more than 25 journal and conference papers. He serves as a reviewer in numerous journals and conferences. He is a member of the IEEE Computational Intelligence Society and the ACM SIGEVO.