Genetic engineering via negative fitness: Evolutionary dynamics for global optimization

Genetic engineering via negative fitness: Evolutionary dynamics for global optimization

0.00 Avg rating0 Votes
Article ID: iaor20014196
Country: Netherlands
Volume: 89
Start Page Number: 297
End Page Number: 318
Publication Date: Jun 1999
Journal: Annals of Operations Research
Authors: ,
Keywords: genetic algorithms
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.