HITTING TIMES OF LOCAL AND GLOBAL OPTIMA IN GENETIC ALGORITHMS WITH VERY HIGH SELECTION PRESSURE

  • Anton V. EREMEEV Omsk Branch of Sobolev Institute of Mathematics SB RAS, Omsk State University n.a.F.M.Dostoevsky

Abstract

The paper is devoted to upper bounds on the expected first hitting times of the sets of local or global optima for non-elitist genetic algorithms with very high selection pressure. The results of this paper extend the range of situations where the upper bounds on the expected runtime are known for genetic algorithms and apply, in particular, to the Canonical Genetic Algorithm. The obtained bounds do not require the probability of fitness-decreasing mutation to be bounded by a constant which is less than one.


Keywords: Combinatorial Optimization,Evolutionary Algorithms, Runtime Analysis, Fitness Level, Local Search.

Published
Sep 21, 2017
How to Cite
EREMEEV, Anton V.. HITTING TIMES OF LOCAL AND GLOBAL OPTIMA IN GENETIC ALGORITHMS WITH VERY HIGH SELECTION PRESSURE. Yugoslav Journal of Operations Research, [S.l.], v. 27, n. 3, p. 323–339, sep. 2017. ISSN 2334-6043. Available at: <http://yujor.fon.bg.ac.rs/index.php/yujor/article/view/113>. Date accessed: 19 oct. 2017.
Section
Articles