Improved Evolutionary Optimization of Difficult Landscapes: Control of Premature Convergence through Scheduled Sharing
Michael E. Palmer
Department of Computer Science, California Institute of Technology,
Pasadena, CA 91125, USA
Stephen J. Smith
Thinking Machines Corporation, 245 First Street,
Cambridge, MA 02142, USA
Abstract
Massively parallel computers afford to genetic algorithms the use of very large populations, which allow the algorithms to attack more difficult optimization problems than were feasible in the past. Optimization performance on difficult search spaces---those that are both vast and have large numbers of local optima---can be particularly crippled by a common problem of genetic algorithms: premature convergence of the population to a suboptimum. In nature, however, competition between like organisms prevents total convergence, and this competition effect can also be introduced to the standard genetic algorithm by an extension called sharing. Sharing forces organisms within a niche to compete. In past work, the size of the niche has been fixed, and calculated by hand for simple test problems.
This paper introduces an improvement to fixed-niche sharing called scheduled sharing, which (1) allows for the application of sharing to complex problems where there is no definable best niche size, and (2) does not violate the "black box'' principle in the calculation of niche size, instead borrowing from simulated annealing an exponentially decreasing schedule. We show that scheduled sharing inhibits convergence and improves performance for optimization problems that are difficult relative to the size of the population used.