Sushil Louis
- Gary McGraw
- Richard O. Wyckoff
Department of Computer Science
Center for Research on Concepts and Cognition
Indiana University, Bloomington, Indiana 47405
(812) 855-6486 (812)
855-6966
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
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.