DIFFERENT
BITS
ARTIFICIAL LIFE:
PART 2 – GENETIC ALGORITHMS:
HELLO WORLD
Last time, we talked about the theory behind genetic algorithms and looked at
an abstract example of how they work. In this month’s article, we will implement
a simple example on the PIC to understand the details and difficulties of doing
this kind of programming on such a limited processor.
Like many of the topics we have
covered in this column, the
circuits are simple but the code is
fairly advanced, so you should tackle
this project with a good amount of
microcontroller programming (and
more specifically troubleshooting)
under your belt. This article will build
upon the ideas and the basic algorithm
discussed in March, so if genetic
algorithms are new territory for you,
it would be wise to read that article
before jumping into this project.
I recently decided to test drive
Microchip’s C18 C language compiler
for 18 series PICs. The software is free
to try for 60 days and is available on
the development tools section of their
website. I determined that this project
would be a good assessment of the
environment, so all of the code you will
SIDE NOTE
Microchip C18 compiler is freely
available to try from their website. Look
for the “Student Edition” download:
www.microchip.com/stellent/idcplg?Id
cService=SS_GET_PAGE&nodeId=1406&
dDocName=en010014&part=SW006011.
68 SERVO 05.2008
see here is written for the C18 compiler. I
will say, it is not the most user-friendly
coding environment to work in, and it
is not intuitively documented at all,
but with a little leg work it is a nice
transition for the intermediate coder
looking to move beyond assembly.
The commands and libraries directly
stem from the processor architecture
making it a very transparent coding
experience if you are already well
acquainted with the PIC framework.
To refresh your memory, genetic
algorithms abstract the natural
process of evolution to solve difficult
computational problems by evolving
populations of possible solutions. They
simulate aspects of the biology behind
evolution, and are interesting as
implementations of life as it could be
(in the words of Christopher Langton).
In this article, we will focus on the
computational aspects and
pragmatics of implementation on a
microcontroller. Next time, we will
delve into what I consider to be the
beauty of the algorithm by looking
at how it can simulate a biological
system, and we will also explore interactive applications of the technique.
Search Space
If you look at any computational
problem, the collection of all the
possible answers to that problem
comprise what is known as the search
space. For example, the classic
traveling salesman needs to visit a
set of cities around the country and
doesn’t want to visit any city twice.
The list of every possible sequence of
cities to visit that meet the specifications would comprise the search
space. In another example, an artificial
chess player would describe the list of
all possible moves they can make during
a game as a search space. The term is
important because the larger the
search space is, the more difficult it
becomes to use brute force, or classic
heuristic techniques to find an answer.
To give you an idea, imagine the
traveling salesman has to visit 30 cities.
The number of possible routes he could
take is equal to 30! or 2.65 1032.
Add one more city to the mix and the
number of possible solutions increases
exponentially to 8. 22 1033 in what
is called a combinatorial explosion.
Meanwhile, the chess player is even
