Solving puzzles with genetic algorithms

The other days i bought a cube puzzle. It was made of small cubes tangled on a string grouped 2 or 3. Here is a picture to make a better idea of what I'm talking about:


The idea was to rotate the groups in such a way to obtain a bigger cube in the end. Before trying to solve this directly i said to myself: "Hey this is a great opportunity for some genetic algorithms programming". So, with this in mind i started to think about a way to program my computer to solve this. It turned out it wasn't very difficult to solve it directly, but hey! i enjoyed it more doing the program then just solving it the classical way.

As you probably know, or if you don't maybe you can check out wiki, the main idea in genetic algorithms is to create populations where each element represents a possible solution to your problem. Each characteristic of the solution is described, like in biology, by one or more chromosomes. So the first step is generating the population, the bigger the number of elements the higher the chances to solve your problem more quickly. Good.

After the population is generated you will need a way to evaluate the precision of your solution. More precisely, you will need a function to calculate the fitness of an element. The fitness will actually tell you how close your solution is from the desired result. Usually the desired result is marked with fitness 0. The more your fitness grows the further you go from the point of interest.

So after calculating the fitness of each element from your current generation, you will want to keep the best ones ( the ones with a better fitness ) and discard the others. Of course you will need to replace the discarded ones with new elements. These will be the offsprings of the survivors. In order to obtain an offspring we will take two random fellows from the previous generation and combine their characteristics(chromosomes). This process is called crossover and it's basically the same like in biology. For example the color ,of your eyes represent the result of the crossover of your parents chromosomes that are in charge with the "color of the eyes" characteristic. You've got the idea. The process of crossover basically represents taking a part of one parent chromosome and the other from the second parent and concatenating them to obtain the offspring chromosome. A chromosome is made of genes so, if let's say you represent your chromosome like an array, a gene will be the value from the ith position.

Now, during the process of crossover, mutations can appear. A mutation represents an anomaly in the process of crossover when a gene, or maybe more, ends up with an arbitrary value which is not present in any of the parents. Mutations are very important because they help you explore other areas of the solutions space although that characteristic was not present in any of the ancestors of the present population. You will need to specify the mutation rate, which represents the percentage of mutation occurrence.

So until now we have the following keywords that you should know when talking about genetic algorithms :

Population - the collection of elements that represent the solution to your problem
Fitness - a value which tells how close from the desired solution an element is
Chromosome - an entity which describes a characteristic of an element
Crossover - the process of combining two chromosomes to obtain another
Mutation - an anomaly occurring during crossover, which modifies the resulting chromosome with a random value.

The hardest part in applying genetic algorithms, at least in solving puzzles, is describing the solution in a programmable manner and even harder then this finding the function to calculate the fitness of an element.

Now, in my case, i found that a good approach is to describe the solution like a series of rotations for each group. The condition was to keep the first group pointing out in the same direction every time. Keeping this in mind i found the following notations :

0 - rotating the group to point forward
1 - rotating the group to point to the left
2 - rotating the group to point backwards ( or at me )
3 - rotating the group to point to the right
4 - rotating the group to point up
5 - rotating the group to point down

The reference position was 0. So i am keeping the first group pointing forward all the time.

I forgot to say that the cube's dimensions were 3x3x3.

Regarding the function to calculate the fitness here we go:

First i needed to find the constraints :

- i couldn't make the same rotation twice for two adjacent groups. Because having only groups with lengths pf 3 and 2, rotating both in the same direction would have exceeded the bounds of my cube (3x3x3).

- the rotations could be made by x , y , or z axes. So using the notations above, rotating by x axis i could only go into 0,2,4 and 5 positions , rotating by y axis 0,1,2 and 3 and rotating by z axis 1,3,4 and 5.
More clearly axis x is represented by 1 and 3 positions , axis y by 4 and 5 and axis z by 0 and 2.
When i'm rotating by an axis i cannot access the positions assigned to that axis so when i am rotating around x i cannot go into 1 or 3 positions.
The next rotation will be done by the axis assigned to my current position . So if my current position is 4, this means that the rotation for my next group will be by the axis y . As you can see the first constraint is covered by this one , so i will only have to worry about the next axis i am going to rotate by.

- the last but certainly not the least. The smaller cubes cannot overlap.

So i have3 constraints that can be reduced to two. Quite OK I'll say.
My plan is to use the second constraint when generating the population. So i am generating only elements that respect the bounding of 3x3x3 but there will be some overlapping. Anyway i will eliminate from the start the unreasonable cases. In order to generate a solution i iterate through every group and based on the previous position I pick a random position from the subset of allowed positions taking care not to break the second constraint. As i have said earlier, the first group always points forward so each generated solution will start with 0.

Now i know how i am going to calculate the fitness . The fitness is the number of groups unhandled because some constraint has been broken. So the function that calculates the fitness will check if the cube dimensions were exceeded or an overlapping occurred and return the number of groups that remained unhandled. In order to check for overlapping I've used a tridimensional matrix, marking the positions already occupied.

After some coding i am able to run the program. Of course it doesn't work from the first shot, but after some debugging I'm ready to go and YES! .. with a starting population of 50000 and a mutation rate of 0.01 in less then 10 seconds i had the solution . Actually they were two, depending from which side i was starting. Of course i needed to run it twice in order to get both solutions. It was pretty fun.


So if i were to derive a recipe for solving puzzles with genetic algorithms here it is:

1. Analyze the problem and think if employing genetic algorithms will actually help or not.
2. Find a way to describe the solution in a programmable manner.
3. Find the restrictions the solution would need to respect and think about a way to implement them.
4. Find the best way to generate the first population. When I'm saying "best" I'm referring to the fact that the fittest each member of the first generation is, the higher the changes to reach success quicker. Try to eliminate the unreasonable elements from the beginning.
5. Find out what fitness represents in the problem's context.
6. Create the function to calculate the fitness.
7. If you've covered the previous six points you can start coding. Design your program to fully obey you. Implement the function to generate a new member, and the crossover. You will also need some statistics like the average fitness, the best fitness, the best member...
   
8. After coding is finished maybe you will need to play a bit with the population number and the mutation ratio to find the most efficient combination. Finding a solution can take from a few seconds to maybe a few hours or more depending on the problem complexity and of course on the way you've thought the program.