William M. Spears

Traditionally, genetic algorithms have relied upon 1 and 2-point crossover operators. Many recent empirical studies, however, have shown the benefits of higher numbers of crossover points. Some of the most intriguing recent work has focused on uniform crossover, which involves on the average L/2 crossover points for strings of length L. Theoretical results suggest that, from the view of hyperplane sampling disruption, uniform crossover has few redeeming features. However, a growing body of experimental evidence suggests otherwise. In this paper, we attempt to reconcile these opposing views of uniform crossover and present a framework for understanding its virtues. 1 Introduction One of the unique aspects of the work involving genetic algorithms (GAs) is the important role that recombination plays. In most GAs, recombination is implemented by means of a crossover operator which operates on pairs of individuals (parents) to produce new offspring by exchanging segments from the parents' ...

A multimodal problem generator was used to test three versions of a genetic algorithm and the binary particle swarm algorithm in a factorial time-series experiment. Specific strengths and weaknesses of the various algorithms were identified.

A strategy for using Genetic Algorithms (GAs) to solve NP-complete problems is presented. The key aspect of the approach taken is to exploit the observation that, although all NP-complete problems are equally difficult in a general computational sense, some have much better GA representations than others, leading to much more successful use of GAs on some NP-complete problems than on others. Since any NP-complete problem can be mapped into any other one in polynomial time, the strategy described here consists of identifying a canonical NP-complete problem on which GAs work well, and solving other NP-complete problems indirectly by mapping them onto the canonical problem. Initial empirical results are presented which support the claim that the Boolean Satisfiability Problem (SAT) is a GAeffective canonical problem, and that other NPcomplete problems with poor GA representations can be solved efficiently by mapping them first onto SAT problems. 1. Introduction One approach to discussin...