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

DOI10.2298/YJOR160318016EzbMATH Open1474.90528arXiv1606.05784OpenAlexW2962740835MaRDI QIDQ4987699FDOQ4987699

Authors: Anton Valentinovich Eremeev 

Publication date: 3 May 2021

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

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.

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

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

zbMATH Keywords

combinatorial optimizationlocal searchevolutionary algorithmsruntime analysisfitness level

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• Choosing selection pressure for wide-gap problems
• Title not available (Why is that?)
• 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)