A Hybrid Evolutionary Algorithm Based on Solution Merging for the Longest Arc-Preserving Common Subsequence Problem
The longest arc-preserving common subsequence problem is an NP-hard combinatorial optimization problem from the field of computational biology. This problem finds applications, in particular, in the comparison of arc-annotated Ribonucleic acid (RNA) sequences. In this work we propose a simple, hybrid evolutionary algorithm to tackle this problem. The most important feature of this algorithm concerns a crossover operator based on solution merging. In solution merging, two or more solutions to the problem are merged, and an exact technique is used to find the best solution within this union. It is experimentally shown that the proposed algorithm outperforms a heuristic from the literature.
Code (0)
등록된 구현이 없습니다.
Tasks
ARCCombinatorial OptimizationSimilar Papers 제목 키워드 기반
CoHSI III: Long proteins and implications for protein evolution
The length distribution of proteins measured in amino acids follows the CoHSI (Conservation of Hartley-Shannon Information) probability distribution. In previous papers we have verified various predictions of this using …
Protein FoldingNeuro-Evolved Heuristics for Variable Gapped Common Subsequence Identification
This study addresses the Variable Gapped Longest Common Subsequence Problem (VGLCSP), a variant of the classical longest common subsequence problem with additional gap constraints and applications in sequence alignment a…
Solving Linear Equations Using a Jacobi Based Time-Variant Adaptive Hybrid Evolutionary Algorithm
Large set of linear equations, especially for sparse and structured coefficient (matrix) equations, solutions using classical methods become arduous. And evolutionary algorithms have mostly been used to solve various opt…
Evolutionary AlgorithmsPure and Hybrid Evolutionary Computing in Global Optimization of Chemical Structures: from Atoms and Molecules to Clusters and Crystals
The growth of evolutionary computing (EC) methods in the exploration of complex potential energy landscapes of atomic and molecular clusters, as well as crystals over the last decade or so is reviewed. The trend of growt…
global-optimizationA Hybrid Genetic Algorithm for the min-max Multiple Traveling Salesman Problem
This paper proposes a hybrid genetic algorithm for solving the Multiple Traveling Salesman Problem (mTSP) to minimize the length of the longest tour. The genetic algorithm utilizes a TSP sequence as the representation of…
DiversityTraveling Salesman Problem