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."

Aged...

This has been around a long while. I recall (sorry, no reference, somebody help me out here!) reading this about a long while ago in Science/Nature/SciAm.

Still, the technology's fascinating. Though I'm a little shocked that the latest articles still have no other examples (in detail, that bit about HAL doesn't count) than the two-tone recognition.

More detail (if memory serves): the FPGA outputs a logic LOW on a 100-Hz wave and a logic HIGH on a 1000-Hz wave. It is programmed by an evolved bit-sequence fed from a host PC computer. IIRC they started with random noise to wire the gates, so that's cool.

--Knots

Re:Aged...

Yes, this is old:

[1] Hugo de Garis. Evolvable Hardware: Principles and Practice. http://www.hip.atr.co.jp/~degaris/CACM-EHard.html (link is not available today)

[2] Adrian Thompson. Evolving Electronic Robot Controllers that Exploit Hardware Resources. CSRP 368 In: Advances in Artificial Life, Proceedings of the 3rd European Conference on Artificial Life (ECAL95) pp640-656. Springer-Verlag Lecture Notes in Artificial Intelligence number 929, 1995.

[3] Adrian Thompson. Evolving Fault Tolerant Systems. CSRP 385. In: Proceedings of The First IEE/IEEE International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications (GALESIA'95), pp524-520, IEE Conference Publication No. 414, 1995.

[4] Adrian Thompson. Silicon Evolution. In: Proceedings of Genetic Programming 1996 (GP96), J.R. Koza et al. (Eds), pages 444-452, MIT Press 1996.

[5] Adrian Thompson. Through the Labyrinth Evolution Finds a Way: A Silicon Ridge. Inman Harvey and Adrian Thompson. In: Proceedings of The First International Conference on Evolvable Systems: from Biology to Hardware (ICES96). Higuchi, T. and Iwata, M. (eds.), 406-422, Springer Verlag LNCS 1259, 1997.

[6] Adrian Thompson. An evolved circuit, intrinsic in silicon, entwined with physics. In: Proceedings of The First International Conference on Evolvable Systems: from Biology to Hardware (ICES96). Higuchi, T. and Iwata, M. (eds.), 390-405, Springer Verlag LNCS 1259, 1997.

[7] Adrian Thompson. Artificial Evolution in the Physical World. In: Evolutionary Robotics: From Intelligent Robots to Artificial Life (ER'97), T. Gomi (Ed.), pages 101-125. AAI Books, 1997.

[8] Adrian Thompson. On the Automatic Design of Robust Electronics Through Artificial Evolution. In: Proc. 2nd Int. Conf. on Evolvable Systems: From biology to hardware (ICES98), M. Sipper, D. Mange & A. Pe'res-Uribe (Eds.), pp13-24, Springer-Verlag,1998.

Very simple...

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!!!!)

Genetic Algorithms are not new

Genetic Algorithms, and the subset of the field called Genetic Programming has been around for a while, and there is some really amazing stuff out there. For example, Tierra [talkorigins.org] is an artificial ecosystem in which computer programs evolve and compete with each-other, it has been around for over 10 years.

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.

Re:Genetic Algorithms are not new

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.

They are good for optimizing functions of very many variables. Like, for instance, the weights for a spam-scoring system, to maximize the score over a sample of junk mails, and minimize it on a sample of not spam mails.

IE, you have a rule that matchs the word "viagra" and a rule that matches the word "money" in a subject, obviously the first one should count more (unless you talk about viagra a lot in your emails), but how much? Imagine you have 100s of rules you came up with, a GA can optimize the weights of each rule, if you have a good selection of emails to let it evolve over.

Cool study using genetic algorithms

There's a very cool application of genetic algorithms that I saw a few years back. Danny Hillis was trying to evolve sorting networks, a way of representing a sorting algorithm for a fixed number of inputs. (See volume 3 of Knuth, The Art of Computer Programming). He wanted to do it using genetic algorithms, on 16-input sorting networks. The best known one at the time used 60 comparison/swaps to sort 16 inputs.

The problem is, in order to measure the "fitness" of a sorting network, you should give it all possible sets of numbers and see how many it sorts correctly (you also give a fitness bonus to smaller networks). It turns out you just need to give it all possible sets of 0's and 1's to see if it will sort any set of numbers correctly, so Hills would have to test each network on 65,536 inputs to see how well it did.

That would take too long, so he wanted to only test the networks on a subset of possible inputs. The clever thing was he made the particular subset used also evolve, as a kind of "parasite" on the sorting networks. The parasites were "rewarded" (had higher fitness) when they broke sorting networks. That way, the system would keep around precisely those test cases which could break the current population of sorting networks, so it was always focusing the testing exactly on the trouble cases, and ignoring the ones "known" to work, and thus saving a ton of time/effort.

Hillis evolved a sorting network which used 61 comparison-swaps, just 1 away from the best man-made one known. I was at Thinking Machines (Hillis' company) for a while, and fiddled around with this myself a bit, thinking that a bit more simulation must beat the record, but I never did beat it.

Hillis had a paper, called "Co-Evolving Parasites Improve Simulated Evolution as an Optimization Procedure", published in Artificial Life II (Langton et al, editors), Addison Wesley, 1991, pages 313-324. A note in my database indicates it may also have been published in the journal Physica D, vol. 42, p. 228-234.

A search also just turned up Hugues Juille [brandeis.edu], who has apparently done some more work in this area. [brandeis.edu] He evolved a 60 comparison sorting network for 16 inputs, tying the record. And he broke a (25-year-old) record for 13-input sorting networks, doing it in 45 comparison/swaps.

Exciting times ahead for 'AI'

Thompson's chip was doing its work preternaturally well. But how? Out of 100 logic cells he had assigned to the task, only a third seemed to be critical to the circuit's work.

Isn't this how a regular brain works? Or, at least close. I recall being taught something called the 80/20 rule, that applies to almost anything and everything. Doesn't 20% of the brain do 80% of the work?

This article is pretty interesting though. I'm not sure how much is true (newsobserver is hardly the New Scientist) but these devices look like they could be the way of the future.

Some people will argue that it's merely a computer program running in these chips and that 'real' creatures are actually 'conscious'. How do we know that? How do we know that the mere task of processing is not 'consciousness'?

On the other side, how do we know that animals are self-aware? When I watch ants, I could just as easily be watching SimAnt, for all the intelligence they seem to have. A computer could do pretty much everything as spontaneously and as accurately as an ant could.

I think as the years pass by, we'll see chips pushing the envelope. Soon we'll have chips that can act in *exactly* the same way as a cat or dog brain. Then what will be the different between the 'consciousness' of that chip and the consciousness of an average dog? I say, none.

I don't like to call this Artificial Intelligence. It's real intelligence. Who knows that some sort of 'god' didn't just program us using their own form of electronics based on carbon rather than silicon?

One day we'll reach human level. I can't wait.

playing god

Although this is far from creating life, it makes you wonder if our existence is also "unexplainable" even by _the_creator_ (if you believe in such a thing.

Imagine if you advance this technology to the point where you can dump a bunch o fthsi stuff on a planet and wait a few millions to come back and see what happens....

Re:Curveball way out to left field

Evolution could very well be the correct term, at a light speed rate of course. Could this be the first step into determining or simulating where the source of life came from, or could this lead to the destruction of it? (insert your favorite Sci-Fi scenario here)

Is it just me, or does this pseudo-scientific babble actually make any sense to anyone?

Stability

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?

tripe! tripe!

It is quite arguable that current hardware implementations aren't the fastest way to solve most problems (we currently eliminate complex behaviours and only using predictable gate structures), since routing is known to be an NPC problem alone, making the problem of routing and calculating other variables at least NPC. Eliminating variables makes it easy to pick a solution that is known to work, but it will not necessarily determine the optimum design.

It is, in fact "some bizarre magic," so to speak, not because we do not understand it, but because it requires considerable algorithmic search to find such an efficient (quick, small and effective) state through which the machine can produce its effect - its magic in the same sense that a chess playing program is magic.

The insight that you fail to grasp is that with this technique, we can take advantage of those variables that you say we should eliminate, making designs better. This allows for the possibility of a much wider range of functionality for chips than we currently have for them.

As far as complexity, what kind of bacteria are you thinking of that its so far from? The techniques used in neural networks are almost all taken straight from biology. The major simplification is a lack of frequency encoding. That's pretty much it; everything else works pretty much the same. Perhaps you're under the impression that the "evolution" of bacteria changes their basic behavior. This is extremely seldom - usually changes in bacteria are no more drastic that the cosmetic changes that occur in a "mutating" FPGA design.

So...at least we can have the complexity of bacteria to do the work of genius hardware designers using search techniques to produce better designs.

One thing further, though: if nature is any indication, it is extremely different to increase the level of complexity of an organism (or in this case, of a network). I would agree that "intelligent" machines that make you into toast are a long way off because we can't make evolving machines - only learning ones, even if they do use genetic algorithms to do it (which is essentially what viruses and bacteria do regularly, I might add).

Old and misinterpreted

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.

Don't get too scared... but they are damn cool.

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 [up.edu], 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. [pointofnoreturn.org]

Not exactly practical...

I found the paper [susx.ac.uk] 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.

Busting the underlying operational model

The major point is that the conventional digital cuircuit logic is based on a certain ideal model.

Some of the assumptions of this model are:

1. we have two states 0 and 1
2. states evolve over time controlled by a regular clock signal
3. signals propagate by conventional electric current (moving electrons)

But guess what, a typical phyiscal device implements only an approximation of this model.

For example we say a certain voltage range is interpreted as a logical 0, a certain different higher volatage range is interpreted as a logical 1.

But the evolutionary algorithm was not constrained in any fashion to make use of this ideal digital model only. It can and will make use of the full available degrees of freedom the physical system, that the fpga device is, offers.

With the result that there might evolve analog cuircuits (which use more than 0 or 1 values), or that we might have electro-magnetic signal transport (Thompson reported some spiral structures which might work as electro-magnetic wave guides), yes it might even employ some quantum mechanical effect that could explained by advanced semiconductor physics only.

One might say that the approximation process that the evolution algorithm is, has started in the domain of digital devices and converged out of that domain into the wider domain of physical devices.

This has a couple of draw backs:

• the resulting design is harder to understand
• individual fgpa chips vary slightly, which is no problem in a digital world, where ranges in the specification allow for slight variations among individual chips, but the resulting evolutionary design migh work only with certain chips, because it has much narrower tolerances than the production spec takes into account

I wonder what would have been happend if the algoritm had a control step after each evolution step which ensured that the next generation design would operate strictly under the assumptions of a conventional digital device model, in that case the evolution process should evolve towards a classical design. Would it have been stil something that is hard to understand?

Perhaps in that case it is easier to stick to software simulation of the design.

Applications

I read an article in Der Spiegel (paper version; I doubt it's archived) about a problem the Royal Air Force was having with their flight simulator: the AI that flew the enemy dogfighting planes was too predictable to challenge the best pilots. They hired the people who made the Norns game to evolve a more challenging AI flight script.

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.

Resources on Evolutionary Computing

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 [alife.org] or the U.S. Navy's GA Archive [navy.mil].

Shameless plug: For five years, I've been developing a free (no ads) web site, Complexity Central [coyotegulch.com], 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 [coyotegulch.com] web site, which contains lots of articles, web links, bibliographies, and free code in C++, Java, and Fortran(!).