Genetic engineering via negative fitness: Evolutionary dynamics for global optimization

In this paper, we provide a novel interpretation of a global optimization procedure for standard quadratic problems (QPs) in terms of selection models. A standard QP consists of maximizing a quadratic form over the standard simplex. Recently, local solutions to standard QPs have been obtained with the help of replicator dynamics, which were designed to model evolutionary processes. Following trajectories under these dynamics, one obtains a sequence of feasible points with strictly increasing objective values, which approach stationary points. We present regularity conditions which ensure that the limiting points are indeed local solutions, so that jamming could be avoided. Genetic engineering via negative fitness is a block pivoting procedure which either delivers a certificate for global optimality of the current local solution, or else enables an escape from its basin of attraction, if it is inefficient. The name originates from the way the block pivot is obtained: via minimization (rather than maximization) of a subproblem. We also elaborate on an important application, the search for a maximum clique in an undirected graph, and report both theoretical and empirical results.