Hard Light Productions Forums
Off-Topic Discussion => General Discussion => Topic started by: Flipside on November 16, 2004, 03:01:51 pm
-
I found a brilliant example of evolution recently......
An experiment held in 1993 by an Engineer called Adrian Thompson....
Thompson wondered what would happen if you used the 'genetic algorithm' approach to an electric circuit. Decide on some task, randomly cross-breed circuits that might or might not solve it, keep the ones that do better than the rest, and repeat for as many generations as it takes.
Most electronic Engineers, thinking about such a project, will quickly realise that it's silly to use genuine circuits. Instead, you can simulate the circuits on a computer (since you know exactly how a circuit behaves) and do the whole job a lot more quickly. Thompson mistrusted this line of argument, though: maybe circuits 'knew' something that a simulation would miss.
He decided on a task, to distinguish between two input signals of different frequencies, 1Khz and 10Khz. Think of them as a low tone and a high tone. The circuit should accept the tone as an input signal, process it in some manner to be determined by it's eventual structure, and produce an output signal. For the high tone, the circuit should output 0 Volts, for the Low tone, a steady 5 volts. (Actually, these properties weren't specified at the start, and two different steady signals would have been acceptable.)
It would take forever to build thousands of trial circuits by hand, so he employed a 'field programmable gate array'. This is a chip that contains a number of tiny 'logic cells' - mildly intelligent switches, so to speak, whose connections can be changed by loading new instructions into the chip.
Those instructions are analogous to DNA code and can be cross bred, which is what was done.
He started with an array of 100 logic cells and used a computer to randomly generate 50 instruction codes. The computer loaded each set into the chip and fed in the two tones, and picked those which reacted best to the signals.
Those that did not react with the signals were 'killed off' and the surviving instruction blocks were 'bred' with each other.
What is most surprising about the experment, however, is not the details, it's the solution.....
By the 220th generation, the fittest circuit produced outputs that were pretty much the same as the input. Basically acting like a bare wire.
By the 650th generation, the low-tone output was steady, but the high-tone output still produced varying output. It took to generation 2800 for the circuit to behave exactly as wished.
The strange part about the final circuit is this. No Human engineer could ever have invented it. Indeed, no human engineer would ever have been able to achieve that result with a mere 100 logic cells. You cannot even make a timing-clock with 100 logic cells. But the new circuit didn't bother with a clock.
Further study of the circuit showed the final solution, in fact, only used 32 cells, 5 of which were in no way whatsoever connected to the circuit, and yet the circuit failed to work if they were not set in that manner.
Thompson described it thus : 'Really, I don't have the faintest idea how it works.'
---------------------------------------------------------------------------------
Not trying to start a creationist/evolution row here, but I found it incredibly interesting :)
-
It could be evolution.
I like to think of it more how life started on this planet and how easily it could start on other planets.
-
Indeed, the current thinking is not that life is rare, but is tending far more along the lines of 'If life can evolve, it'll do everything darn-well possible to evolve' :)
Edit : Microsofts' programming secrets are revealed! ;) hehehe
-
Those aren't secret.
If you look carefully, starting at line #30191 of explorer.exe's source code, you'll notice this line:
Shaft all Microsoft Windows Users=1
If 'Shaft all Microsfot Windows Users'=1, GO TO 'Random errors, CTDs, and other annoyances'
Jokes aside, that's actually very, very interesting.
EDIT: What's the source on this?
-
those cells that were not connected were probably interacting with the rest of the circuit via field interference
-
Yes, that was the theory, that there was some way in which they interacted with the circuit in a physical manner that effected the electronic flow.
The source itself was, curiously enough, 'The Science of Discworld' by Terry Pratchett, Ian Stewart and Jack Cohen. Pratchett writes a Discworld story involving the evolution of Earth, and between each chapter theres a chapter by the 2 scientists who explain what is going on, and the differences between old and new thinking on things. It's an incredibly interesting book :)
-
Silly question: I don't suppose there's a flowchart available showing a visual of what actually happened during the experiment, is there?
-
Originally posted by ionia23
Silly question: I don't suppose there's a flowchart available showing a visual of what actually happened during the experiment, is there?
Probably, but after 2800 stages of selection, random mutation and crossover? Not very readable, I'd expect.
Neat thing about gen algorithms, is that they don't really 'care' about why something happens. It just picks the best output 'genome', and tries to move forward from there. Something which humans would have difficulty with... I'd imagine many (most?) engineers are like me - if they don't know why it's working - even if it is - then they're suspicious of it.
-
Well, quite often because if it stops working, they won't be able to fix it ;)
Obviously, in 'reality' the culling of useless circuits wouldn't be quite so total, some less 'effective' genes may combine with more effective ones, or go off on a completely different branch. Which explains our biodiversity :)
-
Originally posted by aldo_14
Probably, but after 2800 stages of selection, random mutation and crossover? Not very readable, I'd expect.
Neat thing about gen algorithms, is that they don't really 'care' about why something happens. It just picks the best output 'genome', and tries to move forward from there. Something which humans would have difficulty with... I'd imagine many (most?) engineers are like me - if they don't know why it's working - even if it is - then they're suspicious of it.
Oh, agreed for sure, I guess I was looking for something a bit more simplified. One of the many great curses of being visually centered.
I'm probably oversimplifying what the experimenter did, viewing the initial process as a simple if-then-else statement for the input signal, circuit, and output. Obviously I'm quite in the dark on this.
it would make sense that if someone doesn't know why something is working, just that it is, that they would be suspicious. Just another puzzle to solve. Given enough time it'll be figured out.
-
Well, consider a program where you are quite literally sending a block of random instruction to the processor, and then 'cross breeding' the blocks that produce the closest result. You keep repeating this until the program does what you want it to do.
It's far simpler than that in a way, since it's Binary signal, but that, in essense was how it was done :)
-
Well...can you explain to me exactly how every device and appliance you use every day works?
I'm not suspicious of my car, even though I don't understand all the intracies of its operation.
-
Originally posted by Flipside
Well, consider a program where you are quite literally sending a block of random instruction to the processor, and then 'cross breeding' the blocks that produce the closest result. You keep repeating this until the program does what you want it to do.
It's far simpler than that in a way, since it's Binary signal, but that, in essense was how it was done :)
That helps a bit, thank you :)
-
I wish I knew more about the actual 'breeding' of the circuits, I'm assuming some kind of Boolean function was used on them (AND, NOT, OR are simple examples) to generate children, but I'm not sure. :(
-
Originally posted by ionia23
Oh, agreed for sure, I guess I was looking for something a bit more simplified. One of the many great curses of being visually centered.
I'm probably oversimplifying what the experimenter did, viewing the initial process as a simple if-then-else statement for the input signal, circuit, and output. Obviously I'm quite in the dark on this.
it would make sense that if someone doesn't know why something is working, just that it is, that they would be suspicious. Just another puzzle to solve. Given enough time it'll be figured out.
I don't have me notes from uni handy, but IIRC a genetic algorithm works roughly as follows (for reference, dunno how much you know of this so forgive me if it's redundant);
1/ A population is initially created / fed in from 6
2/ The effectiveness of each member of the population is evaluated with a fitness function (i.e. how close to the 'goal' state they are)
3/ The 'best' members are determined in some way (there are multiple ways, such as comparison of random pairings, sorting, etc)
4/ Population members are 'crossed-over' - i.e. parts of them are swapped with each other. The parts chosen - and how much is swapped over- can be calculated using a variety of methods (i.e. fitness based), including simply randomly / arbitrarily.
5/Finally, each of the crossed over members are randomly mutated - this is to stop the population growing static and allowing possibly beneficial changes
6/ the resultant population is fed back in for the next generation (see 1)
Again; must emphasise this is hazy to me. Check a webpage for a more accurate explanation. I really have to find time to read over these things again...
-
That's quite an interesting story. Personally I think it deserves another. I've mentioned this one previously in other threads but I might as well tell the full story.
There's a interesting concept in game theory called the Prisoners Dilema. It goes something like this. Two men are arrested for a crime they commited together and are interrogated seperately. The police know that at least one of them was involved in the crime but not who.
If one man rats out the other one he'll be able to do a deal and get off for free while the other person goes to jail. If both spill the beans they'll end up serving time together although probably not as long a sentence as if one man was convicted. If they both keep silent however the case probably won't be strong enough and the police will have to charge them with a lesser crime.
The reason that the game is called the Prisoners Dilema is because regardless of whatever the second man does the best thing prisoner A can do is to rat out the other guy. If Prisoner B has kept silent he gets away scot free. If Prisoner B has ratted him out then if he doesn't do the same he'll end up as the sucker in jail while the other guy goes free.
Prisoner B has almost certainly followed the same logic in his head and so is almost certain to also rat on prisoner A.
The result is that both men end up in jail convicted by the other's testomony but knowing that if only they could have both kept silent they'd have been better off.
The simple version of The Prisoners Dilema is just an amusing story. What makes the game interesting is the iterated game. In this you have several rounds where both players can choose to co-operate or backstab each other. In the iterated game a score is kept and tatics come into play.
Much study has been carried out into these tactics as there are many real world situations where they can come in useful. One example was the cold war where both the USA and USSR choose to repeatedly co-operate by not launching nukes at each other even though if they could have got away with nuking the other one they would have removed a serious problem. There are many other examples in business etc. too.
A while back a scientist decided to carry a study out to see what tactics worked best in iterated games of PD. He set up a computer tournament where programs would play PD against each other. 14 different programs were submitted and a 15th one which just chose at random was included as a control. To the surprise of all concerned the winner was one of the simplist submitted. The logic was basically this
IF Round = 1 THEN Co-operate
IF Round > 1 THEN do what the other program did last round.
The scientist then divided the stategies into two groups. The nice ones (programs that would never defect unless prevoked by the other program) and nasty ones that however occasionally would defect and try to win. Sure enough all 8 nice stratagies were also the 8 strategies that did the best.
The scientist published his results including an analysis of why this strategy (known as tit-for-tat) had won and then held a second round inviting people to submit strategies.
This time 63 entries (including random) were submitted. Yet again tit for tat won.
A third round was run but instead of scoring points the various strategies were rewarded with a number of offspring dependant on how well they did. After 1000 generations there was no way to tell easily who won cause all the nasty strategies had died off and all the ones remaining simply cooperated the whole time with none of them backstabbing the others.
What this all means for real world examples of the Prisoners Dilema is up to you lot to decide but it certainly gave me a lot to think about :D
(If any one wants to read the whole story it was published in The Selfish Gene by Richard Dawkins)
-
Actually, thinking about it, 2800 generations is far less than I would have predicted for a working circuit. Still, real life doesn't often allow for such 'massive' jumps between parents and children's genetic makeup.
Edit : LOL Good story, just goes to show, Nature has plans ;)
-
Very intersting...
-
genetic algorithms are.... complex
-
It'll be interesting to see if it's possible to adapt this for more complex algorithmic tasks (as opposed to a pure function).
As for the Prisoner's Dilemma, I've read somewhere that they've figured out a strategy that not only beats tit for tat, it also performs better in all situations.
IIRC, it's some complicated scheme where each "player" that uses this tactic somehow finds other players also using this tactic and they all cooperate. Quite clever if you ask me.
-
I remember the origonal article, from what I remember it was some sort of EM interference that the chips had used on them selves that chip makers spend a great deal of time and effort to eleminate, also interesting about it was that if you moved the arangement from one chip to another chip the circits wouldn't work any more, that the adaptations were environment specific.
-
needless to say i think artificial intelegence will be invented on accident.
*edit* just realised that i it happened on accident then it couldnt be considered artificial :D
-
Originally posted by Flipside
Actually, thinking about it, 2800 generations is far less than I would have predicted for a working circuit. Still, real life doesn't often allow for such 'massive' jumps between parents and children's genetic makeup.
Nature probably also doesn't have as good a fitness function :)
-
Originally posted by Nuke
needless to say i think artificial intelegence will be invented on accident.
*edit* just realised that i it happened on accident then it couldnt be considered artificial :D
kinda reminds me of the Ender series
-
Originally posted by Nuke
needless to say i think artificial intelegence will be invented on accident.
*edit* just realised that i it happened on accident then it couldnt be considered artificial :D
Probably can't create it intentionally anyways; how would you even define intelligence, after all?
Although I remember some American bloke setting up a big 10-year project to try and create a sort of 'information library' for an AI; the idea being that in order to have a usable AI you need to provide it with the same sort of rough knowledge base that humans use (what is a tree, what is brown, that sort of thing etc etc). Every night they'd feed in information, and the AI would draw conclusions off it (learning, effectively) - and in the morning they'd review the conclusions made by it.
For example, they AI had problems when given the information that humans shaved - it had trouble distinguishing that the shaver was not part of the human body, and ended up regarding humans and mechanical and thus not alive (or similar, exact details escape me). Very odd conclusions, yet completely logical based on what it knew.
I forget the name of this project, natch, but it should have been 'completed' a few years back. I'd be very interested if anyone knows of how it developed; if it worked, then it'd be leading towards an AI (maybe not intelligent, so much as a knowledge base able to draw inferences) with a basic understanding of how the real world works.
NB: it wasn't just a case of feeding in information like into a dictionary... the idea was that this AI could take basic facts, draw conclusions, and then continue to draw further conclusions from the basis of both what it had been told and also what it had inferred.
-
Originally posted by ChronoReverse
As for the Prisoner's Dilemma, I've read somewhere that they've figured out a strategy that not only beats tit for tat, it also performs better in all situations.
IIRC, it's some complicated scheme where each "player" that uses this tactic somehow finds other players also using this tactic and they all cooperate. Quite clever if you ask me.
Tit for tat has it's problems. It's very easy for it to get into exactly the sort of battle the name implies and end up alternately cooperating and backstabbing.
The main point though is that even if something else can beat tit for tat it's still a nice strategy. I haven't heard of a nasty one that can do that yet :D
-
Well, the solution I mentioned isn't technically nasty, but I'm sure it could be modified so that not only do they collectively support others using the same scheme, but also work together to crush those not using the same scheme.