Illinois Genetic Algorithms Laboratory

Sastry, K. (2002)
TR No.: 2002004 | Download PDF | Download PS

Abstract:
Genetic and evolutionary algorithms have been increasingly applied to
solve complex, large scale search problems with mixed success.
Competent genetic algorithms have been proposed to solve hard problems
quickly, reliably and accurately. They have rendered problems that
were difficult to solve by the earlier GAs to be solvable, requiring
only a subquadratic number of function evaluations. To facilitate
solving large-scale complex problems, and to further enhance the
performance of competent GAs, various efficiency-enhancement
techniques have been developed. This study investigates one such class
of efficiency-enhancement technique called evaluation
relaxation.

Evaluation-relaxation schemes replace a high-cost, low-error fitness
function with a low-cost, high-error fitness function. The error in
fitness functions comes in two flavors: Bias and variance. The
presence of bias and variance in fitness functions is considered in
isolation and strategies for increasing efficiency in both cases are
developed. Specifically, approaches for choosing between two fitness
functions with either differing variance or differing bias values have
been developed. This thesis also investigates fitness inheritance as
an evaluation-relaxation scheme. In fitness inheritance, the fitness
values of some individuals are inherited from their parents rather
than through a costly evaluation function, thereby reducing the total
function-evaluation cost.

Simple facetwise models have been derived to capture the dynamics in
each case and have been verified with simple but illustrating
empirical results. These models are also used to develop analytical
framework to tune algorithm parameters to obtain maximum speed-up.