next up previous
Next: Introduction

CBR Assisted Explanation of GA Results

Sushil Louis tex2html_wrap_inline225 - Gary McGraw tex2html_wrap_inline227
- Richard O. Wyckoff tex2html_wrap_inline225
tex2html_wrap_inline225 Department of Computer Science
tex2html_wrap_inline233 Center for Research on Concepts and Cognition
Indiana University, Bloomington, Indiana 47405
(812) 855-6486 tex2html_wrap_inline225 (812) 855-6966 tex2html_wrap_inline233
Computer Science Technical Report number 361
CRCC Technical Report number 63
louis@cs.indiana.edugem@cogsci.indiana.edu
rwyckoff@copper.ucs.indiana.edu

August 1, 1992

Abstract:

This paper describes a system for explaining solutions generated by genetic algorithms (GAs) using tools developed for case-based reasoning (CBR). In addition, our work empirically supports the building block hypothesis (BBH) which states that genetic algorithms work by combining good sub-solutions called building blocks into complete solutions. Since the space of possible building blocks and their combinations is extremely large, solutions found by GAs are often opaque and cannot be easily explained. Ironically, much of the knowledge required to explain such solutions is implicit in the processing done by the GA. Our system extracts and processes historical information from the GA using knowledge acquisition and analysis tools developed for case-based reasoning. If properly analyzed, the resulting knowledge base can be used: to shed light on the nature of the search space, to explain how a solution evolved, to discover its building blocks, and to justify why it works. Such knowledge about the search space can be used to tune the GA in various ways. As well as being a useful explanatory tool for GA researchers, our system serves as an empirical test of the building block hypothesis. The fact that it works so well lends credence to the theory that GAs work by exploiting common genetic building blocks.




next up previous
Next: Introduction

Sushil J. Louis
Wed Jun 25 14:10:37 PDT 1997