A mixed strategy of combining evolutionary algorithms with multigrid methods

Abstract

Multigrid methods have been proven to be an efficient approach in accelerating the convergence rate of numerical algorithms for solving partial differential equations. This paper investigates whether multigrid methods are helpful to accelerate the convergence rate of evolutionary algorithms for solving global optimization problems. A novel multigrid evolutionary algorithm is proposed and its convergence is proven. The algorithm is tested on a set of 13 well-known benchmark functions. Experiment results demonstrate that multigrid methods can accelerate the convergence rate of evolutionary algorithms and improve their performance.

Keywords:

• global optimization
• multigrid method
• evolutionary algorithm
• mixed strategy
• convergence rate

AMS Subject Classification :

• 65M55
• 68W20
• 78M50

CCS Category :

• G.1.6
• G.3

Acknowledgements

J. He was partially supported by the National Natural Science Foundation of China under Grant (60443003), and the Engineering and Physical Research Council under Grant (GR/T10671/01). L. Kang was partially supported by the National Natural Science Foundation of China under Grant (60473081).

Notes

^†In this paper, a cycle means an iteration from the coarse grid to fine grid.