Table of Content

Open Access iconOpen Access

ABSTRACT

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

Takéhiko Nakama1

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.

Cite This Article

APA Style
Nakama, T. (2009). Using genetic algorithms to find a globally optimal solution in uncertain environments with multiple sources of additive and multiplicative noise. The International Conference on Computational & Experimental Engineering and Sciences, 9(4), 233-242. https://doi.org/10.3970/icces.2009.009.233
Vancouver Style
Nakama T. Using genetic algorithms to find a globally optimal solution in uncertain environments with multiple sources of additive and multiplicative noise. Int Conf Comput Exp Eng Sciences . 2009;9(4):233-242 https://doi.org/10.3970/icces.2009.009.233
IEEE Style
T. Nakama, "Using genetic algorithms to find a globally optimal solution in uncertain environments with multiple sources of additive and multiplicative noise," Int. Conf. Comput. Exp. Eng. Sciences , vol. 9, no. 4, pp. 233-242. 2009. https://doi.org/10.3970/icces.2009.009.233



cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 1014

    View

  • 760

    Download

  • 0

    Like

Share Link