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

DOI10.2298/YJOR160318016EMaRDI QIDQ4987699zbMATH OpenOpenAlexFDO

Authors Anton Valentinovich Eremeev

Publication date 3 May 2021

Published in Yugoslav Journal of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.05784

zbMATH Keywords

combinatorial optimizationlocal searchevolutionary algorithmsruntime analysisfitness level

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Integer programming (90C10)

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 less than one.

Recommendations

• Mean convergence time of inhomogeneous genetic algorithm with elitism
• On the runtime analysis of the simple genetic algorithm
• A genetic algorithm with tournament selection as a local search method
• Finite-time performance analysis for genetic algorithms
• Theory of genetic algorithms

Cites work

• scientific article; zbMATH DE number 1381974 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 194544 (Why is no real title available?)
• scientific article; zbMATH DE number 946251 (Why is no real title available?)
• scientific article; zbMATH DE number 855574 (Why is no real title available?)
• scientific article; zbMATH DE number 4182860 (Why is no real title available?)
• A Sharp Bound on the Ratio Between Optimal Integer and Fractional Covers
• A discipline of evolutionary programming
• A genetic algorithm for the set covering problem
• Attraction probabilities in variable neighborhood search
• Crossover can be constructive when computing unique input-output sequences
• Drift analysis and average time complexity of evolutionary algorithms
• Genetic local search for the graph partitioning problem under cardinality constraints
• Local search, reducibility and approximability of NP-optimization problems
• On the runtime analysis of the simple genetic algorithm
• Optimal recombination in genetic algorithms for combinatorial optimization problems. I
• Optimized Crossover for the Independent Set Problem
• Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems
• Runtime analysis of non-elitist populations: from classical optimisation to partial information
• The analysis of evolutionary algorithms -- A proof that crossover really can help

Cited in

(3)

• Choosing selection pressure for wide-gap problems
• scientific article; zbMATH DE number 6694492 (Why is no real title available?)
• The role of selective pressure when solving symmetric functions in polynomial time

This page was built for publication: Hitting times of local and global optima in genetic algorithms with very high selection pressure

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4987699)