A Framework for Estimating the Applicability of GAs for Real‐World Optimization Problems

Jiang, Hsin-yi (2009) A Framework for Estimating the Applicability of GAs for Real‐World Optimization Problems. PhD thesis, Computer Science, Iowa State University.

Abstract

This paper introduces a methodology for estimating the applicability of a particular Genetic Algorithm (GA) configuration for an arbitrary optimization problem based on run-time data. GAs are increasingly employed to solve complex real-world optimization problems featuring ill-behaved search spaces (e.g., non-continuous, non-convex, non-differentiable) for which traditional algorithms fail. The quality of the optimal solution (i.e., the fitness value of the global optimum) is typically unknown in a real-world problem, making it hard to assess the absolute performance of an algorithm which is being applied to that problem. In other words, with a solution provided by a GA run, there generally lacks a method or a theory to measure how good the solution is. Although many researchers applying GAs have provided experimental results showing their successful applications, those are merely averaged-out, \emph{ad hoc} results. The results cannot represent nor guarantee the usability of the best solutions obtained from a single GA run since the solutions can be very different for each run. Therefore, it is desirable to provide a formalized measurement to estimate the applicability of GAs to real-world problems. This work extends our earlier work on the convergence rate, and proposes an evaluation metric to quantify the applicability of GAs. Through this metric, a degree of convergence can be obtained after each GA run so that researchers and practitioners are able to obtain certain information about the relation between the best solution and all of the feasible solutions. To support the proposed evaluation metric, a series of theorems are formulated from the theory of matrices. Moreover, several experiments are conducted to validate the metric.