Re-evaluating genetic algorithm performance under coordinate rotation of benchmark functions. A survey of some theoretical and practical aspects of genetic algorithms

In recent years, genetic algorithms (GAs) have become increasingly robust and easy to use. Current knowledge and many successful experiments suggest that the application of GAs is not limited to easy-to-optimize unimodal functions. Several results and GA theory give the impression that GAs easily escape from millions of local optima and reliably converge to a single global optimum. The theoretical analysis presented in this paper shows that most of the widely-used test functions have n independent parameters and that, when optimizing such functions, many GAs scale with an O(n ln n) complexity. Furthermore, it is shown that the current design of GAs and its parameter settings are optimal with respect to independent parameters. Both analysis and results show that a rotation of the coordinate system causes a severe performance loss to GAs that use a small mutation rate. In case of a rotation, the GA's complexity can increase up to O(nn) = O(exp(n ln n)). Future work should find new GA designs that solve this performance loss. As long as these problems have not been solved, the application of GAs will be limited to the optimization of easy-to-optimize functions.