TITLE:

Automatic Design of Algorithms via Hyper-heuristic Genetic Programming 

ABSTRACT:

“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 LinKernighan 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.