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

Thumbnail Image
Date
2009-01-01
Authors
Jiang, Hsin-yi
Major Professor
Advisor
Committee Member
Journal Title
Journal ISSN
Volume Title
Publisher
Authors
Research Projects
Organizational Units
Organizational Unit
Computer Science

Computer Science—the theory, representation, processing, communication and use of information—is fundamentally transforming every aspect of human endeavor. The Department of Computer Science at Iowa State University advances computational and information sciences through; 1. educational and research programs within and beyond the university; 2. active engagement to help define national and international research, and 3. educational agendas, and sustained commitment to graduating leaders for academia, industry and government.

History
The Computer Science Department was officially established in 1969, with Robert Stewart serving as the founding Department Chair. Faculty were composed of joint appointments with Mathematics, Statistics, and Electrical Engineering. In 1969, the building which now houses the Computer Science department, then simply called the Computer Science building, was completed. Later it was named Atanasoff Hall. Throughout the 1980s to present, the department expanded and developed its teaching and research agendas to cover many areas of computing.

Dates of Existence
1969-present

Related Units

Journal Issue
Is Version Of
Versions
Series
Department
Computer Science
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.

Comments

Copyright © Hsin-yi Jiang, 2009. All rights reserved.

Description
Keywords
Citation
DOI
Source
Copyright
Collections