Analysis of Linkage-Friendly Genetic Algorithms.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 1996
Accession Number
ADA322922

Entities

People

  • Laurence D. Merkle

Organizations

  • Air Force Institute of Technology

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Artificial Intelligence
  • Computer Programming
  • Computers
  • Data Science
  • Evolutionary Algorithms
  • Genetic Algorithms
  • Information Science
  • Markov Chains
  • Mathematical Models
  • Operations Research
  • Optimization
  • Order Statistics
  • Probabilistic Models
  • Probability
  • Random Variables
  • Statistics

Readers

  • Graph Algorithms and Convex Optimization.
  • Operations Research
  • Statistical inference.

Technology Areas

  • AI & ML
  • AI & ML - Bayesian Inference
  • AI & ML - Machine Learning Algorithms
  • Biotechnology
  • Space