The analysis of evolutionary algorithms on sorting and shortest paths problems

DOI10.1007/s10852-005-2584-0zbMath1073.68080OpenAlexW1981898306MaRDI QIDQ1774629

Karsten Tinnefeld, Ingo Wegener, Jens Scharnow

Publication date: 17 May 2005

Published in: JMMA. Journal of Mathematical Modelling and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10852-005-2584-0

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (29)

Towards a runtime comparison of natural and artificial evolution ⋮ Using multi-objective evolutionary algorithms for single-objective constrained and unconstrained optimization ⋮ Analysis of evolutionary algorithms for the longest common subsequence problem ⋮ Evolutionary algorithms and matroid optimization problems ⋮ Minimum spanning trees made easier via multi-objective optimization ⋮ Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem ⋮ A review of metrics on permutations for search landscape analysis ⋮ Using multi-objective evolutionary algorithms for single-objective optimization ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ Analysis of speedups in parallel evolutionary algorithms and \((1 + \lambda)\) EAs for combinatorial optimization ⋮ Runtime analysis of discrete particle swarm optimization applied to shortest paths computation ⋮ Practical performance models of algorithms in evolutionary program induction and other domains ⋮ Multi-objective evolutionary algorithms are generally good: maximizing monotone submodular functions over sequences ⋮ Running time analysis of ant colony optimization for shortest path problems ⋮ Crossover can provably be useful in evolutionary computation ⋮ On the approximation ability of evolutionary optimization with application to minimum set cover ⋮ Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax ⋮ Runtime analysis of the \((1+1)\) EA on computing unique input output sequences ⋮ Runtime analysis for permutation-based evolutionary algorithms ⋮ A simple ant colony optimizer for stochastic shortest path problems ⋮ Finding Antimagic Labelings of Trees by Evolutionary Search ⋮ Fixed-parameter evolutionary algorithms and the vertex cover problem ⋮ Evolutionary algorithms and dynamic programming ⋮ Sorting by swaps with noisy comparisons ⋮ Static and self-adjusting mutation strengths for multi-valued decision variables ⋮ Variable neighborhood algebraic differential evolution: an application to the linear ordering problem with cumulative costs ⋮ Memetic algorithms: The polynomial local search complexity theory perspective ⋮ Runtime analysis of a binary particle swarm optimizer ⋮ Comparing evolutionary algorithms to the (\(1+1\))-EA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for the determination of longest increasing subsequence in a sequence
• On the analysis of the \((1+1)\) evolutionary algorithm
• A framework for adaptive sorting
• Real royal road functions -- where crossover provably is essential

This page was built for publication: The analysis of evolutionary algorithms on sorting and shortest paths problems