Accession Number : ADA322922

Title :   Analysis of Linkage-Friendly Genetic Algorithms.

Descriptive Note : Doctoral thesis,

Corporate Author : AIR FORCE INST OF TECH WRIGHT-PATTERSON AFB OH

Personal Author(s) : Merkle, Laurence D.

PDF Url : ADA322922

Report Date : DEC 1996

Pagination or Media Count : 173

Abstract : Evolutionary algorithms (EAs) are stochastic population-based algorithms inspired by the natural processes of selection, mutation, and recombination. EAs are often employed as optimum seeking techniques. A formal framework for EAs is proposed, in which evolutionary operators are viewed as mappings from parameter spaces to spaces of random functions. Formal definitions within this framework capture the distinguishing characteristics of the classes of recombination, mutation. and selection operators. EAs which use strictly invariant selection operators and order invariant representation schemes comprise the class of linkage-friendly genetic algorithms (lfGAs). Fast messy genetic algorithms (fmGAs) are lfGAs which use binary tournament selection (BTS) with thresholding. periodic filtering of a fixed number of randomly selected genes from each individual, and generalized single-point crossover. Probabilistic variants of thresholding and filtering are proposed. EAs using the probabilistic operators are generalized fmGAs (gfmGAs). A dynamical systems model of lfGAs is developed which permits prediction of expected effectiveness. BTS with probabilistic thresholding is modeled at various levels of abstraction as a Markov chain. Transitions at the most detailed level involve decisions between classes of individuals. The probability of correct decision making is related to appropriate maximal order statistics. the distributions of which are obtained. Existing filtering models are extended to include probabilistic individual lengths. Sensitivity of lfGA effectiveness to exogenous parameters limits practical applications. The lfGA parameter selection problem is formally posed as a constrained optimization problem in which the cost functional is related to expected effectiveness. Kuhn-Tucker conditions for the optimality of gfmGA parameters are derived.

Descriptors :   *ALGORITHMS, *OPTIMIZATION, MATHEMATICAL MODELS, PARAMETERS, PROBABILITY DISTRIBUTION FUNCTIONS, THESES, MATHEMATICAL PROGRAMMING, MATHEMATICAL FILTERS, ORDER STATISTICS, MARKOV PROCESSES, STOCHASTIC CONTROL, MAPPING(TRANSFORMATIONS), POPULATION(MATHEMATICS).

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE