Back to the program.
Transition models as an incremental approach to problem solving
Anne Defaweux
Como VUB
adefaweu@vub.ac.be

Abstract

In the classical approach of stochastic local search methods such as Evolutionary Algorithms (EA's), solution representations fully define the problem to solve (Hoos and Stuetzle, 2005 ). These fully qualifying representations evolve toward an optimum by means of this particular optimization technique. The aim of the technique is to progress in the solution space in the most efficient and adequate way relatively to the problem at hand. Here, we are interrested in developping an evolutionary algorithm that does not evolve fully qualifying solutions but incrementally ones. We believe this approach is promising on problems in which a structure in the components of the solution exists but for which this structure is unknown before hand. In other words, this structure can be learned by the optimization process. The incremental approach we use to build our solution is refered to as Transition Model as a reference to the biological counterpart it was inspired from (Sober and Wilson, 1998 ; Michod, 1999). The algorithm is currently evaluated on BINCSP problems.

Keywords

incremental solution representation, emergence of complexity, evolutionary optimization, CSP