skip to content

An Evolutionary Approach to Experimental Design for Combinatorial Optimization

Friday 2nd September 2011 - 11:30 to 12:00
INI Seminar Room 1
Session Title: 
Advances in Computational Design and Computer Experiments
Session Chair: 
Hugo Maruri-Aguilar
In this presentation we investigate an approach which combines statistical methods and optimization algorithms in order to explore a large search space when the great number of variables and the economical constraints limit the ability of classical techniques to reach the optimum of a function. The method we propose - the Model Based Ant Colony Design (MACD) - couples real experimentation with simulated experiments and boosts an “Ant Colony” algorithm (Dorigo et al., 2004) by means of a simulator (strictly speaking an emulator), i.e. a predictive statistical model. Candidate solutions are generated by computer simulation using Ant Colony Optimization, a probabilistic technique for solving computational problem which consists in finding good paths through graphs and is based on the foraging behaviour of real ants. The evaluation of the candidate solutions is achieved by physical experiments and is fed back into the simulative phase in a recursive way.

The properties of the proposed approach are studied by means of numerical simulations, testing the algorithm on some mathematical benchmark functions. Generation after generation, the evolving design requires a small number of experimental points to test, and consequently a small investment in terms of resources. Furthermore, since the research was inspired by a real problem in Enzyme Engineering and Design, namely finding a new enzyme with a specific biological function, we have tested MACD on the real application. The results shows that the algorithm has explored a region of the sequence space not sampled by natural evolution, identifying artificial sequences that fold into a tertiary structure closely related to the target one.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons