Intelligent organisms do not simply perform one task, but exhibit multiple distinct modes of behavior. For instance, humans can swim, climb, write, solve problems, and play sports. To be fully autonomous and robust, it would be advantageous for artificial agents, both in physical and virtual worlds, to exhibit a similar diversity of behaviors. This dissertation develops methods for discovering such behavior automatically using multiobjective neuroevolution. First, sensors are designed to allow multiple different interpretations of objects in the environment (such as predator or prey). Second, evolving networks are given ways of representing multiple policies explicitly via modular architectures. Third, the set of objectives is dynamically adjusted in order to lead the population towards the most promising areas of the search space. These methods are evaluated in five domains that provide examples of three different types of task divisions. Isolated tasks are separate from each other, but a single agent must solve each of them. Interleaved tasks are distinct, but switch back and forth within a single evaluation. Blended tasks do not have clear barriers, because an agent may have to perform multiple behaviors at the same time, or learn when to switch between opposing behaviors. The most challenging of the domains is Ms. Pac-Man, a popular classic arcade game with blended tasks. Methods for developing multimodal behavior are shown to achieve scores superior to other Ms. Pac-Man results previously published in the literature. These results demonstrate that complex multimodal behavior can be evolved automatically, resulting in robust and intelligent agents. / text

NEAT är en neuroevolutionsteknik som kan användas för att träna upp AI-kontrollerade robotar utan att behöva tillföra någon mänsklig expertis eller tidigare kunskap till systemet. Detta arbete undersöker hur väl denna teknik fungerar tillsammans med samevolution för att utveckla robotar i en tävlingsmiljö, med fokus på att testa tekniken på flera olika nivåer med varierande mängd komplexitet i form av väggar och hinder. Tekniken utvärderas genom att låta robotarna tävla mot varandra, deras kompetens mäts sedan från resultaten av dessa tävlingar. Exempelvis deras förmåga att vinna matcher. Resultaten visar att tekniken fungerade bra på nivån med låg komplexitet, men att robotarna har vissa svårigheter att lära sig kompetenta strategier på nivåerna med högre komplexitet. Tekniken har dock potential för flera olika varianter och förbättringar som potentiellt kan förbättra resultatet även på de mer komplexa nivåerna.

AN ABSTRACT OF THE THESIS OF SOROOSH SOHANGIR, for the MASTER OF SCIENCE degree in COMPUTER SCIENCE, presented on 9 th November 2011, at Southern Illinois University Carbondale. TITLE: OPTIMIZED FEATURE SELECTION USING NEUROEVOLUTION OF AUGMENTING TOPOLOGIES (NEAT) MAJOR PROFESSOR: Dr. Shahram Rahimi Feature selection using the NeuroEvolution of Augmenting Topologies (NEAT) is a new approach. In this thesis an investigation had been carried out for implementation based on optimization of the network topology and protecting innovation through the speciation which is similar to what happens in nature. The NEAT is implemented through the JNEAT package and Utans method for feature selection is deployed. The performance of this novel method is compared with feature selection using Multilayer Perceptron (MLP) where Belue, Tekto, and Utans feature selection methods is adopted. According to unveiled data from this thesis the number of species, the training, accuracy and number of hidden neurons are notably improved as compared with conventional networks. For instance the time is reduced by factor of three.

In the last decades neural networks have become more frequent in video games. Neuroevolution helps us generate optimal network topologies for specific tasks, but there are still still unexplored areas of neuroevolution, and ways of improving the performance of neural networks, which we could utilize for video game playing. The aim of this thesis is to find a suitable fitness evaluation and improve the plasticity of evolved neural networks, as well as comparing the performance and general video game playing abilities of established neuroevolution methods. Using Analog Genetic Encoding we implement evolving neuromodulatory topologies in a typical two-dimensional platformer video game, and have it play against itself without neuromodulation, and against a popular genetic algorithm known as Neuroevolution of Augmenting Topologies. A suitable input and output structure is developed as well as an appropriate fitness evaluation for properly mating and mutating a population of neural networks. The benefits of neuromodulation are tested by running and completing a number of tile-based platformer video game levels. The results show an increased performance in networks influenced by neuromodulators, but no general video game playing abilities are obtained. This shows us that a more advanced general gameplay learning method with higher influence is required. / Neurala nätverk har blivit allt vanligare i tv-spel. Neuroevolution hjälper oss att utveckla optimala neurala topologier för specifika uppgifter, men det finns fortfarande outforskade områden i neuroevolution, och sätt att förbättra förmågan hos neurala nätverk som vi kan använda i spel. Målet är att hitta en lämplig fitnessbedömning och förbättra plasticiteten hos utvecklade neuralanätverk, samt jämföra deras utförande och förmåga att generellt spela videospel. Detta med hjälp av etablerade neuroevolutionmetoder. Genom Analog Genetisk Kodning implementeras utvecklande neuromodulatoriska topologier i ett typiskt tvådimensionellt platformer spel. Det används sedan för att spela mot en version av sig själv som inte har neuromodulatoriska egenskaper, samt mot en populär genetisk algoritm kallad Neuroevolution of Augmenting Topologies. Ett passande format för input och output, samt en fitnessbedömningsmetod för parande och muterande aven population av neurala nätverk utvecklas. Fördelarna med neuromodulation testas genom att låta nätverken spela ett antal tile-baserade platformerbanor. Resultaten visar en förbättring av utförandet hos nätverk som utvecklat neuromodulatorer, dock inga generella spelkunskaper kunde läras. Detta visar oss att en mer avancerad metod för generellt spelande krävs för att kunna få ett neuralt nätverk kunna spela och lösa mer generella problem.

The field of evolutionary computation is inspired by the achievements of natural evolution, in which there is no final objective. Yet the pursuit of objectives is ubiquitous in simulated evolution because evolutionary algorithms that can consistently achieve established benchmarks are lauded as successful, thus reinforcing this paradigm. A significant problem is that such objective approaches assume that intermediate stepping stones will increasingly resemble the final objective when in fact they often do not. The consequence is that while solutions may exist, searching for such objectives may not discover them. This problem with objectives is demonstrated through an experiment in this dissertation that compares how images discovered serendipitously during interactive evolution in an online system called Picbreeder cannot be rediscovered when they become the final objective of the very same algorithm that originally evolved them. This negative result demonstrates that pursuing an objective limits evolution by selecting offspring only based on the final objective. Furthermore, even when high fitness is achieved, the experimental results suggest that the resulting solutions are typically brittle, piecewise representations that only perform well by exploiting idiosyncratic features in the target. In response to this problem, the dissertation next highlights the importance of leveraging human insight during search as an alternative to articulating explicit objectives. In particular, a new approach called novelty-assisted interactive evolutionary computation (NA-IEC) combines human intuition with a method called novelty search for the first time to facilitate the serendipitous discovery of agent behaviors. iii In this approach, the human user directs evolution by selecting what is interesting from the on-screen population of behaviors. However, unlike in typical IEC, the user can then request that the next generation be filled with novel descendants, as opposed to only the direct descendants of typical IEC. The result of such an approach, unconstrained by a priori objectives, is that it traverses key stepping stones that ultimately accumulate meaningful domain knowledge. To establishes this new evolutionary approach based on the serendipitous discovery of key stepping stones during evolution, this dissertation consists of four key contributions: (1) The first contribution establishes the deleterious effects of a priori objectives on evolution. The second (2) introduces the NA-IEC approach as an alternative to traditional objective-based approaches. The third (3) is a proof-of-concept that demonstrates how combining human insight with novelty search finds solutions significantly faster and at lower genomic complexities than fully-automated processes, including pure novelty search, suggesting an important role for human users in the search for solutions. Finally, (4) the NA-IEC approach is applied in a challenge domain wherein leveraging human intuition and domain knowledge accelerates the evolution of solutions for the nontrivial octopus-arm control task. The culmination of these contributions demonstrates the importance of incorporating human insights into simulated evolution as a means to discovering better solutions more rapidly than traditional approaches.

Existing methods in Reinforcement Learning (RL) that rely on gradient estimates suffer from the slow rate of convergence, poor sample efficiency, and computationally expensive training, especially when dealing with complex real-world problems with a sizable dimensionality of the state and action space. In this work, we attempt to leverage the benefits of evolutionary computation as a competitive, scalable, and gradient-free alternative to training deep neural networks for RL-specific problems. In this context, we present a novel distributed algorithm based on an efficient model encoding that allows the intuitive application of genetic operators. Our results demonstrate improved exploration and considerable reduction of trainable parameters while maintaining comparable performance with algorithms like Deep Q-Network (DQN), Asynchronous Advantage Actor Critic (A3C), and Evolution Strategy (ES) when evaluated on Atari 2600 games. A scalability assessment of the algorithm revealed a significant parallel speedup and over 10,000 fold improvement in memory requirement. Sample efficiency improved in some experiments, but not significantly. Finally, the algorithm was applied on a Remote Electrical Tilt (RET) optimization task, the improvements in Key Performance Indicators (KPIs) show that the algorithm is also effective in other domains. / gradientskattningar är begränsade av långsam konvergenshastighet, låg samplingeffektivitet och beräkningsmässigt dyra träningsprocedurer. Detta är särskilt fallet när dessa hanterar komplexa och verkliga problem med högdimensionella tillstånds- och handlingsrum. I detta arbete försöker vi utnyttja fördelarna med evolutionär beräkning som ett konkurrenskraftigt, skalbart och gradientfritt alternativ till att träna djupa neurala nätverk för RL-specifika problem. I detta sammanhang presenterar vi en ny distribuerad algoritm baserad på en effektiv modellkodning som möjliggör intuitiv tillämpning av genetiska operatorer. Våra resultat visar ett förbättrat utforskande och en avsevärd minskning av träningsbara.

This thesis investigates the use of Bayesian analysis upon an opponent's behaviour in order to determine the desired goals or strategy used by a given adversary. A terrain analysis approach utilising the A* algorithm is investigated, where a probability distribution between discrete behaviours of an opponent relative to a set of possible goals is generated. The Bayesian analysis of agent behaviour accurately determines the intended goal of an opponent agent, even when the opponent's actions are altered randomly. The environment of Poker is introduced and abstracted for ease of analysis. Bayes' theorem is used to generate an effective opponent model, categorizing behaviour according to its similarity with known styles of opponent. The accuracy of Bayes' rule yields a notable improvement in the performance of an agent once an opponent's style is understood. A hybrid of the Bayesian style predictor and a neuroevolutionary approach is shown to lead to effective dynamic play, in comparison to agents that do not use an opponent model. The use of recurrence in evolved networks is also shown to improve the performance and generalizability of an agent in a multiplayer environment. These strategies are then employed in the full-scale environment of Texas Hold'em, where a betting round-based approach proves useful in determining and counteracting an opponent's play. It is shown that the use of opponent models, with the adaptive benefits of neuroevolution aid the performance of an agent, even when the behaviour of an opponent does not necessarily fit within the strict definitions of opponent 'style'.

A evolução de redes neurais artificiais encontra aplicações em diversos campos na área de aprendizado de máquina, em particular, simulações de vida artificial onde uma população de indivíduos controlados por redes neurais se adaptam num ambiente virtual a fim de realizar uma determinada tarefa. Similar ao processo natural pelo qual o comportamento do organismo se modifica filogeneticamente através da complexificação do sistema nervoso, tais simulações oferecem uma nova abordagem sintética no estudo da inteligência, em contraposição aos métodos simbólicos tradicionais. Um recente método, conhecido por NEAT (NeuroEvolution of Augmenting Topologies), é capaz de obter os pesos e a própria topologia de rede neural utilizando algoritmos genéticos. A codificação utilizada pelo NEAT é flexível o suficiente para permitir evolução aberta e arquiteturas neurais arbitrárias. Este trabalho apresenta uma implementação do NEAT que pode ser utilizada em conjunto com um simulador de propósito geral, chamado Breve, formando uma plataforma para experimentos de vida artificial. A implementação proposta também estende o NEAT para lidar com redes neurais dinâmicas, onde o nível de ativação dos neurônios varia continuamente no tempo. Este novo modelo é comparado com o método tradicional numa tarefa clássica de controle não-supervisionado, mostrando um aumento de eficiência na busca pela solução do problema. Os resultados obtidos motivam o uso desta plataforma para experimentos de vida artificial, onde uma população de indivíduos interage continuamente com um ambiente dinâmico, se adaptando ao longo das gerações. / The evolution of artificial neural networks has a wide range of applicability in diverse areas in the field of machine learning, particularly, in artificial life simulations where a population of individuals, controlled by neural networks, adapts in a virtual environment in order to solve a given task. Resembling the natural process in which an organism\'s behavior is subjected to phylogenetic modifications through the complexification of the nervous system, such simulations offer a new synthetic approach in the investigation of intelligence, counter posing traditional symbolic methods. A recent method known as NEAT (NeuroEvolution of Augmenting Topologies), is able to obtain the synaptic weights and the topology with the aid of genetic algorithms. The encoding used by NEAT is flexible enough to allow for open-ended evolution and arbitrary neural architectures. This work presents a NEAT implementation especially suitable to be used with a general purpose simulator known as Breve, constituting a framework for artificial life experiments. The proposed implementation extends NEAT to include dynamical neuron models, where their inner state continuously varies over time. The new model is then compared to the traditional method in a classic unsupervised control benchmark task, showing an efficiency increase while solving the problem. The obtained results motivate the proposed framework for general experiments in artificial life, in which a population of individuals continuously interact with a dynamical environment, adapting through generations.

Les essaims de robots sont des systèmes composés d’un grand nombre de robots relativement simples. Du fait du grand nombre d’unités, ces systèmes ont de bonnes propriétés de robustesse et de passage à l’échelle. Néanmoins, il reste en général difficile de concevoir manuellement des contrôleurs pour les essaims de robots, à cause de la grande complexité des interactions inter-robot. Par conséquent, les approches automatisées pour l’apprentissage de comportements d’essaims de robots constituent une alternative attrayante. Dans cette thèse, nous étudions l’adaptation de comportements d’essaim de robots avec des méthodes de Embodied Evolutionary Robotics (EER) distribuée. Ainsi, nous fournissons trois contributions principales : (1) Nous étudions l’influence de la pression à la sélection dirigée vers une tâche dans un essaim d’agents robotiques qui utilisent une approche d’EER distribuée. Nous évaluons l’impact de différents opérateurs de sélection dans un algorithme d’EER distribuée pour un essaim de robots. Nos résultats montrent que le plus forte la pression à la sélection est, les meilleures performances sont atteintes lorsque les robots doivent s’adapter à des tâches particulières. (2) Nous étudions l’évolution de comportements collaboratifs pour une tâche de récolte d’objets dans un essaim d’agents robotiques qui utilisent une approche d’EER distribuée. Nous réalisons un ensemble d’expériences où un essaim de robots s’adapte à une tâche collaborative avec un algorithme d’EER distribuée. Nos résultats montrent que l’essaim s’adapte à résoudre la tâche, et nous identifions des limitations concernant le choix d’action. (3) Nous proposons et validons expérimentalement un mécanisme complètement distribué pour adapter la structure des neurocontrôleurs des robots dans un essaim qui utilise une approche d’EER distribuée, ce qui permettrait aux neurocontrôleurs d’augmenter leur expressivité. Nos expériences montrent que notre mécanisme, qui est complètement décentralisé, fournit des résultats similaires à un mécanisme qui dépend d’une information globale / Robot swarms are systems composed of a large number of rather simple robots. Due to the large number of units, these systems, have good properties concerning robustness and scalability, among others. However, it remains generally difficult to design controllers for such robotic systems, particularly due to the complexity of inter-robot interactions. Consequently, automatic approaches to synthesize behavior in robot swarms are a compelling alternative. In this thesis, we focus on online behavior adaptation in a swarm of robots using distributed Embodied Evolutionary Robotics (EER) methods. To this end, we provide three main contributions: (1) We investigate the influence of task-driven selection pressure in a swarm of robotic agents using a distributed EER approach. We evaluate the impact of a range of selection pressure strength on the performance of a distributed EER algorithm. The results show that the stronger the task-driven selection pressure, the better the performances obtained when addressing given tasks. (2) We investigate the evolution of collaborative behaviors in a swarm of robotic agents using a distributed EER approach. We perform a set of experiments for a swarm of robots to adapt to a collaborative item collection task that cannot be solved by a single robot. Our results show that the swarm learns to collaborate to solve the task using a distributed approach, and we identify some inefficiencies regarding learning to choose actions. (3) We propose and experimentally validate a completely distributed mechanism that allows to learn the structure and parameters of the robot neurocontrollers in a swarm using a distributed EER approach, which allows for the robot controllers to augment their expressivity. Our experiments show that our fully-decentralized mechanism leads to similar results as a mechanism that depends on global information

No description available.