Transforming Evolutionary Search into Higher-Level Evolutionary Search by Capturing Problem Structure

Rob Mills, Thomas Jansen, Richard Watson

Research output: Contribution to journalArticlepeer-review

11 Citations (SciVal)
219 Downloads (Pure)


The intuitive idea that good solutions to small problems can be reassembled into good solutions to larger prob- lems is widely familiar in many fields including evolutionary computation. This idea has motivated the building-block hypothesis and model-building optimization methods that aim to identify and exploit problem structure automatically. Recently, a small number of works make use of such ideas by learning problem structure and using this information in a particular manner: these works use the results of a simple search process in primitive units to identify structural correlations (such as modularity) in the problem that are then used to redefine the variational operators of the search process. This process is applied recursively such that search operates at successively higher scales of organization, hence multi-scale search. Here, we show for the first time that there is a simple class of (modular) problems that a multi-scale search algorithm can solve in polynomial time that requires super-polynomial time for other methods. We discuss strengths and limitations of the multi-scale search approach and note how it can be developed further.
Original languageEnglish
Pages (from-to)628-642
Number of pages15
JournalIEEE Transactions on Evolutionary Computation
Issue number5
Early online date13 Aug 2014
Publication statusPublished - 31 Oct 2014


Dive into the research topics of 'Transforming Evolutionary Search into Higher-Level Evolutionary Search by Capturing Problem Structure'. Together they form a unique fingerprint.

Cite this