A GRASP-based memetic algorithm with path relinking for the far from most string problem

Such problems have attracted a lot of interest for multiple reasons. From a theoretical (and even from a purely algorithmic) point of view, they constitute a clear and well-defined domain in which computational complexity issues can be analyzed and search/optimization algorithms can be put to work in challenging conditions. From a more practical point of view, there are many real-world problems which can be formalized as SSPs. Such problems are notably found in the area of computational biology, in which technological advances and the numerous initiatives are producing an unprecedented flood of data (Reichhardt, 1999) very much requiring the use of powerful computational tools to overcome the associated challenges (Meneses et al., 2005). Among such problems of interest from the perspective of SSPs we can cite discovering potential drug targets, creating diagnostic probes, designing primers, locating binding sites, or identifying consensus sequences just to name a few (Festa, 2007; Lanctot et al., 2003; Meneses et al., 2005).