Travelling Salesman Problem

I have been extremely busy over the last few weeks with various University projects, so the genetic algorithm work has moved to the bottom of the stack. The ideas and problems are still quite fresh in my mind, so without going straight into programming the physics based evolving creatures, I'm going to have a look at something else quite closely related. It is linked in to both evolution and optimization. There is a very old mathematical problem, known as the travelling salesman problem (TSP). The TSP involves finding the shortest route between a number of cities, visiting each city only once.

Finding fast solutions to the problem is vital for applications such as route finding on maps. Anyway, I recently read an interesting paper one approach to solving the TSP ( Ant colonies for the traveling salesman problem ). The paper shows that using ant agents, which lay virtual pheremones, a shortest path can be found. Ants prefer to follow paths with more pheremones on them - this means that shorter paths will build up more pheremones because more ants will travel along them.

When I get back to my computer I will have a look at creating a similar solution to the problem in flash, and see the kinds of results that can be produced.

It might also be interesting to look at the effects of changing the properties of ants on how well the system optimizes itself.

I'll get back to you with any results!

3D Experiments - New Toy

I've been quite excited at the moment, playing around with my new toy Cinema 4d.

Here are some of of the first things I've made - click the images to run the videos. The first uses bullet physics and the second uses Cinema's hair plugin.

Enjoy!

Creature Evolution in Flash: First Thoughts

Simple 3D Music Visualizer

Just played around a bit with the 3D fluid dynamics thing I made a few days ago. I added some computeSpectrum functionality using the Flash 10 audio features and created a very basic music visualizer. I'm not entirely happy with it but its worth a post, just click to start it up (the song might take a while to load):

The song is "Rabbit In Your Headlights" by Unkle, enjoy!

Image Evolution: Madame Mattisse

I've come back with a new and improved evolution algorithm, one which doesn't stop evolving after 300 generations! I've also uploaded the movie with a bit of a UI which you can have a play around with and see how well you can evolve the images. The ones below show the kind of evolution you might be able to achieve. I've also changed the fitness function image to one of my favourite paintings of all time, Madame Matisse, by Matisse. Just click here to launch the movie.

Enjoy the Genetic Algorithm fun!

A Brief Look At Genetic Algorithms

This post is sort of a continuation of my work on natural selection and evolution as a tool for image compression. Genetic algorithms are an extremely interesting area of study, and over the next few weeks I'll be exploring the kinds of things that can be achieved in the field using actionscript and the flash player. Genetic algorithms are being used to evolve some of the most advanced robots in the world, as well as being used in route finding and compression applications.

So what is a genetic algorithm? In a nutshell it is a computational technique through which solutions to optimization problems can be found. It is an evolutionary method that can be compared to the way evolution and natural selection work in the biological world. A genetic algorithm requires two things to work, a genetic representation of the thing you are trying to evolve, and what is known as a fitness function to compare your genes against.

Lets take the example found in the video below (click the image and it should start up):

Each creature is represented by a set of genetic data. This determines everything about that creature, how big it is, where it has joints, any muscles it might have and how it decides to use them and so on.

By comparing the phenotype (the physical outcome of the genes) to a fitness function, we are able to determine how suited a certain version of the creature is to performing a certain task. Examples of fitness functions include the ability to swim fast, the ability to jump, or the ability to win in a game of football.

Currently there is no evolution going on at all, so we need to introduce random mutations in the genetic data. You should be able to see that a random mutation might cause a creature to be more effective at carrying out the fitness function, if it is we can stick to the new set of genes, otherwise lets go back to the original.

In my program to evolve an image from a few polygons the fitness function was the similarity to the comparison image.

So now that we've discussed computational genetics briefly, how am I going to work this all into a flash project. The first issue is creating a physical world in which my creatures can evolve. Clearly I don't have the computational power to test millions of creatures in 3D with a 3D physics engine, so that isn't an option. I have decided to stick with a simple 2D Verlet Integration based particle engine with constraints and muscles (no line-line or polygon-polygon collisions) and see what happens.

I am quite excited about seeing where this one is going to go, so stay tuned!

Image Evolution

Based on the work by Roger Alsing I thought I'd create a real time evolving image. Initially 30 random numbers are generated from a seed, these numbers are the components of the DNA strand. Each number corresponds to a specific polygon with a characteristic colour, transparency and number of vertices. A mutation in the DNA strand results in a shape changes. Images before and after a mutation are compared to the original painting, Girl With A Pearl Earring, and if a mutation causes greater similarity, then the mutation holds, otherwise the DNA reverts to its previous form. This is similar to how evolution works in the biological world.

Here are the first few mutations showing development of the image:

These are early stages, with up to 165 successful mutations. I will leave the program running over night, and will update the results. The lack of computational power in AS3 and my completely un-optimised code means that comparison processes take quite a while. One way to improve speed would be to reduce canvas size so I may turn to this if the program doesn't produce anything nice.

Having said that the early results are making me feel optimistic. We just need a few more thousand mutations and it'll be there.

Update: Here are the 198th and 238th mutations, I don't think the image will look that interesting until it gets into the 1000s. Its getting there but its clear that its a long process. Unfortunately the rate of improvement also slows down. Its up to about 15000 mutation attempts, and its taking longer and longer to mutate successfully each time. Currently only up to 10 vertices are allowed per polygon. Increasing this maximum number to more could increase the rate of improvement. As could allowing other sorts of mutation such as gene swapping, where two of the seed numbers swap. I'll give this a go soon although I will let this version go to 1000 mutations just to see the results.



Update: Just a though on using this as a compression technique. Each seed number is a 32bit integer. This means 30 numbers comes to 960bits or 120bytes per image. Given that the original version of the image I used (a PNG so already compressed) comes to 231kBytes, thats a compression factor of about 2000. Even using 100 polygons (a factor which would drastically improve the final evolution of the image) the compression factor would still be around 600! This is very impressive. I remember reading about a competition somewhere to send images as twitter messages (a twitter message contains up to 120 characters or 120bytes of ascii?) This means that the images I have produced could indeed be sent as twitter messages.




Update: The evolution process seems to be levelling off at about 360 successful evolutions with over 1.6 Million evolution attempts. This leads me to believe that my evolution parameters weren't ideal. The two images below shows the image as far as I'm going to take it. The second shows a blurred image applied and actually the result is pretty good when compared to the blurred original (in other words when you squint you should be able to see the original image. I'll come back when to you when I've improved the parameters and algorithm slightly!

3D Waves: Projected 2D fluid simulation

I found this experiment quite interesting. In an earlier post I gave an example of a 2-dimension fluid simulation that I'd been working on using the Navier-Stokes equations. I decided to play around with this code a bit and use the 3D point engine from my last experiment in conjunction with the fluid engine. The density from the fluid simulation is simply projected onto the XZ plane with density values corresponding to the height of corresponding point particles.

The results are certainly interesting. Click the image below to start up the experiment. To create waves just move your mouse around and drag the movie to change the camera angle. I decided to add a slight fade and blur on the particles which makes it look very pretty. Enjoy!