Related papers: Evaluating Genetic Algorithms through the Approximability Hierarchy

Evaluating Genetic Algorithms through the Approximability Hierarchy

URL: http://arxiv.org/abs/2402.00444v1
Date: Thu, 1 Feb 2024 09:18:34 GMT
Title: Evaluating Genetic Algorithms through the Approximability Hierarchy
Authors: Alba Mu\~noz, Fernando Rubio
Abstract summary: In this paper, we analyze the usefulness of using genetic algorithms depending on the approximation class the problem belongs to. In particular, we use the standard approximability hierarchy, showing that genetic algorithms are especially useful for the most pessimistic classes of the hierarchy.
Score: 55.938644481736446
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Abstract: Optimization problems frequently appear in any scientific domain. Most of the times, the corresponding decision problem turns out to be NP-hard, and in these cases genetic algorithms are often used to obtain approximated solutions. However, the difficulty to approximate different NP-hard problems can vary a lot. In this paper, we analyze the usefulness of using genetic algorithms depending on the approximation class the problem belongs to. In particular, we use the standard approximability hierarchy, showing that genetic algorithms are especially useful for the most pessimistic classes of the hierarchy

Related papers

Recombination vs Stochasticity: A Comparative Study on the Maximum Clique Problem [0.393259574660092]
The maximum clique problem (MCP) is a fundamental problem in graph theory and computational complexity. Various meta-heuristics have been used to approximate the MCP, including genetic and memetic algorithms, ant colony algorithms, greedy algorithms, Tabu algorithms, and simulated annealing. Our results indicate that Monte Carlo algorithms, which employ random searches to generate subgraphs, often surpass genetic algorithms in both speed and capability.
arXiv Detail & Related papers (2024-09-26T12:50:00Z)
Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z)
When can you trust feature selection? -- I: A condition-based analysis of LASSO and generalised hardness of approximation [49.1574468325115]
We show how no (randomised) algorithm can determine the correct support sets (with probability $> 1/2$) of minimisers of LASSO when reading approximate input. For ill-posed inputs, the algorithm runs forever, hence, it will never produce a wrong answer. For any algorithm defined on an open set containing a point with infinite condition number, there is an input for which the algorithm will either run forever or produce a wrong answer.
arXiv Detail & Related papers (2023-12-18T18:29:01Z)
Temporal Heterogeneity Improves Speed and Convergence in Genetic Algorithms [0.0]
Genetic algorithms simulate natural selection to explore a parameter space in search of solutions for a broad variety of problems. We set the crossover probability to be inversely proportional to the individual's fitness, i.e., better solutions change slower than those with a lower fitness. We find that temporal heterogeneity consistently improves search without having prior knowledge of the parameter space.
arXiv Detail & Related papers (2022-02-02T22:48:56Z)
Power of human-algorithm collaboration in solving combinatorial optimization problems [0.0]
We show that a class of optimization problems can be solved efficiently in expectation up to a multiplicative factor $epsilon$ where $epsilon$ is arbitrary constant. While our proposed methods are merely theoretical, they cast new light on how to approach solving these problems that have been usually considered intractable.
arXiv Detail & Related papers (2021-07-25T11:21:59Z)
Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
arXiv Detail & Related papers (2021-01-07T08:00:02Z)
Towards Meta-Algorithm Selection [78.13985819417974]
Instance-specific algorithm selection (AS) deals with the automatic selection of an algorithm from a fixed set of candidates. We show that meta-algorithm-selection can indeed prove beneficial in some cases.
arXiv Detail & Related papers (2020-11-17T17:27:33Z)
Benchmarking Meta-heuristic Optimization [0.0]
Many meta-heuristic algorithms are very efficient when solving nonlinear functions. A meta-heuristic algorithm is a problem-independent technique that can be applied to a broad range of problems.
arXiv Detail & Related papers (2020-07-27T12:25:31Z)
Run2Survive: A Decision-theoretic Approach to Algorithm Selection based on Survival Analysis [75.64261155172856]
survival analysis (SA) naturally supports censored data and offers appropriate ways to use such data for learning distributional models of algorithm runtime. We leverage such models as a basis of a sophisticated decision-theoretic approach to algorithm selection, which we dub Run2Survive. In an extensive experimental study with the standard benchmark ASlib, our approach is shown to be highly competitive and in many cases even superior to state-of-the-art AS approaches.
arXiv Detail & Related papers (2020-07-06T15:20:17Z)

This list is automatically generated from the titles and abstracts of the papers in this site.