A Biased Random Key Genetic Algorithm for Solving the Longest Run Subsequence Problem

• URL: http://arxiv.org/abs/2508.14020v1
• Date: Tue, 19 Aug 2025 17:27:29 GMT
• Title: A Biased Random Key Genetic Algorithm for Solving the Longest Run Subsequence Problem
• Authors: Christian Blum, Pedro Pinacho-Davidson,
• Abstract summary: We present a solution to the longest run subsequence (LRS) problem using a Biased Random Key Genetic Algorithm (BRKGA)<n>Results show that the proposed BRKGA is currently a state-of-the-art technique for the LRS problem.
• Score: 0.9668407688201361
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The longest run subsequence (LRS) problem is an NP-hard combinatorial optimization problem belonging to the class of subsequence problems from bioinformatics. In particular, the problem plays a role in genome reassembly. In this paper, we present a solution to the LRS problem using a Biased Random Key Genetic Algorithm (BRKGA). Our approach places particular focus on the computational efficiency of evaluating individuals, which involves converting vectors of gray values into valid solutions to the problem. For comparison purposes, a Max-Min Ant System is developed and implemented. This is in addition to the application of the integer linear programming solver CPLEX for solving all considered problem instances. The computation results show that the proposed BRKGA is currently a state-of-the-art technique for the LRS problem. Nevertheless, the results also show that there is room for improvement, especially in the context of input strings based on large alphabet sizes.

Related papers

• Guiding Genetic Programming with Graph Neural Networks [0.20718016474717196]
  We propose EvoNUDGE, which uses a graph neural network to elicit additional knowledge from symbolic regression problems. In an extensive experiment on a large number of problem instances, EvoNUDGE is shown to significantly outperform multiple baselines.
  arXiv  Detail & Related papers  (2024-11-03T20:43:31Z)
• 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)
• Evaluating Genetic Algorithms through the Approximability Hierarchy [55.938644481736446]
  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.
  arXiv  Detail & Related papers  (2024-02-01T09:18:34Z)
• Approximating a RUM from Distributions on k-Slates [88.32814292632675]
  We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average. Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
  arXiv  Detail & Related papers  (2023-05-22T17:43:34Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming [0.0]
  Learning the structure of a Bayesian network (BNSL) from discrete data is known to be an NP-hard task. In this work, we propose a new time algorithm for discovering a subset of all possible cluster cuts. We show that, despite being suboptimal, they improve performance by orders of magnitude. The resulting solver also compares favourably with GOBNILP, a state-of-the-art solver for the BNSL problem.
  arXiv  Detail & Related papers  (2021-06-23T09:46:11Z)
• 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)
• Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
  We study the problem of learning efficient algorithms that strongly generalize in the framework of neural program induction. By carefully designing the input / output interfaces of the neural model and through imitation, we are able to learn models that produce correct results for arbitrary input sizes.
  arXiv  Detail & Related papers  (2020-07-07T17:03:02Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  This paper presents an approach named MineReduce, which uses mined patterns to perform problem size reduction. We present an application of MineReduce to improve a for the heterogeneous fleet vehicle routing problem.
  arXiv  Detail & Related papers  (2020-05-15T08:49:50Z)
• Devolutionary genetic algorithms with application to the minimum labeling Steiner tree problem [0.0]
  This paper characterizes and discusses devolutionary genetic algorithms and evaluates their performances in solving the minimum labeling Steiner tree (MLST) problem. We define devolutionary algorithms as the process of reaching a feasible solution by devolving a population of super-optimal unfeasible solutions over time. We show how classical evolutionary concepts, such as crossing, mutation and fitness can be adapted to aim at reaching an optimal or close-to-optimal solution.
  arXiv  Detail & Related papers  (2020-04-18T13:27:28Z)

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

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.