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."
"I'm sorry, Dave. I can't do that."
Scary, him not being able to explain exactly how the thing works. Still, any good creation is ultimately the creation of madness.
The next Slashdot story will be ready soon, but subscribers can beat the rush and slashdot the links early!
This is obviously a duplicate from a while back
please do your homework
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
Anarchy$ dd if=/dev/random of=~/.signature bs=120 count=1
This has the sounds of something strait out of a movie. Teminator anyone?
This begs the question "Can evolving machines be controlled?"
It's possible that any machine able of changing its logic could change logic that says "DON'T do this..." if it thinks it is an improvement to itself.
-Bryan
I think that in the future, we will have more and more things like this happening. Our machines will create themselves, and they will be so complex that we will have no idea how they work. And eventually, they will decide they don't need us and exterminate the whole human species. Wow. I sure hope that doesn't happen!
Dudes, I have something really important to tell you guys. I'm NOT trying to sound like a troll, so PLEASE don't take me as one. Just listen to what I have to say. This morning while I was eating breakfast and watching TV, I had a vision. I normally don't have visions and I'm not crazy, okay. In this vision I saw three red lights swirling around. They were like forming a circle as they swirled faster and faster. Then the lights moved closer together and formed a single light that turned blue. I noticed the light was the bottom of a spaceship. The blue light moved down like it was landing and I saw trees and a grass field. Then the spaceship started talking to me...like, the people inside the spaceship were talking to me even though I couldn't see them, only the ship I could see. I didn't really understand what they were saying. It sounded like whispers and jibberish. Then, all of a sudden, I woke up from the vision and was sitting at my kitchen table again. I don't understand what happened. I'm am absolutely serious about this. Can somebody help me understand what happened? PLEASE?
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.
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.
mogorific carpentry experiments
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....
I'm too lazy to look it up, but this a duplicate from some time ago. You'd think the editors would be able to detect duplicates better than a semi-regular reader, especially since they're getting paid to do it.
Anybody know where I can buy an EMP gun in case these machines decide to try to make batteries out of me?
From their story, I got the idea that it would be hard to use the identical method to design circuits for mass production, because the designs that evolve may be dependent on any slight imperfections and/or departures from published specs of the components that are wired together in the model as it evolves. They built a second copy with parts out of the same stockroom, and it didn't work.
Nor are FPGAs. Transputers and other self-modifying pieces of computing equipment are pretty nifty boxen, but until these stories end with descriptions of tools that indicate to scientists exactly *how* their toys are doing these amazing feats, they will not be useful for general consumption.
For example, if the transputer this guy was using generated FPGAs, which were then automatically translated into some forth dialect, then his new processors could be refactored into other, more von Neuman like equipment more easily.
A few months ago when I was first designing my stockbot, I faced simmilar problems trying to work with neural networks and other correlation engines. The process time was slow, and the strategies they used were not easily portable. In the end I went with a stack-based language and randomly generated code that examines historical prices. It has worked out a LOT better in the long run.
"Look at me, I invented the stove!" -- Ben Franklin
While reading this article, I continually asked myself the question: if we eventually use these genetic algorithms to create software and possibly an AI, could this AI be the best at doing its job if it simply appears to do exactly as we want it to do, but then turn on us because it simply hides its true intellence? Think about the Matrix. If we have computers evolve themselves, what better way to be the "fittest" than to appear to do as the humans wanted you to do until you became smart enough by running an internal genetic algorithm to take over and become the dominate species? When creating these genetic algorithms, we must be very careful to be sure that there is not a background task running, for it is quite possible that one exists in a more complex genetic-algorithm-created program than those created thus far, and having no clue how the program works is not a step in the right direction.
Starbridge Systems popped up a few years ago (they might have been mentioned on /. even). At the time the things they claimed to do and their client list made them seem like yet another hoax (a la Linux on the N64). The prices they had on their web site at that time didnt help. I mean, who would buy a 94 million dollar (if I remember right) computer... even if you had a "black" budget?! But they didn't go away, and as I bounced around to jobs with big budgets, I heard rumblings and grumblings about this group or that department and Starbridge.
/. interview?
Now, with the mention in this article (even though it's dated in 4/01) maybe its time for an (in)famous
I could be off my rocker, but a SWAG that occured to me could be that he may have stumbled upon a Natural Law (ie. 'gravity' or 'no two forms of matter can occupy the same space at any given time') that has always been in existence and has manifested itself in this. 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)
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
This experiment happened a hell of a long time ago - it was even mentioned in The Science of Discworld, which IIRC came out in 1999.
Old news... IIRC:
1. This will not lead to intelligent machines that will try to make you into toast. This is not even close to the sort of complexity of evolving bacteria.
2. The reason he doesn't understand how it's working is because the design is using the interference generated in one part of the chip someplace else. Conventional designs try to eliminate this because it's so complex to predect. This is not a matter of "some bizarre magic is happenning that we don't understand and it will probably turn us all into pools of gravy."
The Skynet Funding Bill is passed. The system goes on-line August 4th, 1997. Human decisions are removed from strategic defense. Skynet begins to learn at a geometric rate. It becomes self-aware at 2:14 a.m. Eastern time, August 29th.
'Nuff said.
SIGFEH
Computers are getting smarter while Humans are getting dumber (or is it just me?).
PRAISE ALMIGHTY CELERON 600 WORKSTATION UNDER MY DESK, I AM NOT WORTHY.
was done at Brandeis University. There they developed robots through an evolutionary process and a rapid prototyping machine. It was called the "GOLEM" project. The site seems to be broken, but this is the google cache.
Remember, there were no nuclear weapons before women were allowed to vote.
This kind of experiment would be a relatively easy to implement on a Beowulf cluster by simulating one or more chips on every node.
Discover magazine, June 1998 issue. "The darwin chip" need i say more? http://208.245.156.153/archive/outputgo.cfm?ID=145 5 for all the lazy people out there. I have the magazine and some pictures on my site.
small :
http://safemode.homeip.net/small_fpga.jpg
large :
http://safemode.homeip.net/large_fpga.jpg
This appeared in "The Science of Diskworld" by Pratchett, Stewart and Cohen at the end of chapter 26, pages 193-197(First edition, hardcover). I'm suprised it took so long to appear here, as it was published in 1999.
If you havn't read it, do so. It summarises Life, the Universe, and Everything as well as any other book could hope to do without requiring special lifting equipment.
More information on Terry pratchett, and this book, can be found at http://www.lspace.org
Cheers, glen
astfgl@iamnota.org
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 thought this was really cool when the first story was presented on slashdot several years ago. Since then I've been waiting for a SlashBack with more info of recent developments. Oh Well... The article seems to describe the exact same system (although in less detail).
In addition to having untreated hemorrhoids for over two months now, my stool has been an almost black color with a greenish hue and has the viscous consistency of thick mud. It takes a heavy amount of wiping to remove the feces from my anus, and I sometimes have to return to the bathroom to wipe again after I notice a crusty feeling in my butt crack.
Also, I leave skidmarks on the toilet seat behind my butt crack, and I sometimes have to wipe my ass after I pee, since I let out a greasy fart that leaves a stain inside my butt crack.
Help!
This is not significant work. As several people have already mentioned, this is old news. More importantly, this is just one more application of GA's - this time implementing them with hardware.
Every time a significant advancement is made (in this case GA's) there are a hoarde of me toos that write a million and one papers on "yet another application" of the new technique, without any advancement of the underlying science. It happened with neural nets and it is happening with GA's (among others).
I saw this guy present his results at a conference and I was not impressed. Not only does this not contribute to the underlying science, but the generated design was weak at best. The reason he did not understand why the design worked was not because it was complicated (we are talking logic gates after all), but because it was implemented incorrectly - some of the gate inputs were left floating. Tell me that that makes for a stable system.
We don't know how our brain works, how ants brains work.. and most importantly how LIFE works.
this sort of development poses serious philisophical questions, that I don't think our society *can* answer.
What is life? We really don't know. Some say its some form of inteligence... so are these chips intelligence? yes.. but are they life?
We really don't know, and quite frankly, we'll never know.
Every explanation leads into a cycle of questions.
This technology is great, however we don't know how it will be implimented, nor do we know IF it will be implimented. If it ever got advanced enough, we would see INTENSE legislation being thrown back and forth. Chances are, the democratic world will destroy the technology if it is dangerous.
The problem could be others. The others. The other people from some unkown country, pissed off at the world, with their hands on this technology, ready to start another war.
Interesting.
------------
Sase
"It's the opposite of that."
we will have chips that will evolve and reprogram themselves so they will increase in effeciently and speed.
On the otherhand we have the ability to put chips into humans for tracking medical info and possibly control the populous.
I am not worried about the future. I am worried about today.
-THIS SPACE FOR RENT!
OK, how seriously can I take this article if the author makes statements like this:
.3 was not 1/10th of 1. Maybe "huge" orders of magnitude work differently... And if NASA buys "a HAL hypercomputer from Star Bridge Systems", then their claim that it "is no larger than a regular desktop machine, yet it's roughly 1,000 times faster than traditional commercial systems" has to be true, too.
"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. In other words, the circuit was more efficient by a huge order of magnitude than a similar circuit designed by humans using known principles."
Last I checked, orders of magnitude were powers of 10, and
I'm excited about this technology, I hope it gets faster, but this kind of coverage isn't what it needs. And I thought that Linux had bad advocates...
"Space Exploration is not endless circles in low earth orbit." -Buzz Aldrin
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.
Several people, including James Foster at the University of Idaho have been doing this kind of thing for a while. He got some really interesting results, including circuits evolved to take advantage of quantum effects and highly temperature dependant circuits. Actually, the gist of his work is that there are some severe limitations to this approach. There are references for papers on his web page.
These FPGA's sound pretty interesting, where do you get them? Could one build a useful, interesting homebrew computer with them? Thanks,
David
Any AI with a FPGA starts with a limited number of inputs:
x inputs with values 0 or 1 (or neither) == 2^x (++) possibles.
Any AI with a FPGA ends with a limited number of outputs:
y outputs with values 0 or 1 (or unknown) == 2^y (++) possibles
Inputs-to-Outputs are linked (joined, coupled, etc) by the logic between them (a 'black-box' so-to-speak). An 'evolve' can never happen without linking output to input (feedback).
So, all AI inputs/outputs are constrained by their outputs and their sampling periods.
So for some boxes, an input of (properly encoded)"what is the meaning of the universe?" will return "43". After tuning, these boxes may produce "4f*@#%(#@" or perhaps "forth", "For Linux", "forsooth, BG", "for you use..." or "for more useless answers, call your ISP, then ask BG; if in doubt, ask your mother".
This box apparently returned a tone.
Hmmm...
In the christmas/new year tradition...
this is true intelligence.
Evolving hardware is nothing new. earlier it was done in software infact there's a whole book on VLSI design using genetic algoriths (sorry don't remember the author)> Work on reconfigurable hardware has been going on for a long time now. here's one reference: http://www.work/research/nichol2full.html
It is funny you should mention this, because a few years ago I wrote a simple piece of software which attempted to evolve a regular expression (actually, it was a subset of the standard R.E language) that could filter spam. It never really got far beyond being a toy, although I did give the code to the Jazilla project, not sure if they did anything with it though...
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).
Mod me down and I will become more powerful than you can possibly imagine!
There's an account of the same story in Science of Discworld (by Terry Pratchett, Ian Stewart and Jack Cohen) in the chapter where Ian & Jack tell about 'real' evolution, genetic codes, DNA and Darwin.
it's becoming incredibly accurate (it was already 99% accurate before they used GAs)
I wonder just how effective a widely-deployed spam-killing technology would have to be to make spam a money-losing proposition in nearly all cases.
-jcr
The only title of honor that a tyrant can grant is "Enemy of the State."
And get this: Evolution had left five logic cells unconnected to the rest of the circuit, in a position where they should not have been able to influence its workings. Yet if Thompson disconnected them, the circuit failed.
:: More Magic
I only have one thing to say:
Magic
For those unfamiliar with the story.
War is Peace. Freedom is Slavery. Ignorance is Strength. - George Orwell or George Bush?
Sounds like the skroderider's skrodes from Vernor Vinge's "A Fire Upon the Deep". No one could explain how they worked, or what any individual piece of the machine did, but it all worked. Kinda cool.
There was an episode of STNG in which a group of special "adaptive" robot-like drones evolved an awareness and Data tries to save them when they are put in danger. The problem encountered in the episode was an ethical one. It asked the crew to look at what was considered intelligent, aware life for a machine. It should be a while before we are faced with such a problem, but it still doesn't mean we shouldn't be asking some questions.
:)
Personally I can't wait for more and more of these systems to be designed and to see how they act and react. If the statement is accurate that only a third of the circuits of a human designed chip were used then this is a potentially incredible resource. Drawing again from my Sci-Fi background, if you look at Issac Asimov's robot's books you will find a short about a AI Brain that was used to create the first hyperdrive ship. While only science fiction, a computer has the advantage of being able to look at all possible known rules, be able to test its environment and summarily report back on a problem that it is given. Seeing what humans may not be able to consider, because we just don't have the perspective, is what makes these systems really valueable. In no time computers like these evolving ones will be giving scientists new puzzles to solve, and a challenged scientist is a happy one (most of the time
I can't help but be reminded of Pierre Ouellette's The Deus Machine (Random House, ISBN: 0679424075).
Quite a good read, at the heart of which lies a computer which is constantly redesigning itself to make it better, evolving well beyond the point where humans understand how it works. Eventually (not a spoiler) it even decides to stop evolving... it concludes each time it designs new hardware to replace itself, it is essentially "killing" itself.
Great read (it deals with much more, such as some twisted biological mutation and perverse, sadistic madmen), though I think I'd like to keep it science fiction.
well.. it looks as if the matrix could happen now. since computers can improve themseves, it's only a matter of time before they discover they don't need us and enslave us to be energy generators for their cycles...
crud
I got dibs on being CowboyNeal in the new virtual world... as long as I'm going to be the robot's whipping boy, why not slashdots as well?
CoyboyNeal is God
Check these out:
http://slashdot.org/article.pl?sid=99/08/27/123821 3
http://slashdot.org/article.pl?sid=01/04/10/043622 0
Stop the insanity!
Donny
One of my coleagues did that at York University (UK) about 5 years ago as a final year project.
:-(
He was using FPGA-type chips, and started with a few thousand randomly-designed circuits, and then merged the most successfull ones. He was able to differentiate between a 1hz and 1khz pulse to one of its inputs.
There was one case where there was a single AND gate tucked away in a little corner somewhere, with its inputs tied only to its output - effectively useless. But the circuit failed to work if it was removed.
I wish I could remember his name
The more advanced the technology, the more open it is to primitive attack
Some of the assumptions of this model are:
- we have two states 0 and 1
- states evolve over time controlled by a regular clock signal
- 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:
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.
The coolest thing about this is the fact that a phenomenon occured which would have never been discovered/used if it had been done in a software simulation (because the phenomenon would have never been coded in by the programmers). Those circuits which seemed to have nothing to do with the process could have a quantummechanical function, a magnetic one, or (who knows?) might tap into the "new" force which makes the universe expand so quickly.
The thing is, an emergent behavior has shown up! And we humans had little to do with it, expect set it in motion. This proves to me that the future of design lies with computers, as they do it faster, and (if done physically) can utilise properties we know nothing of or are too complex for us to use. The only problem here is that we wont know (at first) if a new design is fit for production, or if it is (in part) due to a flaw in the chip used. See asimov's tale of the mind reading robot (and many other authors) to find some nice problems this can lead to...
"hey, this one can unify quantummechanics and the general theory of relativity, and use it to go past lightspeed!"..."Damn, we used the exact design on another chip, but it didnt work...looks like the original chip has a design flaw, and we cant figure out how it works!" The problem might be that one micrometer consisting of silicon and two borium atoms...or it might not...
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.
check the site - they run Win98 on their hypercomputers. That is *bound* to fuck up the evolutionary cycle.
Martijn
Weeelll... not quite right. The program which generates the chip intelligently selects and randomly modifies portions of the existing design (initally generated randomly) based on the performance (if any) of previous iterations. For example, the winner of the first iteration got the door prize for actually having an output. Any output.
For this to match real life, BTW, you need to postulate the pre-existance of FPGA-equivalents - chemicals at least as complex as RNA although RNA itself would not turn the trick - and some kind of teleology to permit selection to operate well in advance of where it would normally kick in, else the critter is quickly crushed by its own genetic burden.
And mine! Perzactly! It's part of The Rules, don'cha know? (-:
Got time? Spend some of it coding or testing
Next thing you're gonna tell me is that all computers were once just blobs of silicon, copper and undifferentiated polymers in some primordial soup. Well I just ain't buying it. I'll have you know that God created computers in 7 days and then sent us his Son, Linus, to show us the Way, the Truth and the Light. Nonbelievers will be punished on Judgement Day.
Fried ice cream is a reality. - George Clinton
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
Dear Internet user,
We have recently patented a sure fire way to rid your Inbox of spam, FOREVER.
Our new Genetic Algorithms have been researched for nearly ten years and have increased our already successful 99% kill rate to an incredible >99% kill rate. That's right an unbelieveable less than one percentage point increase. This means that if you upgrade NOW you will REDUCE your spam intake by up to 1 unsolicited email per day *
So don't delay, download Spam Assassin today and wave that spam goodbye forever.
* based on an estimated 100 unsolicited emails per day
--
No animals were harmed during the typing of this post
There are places where the networks are not touching,and there are places where they are-Boeing's Lori Gunter
To me it has always sounded like nonsense. When you build something it's always only a sum of its parts. Ok, if you have a very complex system it might look like it's exhibiting "emergent behaviour" but is, in fact, nothing special. Just very complex.
I was extremenly fortunate enough to be taught by Adrian Thompson (he's an extremely affable guy, btw) at Sussex uni. IIRC the GA exploited the physical properties of the silicon. What I found interesting was the fact there was a tiny portion of the FPGA, that was not connected to the main 1/3, when removed the chip would not work. Also, IIRC, a big issue surrounding GA's, is choosing an encoding scheme - deciding gene location and composition. For my final year proj, I evolved flocking behaviour for Braitenberg type virtual robots, the idea was to evolve an Artificial Neural Network that would control the left and right motors from minimal environmental input (it actually worked - once :)
I also remember a demo that was given showing an eight legged robot that had had ANNs evolved that made it walk, climb over and avoid obstacles. This kind of application of GA's, moves them away from (though not entirely) being a search technique and may perhaps make them useful tools rather than a different way to seach a problem space.
Anyhow, this research is 4 or 5 years old (at least) by now!
I thought GA's might be an approach to making bots for Quake and the like (I always bring it back down to gaming - sorry!), with the fitness of an evolved bot being tested by playing against real people.
if any of you get the chance to go to COGS (the School of Cognitive and Computing Sciences) @ Sussex Uni, I heartily recommend it, fabulous place, and fabulous people!
Nice
Jaymz
...old news from 1997. This older article is much better than the submitted one, so check it out.
Score:-1, Wrong
Not only is this a truly ancient piece of "news", but I do recall overhearing my Digital Systems Design lecturer saying that this kind of work recently got *much* harder, because they stopped making the FPGAs cell-addressable, so you have to deal with a row at a time. I don't know if this is still the case, but he was really annoyed by it at the time. There are workarounds, but they can slow down the evolution time something rotten.
Star Bridge Systems Inc. is the place NASA went to for their HAL-15, according to newsobserver.com.
...and then we'll report to termination centres when the machines on our side lose!
You're using her as bait, Master!
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, who has apparently done some more work in this area. 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.
Notice how you tried to be funny but didn't get modded to funny? The joke's on you. Next time, try to live and let live, would ya?
making an evolving fpga try to imitate current computers may be hopelessly pointless, because we do not know how much our view of computing may slow down the processes it is handling. however, if the fpga was used to evolve a simple (at first) turing machine, it could essentially do everything that computers can currently do. if, however, this turing machine was optimized, (the modules would be separate, having different fitness functions, but in sync, namely the operation of one would depend on another), we dont know how efficient the machine would become.
maybe the hal in the article (not 2001, at least yet) really IS a reality soon...
QED
BSD is for people who love UNIX. Linux is for those who hate Microsoft.
Typical Slashdot for someone to look at The Matrix and overlook the fact that the basic plot was blatantly stolen from The Terminator. All they did was replace time travel with a false reality. The flying robots even looked the same.
If anything, The Terminator scenario is more likely. If the computers had control of our nuclear weaponary, which they undoubtably would, they could easily set it off. Forcibly putting human bodies into a "harvest" and putting tubes to their brains is not so simple.
The Matrix? It's an okay movie, but it's been done before. The Terminator series really does make a lot more sense, and IMHO would've been a much stronger argument for your case.
Being a chip designer, and having designed asynchronous and synchronous circuits, I can tell you that what is happening is delays. The feedback paths are, most likely, being tuned for delay but in an "analog" way - that is, the paths selected are being selected for their precise timing and interoperation with a specific timing.
As to the circuits that don't work when they are removed from the system? It could be a number of factors, including:
1. Quiescent power use affecting delays through power drops of nearby circuits - in other words, even small bits of power consumption could be locally affecting the voltage applied to the circuits, where the drop would cause a tiny performance degradation that may be used in the tuning of the circuit in the analog sense.
2. Loading on input or output paths - this, again, affects delays in small ways by altering capacitance. If a line goes to an input, but the output is not used, if you remove that branch, you alter the capacitance on the input line that may have fanned to other used inputs in the circuit.
These types of phenomena might also explain why the resultant circuits are much smaller than their digital counterparts. To create an analog tone detector (passive), you need a network of resistors, inductors, and capacitors, but it is very small. To create a digital tone detector, there are several methods but you can create a small digital filter with resonance at the frequency you need. Problem is, it needs to have a time base in order to find the weighted coefficients for the filters, so it needs to be synchronous.
Oh, and one more point - the poster above who mentioned that FPGAs are not as well suited as custom ICs - this is NOT correct! In fact, the ability to change in the way FPGAs do makes this genetic algorithm possible! You have to choose an operating point for which you design a custom IC, and then that's pretty much it. Beyond that, you need special compensation circuits and the size of the design blows up. FPGAs are the best way to do this type of operation.
"Shall we next create false gods to rule over us?
How proud we have become, and how blind..." --Sister Miriam Godwinson, We Must Dissent
"The scary part: Thompson cannot explain exactly how the chip works! "
Isn't the whole point of computer science and mathmatics one of learning things like how and why so we can define and then use control?
Of all the possibilities of why Thompson cannot explain how the chip works, could marketing (investments), NDAs, lack of self reflection (doesn't know what he did)...etc. have anything at all to do with it?
Gee, I plowed this field, put down a bunch of seeds, watered it and I don't know how, but this crop grew.
AI - nothing is naturally that stupid!
Now that's SCARY!!!! Is Thompson an AI?
Oh I get it, Slashdot is the FPGAs and WE are the Genetic Algorithims that are being feed articles that we then generate feedback on. So as to improve the /. FPGA.
Isn't there like a +10 mode for self awareness?
Women, alone of all known organisms on the face of the Earth, are capable of sustaining an emotional state (such as anger, rage, jealosy, etc.) without the need for any external stimulous. Women can be angry at men for what they think they may say, what they said ten years ago, or what they would have said if everything had been completely different. And it is always the man's fault.
I'm the stranger...posting to
There has been no real step forward by Thompson et al. Recall too the article "Supercomputer for less than $1000". It claimed to be using a similar principal and technology. Still, when I asked for info there was no reply. NASA had an instance of their computer for a trial but nothing has been printed so ....
There's a real difference between an ant and my cat: The ant simply responds to stimulus by instinct, with little or no capacity for learning or thought. While cats certainly are not capable of thought on the same level of humans, they are infinately more capable than ants.
My cat routinely behaves in ways that suggest a capacity for comparing past events to present and future ones, an ability to plan, emotional states ranging from "fear" to "anger" and "sense of fun", and other cognitive abilities that are well beyond those of an ant.
Another thing my cat can do that would be very hard to program is form extremely complex associations. For example, she has learned that when I walk towards the food-closet door at breakfast-time or dinnertime, she is about to be fed. She acts on this knowledge by walking over to her food dish and meowing for food - a fairly unambiguous action.
Thing is, she also knows that if I start walking towards the closet door during the middle of the day and saying "Kibble!", this is a ruse to get her into the kitty carrier, and from there to the vet's office. Is that amazing or what! From just two or so incidents every year, my cat has learned to tell when I'm lying to her.
Yes, I'm a very proud cat owner. My point is, these behaviours would all be much harder to model than those of an ant.
I'm the stranger...posting to
Just a few years down the road...
Yhcrana
The voices in my head don't like you
Interestingly, one of the reasons more people don't is that there are often criteria that need to be taken into account which people would rather not state explicitly (which they would need to do for a GA), such as the fact that more senior lecturers don't like supervising exams early in the morning.
More of a social than a technical problem I suppose.
I believe this is the Discover article everyone's referencing:
Kind thoughts do not change the world
It might work. And it might get more dangerous than can be imagined. Creating a adaptable robot that we don't understand, but which has been evolved as a killing machine is, perhaps, a bit less than intelligent.
In fact, quite a bit less than intelligent. Does anyone really expect that this thing wouldn't be adapted to other applications? And evolved for them, of course. But the original layer would persist. Inevitably. Otherwise one would start from scratch (a much better idea!).
If one wants to do this, then start with an AI pilot. Perhaps for crop dusters. Evolve from there. And let the fighter be a spur off of that bush.
An AI pilot is probably a good choice. The environment is relatively simple, and most of the information is already instrumented. (Well, not on crop dusters, but the techniques are there.) And for crop dusters one could even have a square of markers (say microwave frequency corner reflectors, or even transmitters) to mark the edges of the area to be dusted. I don't know that the crop duster would pay much, but it's a much safer application. It's simple. And it's a place to grow from.
.
I think we've pushed this "anyone can grow up to be president" thing too far.
Not hate. Avoiding objects could be dislike, disgust, or something analogous. Hate would cause it to attack (or some analog).
.
I think we've pushed this "anyone can grow up to be president" thing too far.
A chip that recognizes a tone, wow, what wonders.
</Sarcasm>
If you set the bar low enough, you can claim that any learning method is a magic bullet.
Rocky J. Squirrel
From pro-StarBridge (PDF) article:
... reconfigurable computers are uniquely fault-tolerant. If part of the hardware goes down, the remaining circuitry functions without it - a point Star Bridge has illustrated by shooting a hole in a circuit board and demonstrating that the computer continues to function without a glitch.
...
There are those who already believe in the inevitability of hypercomputing dominance. "This is eventually going to change the way everything happens in the computing world," said Ed Bradley, a senior engineer in the munitions branch for the Air Force Research Laboratory at Florida's Eglin Air Force Base. "In the not too distant future, people will be tearing down Bill Gates statues and replacing them with statues of Kent Gilson."
:-)
Rich
The trouble with this sort of thing is that you get circuits that only work for a specific set of components. Copies require different tuning. This is partly why old TV sets had so many screwdriver adjustments in the back. Back when resistors were rated +-20%, capacitors were rated -40+100%, and keeping the tube count down was crucial, it was hard to design for repeatable prodution. Today, we have tighter tolerances and big transistor budgets, so we can use much more conservative designs that work every time.
So this is a neat hack, but not a profound result.
One problem as far as I see it with GA's is that you need a decent ranking function to judge success... i.e. effectively you have to "know" the answer, AND know how to rank or grade non-or partial solutions with respect to it, before you learn the solution. Otherwise its basically just the regular Generate and Test algorithm which can never scale to large enough problems.
Winton
. When a woman asks "Honey, does my ass look big in these?", according to her complete system there is a valid answer, despite the fact that it may not be consistent with other questions (ex. "So, how much do you think I weigh?").
:-)
But there is a consistant pair of answers to these questions that is also "correct" according to female logic. Specifically, these answers are "No, Honey, of course not," and "An amount that looks damn sexy, whatever it is." Alternatively, question 2 can be answered with any value w, where w is the average of your actual estimate of the woman's weight and the average weight for a woman of her height, and then subtract 10-15 pounds. However, that method can lead to answers inconsistant with the answer to the first question, and both methods can produce answers that will not satisfy the woman in question for some reason incomprehensible to male logic.
Incidentally, that's why I don't understand why you said "no no no". I provided a rough model of women's emotional responses in general, and you provided an outline of feminine logic - the two do not contradict each other, they complement each other. My own post provides a rough explanation of observed phenomena and a crude predictive model - yours provided a methematical model.
Water under the bridge, though. Excellent piece of work - thank you for posting it. And God save us both if our girlfriends ever read this thread.
I'm the stranger...posting to
I meant "not in our lifetime." I don't believe there's anything magical about cat or human brains, I just think modeling them will be very very hard, and so unlikely to take place in our lifetimes. Of course, I freely admit I may be speaking out of my ass here. :-)
I'm the stranger...posting to
"I blame Goedel"
Don't. I suspect women's use of the complete system is intuitive in the majority of cases, rather than based on advanced mathematical study. Goedel described the Incompleteness Theorem, but used it long before he did, I'll bet, and would have kept on using it even if he didn't.
I'm the stranger...posting to
Last sentence should have read: "But women used it long before he did...". I'm an idiot, I blame my cat.
I'm the stranger...posting to
"[the algorithm].. had left five logic cells unconnected to the rest of the circuit, in a position where they should not have been able to influence its workings. Yet if Thompson disconnected them, the circuit failed... The fact is that Thompson doesn't know how it works."
Right, so he's got an algorithm. He doesn't know how it works, and changing the slightest thing breaks his code. Sounds more or less like every bit of spaghetti programming I've ever seen. Nobody knows how it works, nobody can change anything, and if anyone tries, it refuses to work at all..
It's astounding the progress we've made
This very same article was linked and referenced about six months ago. This is OLD NEWS!
projects like seti should sell $150 pci cards with fpga onboard, and seriously accelerate their/our number crunching.
et? sorry, you've got the wrong number.
The process outlined by this chip is not evolution -- it is that of "natural selection", or in this case, un-natural selection. Selection is the process whereby survival of the fittest gradually producess the optimal population, which is logical and perfectly acceptable.
Evolution, on the other hand, is not: these chips cannot evolve new inputs to gather data from the world around them, they cannot evolve new logic cells, nor can they evolve an adaptation to survive without electricity.
Finally, one must note that unlike that primordial goop, this "evolving" system worked from four years of hardware design and carefully debugged code -- not a random assortment of silicon, copper, and plastic.
It seems to me that the exhastive checking of every "gene" could be accelerated by quantum computing techniques... After all, why analyze ten thousand configurations to determine fitness, when you could theoretically analyze ALL possible configurations simultaneously? (Assuming we had an arbitrary number of qubits, of course...)
I'm sure there's a hole in my logic here... can anyone point it out for me?
There are a thousand hacking at the branches of evil to one who is striking at the root.
Revolutionary Computing Via FRPG's