The Application of Software Visualization Technology
to Evolutionary Computation: A Case Study in Genetic Algorithms
Trevor D. Collins
Knowledge Media Institute
The Open University, UK
A dissertation submitted in partial satisfaction of
the requirements for the degree Doctor of Philosophy in Artificial Intelligence
Evolutionary computation is an area within the field of artificial
intelligence that is founded upon the principles of biological evolution.
Evolution can be defined as the process of gradual development. Evolutionary
algorithms are typically applied as a generic problem solving method,
searching a problem space in order to locate good solutions. These
solutions are found through an iterative evolutionary search that
progresses by means of gradual developments.
In the majority of cases of evolutionary computation the user is
not aware of their algorithm's search behaviour. This causes two problems.
First, the user has no way of assuring the quality of any solutions
found other than to compare the solutions found by the algorithm with
any available benchmark solutions or to re-run the algorithm and check
if the results can be repeated or improved upon. Second, because the
user is unaware of the algorithm's behaviour they have no way of identifying
the contribution of the different components of the algorithm and
therefore, no direct way of analyzing the algorithm's design and assigning
credit to good algorithm components, or locating and improving ineffective
The artificial intelligence and engineering communities have been
slow to accept evolutionary computation as a robust problem-solving
method because, unlike cased-based systems, rule-based systems or
belief networks, they are unable to follow the algorithm's reasoning
when locating a set of solutions in the problem space. During an evolutionary
algorithm's execution the user may be able to see the results of the
search but the search process itself like is a "black box"
to the user. It is the search behaviour of evolutionary algorithms
that needs to be understood by the user, in order for evolutionary
computation to become more accepted within these communities.
The aim of software visualization is to help people understand and
use computer software. Software visualization technology has been
applied successfully to illustrate a variety of heuristic search algorithms,
programming languages and data structures. This thesis adopts software
visualization as an approach for illustrating the search behaviour
of evolutionary algorithms.
Genetic Algorithms ("GAs") are used here as a specific
case study to illustrate how software visualization may be applied
to evolutionary computation. A set of visualization requirements are
derived from the findings of a GA user study. A number of search space
visualization techniques are examined for illustrating the search
behaviour of a GA. "Henson," an extendable framework for
developing visualization tools for genetic algorithms is presented.
Finally, the application of the Henson framework is illustrated by
the development of "Gonzo," a visualization tool designed
to enable GA users to explore their algorithm's search behaviour.
The contributions made in this thesis extend into the areas of software
visualization, evolutionary computation and the psychology of programming.
The GA user study presented here is the first and only known study
of the working practices of GA users. The search space visualization
techniques proposed here have never been applied in this domain before,
and the resulting interactive visualizations provide the GA user with
a previously unavailable insight into their algorithm's operation.
Contents- Including the thesis cover page, acknowledgments,
list of associated publications, abstract, contents list, list of
figures and list of tables. pages 0-32.
contents.pdf - 221K.
Chapter 1- Introduction. pages 33-38.
chapter1.pdf - 126K.
Chapter 2- An Overview of Evolutionary Computation. pages
chapter2.pdf - 189K.
Chapter 3- GA User Study. pages 52-82.
chapter3.pdf - 252K.
Chapter 4- Review of Related Work. pages 83-127.
chapter4a.pdf - 410K, chapter4b.pdf
- 315K, chapter4c.pdf - 284K.
Chapter 5- Visualization Design Rationale. pages 128-159.
chapter5.pdf - 536K.
Chapter 6- Henson: A GA Visualization Framework. pages 160-176.
chapter6.pdf - 252K.
Chapter 7- Gonzo: A Search Space Visualization Tool. pages
chapter7a.pdf - 315K, chapter7b.pdf
- 441K, chapter7c.pdf - 252K, chapter7d.pdf
- 284K, chapter7e.pdf - 189K.
Chapter 8- Discussion. pages 214-247.
chapter8.pdf - 252K.
Appendix A- GA User Questionnaire. pages 248-258.
appendixa.pdf - 95K.
Appendix B- GA User Study: Results Summary. pages 259-314.
appendixb.pdf - 284K.
Appendix C- GA Users Questionnaire Responses. pages 315-448.
appendixc.pdf - 347K.
Appendix D- Gonzo Example Applications. pages 449-456.
appendixd.pdf - 126K.