Analysis of the behaviour of evolutionary algorithms for variable length problems

The School of EECS is hosting the following thesis review 3 seminar:

Analysis of the behaviour of evolutionary algorithms for variable length problems

Speaker: Saskia Van Ryt

Abstract: Variable length optimisation, where solution length may vary throughout the optimisation process, is an understudied area of optimisation. While there are many instances in the literature where fixed length Evolutionary Algorithms have been adjusted and applied to variable length problems, there is very little in the way of theory and analysis.

In this talk we focus on the application of Evolutionary Algorithms to component based variable length problems, developing theory and understanding to support better algorithm design. A type of local optimum specific to variable length problems is defined, with a set of abstract problems developed to target this characteristic. A range of operators proposed in the literature are tested on these problems and others in the literature, with their behaviour analysed to extract knowledge for operator design. This analysis is then used to suggest improvements for existing operators, and to propose new ones. We found that operator performance is highly sensitive to what may seem like small design choices, with an appropriate amount of length diversity being a key factor in performance. Operators that assigned meaning to components based on their numerical value outperformed those that assigned meaning based on position in the genome. Methods that focused on allowing length diverse, but less competitive, solutions to improve and persist in the population found the most success - outperforming a similarly sophisticated fixed length algorithm on some problems, even when that fixed length algorithm knows the optimal solution length a priori.