Designing FIR Filters at a Logic Level using Evolutionary Algorithms
Traditionally digital filters are designed using the concept of a linear difference equation with the output response being a weighted sum of signal samples with usually floating point coefficients. Unfortunately such a model is necessarily expensive in terms of hardware as it requires many large bit additions and multiplications. In this paper it is shown how it is possible to evolve a tiny feed-forward rectangular array of logic gates to perform various filtering tasks - lowpass, bandpass, and multiband. The circuit is evolved by assessing its response to digitised pure sine waves. Some of the evolved circuit possess almost linear properties, which means that they are capable of filtering composite signals which have not been encountered in training.
The Revenge of the Schema Theorem: Steps Towards a Schema-based Proof of GA Convergence
In this seminar I first develop a new form of schema theorem in which expectations are not present. This theorem allows one to predict with a known probability whether the number of instances of a schema at the next generation will be above a given threshold. Then I use this version of the schema theorem backwards, i.e. to predict the past from the future. Assuming that at least one solution is found at one generation, this allows me to find the conditions (at the previous generation) under which such a solution will indeed be found. By using the notion of left-to-right convergence (i.e. the idea of discovering one new bit of the solution per generation) and by recursively applying the schema theorem to such conditions it is possible to find under which conditions on the initial generation the GA will converge in a constant time. These results allow to write very simple population sizing equations for different initialisation strategies.
The results do not represent a full schema-theorem-based proof of convergence for GAs, because they assume the knowledge of the fitness of the population and of the building blocks being assembled by the GA at each generation. I have done work which overcomes these problems, but this is not fully checked and I will present it in a future seminar.
Continuous Learning in Continuous State-Spaces: Variable Resolution Model-Free Reinforcement Learning
Reinforcement learning agents attempt to learn and construct a decision policy which maximises some immediate reward signal. In turn, this policy is directly derived from long-term value (i.e. utility) estimates of state-action pairs, which the learner constructs. In environments with real-valued state-spaces, however, it is impractical to enumerate the value of every state-action pair. This necessitates the use of a function approximator in order to infer values from similar states. Typically, function approximators require many parameters for which suitable values may be difficult to determine a priori. Systems are also then bound to the fixed limits imposed by the initial parameters, beyond which no further improvements are possible.
I introduce a method to adaptively increase the resolution of a discretised action-value function based upon which regions of the state-space are most important for the purposes of deciding upon an action. The potential applications of the work are very wide and may enable reinforcement learning controllers to be used in a wider class of problems than has previously been possible. For example: finding (near) optimal controllers in high-dimensional and continuous state-spaces with highly non-linear and stochastic dynamics in sub-exponential time and space.
I won't assume a knowledge of reinforcement learning and so will being giving a brief introduction to the methods involved (which includes Markov Decision Processes). This is very much work in progress and will hopefully form part of my thesis work. I'd like to keep the talk fairly informal and open for discussion all the way through.
An examination of symbiosis as an evolutionary concept
I shall examine the claim that symbiosis and the prevalence of symbiostic associations in nature present a challenge to current neo-Darwinist evolutionary theory. I would like to argue that symbiosis may challenge the idealised seperability of the organism and the environment, as well as affecting the accepted informational flow of biological systems.
Using genetic programming to evolve a goalkeeper control program for the RoboCup middle size competition
In this talk, I will describe a genetic programming (GP) approach to the design of a motion-control strategy for a goalkeeper robot created to compete in the RoboCup99, the robot soccer world championships that will be held in Stockholm during IJCAI99.
After discussing some general design issues for a better understanding of the problem, I will show how we have used GP to design a control function that issues motion commands to the robot, based on the output of a vision sub-system controlled by a human-encoded algorithm. Preliminary results, and a short videotape showing a working prototype of the goalkeeper, will also be shown.
Axel Großmann , School of Computer Science, The University of Birmingham
The estimation of the position and orientation of a mobile robot in an environment is a difficult problem. This problem is even harder if only a small number of proximity sensors is available and the readings provided by those sensors are noisy, as it is the case of sonar sensing. Most existing localisation methods for mobile robots make simplifying assumptions about the properties of the sensors. Many methods, for example, assume a large number of evenly spaced sensors, which render them useless in robots with very few sensors. Unfortunately, the performance of a method depends on whether the inherent assumptions hold for the particular robot, its behaviour, and its environment. In the talk, I will give an overview of existing localisation methods such as feature-based detection techniques and Markov localisation methods. I will present a robust position tracking method for a mobile robot with seven sonar sensors. We use the Hough transform to detect features in the sonar readings that correspond to walls and corners in the environment. The detected features are matched with the world map directly in the Hough space. The correlation values obtained in the matching process are used to compute position probabilities in a probability grid.
Dietmar Heinke, School of Psychology, University of Birmingham
The human object identification of complex visual scenes is a long standing research topic in cognitive psychology. Humans attend to certain objects of complex scenes while ignoring other objects, i.e. they perform a selection for object identification. While this general account is undebated in cognitive psychology, the underlying mechanisms of the selection process are still unclear. Numerous experiments have been conducted to examine the mechanisms. The talk will give a brief introduction to some of the most important ones. SAIM (Selective Attention and Identification Model) tries to tackle the problem from a computational angle in a connectionist framework. SAIM aims to achieve a translation-invariant object identification by mapping selectively one object into a ''focus of attention'' and then matching it to stored templates. The design of the model uses a constraint satisfaction routine based on a continuous Hopfield network, resulting in cooperative and competitive connections in the model. From the simulations of SAIM there emerge several effects which mimic experimental findings. Apart from reproducing known effects SAIM also shows some verifiable predictions some of which we have recently confirmed. Overall, SAIM supports the idea that attentional effects found in humans are emergent properties of competition in the selection process.
Peter Nordin, Chalmers University of Technology, Sweden
My talk describes the hardware and software architecture behind the ELVIS robot. ELVIS is a bipedal robot with human-like geometry and motion capabilities - a humanoid. The control architecture is completely built around evolutionary systems and genetic programming. ELVIS is the first robot in a series of planned humanoid experiments, all of which will be primarily controlled by evolutionary adaptive methods. The final goal of our research project is to build a human-sized robot based on a plastic human skeleton to ensure geometric authenticity.
Tim Kovacs, School of Computer Science
The issue of deletion schemes for classifier systems has received little attention. In a standard genetic algorithm a chromosome can be evaluated (assigned a reasonable fitness) immediately. In classifier systems, however, a chromosome can normally only be fully evaluated after many interactions with the environment, since a chromosome may generalise over many environmental states. A new deletion technique which protects poorly evaluated chromosomes outperforms both techniques from (Wilson, 1995) in two very different single step problems. Results indicate the XCS classifier system is able to learn single step problems for which no (or few) useful generalisations can be made over the input string, despite its drive towards accurate generalisation.
Rachel Pearce, Computational Intelligence Group, Rolls Royce plc
Condition monitoring and diagnostics is an important field for the efficient and cost-effective use of a range of systems, machinery and industrial plants. This includes power stations, aircraft or motor fleet operation, machine tools, etc. By understanding the state a system is in, the operator is better able to manage its operation. Confidence in plannning can be gained from the certainty that everything is running normally. When faults do occur, prior identification of the nature of the fault means that parts can be ordered and ensures that the correct maintenance operations can be carried out. Also, early warning of the onset of a fault allows maintenance downtime to be planned in advance to minimise disruption and reduce the risk of secondary damage.
Computational intelligence has been widely applied to condition monitoring. The techniques used include neural networks, dimension reduction, visualisation and mapping, case-based reasoning, model manipulation using optimisation techniques. The talk will describe some of the issues that arise from monitoring high integrity systems, and how computational intelligence techniques have been used to address these issues.
Kazuhiro Ohkura, Department of Mechanical Engineering, Kobe University, Japan
An approach to extending genetic algorithms for overcoming premature convergence, which is the source of GA-difficulties, is presented. The motivation for the proposed method is based on the consideration that the premature convergence cannot be avoided as long as a GA employs neo-Darwinism as its framework, because of a dilemma between the effective genetic search based on building blocks and the diversity maintenance in the population. The proposed GA, which is named operon-GA, has new genetic mechanisms for growing building blocks in its evolutionary process. The diversity is maintained by the adaptive genetic changes due to the same genetic mechanisms. This extension is inspired by the neutral theory and the genetic mechanisms in microbial organisms. Several computer simulations are conducted to discuss the evolving behaviors and the optimization performance for different GA-difficulties.
Stevan J Anastasoff, School of Computer Science, University of Birmingham
A number of models of macroevolutionary extinction dynamics have been proposed during the past decade or so. Many of these models produce results that are in good accord with empirical data, as drawn from the fossil record. However, they all still suffer from significant shortcomings. A new simulation based model will be presented that attempts to address some of the limitations and weaknesses of the existing models. The simulation is driven by ecology level interaction amongst dynamically changing populations of species in a theoretical food web, coupled with the effects of external environmental stresses. The results of a number of extended runs of the simulation will be presented and discussed. It is observed that it is the interactions between intrinsic ecological factors, and extrinsic environmental factors, that determine the specific extinction dynamics generated. Ecological factors are key in defining the large-scale statistical trends of the system. Environmental stresses act as a sort of 'tempo keeper', determing the precise timing of extinction events within the large-scale framework. Overall, the results of the simulation suggest that macroevolutionary patterns of extinctions are primarily generated intrinsically by an ecosystem. Environmental factors are not so much a direct cause of extinction events, as a determinant of the precise timing of events that will, in any case, inevitably ensue.
Axel Grossmann, School of Computer Science, University of Birmingham
We would prefer that our robots learn their behaviours rather than have them hand-coded. This is the case because programming all the details by hand is tedious, we may not know the environment ahead of time, and we want the robots to adapt their behaviours as the environment changes. Reinforcement learning (RL) has been used by a number of researchers as a computational tool for building robots that improve themselves with experience. There are a number of reinforcement learning techniques that work well on small problems. But only few of them scale well to larger problems. In this work, we address the issue of learning multiple tasks in reinforcement environments. The motivation is to speed-up the learning process and to build agents that can adapt to changes in their environment during their entire lifetime. In most RL work so far, the algorithms do not use previously learned knowledge to speed up the learning of a new task. Instead, the learning agent must either ignore the existing policy, or worse, the current policy may be harmful while learning the next one.
The main challenge in building continually learning agents is to find effective mechanisms for the transfer of information between learning tasks. In the talk, I introduce a novel constructive neural-network model, called dynamic cell structures, which is based on local representations and which can be used to learn a task-dependent state representation for continuous input values. This algorithm uses a statistical criterion, the Kolmogorov-Smirnov test, for splitting states. Dynamic cell structures can be used as function approximator for model-based RL algorithms such as value iteration and prioritised sweeping. The algorithm has been applied to a Pioneer 1 mobile robot in two experimental scenarios: a robot navigation task and learning to collect soda cans. In the former, the learning agent has to adapt its action policy when parts of the environment change. In the latter, the robot learns to navigate safely, then learns to find soda cans using its vision system, and finally learns to pick up a can. The behaviours are learned in a bottom-up process whereby an old behaviour is used as constituent of a new behaviour.
Pauline C. Haddow, Department of Computer Science and Informatics, The Norwegian University of Science and Technology
The application of evolutionary techniques to hardware design is termed evolvable (evolutionary) hardware. The main goal being to replace traditional design methods with evolutionary techniques for given applications which are either not achievable using traditional methods or which benefit from an evolutionary approach.
Our group in Trondheim launched into this area just one year ago, looking at a newer approach to Evolvable Hardware - "Complete Hardware Evolution (CHE)". Here the complete evolution process and the evolving design are located on a single chip. Many spin off projects have arisen from this work including work within evolvable robotics, evolving adaptive filters, evolving a router controller and related work within VHDL code evolution, selection methods and genetic operator analysis.
Our long term focus is to build on our work within CHE, using the resources now available in reconfigurable technology, to achieve modelling and simulation of complex biological processes in hardware. This involves cooperation with biologists to establish realistic models which may be evolved so as to identify realistic hypothesis that may be followed through by biological experimentation. Our ongoing project in this area is within the field of cell signal transduction.
This talk will provide a short introduction to evolvable hardware, CHE itself and present a selection of our ongoing projects.
Xin Yao, School of Computer Science, The University of Birmingham
The iterated prisoner's dilemma (IPD) game has been used extensively in modelling various real-world situations. This talk is concerned with the evolutionary approach to the IPD game. First, we generalise the game from 2 players to N players and investigate the impact of the group size on the evolution. Then we study a more realistic IPD game where more than two levels of cooperations are allowed. Surprisingly, more choices appear to discourage cooperation among players. Lastly, we move the game yet another step closer to the real world situation where players may not be able to interact with each other for a long time. We also consider the case where some players may not be able to interact with other directly, but they can see their opponent's reputation. It turns out that the reputation of a player is an important factor in encouraging cooperative behaviours in a group.
Bill Langdon, CWI, Holland
Once some minimum size threshold has been exceeded, the distribution of performance (particularly of fitness) of programs within the search space is approximately independent of program length.
This can be proved for linear programs and for simple side effect free parse trees.
Limited experiments with programs including side effects and iteration suggest a similar result may also hold for a wider class of programs.
Ian Millington, SoCS
A society's understanding of its own identity is central to a number of its dynamics. From fashion and clique-formation at a local level to culture and nationalism at a larger scale, all are affected by the way in which individuals understand their own identity and their aspirations to achieve a different identity or change the identity of those around them. This paper develops one possible agent based model for the change in self-understanding based on a five year investigation into the changes of social structure in renaissance florence during the emergence of modern banking institutions. It has shown that the dynamics of the model change depending on the communication structure in the agent-population, and that slower, more radical change occurs in populations with localised communication, and swifter changes with less momentum are characteristic of populations whose communication is described by a small world network.
Dr Ali Zalzala, Computing and Electrical Engineering Department, Heriot-Watt University
This seminar will discuss the application of computational intelligence (in particular neural networks and evolutionary computation) to the design and control of intelligent systems. Two applications will be redressed, hybrid position/force control of robots and the functional control of medical prosthesis via EMG signals. Theoretical background will include the modular design of neural nets, neuro-genetic structures and combining computational intelligent algorithms with conventional methods.
Kauffman's model of genetic optimisation; the NK landscape has been widely studied in various contexts. It is a simple model that seeks to explain the way that inter-related networks of genes can go about optimising themselves for a given task. The work described in this talk is an exploration of an under-investigated parameter in Kauffman's model; the distribution of epistatic connections (sometimes called 'K among the N'). It has been shown that various network architectures considered to be beneficial in evolution show poor performance in the NK model; random architectures perform better than networks with any explicit organisation. Finally a metric is given that seems to be able to distinguish random networks and optimal genetic networks.
I intend to spend the first part of this talk giving a quick tutorial on the NK landscape and some of its better known reincarnations. I will also give a quick overview of biological context of this work (genetic epistasis and genetic regulatory networks), before talking about this new, but not entirely complete work. It is a particularly exciting area of research given that with this week's release of Chromosome 22 human genome data, the first large scale investigations are now beginning into the architecture of real genetic networks.
Riccardo Poli, SoCS, U. B'ham
Two main weaknesses of GA and GP schema theorems are that they provide only information on the EXPECTED VALUE of the number of instances of a given schema at the next generation E[m(H,t+1)], and they can only give a LOWER BOUND for such a quantity. I will present (in an informal and relaxed way... be warned :-) new theoretical results obtained by myself and by others on GP and GA schemata which largely overcome these weaknesses. These include, for example, two long-sought EXACT schema theorems for GAs (due to Stephens and Waelbroeck) and GP.
Some of these results (at last) provide strong mathematical support for the existence of building blocks in GAs and GP which, surprisingly, are not necessarily all short, low-order or highly fit.
Christopher Stephens, Instituto de Ciencias Nucleares, Mexico
In evolutionary computation the concept of a fitness landscape has played an important role, evolution itself being portrayed as a hill-climbing process on a rugged landscape. I show that, in general, in the presence of other genetic operators such as mutation and recombination, hill-climbing is the exception rather than the rule. This descrepency can be traced to the different ways that the concept of fitness appears --- as a measure of the number of fit offspring, or as a measure of the probability to reach reproductive age. Effective fitness models the former not the latter and gives an intuitive way to understand population dynamics as flows on an effective fitness landscape when genetic operators other than selection play an important role and particularly in the case when the genotype-phenotype map is non-trivial. The efficacy of the concept is shown using several simple analytic examples and also some more complicated cases illustrated by simulations.