Evaluation-Relaxation Schemes for Genetic and Evolutionary Algorithms

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-