Evolutionary VHDL code example
in [FPGA]
|
Prev: NIOS II + USB 2.0 host
Next: CPLD Jitter
From: apsolar on 18 Aug 2005 04:11 Hi Andrew 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. Ankit
From: Phil Tomson on 20 Aug 2005 15:43
In article <1124260721.732953.159600(a)g14g2000cwa.googlegroups.com>, <apsolar(a)rediffmail.com> wrote: >Hello everyone >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 >Hardware. >Ankit Parikh >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. Phil |