IEEE TRANSACTION ON EVOLUTIONARY COMPUTATION 1 Transforming Evolutionary Search Into Higher-Level Evolutionary Search by Capturing Problem Structure

Abstract—The intuitive idea that good solutions to small problems can be reassembled into good solutions to larger problems is widely familiar in many fields including evolutionary computation. This idea has motivated the building-block hy-pothesis and model-building optimisation 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 organisation, 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 point out how it can be developed further. Index Terms—Evolutionary computation, automatic problem decomposition, linkage-learning, modularity, scalability I