tailieunhanh - Hitting times of local and global optima in genetic algorithms with very high selection pressure

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. | Yugoslav Journal of Operations Research 27 (2017), Number 3, 323–339 DOI: HITTING TIMES OF LOCAL AND GLOBAL OPTIMA IN GENETIC ALGORITHMS WITH VERY HIGH SELECTION PRESSURE Anton V. EREMEEV Sobolev Institute of Mathematics SB RAS, Omsk State University . . Dostoevsky eremeev@ Received: March 2016 / Accepted: September 2016 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. MSC: 90C59, 90C10. 1. INTRODUCTION The genetic algorithms (GAs) are randomized heuristic algorithms that employ a population of tentative solutions (individuals), which is iteratively updated by means of selection, mutation and crossover operators, thus simulating an evolutionary type of search for optimal or near-optimal solutions. Different modifications of GAs are widely used in areas of operations research and artificial intelligence. A wider class of evolutionary algorithms (EAs), having a more flexible outline, possibly neglecting the crossover operator and admitting a population which consists of a single individual. Two major types of evolutionary algorithm outline are now well-known: the elitist EAs keep a certain number of 324 A., Eremeev / Hitting Times of Local and Global “most promising” individuals from the previous iteration, while the non-elitist EAs compute all individuals of a new population independently using the same randomized procedure. The theoretical