Genetic Algorithms and the O(n ln n)

Complexity on Selected Test Functions

Ralf Salomon
AI Lab, Computer Science Department, University of Zurich
Winterthurerstrasse 190, 8057 Zurich, Switzerland
FAX: +41-1-363 00 35; Email: [email protected]

Abstract

Genetic algorithms (GAs) are useful in the field of continuous parameter optimization. Many results indicate that, due to their robustness and their ability of escaping from local optima, GAs are especially suitable for optimizing multimodal functions that contain millions of misleading local optima. The existing theory is based on spherical symmetric functions and suggest an O(n ln n) complexity for particular GAs. However, the widely-used test functions are not spherical symmetric but decomposable and recent results indicate that GAs fail under a a simple rotation of the coordinate system. This paper shows that, when applied to a decomposable function with n independent parameters, any GA that features an elitist selection scheme, a broad mutation operator, and uses a mutation probability mp = 1=n, converges with an O(n ln n) complexity; it is not necessary to use a highly optimized genetic algorithms.

1 Introduction

Genetic algorithms (GAs) are a class of randomized optimization procedures that are based on natural selection and genetics. The basic scheme of a simple genetic algorithm (SGA) works on a population of fixed bit strings. Each iteration, also called generation, is performed in four steps. First, it selects a specified number of individuals as parents for the next generation.