Date of Award

12-1992

Document Type

Thesis

Degree Name

Master of Science in Computer Engineering

Department

Department of Electrical and Computer Engineering

First Advisor

Gary B. Lamont, PhD

Abstract

Genetic algorithms (GA) are highly parallelizable, robust semi- optimization algorithms of polynomial complexity. The most commonly implemented GAs are 'simple' GAs (SGAs). Reproduction, crossover, and mutation operate on solution populations. Deceptive and GA-hard problems are provably difficult for simple GAs. Messy GAs (MGA) are designed to overcome these limitations. The MGA is generalized to solve permutation type optimization problems. Its performance is compared to another MGA's, an SGA's, and a permutation SGA's. Against a fully deceptive problem the generalized MGA (GMGA) consistently performs better than the simple GA. Against an NP-complete permutation problem, the GMGA performs better than the other GAs. Against DeJong function f2, the GMGA performs better than the other MGA, but not as well as the SGA. Four parallel MGA data distribution strategies are compared and not found to significantly affect solution quality. The interleaved strategy obtains near linear speedup. The indexed, modified indexed, and block strategies obtain 'super-linear speedup,' indicating that the sequential algorithm can be improved. Population partitioning impacts implementation of selection and crossover. Experiments which compare the solution quality, execution time, and convergence characteristics of three selection algorithms and three solution sharing strategies are performed.

AFIT Designator

AFIT-GCE-ENG-92D-08

DTIC Accession Number

ADA258994

Comments

The author's Vita page is omitted.

Download

Share

COinS