Genetic Programming Using a Minimum Description Length Principle
Hitoshi Iba, Hugo de GARIS, Taisuke Sato · The MIT Press eBooks · 2003
This paper introduces a Minimum Description Length (MDL) principle to define fitness functions in Genetic Programming (GP). In traditional (Koza-style) GP, the size of trees was usually controlled by user-defined parameters, such as the maximum number of nodes and maximum tree depth. Large tree sizes meant that the time necessary to measure their fitnesses often dominated total processing time. To overcome this difficulty, we introduce a method for controlling tree growth, which uses an MDL principle. Initially we choose a "decision tree" representation for the GP chromosomes, and then show how an MDL principle can be used to define GP fitness functions. Thereafter we apply the MDL-based fitness functions to some practical problems. Using our implemented system "STROGANOFF", we show how MDL-based fitness functions can be applied successfully to problems of pattern recognitions. The results demonstrate that our approach is superior to usual neural networks in terms of general...