An Evolutionary Approach to Experimental Design for Combinatorial Optimization
Seminar Room 1, Newton Institute
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.