The ant colony optimisation algorithm was developed by Dorigo about
10 years ago. It is motivated by how real ant colonies find the short routes
around obstacles.
It has been widely applied to routing problems such as the travelling
salesman problem, and route optimisation in telecommunication networks,
and has recently been
applied to other fields. See Dorigo's Ant Colony Optimization Page
at http://iridia.ulb.ac.be/~mdorigo/ACO/ACO.html for more information.
However, ant colony algorithms can be view in a wider context. They
are distributed implementations of an algorithm which is related to other,
well-studied search
algorithms. The ant colony algorithm basically has a population of
agents (ants) which are each carrying out approximately greedy search.
At the same time, the
agents are trying to learn a local value function on which greedy search
produces near optimal solutions. As such, is is related both to reinforcement
learning, and to
approximately-greedy search algorithms such as simulated annealing
and the Go-With-the-Winner algorithm.
The goal of this project is to study the ant colony algorithm on search
spaces which are constructed to have known properties and learn about its
performance when
compared to these other algorithms.
JLS.2 A New Method for Learning a Mixture of Local Models (ACS,CaS,
CMIM)
In a recent paper, Williams and Titsias (2003) developed a model for
discovering object in images. This involved making a probabilistic model
for
each possible object. Normally, such a model would suffer from combinatorial
explosion, there being an exponential (in the number of objects)
number of possibilities to consider. They get around this by learning
one object at a time, and removing them after they are found. In order
to do this,
they need to use a robust approach, which is able to learn one object
without contamination from other objects. To do this, they use a mixture
model
with a "robustifying component" which is common for all objects and
background.
The goal of this work is to apply this approach to supervised learning.
Instead of learning about localized objects in an image, the system will
learn
local rules which predict output variables from input variables. Each
rule will be learnt one at a time, using a mixture model with a robustifying
component, and learning via an EM algorithm. Such an approach may be
particularly useful in problems in which there are regions of predictability
against a background which is hard to predict (as is often supposed
about the stock market). This project will attempt to prove the concept.
It would be very helpful if the person doing this project has taken the Machine Learning module, or the Neural Networks module.
Reference: Christopher K.I. Williams and Michalis K. Titsias. Learning
About Multiple Objects in Images: Factorial Learning without Factorial
Search . To appear in Advances in NIPS 15, 2003.
JLS.3 Algorithmic Music Composition on Simulated Autonomous Instruments
by the Learning of Statistical Similarity. (ACS, CS, CaS, CMIM)
A player piano is an autonomous musical instrument which plays an exact
copy of some piece played by a human player. It allows no interaction.
A
set of wind chimes in a gentle breeze can also be thought of an autonomous
instrument. It differs from the player piano in that it has variation in
what
it plays and can be influenced by a user, but it plays only very simple
sounds.
The algorithmic composer Assaf Talmudi has proposed and developed a
combination of the two. A fairly complex dynamical system is constructed
(in
computer simulation) consisting of bells connected by springs. The
properties of this system are constructed (using a search algorithm) to
have
similar statistical properties of some musical piece. Thus, the instrument
produces music which can be influenced by the user, but still has some
statistical similarity with a piece of music. The statistical property
used in the work of Talmudi was the distribution of pitches.
The idea of this project is to extend this idea to more complex statistics,
such as the distribution of time intervals, or the pairwise correlation
between
notes. It may also be interesting to compose more complex pieces by
creating several different instruments of this form, and use them together.
JLS.4 Machine Learning and Optimisation (ACS, CS, CaS, CMIM)
A new class of optimisation algorithms, called Estimation of Distribution
algorithms (EDAs), uses machine learning to try to learn where good
solutions to a problem are. The method works like this: a probability
model (usually a graphical model) generates test solutions to the problem.
The
better solutions are selected, using some selection method. The probability
model is then updated. so that the selected solutions are more likely to
be
generated. This is repeated, in the hope that the probability distribution
will evolve to one which generates good solutions with a high probability.
This approach is related to genetic algorithms, where mutation and crossover
are replaced by sampling from the distribution. Sampling generates new
solutions which have similar statistics to the recently sampled solutions,
just like mutation and crossover generate new strings which have similar
statistics to the "parent" strings. For a review on EDAs, see [1].
I have been studying these algorithms and have a number of studies I would like to see done. I will discuss possible specific projects in a meeting.
References: P. Larranaga and J. A. Lozano, "Estimation of Distribution
Algorithms, A New Tool for Evolutionary Computation", Kluwer Academic
Publishers, 2001.
J. L. Shapiro, "The Sensitivity of PBIL to the Learning Rate, and How
Detailed Balance Can Remove It", Foundations of Genetic Algorithms 7,
2003.