Co-evolutionary and Reinforcement Learning Techniques Applied to Computer Go players

The objective of this thesis is model some processes from the nature as evolution and co-evolution, and proposing some techniques that can ensure that these learning process really happens and useful to solve some complex problems as Go game. The Go game is ancient and very complex game with simple rules which still is a challenge for the Artificial Intelligence. This dissertation cover some approaches that were applied to solve this problem, proposing solve this problem using competitive and cooperative co-evolutionary learning methods and other techniques proposed by the author. To study, implement and prove these methods were used some neural networks structures, a framework free available and coded many programs. The techniques proposed were coded by the author, performed many experiments to find the best configuration to ensure that co-evolution is progressing and discussed the results. Using co-evolutionary learning processes can be observed some pathologies which could impact co-evolution progress. In this dissertation is introduced some techniques to solve pathologies as loss of gradients, cycling dynamics and forgetting. According to some authors, one solution to solve these co-evolution pathologies is introduce more diversity in populations that are evolving. In this thesis is proposed some techniques to introduce more diversity and some diversity measurements for neural networks structures to monitor diversity during co-evolution. The genotype diversity evolved were analyzed in terms of its impact to global fitness of the strategies evolved and their generalization. Additionally, it was introduced a memory mechanism in the network neural structures to reinforce some strategies in the genes of the neurons evolved with the intention that some good strategies learned are not forgotten. In this dissertation is presented some works from other authors in which cooperative and competitive co-evolution has been applied. The Go board size used in this thesis was 9x9, but can be easily escalated to more bigger boards.The author believe that programs coded and techniques introduced in this dissertation can be used for other domains.

On the Structural Difference between the Evolutionary Approach of Young and that of Kandori, Mailath, and Rob

We provide robust examples of symmetric two-player coordination games in normal form that reveal that equilibrium selection by the evolutionary model of Young (1993) is essentially different from equilibrium selection by the evolutionary model of Kandori, Mailath and Rob (1993).

On the structural difference between the evolutionary approach of Young and that of Kandori, Mailath and Rob

We provide robust examples of symmetric two-player coordination games in normal form that reveal that equilibrium selection bythe evolutionary model of Young (1993) is essentially different from equilibrium selection by the evolutionary model of Kandori, Mailath and Rob (1993).

Uncertainty assessment approach for composite structures based on global sensitivity indices

The problem of uncertainty propagation in composite laminate structures is studied. An approach based on the optimal design of composite structures to achieve a target reliability level is proposed. Using the Uniform Design Method (UDM), a set of design points is generated over a design domain centred at mean values of random variables, aimed at studying the space variability. The most critical Tsai number, the structural reliability index and the sensitivities are obtained for each UDM design point, using the maximum load obtained from optimal design search. Using the UDM design points as input/output patterns, an Artificial Neural Network (ANN) is developed based on supervised evolutionary learning. Finally, using the developed ANN a Monte Carlo simulation procedure is implemented and the variability of the structural response based on global sensitivity analysis (GSA) is studied. The GSA is based on the first order Sobol indices and relative sensitivities. An appropriate GSA algorithm aiming to obtain Sobol indices is proposed. The most important sources of uncertainty are identified.

Uncertainty propagation in inverse reliability-based design of composite structures

An approach for the analysis of uncertainty propagation in reliability-based design optimization of composite laminate structures is presented. Using the Uniform Design Method (UDM), a set of design points is generated over a domain centered on the mean reference values of the random variables. A methodology based on inverse optimal design of composite structures to achieve a specified reliability level is proposed, and the corresponding maximum load is outlined as a function of ply angle. Using the generated UDM design points as input/output patterns, an Artificial Neural Network (ANN) is developed based on an evolutionary learning process. Then, a Monte Carlo simulation using ANN development is performed to simulate the behavior of the critical Tsai number, structural reliability index, and their relative sensitivities as a function of the ply angle of laminates. The results are generated for uniformly distributed random variables on a domain centered on mean values. The statistical analysis of the results enables the study of the variability of the reliability index and its sensitivity relative to the ply angle. Numerical examples showing the utility of the approach for robust design of angle-ply laminates are presented.

Adapting Meeting Tools to Agent Decision

Electricity markets are complex environments comprising several negotiation mechanisms. MASCEM (Multi- Agent System for Competitive Electricity Markets) is a simulator developed to allow deep studies of the interactions between the players that take part in the electricity market negotiations. ALBidS (Adaptive Learning Strategic Bidding System) is a multiagent system created to provide decision support to market negotiating players. Fully integrated with MASCEM it considers several different methodologies based on very distinct approaches. The Six Thinking Hats is a powerful technique used to look at decisions from different perspectives. This paper aims to complement ALBidS strategies usage by MASCEM players, providing, through the Six Thinking Hats group decision technique, a means to combine them and take advantages from their different perspectives. The combination of the different proposals resulting from ALBidS’ strategies is performed through the application of a Genetic Algorithm, resulting in an evolutionary learning approach.

Six thinking hats: A novel metalearner for intelligent decision support in electricity markets

The energy sector has suffered a significant restructuring that has increased the complexity in electricity market players' interactions. The complexity that these changes brought requires the creation of decision support tools to facilitate the study and understanding of these markets. The Multiagent Simulator of Competitive Electricity Markets (MASCEM) arose in this context, providing a simulation framework for deregulated electricity markets. The Adaptive Learning strategic Bidding System (ALBidS) is a multiagent system created to provide decision support to market negotiating players. Fully integrated with MASCEM, ALBidS considers several different strategic methodologies based on highly distinct approaches. Six Thinking Hats (STH) is a powerful technique used to look at decisions from different perspectives, forcing the thinker to move outside its usual way of thinking. This paper aims to complement the ALBidS strategies by combining them and taking advantage of their different perspectives through the use of the STH group decision technique. The combination of ALBidS' strategies is performed through the application of a genetic algorithm, resulting in an evolutionary learning approach.

The evolution of conventions under incomplete information

We formulate an evolutionary learning process in the spirit ofYoung (1993a) for games of incomplete information. The process involves trembles. For many games, if the amount of trembling is small, play will be in accordance with the games' (semi-strict) Bayesian equilibria most of the time. This supports the notion of Bayesian equilibrium. Further, often play will most of the time be in accordance with exactly one Bayesian equilibrium. This gives a selection among the Bayesian equilibria. For two specific games of economic interest wecharacterize this selection. The first is an extension to incomplete information of the prototype strategic conflict known as Chicken. The second is an incomplete information bilateral monopoly, which is also an extension to incompleteinformation of Nash's demand game, or a simple version ofthe so-called sealed bid double auction. For both gamesselection by evolutionary learning is in favor of Bayesianequilibria where some types of players fail to coordinate, such that the outcome is inefficient.

Creating capabilities in local environments and production networks

Includes bibliography

Evolutionary ecology of learning: insights from fruit flies

Ecologically and evolutionarily oriented research on learning has traditionally been carried out on vertebrates and bees. While less sophisticated than those animals, fruit flies (Drosophila) are capable of several forms of learning, and have an advantage of a short generation time, which makes them an ideal system for experimental evolution studies. This review summarizes the insights into evolutionary questions about learning gained in the last decade from evolutionary experiments on Drosophila. These experiments demonstrate that Drosophila have the genetic potential to evolve substantially improved learning performance in ecologically relevant learning tasks. In at least one set of selected populations the improved learning generalized to another task than that used to impose selection, involving a different behavior, different stimuli, and a different sensory channel for the aversive reinforcement. This improvement in learning ability was associated with reduction in other fitness-related traits, such as larval competitive ability and lifespan, pointing out to evolutionary trade-offs of improved learning. These trade-offs were confirmed by other evolutionary experiments where reduction in learning performance was observed as a correlated response to selection for tolerance to larval nutritional stress or for delayed aging. Such trade-offs could be one reason why fruit flies have not fully used up their evolutionary potential for learning ability. Finally, another evolutionary experiment with Drosophila provided the first direct evidence for the long-standing ideas that learning can under some circumstances accelerate and in other slow down genetically-based evolutionary change. These results demonstrate the usefulness of fruit flies as a model system to address evolutionary questions about learning.

Reduced learning ability as a consequence of evolutionary adaptation to nutritional stress in Drosophila melanogaster

1. Dietary conditions affect cognitive abilities of many species, but it is unclear to what extent this physiological effect translates into an evolutionary relationship. 2. A reduction of competitive ability under nutritional stress has been reported as a correlated response to selection for learning ability in Drosophila melanogaster. Here we test whether the reverse holds as well, i.e. whether an evolutionary adaptation to poor food conditions leads to a decrease in learning capacities. 3. Populations of D. melanogaster were: (i) not subject to selection (control), (ii) selected for improved learning ability, (iii) selected for survival and fast development on poor food, or (iv) subject to both selection regimes. 4. There was no detectable response to selection for learning ability. 5. Selection on poor food led to higher survival, faster development and smaller adult size as a direct response, and to reduced learning ability as a correlated response. This study supports the hypothesis that adaptation to poor nutrition is likely to trade off with the evolution of improved learning ability.

Learning ability and longevity: a symmetrical evolutionary trade-off in Drosophila.

Learning ability can be substantially improved by artificial selection in animals ranging from Drosophila to rats. Thus these species have not used their evolutionary potential with respect to learning ability, despite intuitively expected and experimentally demonstrated adaptive advantages of learning. This suggests that learning is costly, but this notion has rarely been tested. Here we report correlated responses of life-history traits to selection for improved learning in Drosophila melanogaster. Replicate populations selected for improved learning lived on average 15% shorter than the corresponding unselected control populations. They also showed a minor reduction in fecundity late in life and possibly a minor increase in dry adult mass. Selection for improved learning had no effect on egg-to-adult viability, development rate, or desiccation resistance. Because shortened longevity was the strongest correlated response to selection for improved learning, we also measured learning ability in another set of replicate populations that had been selected for extended longevity. In a classical olfactory conditioning assay, these long-lived flies showed an almost 40% reduction in learning ability early in life. This effect disappeared with age. Our results suggest a symmetrical evolutionary trade-off between learning ability and longevity in Drosophila.

What can ecosystems learn? Expanding evolutionary ecology with learning theory.

BACKGROUND: The structure and organisation of ecological interactions within an ecosystem is modified by the evolution and coevolution of the individual species it contains. Understanding how historical conditions have shaped this architecture is vital for understanding system responses to change at scales from the microbial upwards. However, in the absence of a group selection process, the collective behaviours and ecosystem functions exhibited by the whole community cannot be organised or adapted in a Darwinian sense. A long-standing open question thus persists: Are there alternative organising principles that enable us to understand and predict how the coevolution of the component species creates and maintains complex collective behaviours exhibited by the ecosystem as a whole? RESULTS: Here we answer this question by incorporating principles from connectionist learning, a previously unrelated discipline already using well-developed theories on how emergent behaviours arise in simple networks. Specifically, we show conditions where natural selection on ecological interactions is functionally equivalent to a simple type of connectionist learning, 'unsupervised learning', well-known in neural-network models of cognitive systems to produce many non-trivial collective behaviours. Accordingly, we find that a community can self-organise in a well-defined and non-trivial sense without selection at the community level; its organisation can be conditioned by past experience in the same sense as connectionist learning models habituate to stimuli. This conditioning drives the community to form a distributed ecological memory of multiple past states, causing the community to: a) converge to these states from any random initial composition; b) accurately restore historical compositions from small fragments; c) recover a state composition following disturbance; and d) to correctly classify ambiguous initial compositions according to their similarity to learned compositions. We examine how the formation of alternative stable states alters the community's response to changing environmental forcing, and we identify conditions under which the ecosystem exhibits hysteresis with potential for catastrophic regime shifts. CONCLUSIONS: This work highlights the potential of connectionist theory to expand our understanding of evo-eco dynamics and collective ecological behaviours. Within this framework we find that, despite not being a Darwinian unit, ecological communities can behave like connectionist learning systems, creating internal conditions that habituate to past environmental conditions and actively recalling those conditions. REVIEWERS: This article was reviewed by Prof. Ricard V Solé, Universitat Pompeu Fabra, Barcelona and Prof. Rob Knight, University of Colorado, Boulder.

Evolutionary model trees for handling continuous classes in machine learning

Model trees are a particular case of decision trees employed to solve regression problems. They have the advantage of presenting an interpretable output, helping the end-user to get more confidence in the prediction and providing the basis for the end-user to have new insight about the data, confirming or rejecting hypotheses previously formed. Moreover, model trees present an acceptable level of predictive performance in comparison to most techniques used for solving regression problems. Since generating the optimal model tree is an NP-Complete problem, traditional model tree induction algorithms make use of a greedy top-down divide-and-conquer strategy, which may not converge to the global optimal solution. In this paper, we propose a novel algorithm based on the use of the evolutionary algorithms paradigm as an alternate heuristic to generate model trees in order to improve the convergence to globally near-optimal solutions. We call our new approach evolutionary model tree induction (E-Motion). We test its predictive performance using public UCI data sets, and we compare the results to traditional greedy regression/model trees induction algorithms, as well as to other evolutionary approaches. Results show that our method presents a good trade-off between predictive performance and model comprehensibility, which may be crucial in many machine learning applications. (C) 2010 Elsevier Inc. All rights reserved.