Hacker Monthly #18 by Netizens Media

Author:Netizens Media [Media, Netizens]
Language: eng
Format: epub, mobi, pdf
Publisher: Netizens Media
Published: 2011-11-01T03:06:59+00:00

Evolutionary Algorithm

Evolving “Hello, World!”

By FERRY BOENDER

My interest in Evolutionary Algorithms started when I read 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, and methodology, and I 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, organisms consist of DNA, which determines their characteristics. When organisms reproduce, there is a chance their offspring’s DNA contains a mutation, which can lead to differences 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, a 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. For example, 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, let’s 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. This is called the distance between two characters. 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.

def fitness(source, target):

fitval = 0

for i in range(0, len(source)):

fitval += (ord(target[i]) - ord(source[i])) ** 2

return(fitval)

If you look closely, you’ll notice that for each character, I square the difference.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.