Genetic Algorithms, Walsh Transforms And Boolean Satisfiability

Dr. Soraya Rana
Computer Science Department
Colorado State University

Friday, February 12, 1999
11 a.m.
Fuller Labs 311

Genetic algorithms are a form of population-based local search. The computational behavior of genetic algorithms is believed to be driven by schema processing, where a schema is a subpartition of the search space. Through the use of a population, genetic algorithms are implicitly and simultaneously comparing sets of schemata and allocating more trials to schemata with higher fitnesses. If genetic algorithms are to be successful for optimization purposes, a natural question to ask is whether or not useful schema relationships exist for particular types of optimization problems.

The Walsh transform can be used to compute the exact fitnesses of schemata. Unfortunately, the Walsh transform usually requires enumeration of the search space so it is no more efficient for schema fitness calculations than a brute force approach. For MAXSAT problems with a bounded clause length, however, the Walsh transform can be performed in polynomial time. The resulting Walsh coefficients can then be used to exactly compute the low-order schema fitnesses which are believed to be particularly important for genetic algorithms. This analysis explains why standard simple genetic algorithms have performed poorly on MAXSAT problems and suggests the need for a more informative evaluation function.

Host

Micha Hofri

Colloquium Coordinator

Carolina Ruiz

Maintained by webmaster@wpi.edu
Last modified: Sep 27, 2006, 16:05 EDT