This Wednesday (11-1) I will be giving a free live online tutorial on Automatic Design of Algorithms via Hyper-heuristic Genetic Programming
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.