Open Access

ABSTRACT

Using genetic algorithms to find a globally optimal solution in uncertain environments with multiple sources of additive and multiplicative noise

Takéhiko Nakama¹

1 Department of Applied Mathematics and Statistics, The Johns Hopkins University, 3400 N.Charles Street, Baltimore, MD 21218 USA

The International Conference on Computational & Experimental Engineering and Sciences 2009, 9(4), 233-242. https://doi.org/10.3970/icces.2009.009.233

Abstract

Random noise perturbs objective functions in a variety of practical optimization problems, and genetic algorithms (GAs) have been widely proposed as an effective optimization tool for dealing with noisy objective functions. In this paper, we investigate GAs applied to objective functions that are perturbed by multiple sources of additive and multiplicative noise that each take on finitely many values. We reveal the convergence properties of GAs by constructing and analyzing a Markov chain that explicitly models the evolution of the algorithms in noisy environments. Our analysis shows that this Markov chain is indecomposable; it has only one positive recurrent communication class. Using this property, we establish a condition that is both necessary and sufficient for GAs to eventually (i.e., as the number of iterations goes to infinity) find a globally optimal solution with probability 1. Similarly, we identify a condition that is both necessary and sufficient for the algorithms to eventually with probability 1 fail to find any globally optimal solution. We also discuss how the transition probabilities of the chain can be used to derive an upper bound for the number of iterations sufficient to ensure with certain probability that a GA selects a globally optimal solution upon termination.

---