Examining the role of local optima and schema processing in genetic search

Abstract

Several factors contribute to making search problems easy or difficult. One of these factors is the modality of the fitness landscape. Quite often, when local search algorithms fail to locate the global optimum, it is because the algorithm converged to a local optimum. The majority of local search methods in use today maneuver through the search space using local neighborhood information around a single point to guide the search. In that search paradigm, the number of local optima that occur in the search space has a tremendous effect on search performance. Genetic algorithms are a population based search algorithm that use an ever changing neighborhood structure, based on the population mixture and genetic operators, to sample points in the search space. Genetic algorithms are believed to process schemata, where a schema is a subpartition of the search space, rather than individual points. When genetic algorithms fail to locate the global optimum, the typical analysis is that the schema information in the optimization problem was misleading. Consequently, it is unclear how local optima can affect such algorithms. While misleading schema information may be one source of problem difficulty for genetic algorithms, the existence of multiple high quality local optima may also be responsible for misleading the genetic algorithm. This research explores the relationship between local optima, schema processing and genetic algorithm behavior from a variety of perspectives.