Programming Challenge - Let's build some AI!

Hi everyone! In this challenge, we will build simple genetic algorithm.

The goal is to create genetic algorithm that will learn and output predefined text ("Hello World!").

The goal can be achieved with any language and you'll need just simple loops, collection and knowledge how to create and use objects, even beginners can try to complete this challenge.

How?
I'll try to explain it as best as I can. Genetic algorithms are approximation algorithms - they often do not find the best solution, but they can find very good solutions, fast. It's used when traditional algorithms are either way too slow, or they even don't exist. It's used to, for example, design antennas, or wind turbines. We will use it to write "Hello World".

First of all, we define our Entity. It is solution to given problem, it can be list of integers that describe antenna shape, decision tree, or string ("Hello World"). Each entity contains the solution (string solution) and fitness function. Fitness function says, how good our entity is. Our fitness function will return, how similar is entity solution text to "Hello World" string.

But how will the program work? First of all, we will create list of entities List<Entity>. We will make, for example, 1000 entities (randomly generated). Their Entity.solution will be randomized string of length 11 (because "Hello World" is 11 characters long).

Once we have these entities, we will repeat following steps, until the best entity has fitness == 1.0, or 100% similarity to target string.

First of all, we compute fitness function of all entities. Then, we will create empty list of entities of length 1000. Now, we will 1000-times pick two entities (probably weighted based on their fitness) and combine their strings. We will use the string to create new entity and we will add the new entity to the new list of entities.

Now, we delete old entities and replace them with entities we just made.

The last step is mutation - because what if no entity has the "W" character? We will never get our "Hello World". So we will go through every entity and change 5% (or whatever number you want) of characters in their solution to random characters.

We let it run for a while - and it is done!

So to sum up what we did:

entities <- 1000 random entities
while entities.best.fitness < 1:
  for every entity: compute fitness
  newEntities <- empty list
  1000-times:
    choose two entities from "entities", based on their fitness
    combine solutions of these entities and make newEntity
    newEntities.add(newEntity)
  for every entity: mutate // Randomly change parts of their strings

print(entities.best.solution) // Hello World!
Now go and create the best, fastest, and most pointless, genetic algorithm we've ever seen!