Genetic Algorithms
The very basics.....
COMPUTING TURNS TO NATURE
How Darwin has influenced Artificial Intelligence.
Talapala Prashanth Naidu.
Mention Artificial Intelligence (AI) and one instantly conjures up
images of high-tech computers; state-of-the-art robotics and machines
thinking for themselves. However, a new approach in AI is providing a
totally different image inspired by the 19th Century scientist who
studied wildlife on the Galapagos Islands.
Genetic Algorithms (GAs) are a relatively new development in the AI
world, following the ideas of natural selection put forward by Darwin
from his observations of nature. Proposed in Professor John Holland's
1975 book "Adaptation in Natural and Artificial Systems", the GA
utilises a radically different method of finding good answers to
problems with a number of possible solutions. These problems are not
just hypothetical situations created by academics, but can include
everyday activities such as timetabling lessons in a school or working
out how best to stack beer on a delivery truck.
So how can computing techniques in 1994 have any relevance to
evolution, zoologists' theories and beer delivery? The answer is
nature's law of 'survival of the fittest' and the methods used by
living creatures to pass on their characteristics through breeding.
For example, a short-sighted zebra is far less able to see a cheetah
than a zebra with 20/20 vision, and it will quickly be killed. The
offspring of zebra with good eyesight which have passed that feature on
through the chromosome structures of their DNA will be more likely to
survive than the short-sighted offspring of zebra with poor eyesight.
It is this principle of passing on useful features from one generation
to the next that is followed by GAs.
The GA creates an 'individual' - in reality a code representing one
possible answer to the problem being tackled. Many 'individuals' are
randomly generated, until a 'population' of possible answers to the
problem exists. Some of these answers will obviously be better than
others, so each answer is given a 'fitness' - some measure of how well
it performs at solving the problem. In a simple example, a brewery
delivery truck with its first delivery of beer packed furthest from the
tailgate is a possible, but not very good, way of delivering beer. A
better way might be to pack the beer with the first delivery closest.
Having assigned a fitness value to each individual in the population of
possible answers, the GA then follows the processes of evolution.
Reproduction takes place, by selecting two solutions, exchanging some
of the coded information from which they are made (as parents' X and Y
chromosomes are exchanged in nature) and creating two new possible
solutions ('individuals'). This process of generating 'children' from
'parents' continues until a new population has been created. Because
the GA takes into account the fitness of the parents when selecting
them for breeding, members of the new generation should be considerably
fitter than their parents.
This is indeed what happens, and as this generational cycle is
repeated, solutions become increasingly better with time. So what do
GAs mean for you and I? The GA is already translating into tangible
advantages for both companies and the man on the street. They have
been successfully applied by the FBI to produce composite images of
suspects from witness evidence; by telecommunications companies to
design more robust communications networks and by airlines to save
thousands of pounds in hotel bills, by minimising pilot and cabin crew
stopovers.
By looking back to nature (which has been evolving for millions of
years), Artificial Intelligence researchers can now apply this powerful
technique to everyday problems, making use of the phenomenal speeds
available from modern computers. As a new and active field of
research, Genetic Algorithms have only recently begun to make a serious
impression on the financially minded business community. However, when
applied appropriately, the principles that have led to the advancement
of so many species for so many millions of years can provide huge
benefits. It may also serve to remind us that perhaps nature really
does know better after all?Other Places to go:
