Computer Science Department
School of Computer Science, Carnegie Mellon University
Algorithms Evolution with Internal Reinforcement
The central algorithmic innovation of this thesis is the process by which a novel principled credit-blame assignment is introduced and incorporated into the evolution of algorithms, thus improving the evolutionary process. This principled credit-blame assignment is done through a new program representation called neural programming and applied through a set of principled processes collectively called internal reinforcement in neural programming. This thesis concentrates on these algorithmic innovations in real world signal domains where the signals are typically large and/or poorly understood.
This evolutionary learning of algorithms takes place in PADO, a system developed in this thesis for "parallel algorithm discovery and orchestration" and as a demonstrably effective strategy for divide-and-conquer in signal classification domains. This thesis includes an extensive empirical evaluation of the techniques developed in a rich variety of real-world signals. The results obtained demonstrate, among other things, the effectiveness of principled credit-blame assignment in algorithm evolution.
This work is unique in three aspects. No other currently existing system can learn to classify or otherwise "symbolize" signals with no space or size penalties for the signal's size or type. No other system based on genetic programming currently exists that purposefully generates and orchestrates a variety of experts along problem specific lines. And, most centrally, the thesis introduces the first analytically sound mechanism for explaining and reinforcing specific parts of an evolving program.
The goal of this thesis is to argue, explain, and demonstrate how representation and search are intimately connected in evolutionary computation and to address these dual concerns in the context of the evolution of Turing complete programs. Ideally, this thesis will inspire future research in this same area and along similar lines.