DocumentCode :
25463
Title :
Transforming Evolutionary Search into Higher-Level Evolutionary Search by Capturing Problem Structure
Author :
Mills, Richard ; Jansen, T. ; Watson, Richard A.
Author_Institution :
Dept. of Electron. & Comput. Sci., Univ. of Southampton, Southampton, UK
Volume :
18
Issue :
5
fYear :
2014
fDate :
Oct. 2014
Firstpage :
628
Lastpage :
642
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 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.
Keywords :
computational complexity; evolutionary computation; learning (artificial intelligence); problem solving; search problems; building-block hypothesis; evolutionary computation; evolutionary search transformation; model-building optimization methods; multiscale search algorithm; polynomial time; problem structure learning; structural correlations; Correlation; Couplings; Evolutionary computation; Genetic algorithms; Polynomials; Search problems; Sociology; Automatic problem decomposition; evolutionary computation; linkage learning; modularity; scalability;
fLanguage :
English
Journal_Title :
Evolutionary Computation, IEEE Transactions on
Publisher :
ieee
ISSN :
1089-778X
Type :
jour
DOI :
10.1109/TEVC.2014.2347702
Filename :
6877683
Link To Document :
بازگشت