On the Origin of Circuits over at DamnInteresting.com. I always wanted to try something like that out for myself, but never really found the time. Now I have, and I think I've found some interesting results.
Disclaimer: I know next to nothing about Evolutionary Algorithms. Everything you read in here is the product of my own imagination and tests. I may use the wrong algorithms, nomenclature, methodology and might just be getting very bad results. They are, however, interesting to me, and I do know something about evolution, so here it is anyway.
How Evolution Works
So, how does an Evolutionary Algorithm work? Why, the same as normal biological evolution, mostly! Very (very) simply said, organism consist of DNA, which determine their characteristics. When organisms reproduce, there is a chance their offspring's DNA contains a mutation, which can lead to difference in characteristics. Sufficiently negative changes in offspring make that offspring less fit to survive, causing it, and the mutation, to die out eventually. Positive changes are passed on to future offspring. So through evolution an set of DNA naturally tends to grow towards its "goal", which is ultimate fitness for its environment. Now this is not an entirely correct description, but for our purposes it is good enough.
A simple evolutionary algorithm
There is nothing stopping us from using the same technique to evolve things towards goals set by a programmer. As can be seen from the Antenna example in the DamnInteresting article, this can sometimes even produce better things than engineers can come up with. In this post, I'm going to evolve the string "Hello, World!" from random garbage. The first example won't be very interesting, but it demonstrates the concept rather well.
First, lets define our starting point and end goal:
source = "jiKnp4bqpmAbp"
target = "Hello, World!"
Our evolutionary algorithm will start with "jiKnp4bqpmAbp", which we can view as the DNA of our "organism". It will then randomly mutate some of the DNA, and judge the new mutated string's fitness. But how do we determine fitness? This is probably the most difficult part of any evolutionary algorithm.
Lucky for us, there's an easy way to do this with strings. All we have to do is take the value of each character in the mutated string, and see how much it differs from the same character in the target string. We then add all those differences, which leads us to a single value which is the fitness of that string. A fitness of 0 is perfect, and means that both strings are exactly the same. A fitness of 1 means one of the characters is off by one. For instance, the strings "Hfllo" and "Hdllo" both have a fitness of one. The higher the fitness number, the less fit it actually is!
Here's the fitness function.
- - - - - - - - - - - >
Fake software downloads are a huge problem on the web. A few weeks ago a non-technical friend called me and asked how to play some Xvid encoded movies he had downloaded. I told him that the best and easiest software to use is VLC Player. He asked if I could send him a copy or a link, and I said "it's ok, just Google for 'VLC download' and you will find it". Big mistake.
Since it was Father’s Day here in Sweden yesterday - yes we know it varies around the world - we thought we’d pay homage to some of the people behind the Internet as we know it today.
Them All!
;)
