A multi-granular general evolutionary computation framework by fully utilizing the eliminated particles

In the evolutionary algorithm, an intuitive phenomenon is that the eliminated bad particles are also beneficial to convergence in evolutionary algorithms by preventing the generated particles from being close to those eliminated bad particles. Most existing algorithms do not take full advantage of the historical information of these particles or use surrogate models without guaranteeing approximation accuracy. In this study, we propose a multi-granularity general framework to divide the feasible region into different granularities by utilizing completely random trees and computing the spatial distribution of individuals. Secondly, through the sampling and migration strategy, make full use of the sparsity of the calculated individual space distribution and the locality of the best individual in history to replace the poor individual in the current population to speed up the local convergence speed of the algorithm. The time complexity of the algorithm using this framework is equal to the maximum between the time complexity of the evolutionary algorithm using this framework and O(tMlogM), where M denotes the number of points and historical particles generated in an iteration and t denotes the number of iterations. Therefore, the additional computational cost incurred by this framework is very low. Experiments on 12 classical functions, including high-dimensional functions, show that the proposed framework can improve four respective evolutionary algorithms and achieve significantly better results in terms of convergence performance and optimization accuracy.

Automated summary

This study proposes a multi-granularity framework that utilizes completely random trees and computes the spatial distribution of individuals to divide the feasible region into different granularities. Through sampling and migration strategy, it takes full advantage of the historical information to improve the convergence speed and optimization accuracy of the algorithm.