Date of Award

12-1996

Document Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Department of Electrical and Computer Engineering

First Advisor

Gary B. Lamont, PhD

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.

AFIT Designator

AFIT-DS-ENG-96-11

DTIC Accession Number

ADA322922

Download

Share

COinS