Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
From MaRDI portal
Publication:884444
DOI10.1016/j.tcs.2006.11.002zbMath1117.68090OpenAlexW2153401898MaRDI QIDQ884444
Publication date: 6 June 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2003/5454
minimum spanning trees\((1+\lambda)\) EAanalysis of expected optimization timeparallel random search
Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)
Related Items
Towards a runtime comparison of natural and artificial evolution ⋮ A comparative performance analysis of evolutionary algorithms on \(k\)-median and facility location problems ⋮ Variable solution structure can be helpful in evolutionary optimization ⋮ On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem ⋮ Fixed-target runtime analysis ⋮ Plateaus can be harder in multi-objective optimization ⋮ Evolutionary algorithms and matroid optimization problems ⋮ Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems ⋮ Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ Practical performance models of algorithms in evolutionary program induction and other domains ⋮ Adaptive drift analysis ⋮ Analysis of an iterated local search algorithm for vertex cover in sparse random graphs ⋮ (1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error ⋮ Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution ⋮ Runtime analysis of the \((1+1)\) EA on computing unique input output sequences ⋮ Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem ⋮ Multiplicative drift analysis ⋮ Black-box search by unbiased variation ⋮ Approximate optimal hybrid control synthesis by classification-based derivative-free optimization ⋮ Free lunches on the discrete Lipschitz class ⋮ Runtime analysis of the 1-ANT ant colony optimizer ⋮ Computing minimum cuts by randomized search heuristics ⋮ Hybridizing evolutionary algorithms with variable-depth search to overcome local optima ⋮ Fixed-parameter evolutionary algorithms and the vertex cover problem ⋮ Evolutionary algorithms and dynamic programming ⋮ The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate ⋮ Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances ⋮ Drift conditions for estimating the first hitting times of evolutionary algorithms ⋮ An analysis on recombination in multi-objective evolutionary optimization ⋮ Stagnation detection with randomized local search ⋮ Performance analysis of the \((1+1)\) evolutionary algorithm for the multiprocessor scheduling problem ⋮ Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem ⋮ Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint ⋮ First steps to the runtime complexity analysis of ant colony optimization ⋮ Ranking-based black-box complexity ⋮ Ant colony optimization and the minimum spanning tree problem ⋮ Runtime analysis of a binary particle swarm optimizer ⋮ Kruskal with embedded C-semirings to solve MST problems with partially-ordered costs ⋮ Welch sets for random generation and representation of reversible one-dimensional cellular automata ⋮ Comparison of simple diversity mechanisms on plateau functions ⋮ The impact of parametrization in memetic evolutionary algorithms ⋮ Maximizing submodular or monotone approximately submodular functions by multi-objective evolutionary algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Maximum of k-th maximal spanning trees of a weighted graph
- On the spanning trees of weighted graphs
- On spanning tree problems with multiple objectives
- The Metropolis algorithm for graph bisection
- On the analysis of the \((1+1)\) evolutionary algorithm
- Genetic algorithm approach on multi-criteria minimum spanning tree problem
- How to analyse evolutionary algorithms.
- The time complexity of maximum matching by simulated annealing
- STACS 2005
