The Parameterized Complexity of Multiparent Recombination
Carlos Cotta, Pablo Moscato · 2005
We introduce the flrst model for the computational complexity analysis of decision problems that arise in population-based metaheuristic design. In particular our hardness results could be linked to the practical di‐culties of designing multiparent recombination metaheuristics in Evolutionary Algorithms and the path relinking recombination mechanisms that use multiple \elite solutions in Scatter Search and other memetic algorithms. We expect that the new formalization will provide insights that will help to create more mathematically well founded exact or heuristic recombination algorithms aimed to solve a variety of associated combinatorial optimization problems. This has the similar spirit than the addition of behaviors had for parameterizing recombination operators [1], which we can now see as a instantiation of a more systematic and generic pattern for recombination design based on this new formulation of the problem. An NP-hard combinatorial optimization problem known as Min Feature Set (MFS) problem perfectly casts the issues involved in multiparent recombination algorithm design. In this paper we discuss it within its parameterized complexity membership. Recombination is undoubtedly the major component of population-based metaheuristics. While its intuitive r^ole has been always clear (to combine the \information present in a set of solutions to create new solutions), the guidelines for designing practical recombination operators have experienced a remarkable evolution. First of all, nowadays it is increasingly more accepted that instead of directly manipulating the syntactic units used to encode solutions, the operator must extract relevant from these solutions and recombine it (with independence of whether solutions are encoded on the basis of these particular pieces or not). The Min Traveling Salesman (Min TSP) is a good example of this situation (the relevant pieces would be \edges). We will refer to these relevant \pieces of information as features. These features of the solutions are also known as \attributes in the Tabu Search and Scatter Search literature. We note, however, that in most of the cases where the original problem is intractable, these features of the solutions generally correspond