Slashdot Mirror
Evolutionary Computing Via FPGAs
fm6 writes "There's this computer scientist named Adrian Thompson who's into what he calls "soft computing". He takes FPGAs and programs them to "evolve", Darwin-style. The chip modifies its own logic randomly. Changes that improve the chips ability to do some task are kept, others are discarded. He's actually succeeded in producing a chip that recognized a tone. The scary part: Thompson cannot explain exactly how the chip works! Article here."
The chip modifies its own logic randomly.
This sounds suspiciously like my lovely wife.
The scary part: Thompson cannot explain exactly how the chip works!
I knew it. Male engineer, female chips. Easy explanation.
Soko
(Posting from the basement so said lovely wife doesn't tear of my baaa-aa-allsssss.... YOWWWUUCH!!!!)
"Depression is merely anger without enthusiasm." - Anonymous
The curious thing is that despite GAs being widely researched for over 20 years, they seem to have found few practical applications that I am aware of. It is tempting to blame this on lack of computing power, but I am not sure that is the real reason. Either way, the possibility of automated design is very exciting indeed and I hope more people find ways to apply it in the real world.
Does the circuit still work properly if the temperature increases by 10 C? What if the FPGA data file is loaded into an FPGA from a different vendor or an FPGA fabbed on a newer process?
Mea navis aericumbens anguillis abundat
I have the Discover magazine this guy was on the cover of. I believe it was July of 1998 or so. It was very cool then, it's still very cool, but it's old and I don't know why it was submitted.
Additionally, the submitter severely misinterpreted what Thompson's system does. He has the FPGA programmer connected via serial or parallel (I'm not sure), and he runs a genetic algorithm on his computer, the fitness function (the component of a GA which evaluates offspring) loads each offspring's genome (each genome in this case codes for different gate settings on the FPGA) into the FPGA, and separate data acquisition equipment supplies input to the FPGA, and checks the output, and based on that supplies a fitness value, which the GA uses to breed and kill off children for subsequent generations.
He has *NOT* implemented a GA inside a 1998 era FPGA (120000 gates max or so at the time on a Xilinx, which is what he was using) when he had a perfectly good freaking general purpose computer sitting right next to it.
One thing people should consider is that while Genetic Algorithms are neat, they are limited.
Here's the fundamental decoder-based GA:
* Take an array of N identically long bits.
* Write a function, called the fitness function, that considers a single element in the array as a solution to your problem, and rates how good that solution is as a floating point number. Rate every bit string in the population of N.
* Take the M strings with the highest ratings. Create N-M new strings by randomly picking two or more parent strings, randmoly picking a spot or two in them, and combining the two parts of them.
* Rinse and repeat until the entire population is identical.
Their main limitation is that they take a lot of memory. Take the number of bits in a genome, multiply by population size, and your processing time grows exponentially with both population size and parent genome grouping. The other problem is that they require that the problem have a quantifiable form of measurement - how do you rate an AI as a single number?
The other problem is commonly called the "superman" problem - what happens if you get a gene by chance very early in your generations that rates very very high, but isn't perfect. Imagine a human walking out of apes, albeit with only one arm. It'll dominate the population. GAs do not guarantee an optimal solution. For some problems, this isn't a problem, or it can be avoided, or reduced to a very small probability. For others, this is unacceptable.
That said, you can do some neat shit with them. This screenshot is from a project I did during undergraduate studies at UP, geared towards an RTS style of game, automatically generating waypoints between a start and end position. I'll probably clean it up sometime, add a little guy actually walking around the landscape, stick it in my portfolio. Yay, OpenGL eye candy.
I found the paper on this project, and I found a few things disturbing. First of all, there was no clock: the circuit was completely asynchronous. In other words, the only timing reference they had was the timing of the FPGA itself. Trying to do something like this in silicon is difficult, and doing it in an FPGA is just plain insane. Delays in a circuit vary with just about everything: power supply voltage (and noise), temperature, different chips, the current state of the circuit, and so on. While you might be able to deal with these problems in a custom chip, an FPGA was never designed to be stable in these respects. Also mentioned is that there are several cells in the circuit that appear to have no real use, but when removed, the circuit ceases to operate. As they mention, this could be because of electromagnetic coupling or coupling through the power supplies. Again, I would never want to see something like that in one of my chips.
Another thing that bothers me, how the heck does he know which cells are being used? Last time I checked, the bitstream (programming) files for these chips is extremely proprietary, and nobody (except XILINX) has the formats for these files. I really want to know how they know how this thing is wired.
Now I should mention, this is pretty cool from an academic standpoint, and it would be interesting if they could produce something that is both stable and useful using these techniques. It's also pretty cool that they could get this to work at all.
Interestingly, if I remember right, it was all machine code, ultimately a series of conditionals about what stick movements to do as a response to certain patterns of instrument readings. They started the evolution by "rewarding" the code which just kept the plane in the air the longest... which, at first, was like 5 seconds. Within a few days of cranking, the code could achieve level flight with ease, and a few weeks later, with more added parameters, it was dogfighting mutated versions of itself. Then they brought in real RAF pilots and the thing just kept learning.
If I remember right, the article ended by saying that by now the AI, which runs totally incomprehensible code, wins most of the dogfights against human pilots, and uses some very interesting maneuvers which it wasn't taught (it wasn't taught anything). The RAF is impressed, and are thinking about a class of dogfighting planes that fly on AI. These things wouldn't mind doing turns at over 10 G's. My guess is that I've read this three or four years ago. Maybe the subsequent developments of the program got classified or maybe it just fizzled, but it sure seems like a promising avenue of research.
Being who I am, I don't get thrilled about the prospects of fancy new AI killing machines, but on the other hand, I want these designs to penetrate video game AI soon! For example I now play Civ3, which has pretty good, but not great AI. What would prevent developers from taking that AI, defining a "mutation function" by which certain parameters in it can change randomly, and then play different mutations against each other millions of times on a supercomputer? Or, even better, outsource the whole number-crunching part to a project like seti@home, where our machines do the crunching. Can you imagine an AI war between the best routines from Team Slashdot and Team Anand? Sure it's frivolous, but waay more fun to watch than brute force encryption cracking.
I've been evolving algorithms for a long time now, using finite state machines (FSM) which can be easily moved across architectures and programming languages. Quite often, an FSM evolves to exhibit surprising behavior -- and given the complexity of the machines, it is impractical to understand why the FSM acts as it does.
Note that I said "impractical" -- given time, I could follow the FSM's logic and discern it's "thinking" (and I have done so with simpler machines).
If you want real, concrete information about genetic algorithms and artificial life, I suggest visiting ALife.org or the U.S. Navy's GA Archive.
Shameless plug: For five years, I've been developing a free (no ads) web site, Complexity Central, devoted to evolutionary algorithms, artificial life, and emergent behavior. I've posted several Java applets that demonstrate genetic algorithms, cellular automata, flocking behavior, and related subjects.
This is part of my Coyote Gulch web site, which contains lots of articles, web links, bibliographies, and free code in C++, Java, and Fortran(!).
All about me