Real World Evolutionary Computing
A range of computational techniques and methods are currently available which, to a lesser or greater degree, are based on some aspect of evolution from the natural world. Computer scientists with little, or no, knowledge of the real world phenomena that they are trying to model have developed these techniques. There have been many success stories but this area has a proliferation of approaches, many of which have to be customised for a given problem type. Many researchers have their own favourite techniques which they use, no matter what problem they are trying to solve. In addition, many biologists have also devised evolutionary programs, but they have tended to use very simple programming languages and very simple concepts (e.g. Dawkins' biomorphs). There is a challenge for the computer science community to develop evolutionary computing so that it really does mimic the real world. The aim is to capture the real essence of evolution so that we can solve ever more complex and sophisticated problems.
Whilst most evolutionary computation has a link with Darwinism, many of the techniques used today have diverged from these ideals. For example:
Ant Algorithms are based on the way ants forage for food. When implemented as an algorithm by computer scientists, it models the idea of a pheromone trail that the ants follow with some probability. In addition, the ants use a heuristic to determine which route to follow. Ant algorithms are flawed in that ants are practically blind and, although they can sense pheromone, they cannot see how far it is to the next location. If ant algorithms are to truly mimic the real world we need more knowledge from biologists so that an algorithm utilising the true potential of ants (and other creatures such as termites and bees) can be realised.
Case Based Reasoning is based on the idea that we can remember past experiences and use those as a starting point for new problems. This is implemented by storing previous solutions and then retrieving the “closest” solution for a new problem, using some similarity measure. This idea is flawed for a number of reasons. At the present time we really have no idea as to how we use past experiences to solve new instances of problems. Therefore, any implementation cannot claim to solve a problem in the same way that a human does. Also, CBR uses a similarity measure to retrieve old solutions from the case base and much CBR research considers how good similarity measures can be defined. Yet, we have little, or no idea, as to how we retrieve information from our brain, so how can we reliably implement a CBR system that we claim is based on the way we use past experiences?
Evolutionary Strategies are based on the hypothesis that, in the real world, small mutations are made more often than large mutations. The claim is that this mimics the evolutionary process. However, typically, ES’s only use mutation and not crossover. Therefore, there is no concept of passing on genetic material from two parents from one generation to another.
Genetic Algorithms mimic Darwin’s principles of natural evolution by modelling a chromosome and then applying crossover and mutation. In the earliest GA’s, the chromosome was represented as a bit string, although this practise has gradually changed over the last 30 years. The problem with GA’s, from an evolutionary point of view, is that they do not model the biological chromosome. For example, genetic material is not represented as a bit string. Also, it is known that there is redundancy built into a human chromosome, which is not modelled in GA’s.
Genetic Programming is an evolutionary process that also uses crossover and mutation. However, instead of using a chromosome representation, GP uses a tree based structure with the aim being to evolve computer programs. The same criticisms can be levelled at GP as at GA with the added criticism that there is no real world evolutionary process that aims to evolve a set of instructions that can be executed by a computer.
Island Models are an attempt (typically in a GA environment) to mimic the real world phenomena of there being islands of species (typically on different continents) which evolve independently of each other. Only when certain conditions are met (the continental plates collide, birds manage to fly from one continent etc.) do the species within different islands manage to exchange genetic material. The island model is typically implemented so that an exchange of genetic material is carried out at pre-set times (e.g. after a given number of iterations, when a species has stagnated etc.). This does not model the real world, in that the real process is a lot more stochastic than this and there are many more environmental factors to consider.
If we can achieve evolutionary computation that truly mimics the natural world then the potential impacts are enormous. At the present time, evolutionary computation is little more than an abstraction of what occurs in the world around us. If we can capture just a small part of those processes and harness it in a way that can solve real-world, large-scale problems then we could be on the verge of narrowing the gap between computer science and the natural science.