A GRASP-based memetic algorithm with path relinking for the far from most string problem. (May 2015)

• Record Type: Journal Article
• Authors: Gallardo, José E.; Cotta, Carlos
• Is Part Of: Engineering applications of artificial intelligence. Volume 41(2015:May)
• Page Start: 183
• Page End: 194
• Publication Date: 2015-05
• Subjects: Far from most string problem -- String selection problems -- Bioinformatics -- Metaheuristics -- Memetic algorithms; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2015.01.020
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: 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 via path 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.