Scatter search and star-paths: beyond the genetic metaphor

Scatter search and genetic algorithms have originated from somewhat different traditions and perspectives, yet exhibit features that are strongly complementary. Links between the approaches have increased in recent years as variants of genetic algorithms have been introduced that embody themes in closer harmony with those of scatter search. Some researchers are now beginning to take advantage of these connections by identifying additional ways to incorporate elements of scatter search into genetic algorithm approaches. There remain aspects of the scatter approach that have not been exploited in conjunction with genetic algorithms, yet that provide ways to achieve goals that are basic to the genetic algorithm design. Part of the gap in implementing hybrids of these procedures may derive from relying too literally on the genetic metaphor, which in its narrower interpretation does not readily accommodate the strategic elements underlying scatter search. The theme of this paper is to show there are benefits to be gained by going beyond a perspective constrained too tightly by the connotations of the term genetic. We show that the scatter search framework directly leads to processes for combining solutions that exhibit special properties for exploiting combinatorial optimization problems. In the setting of zero-one integer programming, we identify a mapping that gives new ways to create combined solutions, producing constructions calledstar-paths for exploring the zero-one solution space. Star-path trajectories have the special property of lying within regions assured to include optimal solutions. They also can be exploited in association with both cutting plane and extreme point solution approaches. These outcomes motivate a deeper look into current conceptions of appropriate ways to combine solutions, and disclose there are more powerful methods to derive information from these combinations than those traditionally applied.This research is supported in part by the Joint Air Force Office of Scientific Research and Office of Naval Research Contract No. F49620-90-C-0033 at the University of Colorado