Reviewed by
Robin Matthews
Institute
of Water and Environment, Cranfield University, UK.
This book is Number 1829 in the series "Lecture Notes in Computer Science", the purpose of the series being to report new developments in computer science at a high level. The book contains 20 selected papers presented at the Artificial Evolution conference in Dunkerque in November 1999. I am not an expert in the field of artificial evolution, and therefore review the book more as an interested and (slightly) informed layman.
The papers have been grouped into four sections - Genetic Operators and Theoretical Models, Applications, Agents and Cooperation, and Heuristics and Outlooks. In addition, by way of introduction, there is an invited paper reviewing fitness landscapes by Colin Reeves of Coventry University, who discusses the basic mathematical theory and methods associated with a search landscape, and describes some empirically determined properties of a number of such landscapes. He suggests that future research directions in this area include formally defining the meaning of the existence of a 'big valley' in the search landscape, and attempting to define classes of problems where such a big valley doesn't exist.
The first section, Genetic Operators and Theoretical Models, contains five papers on the behaviour of genetic operators. In the first, Jens Gottlieb reviews previously published Evolutionary Algorithms (EA) in relation to the Multidimensional Knapsack Problem. In this problem, the aim is to choose from a number of objects of different sizes, shapes and value the most valuable collection of items to pack in a knapsack subject to a volume or weight limit on the size of the knapsack. New initialisation routines are presented, along with a comparison of several repair and optimisation methods. In the following paper, Gottlieb and Günther Raidl investigate the influence of phenotypic locality on the efficiency of EAs. Small changes in genotype should also cause small changes in fitness or else the EA is like a random search and less efficient. In the third paper, Mike Rosenman describes the use of EA to arrive at desired house designs by adapting members of a list of pre-existing cases. He makes the point that the approach was able to provide a number of potentially satisfactory solutions, rather than a single solution, from which the designer could make a final selection. This paper would perhaps have been better in the Applications section. Next, Anikó Ekárt describes a mutation operator to remove redundant code and simplify algebraic expressions in genetic programs. In the last paper of this section, Anton Eremeev develops a simplified Genetic Algorithm (GA) and investigates the influence of tournament selection in which individuals are chosen at random and the best selected for the next generation. The upper and lower bounds of the expected proportion of individuals above a given threshold are also calculated.
The next section, Applications, contains six papers describing the application of evolutionary computation to a number of problems. For example, Nicholas Monmarché and his colleagues describe an interactive method similar to that used by Dawkins in 'The Blind Watchmaker'. In this application, a genetic algorithm is used to generate web page style sheets from which a user selects a proportion according to his or her artistic preferences. These are used to generate the next generation of sheets. The cycle continues until the processes of mutation, recombination and selection have produced a page that the user is happy with. Next, Alain Ratle investigates the use of EA consisting of three-dimensional blocks (rather than the more usual linear 'chromosomes') in trying to find the optimal distribution of two or more types of sound absorbing material elements that will maximise the absorbing properties of a 3D composite material. He describes the development of evolutionary operators (initialisation, crossover, mutation) specifically for 3D structures, concluding that optimisation performed in this way gave significant improvements in the quality of solutions compared to the classical approach. In the third paper in this section, Laurence Moreau-Giraud and Pascal Lafon describe a hybrid evolution strategy to solve mixed discrete and continuous constraint problems. This is a two-stage procedure which first uses EA to overcome local minima, followed by a deterministic gradient-based method (Lagrangian based quasi-Newton for the technically minded!) for the continuous variables to speed up the search. This approach significantly reduced the number of evaluations required and improved the reliability compared to using EA alone. Fourthly, Anne Spalanzani compared Darwinian and Lamarckian evolutionary learning in neural nets in the context of automatic speech recognition systems that need to be able to adapt to changes in the acoustic environment such as reverberation and background noise. In Darwinian evolution, what is learnt in one generation is not passed on to the next, only the capacity to learn, while in Lamarckian evolution, the knowledge accumulated in one generation is passed in the genotype to the next generation. She found no difference between the two approaches in terms of recognition rate of particular sounds subject to reverberation, but the Lamarckian approach was significantly quicker in learning. In the fifth paper, Jean Louchet describes a method of speeding up scene analysis in artificial stereoscopic vision. This method involves evolving a population of points in space that are most likely to be on the surfaces of 3D objects. Advantages claimed for the approach are that it doesn't require any image pre-processing or segmentation and that knowledge of a scene can be used at any stage of the computation even though it is being progressively improved all the time. Finally, Yu Li and Youcef Bouchebaba present an approach to solve the Optimum Communication Spanning Tree (OCST) problem of finding a minimum cost way of communicating to a number of nodes by assuming the whole tree is the 'chromosome' of a GA rather than the linear chromosome normally used. Routines are presented for crossover, mutation and initialisation of this structure. Results showed it to be a simple yet effective approach.
In the third section, four papers on interactions between agents, particularly that of co-operation, are presented. In the first paper, Philippe Mathieu and his colleagues studied a number of strategies in the Classical Iterated Prisoner's Dilemma (CIPD) problem, and classified their behaviours into five groups - monotonous convergence, attenuated oscillatory movements, periodic movements, increasing oscillations and disordered oscillations. They also investigated the sensitivity of these behaviours to initial conditions, population size, game length, pay off and computation method. Contrary to the accepted view, they conclude that co-operation is not the most frequent basin of attraction, particularly where complex strategies are involved. In the second paper, A. J. Bagnall and G. D. Smith describe a multi-agent model of the UK electricity market, consisting of a single adaptive agent using two Learning Classifier Systems (LCS) which attempts to evolve bidding strategies against several non-adaptive agents with static bidding strategies. The objective of the adaptive agent is to develop a strategy that optimises its profit within a specific environment. The justification for using LCS rather than neural nets is that they are better at generating actions to maximise profit and allow modelling of different objectives in a single agent. In the third paper in this section, Samuel Delepoulle, Philippe Preux and Jean-Claude Darcheville study the evolution of co-operation through the use of both human subjects and computer simulation. Firstly, they carried out an experiment with human subjects interacting with each other through a computer, and were able to show that co-operative social behaviour could emerge from rational individual behaviour. They then describe the development of an agent-based model to compare five reinforcement-learning architectures and conclude that the best of these, the Staddon-Zhang algorithm, matched human performance and behaviour quite closely and outperformed the well-known Q-learning algorithm. In the fourth paper, David Griffiths and Anargyros Serafopoulos describe their work on simulated agent colonies within a specified virtual environment. 'Genes' define the characteristics of agents and during their lifetime they must learn to eat, mate, fight and signal. They also have the capacity to learn using a simple artificial neural network. The whole system is represented visually in a 3D real-time display. The approach was used to evolve emergent behaviour, such as strategies for eating based on the colour of food, and signalling to other agents based on energy level. In the latter case, neighbouring agents would gather round using the signal as an indication of mating potential!
The last section, entitled Heuristics - Outlooks, contains five papers on various aspects of evolutionary computation. Firstly, Olivier Roux, Cyril Fonlupt and Denis Robilliard use the ant colony paradigm to solve quadratic assignment problems, which involve finding the best assignment of a number of facilities to a number of locations at the minimum cost. This approach to finding solutions is based on the observation that, using very simple communication mechanisms involving pheromones, an ant group is able to co-operate to find the shortest path between two points. They concluded that this approach was more efficient when applied to the solution of quadratic assignment problems compared to the use of other techniques based on brute parallel computing power. In the second paper in this section, Meriema Belaidouni and Jin-Kao Hao proposed two factors to analyse Maximal Constraint Satisfaction Problem landscapes - the Hamming distance inside an iso-cost level, and the Hamming distance between levels. Next, Philippe Collard, Manuel Clergue, and Michael Defoin-Platel investigate the concept of synthetic neutrality for exploring search landscapes. This idea is based on the observation in biological evolution that different genotypes may have the same fitness, and as such movement from one to the other is by random mutations rather than due to selective pressure, analogous to a horizontal ridge on the fitness landscape. The approach allows genetic diversity to remain at local optima, thereby reducing the risk of premature convergence. In the fourth paper, Sana Ben Hamida, Alain Racine and Marc Schoenauer compared an EA approach with a genetic programming approach using parse trees to design the two-dimensional profile of an optical lens. Both approaches gave good results, but interestingly the GP was not so efficient as the EA at fine tuning the solutions it had found. Finally, Denis Robilliard and Cyril Fonlupt describe the use of an attractor-repellor strategy to guide evolutionary computation. In this method, information on the best and the worst individuals is kept at the end of each generation, and new individuals created either by adjusting alleles towards those of attractor genotypes or away from those of repellor genotypes. Mutations in this case are not blind as they are in biological evolution. Although it worked reasonably well for binary problems, there was no advantage in using the approach for non-binary problems.
It is clear that the papers presented all focus either on the mechanics and efficiency of evolutionary search techniques or on the use of these techniques to help find solutions to particular practical problems. Coming from a biological background, I was perhaps a little disappointed not to find some papers on the use of AE approaches to provide scientific insight into ecological or social processes. I found many of the papers interesting, and was keen to try out some of the approaches for myself, but the material covered in this book is fairly high-level and rather specialised, and is likely to be of interest mainly to those actively involved in the field of evolutionary computation.
Return to Contents
of this issue
© Copyright Journal of Artificial Societies and Social Simulation, 2002