Degree Type

Dissertation

Date of Award

2009

Degree Name

Doctor of Philosophy

Department

Computer Science

First Advisor

Carl K. Chang

Second Advisor

Andrew S. Miner

Abstract

Genetic Algorithms (GAs) have been gradually identified as an optimization-problem solver for certain classes of real-world applications. As GAs are increasingly utilized, a foundational

study on how well GAs can perform with respect to varying problem domains becomes crucial. Yet, none of the prevalent theoretical studies are built upon the linkage between the theory and application of GAs. This dissertation introduces a methodology for estimating the

applicability of a GA configuration for an arbitrary optimization problem based on run-time data. More specifically, this work analyzes the convergence behavior within a finite number of generations for each GA run through the estimation of the trace of the transition matrix of the

corresponding Markov chain from run-time data. The analytical and empirical results show that the methodology is helpful for evaluating the applicability of GAs to optimization problems. Through the methodology, the number of generations needed for empirical convergence

with respect to a fitness function (or a problem) can be estimated. The proposed methodology entails an evaluation metric and connects theory to application of GAs, for estimating the applicability of a GA to a problem. The methodology is demonstrated through a case study on evolutionary testing.

Copyright Owner

Hsin-yi Jiang

Language

en

Date Available

2012-04-30

File Format

application/pdf

File Size

123 pages

Share

COinS