Symbiotic Evolution of Neural Networks in Sequential Decision Tasks

Sequential decision tasks appear in many practical situations ranging from robot navigation to stock market trading. Because of the complexity of such tasks, it is often difficult to perceive the direct consequences of individual decisions and even harder to generate examples of correct behavior. Consequently, difficult decision problems such as routing traffic, autonomous control, and resource allocation are often unautomated or are only semi-automated using "rule-of-thumb" strategies or simple heuristics. This dissertation proposes a general methodology for automating these tasks using techniques from machine learning. Specifically, this research studies the combination of evolutionary algorithms and artificial neural networks to learn and perform difficult decision tasks. Evolutionary algorithms provide an efficient search engine for building decision strategies and require only minimal reinforcement or direction from the environment. Neural networks provide an efficient storage mechanism for the decision policy and can generalize experiences from one situation to another. The learning system developed in this dissertation called SANE contains an evolutionary algorithm specifically tailored to sequential decision learning. Populations evolve faster than previous methods and rarely converge on suboptimal solutions. SANE is extensively evaluated and compared to existing decision learning systems and other evolutionary algorithms. SANE is shown to be significantly faster, more robust, and more adaptive in almost every situation. Moreover, SANE's efficient searches return more profitable decision strategies. The flexibility and scope of SANE is demonstrated in two real-world applications. First, SANE significantly improves the play of a world champion Othello program. Second, SANE successfully forms neural networks that guide a robot arm to target objects while avoiding randomly placed obstacles. The contributions of this research are twofold: a novel integration of evolutionary algorithms and neural networks and an efficient system for learning decision strategies in complex problems.