23 votes

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!

11 comments

  1. Soptik
    Link
    Here is my C# solution. The code is long, so I'll give you a link instead. You can even run it right there. Solution Please note, that my solution is not optimal. There are some lines where I was...

    Here is my C# solution. The code is long, so I'll give you a link instead. You can even run it right there.

    Solution

    Please note, that my solution is not optimal. There are some lines where I was too lazy to make it efficient and breeding should not be done this way. But it works and it could help you when you get stuck :-)

    4 votes
  2. [3]
    PJDuchesne
    Link
    Here's a 'quick' python solution, also on tio.run as @Soptik used. Code The "combination" portion of the challenge was rather open ended and drastically changes the code, so I just went ahead and...

    Here's a 'quick' python solution, also on tio.run as @Soptik used.

    Code

    The "combination" portion of the challenge was rather open ended and drastically changes the code, so I just went ahead and did what I felt was fun. After getting all entity fitnesses I simply allowed only the top 10% percentage of the population to reproduce. To reproduce, I simply randomly look through the entity list until I find two entities that are allowed to reproduce and then combine their solutions to make a new entity.

    There are parameters at the top of the code if you want to play with them:

    • Solution String: The solution string to look for (Default: "Hello World")
    • Population Size: The number of entities in the list (Default: 1000)
    • Reproduction Cutoff: The percentage of the population allowed to reproduce between iterations (Default: 0.1 -> 10% )
    • Mutation Chance: The chance for each character to mutate within an entity. Mutation occurs during entity creation. (Default: 0.05 -> 5%)
    3 votes
    1. [2]
      Soptik
      Link Parent
      Only 7 generations to find solution, nice! If you wanted to experiment with this further, you could try this: Make world with some obstacles. Each entity is bird or something like this, trying to...

      Only 7 generations to find solution, nice!

      If you wanted to experiment with this further, you could try this:
      Make world with some obstacles. Each entity is bird or something like this, trying to get from left to right without hitting an obstacle. The fitness function is based on maximum x position of each bird. The solution could be, instead of string, list of numbers, where each number indicates, if the bird turns left, right, or flies straight.

      I made it and it looks really good, especially when you watch entities learn how to get through the map and then you add new obstacles to their path.

      1. PJDuchesne
        Link Parent
        That sounds fun, maybe I'll check it out tomorrow when I have more free time. That could make an interesting ascii screensaver :)

        That sounds fun, maybe I'll check it out tomorrow when I have more free time.

        That could make an interesting ascii screensaver :)

  3. vid
    Link
    Here is my basic python solution. I have never done anything like this and I think its pretty neat, so thanks for the challenge!

    Here is my basic python solution. I have never done anything like this and I think its pretty neat, so thanks for the challenge!

    2 votes
  4. [6]
    39hp
    Link
    So intimidated by the code that’s been posted so far and the challenge, lol. I think I understand how some of the code works, but when I try to make my own from scratch or reverse engineer it, I...

    So intimidated by the code that’s been posted so far and the challenge, lol.

    I think I understand how some of the code works, but when I try to make my own from scratch or reverse engineer it, I get so lost.

    I’m gonna keep cracking at this while also going through some basic python exercises. This is so much fun!

    1 vote
    1. Emerald_Knight
      Link Parent
      If you find yourself at a loss, feel free to check out some of the other challenges that have been posted to get some extra practice in. There's even a classic FizzBuzz problem :)

      If you find yourself at a loss, feel free to check out some of the other challenges that have been posted to get some extra practice in. There's even a classic FizzBuzz problem :)

      1 vote
    2. [2]
      Soptik
      Link Parent
      I know you just started with programming, do you know how to debug? Google "[name of your editor] debugging", it'll help you a lot If you get stuck, just ask me (or someone else here), we will...

      I know you just started with programming, do you know how to debug? Google "[name of your editor] debugging", it'll help you a lot

      If you get stuck, just ask me (or someone else here), we will help you :-)

      1 vote
      1. 39hp
        Link Parent
        For now, I’m mostly getting hung up on syntax. I just learned how to use for x in/not in y, lol. Don’t be surprised if there are some zombie posts in the older challenges in a few days.

        For now, I’m mostly getting hung up on syntax. I just learned how to use for x in/not in y, lol.

        Don’t be surprised if there are some zombie posts in the older challenges in a few days.

    3. [2]
      PJDuchesne
      Link Parent
      Many of the challenges are being drawn from Project Euler, which is a great way to practice programming either as a new programmer or simply learning a new language. I'd definitely recommend...

      Many of the challenges are being drawn from Project Euler, which is a great way to practice programming either as a new programmer or simply learning a new language. I'd definitely recommend trying out some of the earlier problems as you get started.

      The first few problems can be easily brute forced and just test your syntax, but it quickly moves to more thought provoking problems that require a reasonable approach to find the solution in a timely fashion.

      1 vote
      1. 39hp
        Link Parent
        Thanks for pointing me there! I tried the first few and I feel like I’m starting to get the hang of it. I found this place that has some solutions and when I looked I was like, ‘Wow, I am doing...

        Thanks for pointing me there!

        I tried the first few and I feel like I’m starting to get the hang of it. I found this place that has some solutions and when I looked I was like, ‘Wow, I am doing caveman Python’ 😂!