Software Engineering || Net-Centric Computing || Postdoc & Visiting Scholars

   A Foundational Study on Applications of GA to SE Problems

       Genetic algorithm (GA) is invented by John Holland in 1960s. The algorithm is basically composed of repeated use of three operators: selection, crossover, and mutation. It is one of the powerful tools to solve optimization problems nowadays. Researchers have applied genetic algorithms to the optimization problems in software engineering (SE) for at least a decade. The so-called SE optimization problem, such as optimal scheduling, optimal test data generation, and optimal module clustering, is a problem in SE that 1) it can be solved by more than one feasible solution, 2) there is at least one criterion to evaluate solutions, and 3) the goal of the problem is to search for the best solution within the domain of all feasible solutions. Many experiments had been conducted by researchers to show that their applications of GAs indeed improved the solutions of optimization problems in SE. However, a support theory for the applicability of GAs to SE optimization problems is yet to be developed. It is because such experiments often only show that GAs can improve the solutions, but there generally lack evidence or proof whether the solutions found by the experiments are optimal or near optimal.

Markov chain will be applied in this research to analyze the behaviors of GAs since the fitness function, selection operator, crossover operator, and mutation operator can be embedded in the transition matrix. The state of the transition matrix represents every possible configuration of an entire population of bit strings (Gunter Rudolph & David B. Fogel et al.). Based on this analysis method, some useful results can be directly derived from Markov chain theorems.

The theory will be developed with a set of definitions from the SE perspectives. The goal is to better understand the behaviors of GAs with respect to SE optimization problems and provide the researchers or software engineers with a numerical reference model so that they can gain some insight before applying GAs.

International Center for Software Engineering

Iowa State Univerisity,  Department of Computer Science

226 Atanasoff Hall, Ames, IA 50011

1-515-294-4377 (Office) 1-515-294-0258(Fax) E-mail: chang@cs.iastate.edu

Copyright © 2002, Prof. Carl K. Chang