Illinois Genetic Algorithms Laboratory

Winward, P. (2007)
TR No.: 2007018 | Download PDF | Download PS

Abstract:
The genetic algorithm (GA) is gaining increasing interest in both academia and industry in attempts to solve hard search problems quickly, accurately, and reliably. Various theories of what makes a problem difficult for the GA to solve have been put forward; yet, none of them has been completely confirmed experimentally. This thesis examines one theory of GA problem difficulty and investigates one facet of that theory that has received scant empirical attention and only passing theoretical consideration.

The theory of problem difficulty assumed in this thesis is centered on the notion that GAs process building blocks in their search for optimal solutions. A source of difficulty commonly referred to in the literature is crosstalk, or nonlinear interactions among building blocks. The purpose of this thesis is to explore the effects of one type of crosstalk, fluctuating crosstalk, on population size, convergence time, and the number of function evaluations for boundedly difficult test functions.

By modeling fluctuating crosstalk with Walsh coefficients, this thesis investigates fluctuating crosstalk effects on GA scalability by varying the order and magnitude of the crosstalk and the scaling of building blocks in the underlying fitness function. High-order fluctuating crosstalk induces scalability effects similar to exogenous noise, and can be modeled by known facetwise models of GA scalability that account for external noise until the strength of the crosstalk far exceeds the underlying fitness variance by a certain factor empirically observed. Additionally, for multiple small-order coefficients, the fluctuating crosstalk has the potential to disrupt the optimal solution. The results have implications for the relative performance of building block-wise mutation to crossover.