Andrew Dymek

Date of Award

3-1992

Document Type

Thesis

Degree Name

Master of Science

Department

Department of Electrical and Computer Engineering

First Advisor

Gary B. Lamont, PhD

Abstract

Genetic algorithms are stochastic search algorithms which model natural adaptive systems. In support of the development of a genetic search package for AFIT's iPSC/2 Hypercube, this study focused on two problem areas associated with hypercube implementations. Premature convergence occurs when the population becomes dominated by locally optimal, but globally inferior, solutions. Based on an examination of past hypercube implementations, the selection and communication strategies were hypothesized as causes of premature convergence. Experiments to test these hypotheses were conducted on Rosenbrock's saddle, a function often associated with premature convergence. Communication of best solutions led to premature convergence in small population sizes, but increased the likelihood of finding the global optimal in large population sizes. Genetic algorithms using global selection were more robust than those using local selection. GA-hard problems are intrinsically difficult for standard genetic algorithms. Messy genetic algorithms are effective against GA-hard problems. The second part of this study added a parallel version of a messy genetic algorithm to the genetic algorithm package. Against a sample GA-hard problem, the parallel implementation achieved a linear speedup of the sequential bottleneck while still finding the global optimal. The messy genetic algorithm should be applied to problems of practical importance.

AFIT Designator

AFIT-GCS-ENG-92M-02

DTIC Accession Number

ADA248092

Comments

The author's Vita page is omitted.

Download

Share

COinS