On the effectiveness of genetic search in combinatorial optimization
Ki‐Hong Park, Bob S. Carter · 1995
In this paper, we study the efficacy of genetic algorithms in the context of combinatorial optimization.In particular, we isolate the effects of cross-over, treated as the central component.of genetic search.We show that for problems of nont,rivial size and difficulty, the contribution of cross-over search is marginal, both synergistically when run in conjunction with mutation and selection, or when run with selection alone, t,he reference point being the search procedure consisting of just mutation and selection.The latter can be viewed as another manifestat,ion of the Metropolis process.Considering the high computational cost of maintaining a population to facilitate cross-over search, its marginal benefit renders genetic search inferior to its singleton-population counterpart, the Metropolis process, and by extension, simulated annealing.This is further compounded by the fact.that many problems arising in practice may inherently require a large number of state transitions for a nearoptimal solution to be found, making genetic search infeasible given the high cost of computing a single iteration in the enlarged state-space.