From: apsolar on 18 Aug 2005 04:11
I have read a lot of conference papers on Evolvable Hardware. They
always mention about the implementation but i couldn't find any
examples. So its like I have a vague idea about this but I need to see
it in reality to try something myself.
From: Phil Tomson on 20 Aug 2005 15:43
In article <1124260721.732953.159600(a)g14g2000cwa.googlegroups.com>,
>Does anyone where I can find a simple VHDl code example based on
>evolutionary algorithms.I am doing a project on evolvable hardware.
>This will help me get a start on the implementation of Evolvable
>Manukau Institute Of Technology
There are many different directions you can take this as it is still a
wide open field.
Even within the category of 'evolutionary algorithms' there are a lot of
sub-categories, two big ones would be:
1) Genetic algorithms (using reproduction (crossover), mutation
operators). If you were to take this kind of approach in hardware you
wuold probably just be implementing the GA algorithm in hardware. The
result would be a sort of GA accelerator (one could imagine it running
faster than on a generalpurpose CPU). However, you don't really end up
with 'evolvable hardware' going this route (where 'evolvable hardware'
would indicate that some structural changes have been made to the
hardware to increase it's fitness)
2) Genetic programming: Where the actual code is mutated and adapted
(traditionally Lisp has been used for this because the syntax is very
forgiving - neither VHDL nor Verilog seem very amenable, but the paper
mentioned here earilier
[http://www.ce.chalmers.se/~mekman/MasterThesis.pdf ] seems to do
something like this with within constraints imposed by the syntax of
VHDL. In that paper the investigator actually seems to be mixing and
matching candidate state machines from two sets of state machines to come
up with a chain of resulting FSMs that produces the desired behavior.
This 'evolution' does't actually take place on the target FPGA, but
instead candidates are 'evolved' and then simulated in ModelSim. Seems
like a valid approach, but also seems to be very tedious and the
resulting hardware is static (it's not going to be changing once the FPGA
has been programmed).
I wonder if perhaps a better approach would be adaptable hardware. This
would be very useful. Imagine things like planetary probes
(essentially robots) that need to adapt to various changes in their
environment because no operators are within several hours (by radio) able
to control them. So how could we have this adaptation (or learning) take
place inside the FPGA?
Here's a crazy, off-the-top-of-my-head idea:
One could imagine a state machine with many different
inputs (from the environment) and many different potential states and
resulting actions. If the FSM encountered a set of inputs for which it has
no resulting state perhaps a new state could be created in the machine,
it would be akin to the robot encountering a new situation and making a note
of it. But then what action should be taken when this new state is
encountered the first time (or in the future)?... well that's the part you
have to figure out. Maybe it iterates through some candidate actions
until it finds one that is deemed suitable for the situation and then
saves that one for future use... Or maybe it considers what actions are
performed in other similar states (a-priori defined states which resulted
from a similar set of inputs). So let's say we have inputs A,B and C. We've
got a next-state defined for inputs A=1, B=1, C=1, but nothing was defined for
when inputs A=1, B=1 and C=0 so we add a new state for that condition and
now we look at what actions are performed for the next closest state
(A=1,B=1,C=1) - eventually, if it is determined that the two are
equivilent then they can be collapsed into one single state (A=1, B=1,
C=*) - generalization?
In some ways the proposed system is
similar to a Classifier System, so you might want to study those.
You would probably want to use some sort of lookup-table based state
machine where the inputs are the address to your state table RAM. Oh,
and maybe you make it so that currently mapped actions can be modified in
the future. Also, instead of having one big state machine maybe it would
be best to have several smaller FSMs that can each contribute to
generating an answer.
Anyway, this quick brainstorm idea might be totally unworkable. As I said
the field is wide open right now. You need to
think of a lot of questions that you can use to create experiments.