Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

In this Discussion

Fun with genetic algorithms

IgnatzIgnatz Mod
edited March 2013 in Code Sharing Posts: 5,396

I've written a simple genetic algorithm class for Codea, and tried it out with several different optimization problems. You can play with it here: http://pastebin.com/embed_js.php?i=V7jn9gu2

It is designed for easy export to other projects, but isn't ready for that at the moment, because it needs documentation and cleaning up which I'll only do if there's interest. I've added some notes below for anyone who may be interested, because this can be a lot of fun and isn't too technical. (Update: I've created a template that can be adapted, here: http://pastebin.com/embed_js.php?i=tBx1NpGT)

For those who don't know, genetic algorithms use evolutionary tricks to solve difficult problems, such as finding the shortest route around 20 cities, or scheduling classes with all sorts of restrictions. This project creates a population of test solutions, measures how good they are, and replaces the worst of them. Replacement is done by choosing two of the better solutions and mixing them together to hopefully produce an improved result.

What my class does is to create a set of random numbers for each test solution in the population. It is up to you to use those numbers to produce a meaningful solution. For example, if you are finding the shortest route round some cities, you could have one random number per city, sort them, and use the sort order to give you the sequence. This is in fact how my code for this problem works.

So my class creates these random number sets, and asks you to tell it how good their solutions are. Then the class dumps the bad solutions and creates new ones through recombination. It repeats this process for as many times as you have selected.

Much of the fun and challenge in genetic algorithms is
1. choosing how to use the random numbers in a way that uses the advantages of genetic algorithms.
2. calculating how good the solutions are. For example, my path finding problem in the above code allows movement in all 4 directions, which can lead to landing on the same square more than once, or going round in circles. I've included a bonus for ending up on the target square, but I haven't made it too big, because if I do, the evolution will home in on the first solution that manages to finish, discarding lots of others that may ultimately be better (with a few tweaks). I've also included fairly gentle penalties for landing on the same square twice.
3. Tweaking the parameters, such as the size of the population, and what percentage of it gets replaced in each generation.

This particular class is fairly simple, but it does all the genetic stuff for you, is good enough to show how the process works, and it can be enhanced. I'm happy to discuss further with anyone who is interested in using it elsewhere.

Dermot

Tagged:

Comments

  • Jmv38Jmv38 Mod
    Posts: 3,297

    Wow! Thanks for sharing. If you publish more i'll certainly follow you work very closely. I would love to adapt you algo to make my pushball game teams play and become smarter...

  • IgnatzIgnatz Mod
    Posts: 5,396

    I had a look at your pushball game, and it's not suitable for a genetic algorithm, which takes a lot of time to solve fixed problems, as opposed to a constantly changing game situation. I would suggest looking at the Ant project on the forum, which seems to have a really good AI design and lots of behavioural programming.

  • Jmv38Jmv38 Mod
    Posts: 3,297

    Thanks for sharing this project @ignatz. For further reference i have put a copy of your code there
    http://jmv38.comze.com/CODEAbis/server.php#GA

Sign In or Register to comment.