Fast algorithm for fair comparison of genetic algorithms
Journal
GECCO 2018 - Proceedings of the 2018 Genetic and Evolutionary Computation Conference
Pages
913-920
Date Issued
2018
Author(s)
Abstract
Since numerous genetic algorithms (GAs) are developed every year, GA researchers need a fast algorithm to fairly compare their performances. In this paper, we formalized the performance metric and listed three algorithms to find the right population size for performance comparing in terms of the Number of Fitness Evaluations (NFE). Instead of finding the population nmNFE producing minimum NFE (mNFE), we took the methodology of finding n* which would converge to an arbitrary notion of success with a desired probability p*. Among all three algorithms, the first, the most commonly used bisection method, was proved to be biased and without generality. The second is an unbiased modification of the first with trade-off of more function evaluations. The third, called Greedy Approach Regarding Locality (GARL), is our recommendation, empirically outperforming the second one by an exponential factor. We also analyzed the time complexity of the second and third algorithms, providing the upper bound for an average case. This work could be viewed as a general efficiency-comparing framework to almost all GAs except for parameterless schemes.
Type
conference paper