Problem decomposition-based scalable macro-evolutionary algorithms
Tao Xiehuowang Chen · 2002
Due to its susceptibility to being trapped by local optima, the performance of standard evolutionary algorithms will be severely degraded when applied to complex problems with large dimensionality and intensive epistasis. By the principle of parallel processing, this paper suggests that complex problems be more or less divided into easier subproblems that are independent of each other or weakly correlated through variables, and then a decomposition-based scalable macro-evolutionary algorithm is proposed. This macro-evolutionary algorithm comprises of a competitive evolution layer called a local evolution process with respect to each subproblem and a cooperative evolution layer called global evolution process that coordinates all the subproblems, two layers are bridged through a multi-parents crossover operator which is specially designed for it. The exponential relationship between the convergence of macro-evolutionaly algorithm and the granularity of problem decomposition is primarily analyzed mathematically, indicating that the macro-evolutionary algorithm converges earlier than standard evolutionary algorithms, and the numerical experiments of optimizing two complex functions consist well with this theoretical result. The macro-evolutionary algorithm can overcome the difficulty associated with dimensionality and reduce as much as possible the difficulty due to intensive epistasis; if is thus scalable and useful in engineering.