RT Journal Article
T1 A GRASP-based memetic algorithm with path relinking for the far from most string problem.
A1 Gallardo-Ruiz, José Enrique
A1 Cotta-Porras, Carlos
K1 Algoritmos evolutivos
K1 Bioinformática
AB The FAR FROM MOST STRING PROBLEM (FFMSP) is a string selection problem. The objective is to find a string whose distance to other strings in a certain input set is above a given threshold for as many of those strings as possible. This problem has links with some tasks in computational biology and its resolution has been shown to be very hard. We propose a memetic algorithm (MA) to tackle the FFMSP. This MA exploits a heuristic objective function for the problem and features initialization of the population via a Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic, intensive recombination viapath relinking and local improvement via hill climbing. An extensive empirical evaluation using problem instances of both random and biological origin is done to assess parameter sensitivity and draw performance comparisons with other state-of-the-art techniques. The MA is shown to perform better than these latter techniques with statistical significance.
PB Elsevier
YR 2015
FD 2015
LK https://hdl.handle.net/10630/31418
UL https://hdl.handle.net/10630/31418
LA eng
NO José E. Gallardo and Carlos Cotta. 2015. A GRASP-based memetic algorithm with path relinking for the far from most string problem. Eng. Appl. Artif. Intell. 41, C (May 2015), 183–194. https://doi.org/10.1016/j.engappai.2015.01.020
NO Política de acceso abierto tomada de: https://www.elsevier.com/about/policies-and-standards/copyright
NO ANYSELF (TIN2011-28627-C04-01) of MICINN and DNEMESIS (TIC-6083) of Junta de Andalucía.
DS RIUMA. Repositorio Institucional de la Universidad de Málaga
RD 4 mar 2026