A framework for estimating the applicability of GAs for real-world optimization problems

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