A journey in algorithmic. Week 5 – Nature to the rescue - part II

Last week, I provided you with a high-level presentation of neural networks. This week, I would like to introduce you to two nature-inspired optimization algorithms: Ant Colony Optimization (ADO) and Genetic Algorithms (GA).

Ant Colony Optimization (ACO)

To develop their colonies, ants need to find food and then find the optimal path from the food source to the colony. They do this by dropping pheromones in an amount linked to the length of the path they found (the shorter the path, the more the pheromones).  When new ants leave the colony, they are eager to follow a path full of pheromones. They will in turn drop their pheromones, so the path becomes more and more loaded with pheromones, until the food source is empty or no longer reachable (pheromones decay over time).

Figure 1: Principle of the ant colony algorithm

The output of the algorithm is then the path that maximizes the number of pheromones at each step. It can adapt over time if the goal to reach (here the strawberry field) changes.

And this algorithm performs well. Great, now we can help ants find food! But wait a second! The question arises: are there practical applications for this algorithm? Yes, this ACO algorithm and its derivatives can solve some “path optimization” problems such as the Travelling Salesman Problem.

The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route to visit each city exactly once and return to the origin city?".

Figure 2: The Travelling Salesman Problem (TSP)

This problem is a very famous one, as it is one of the most representative “NP – Complete” problems. Don’t worry if you don’t know what this means. All you must know is that the only way to find the optimized solution is to try every combination of cities. Assuming there are N cities, then there are N possibilities for the first city to visit. Then N-1 for the second city, N-2 for the 3rd one, etc. This is the factorial function that I talked about in week 2. And this function grows exponentially, which means it increases faster and faster as N gets bigger. Quickly it becomes impossible to test all combinations in a reasonable time, even on the most powerful computer. In turns, ACO will not find “the” best path, but it will give a fairly good solution in a reasonable time.

That’s all for ACO. Before moving to Genetic Algorithms, let me just mention that ACO is not the only algorithm that mimics the behavior of social animals. There are algorithms based on bees’ behavior for example.

Genetic Algorithms

Let’s now address a last example of nature-based algorithms: “Genetic Algorithms”. As with ACO, genetic algorithms fall in the “optimization algorithms” category.  The idea behind genetic algorithms is that, according to Darwin’s Theory of Evolution, nature provides living beings with a capacity to evolve and adapt to their environments. A DNA code is assigned to everyone. This code fully defines everyone. Therefore, it also defines how everyone will perform in its environment.  Living beings that perform the best will have more chance to reproduce, spreading the most efficient genes.

Let’s develop the reproduction part of this process. So, a man and a woman have both their unique DNA as presented in the following picture (obviously DNA codes are much, much longer sequences than this).

Figure 3: Example of man and woman DNA

When a baby is conceived, his DNA is composed of a mix of the man’s and the woman’s DNA. The mechanism that chooses which part of whom to pick up is called “crossover”. Basically, it randomly chooses a few positions in the DNA to “switch” from one parent to the other, as illustrated below.

Figure 4: Crossover mechanism

We are not totally done with reproduction yet. To explore new solutions, nature sometimes produces mutations. The mutation mechanism is easy to understand. It randomly chooses a DNA position and changes the DNA value at this position.

Figure 5: Mutation mechanism

Ok, we know it works in nature, but how do we transfer it to an “optimization algorithm”? Well, the concept is simple: find a way to represent the potential solution to your problem as a sequence of genes (the DNA code) and design an evaluation function that will associate a score to this potential solution (the better the score, the best fit between this solution and its environment.) Then, run a “Darwin-based evolution engine” that will evaluate candidate solutions, make them reproduce based on their performance, and repeat the process with the next generation until a certain score or time limit has been reached.

Still kind of abstract? Well, let’s go back to the Travelling Salesman Problem. So, first, let’s get a DNA representation for a possible solution. Easy, let’s just take the sequence of cities to travel to. What about the evaluation function? Easy again: Just take the length of the path through all these cities.

It is a little bit tricker for the crossover mechanism. If we applied the standard mechanism we just presented above, we would have “children” that are not valid solutions because the same city could appear two times as shown below.

Figure 6: Standard crossover produces invalid solutions for TSP

To solve this issue, the crossover mechanism has been modified as follows. For simplification, let’s assume there is only one crossover position (il also works with more but the explanation is simpler with one). Let’s say we start with the father DNA. When the crossover position is reached, we then take the first city of the mother that is not already in the baby DNA, then the second city, etc.

Figure 7: TSP specific crossover mechanism

For mutations, we encounter the same issue: if we apply the standard mechanism, we replace a city with another one that necessarily is already present in the solution. The solution is to have a mutation mechanism that randomly switches the position of two cities.

Wow, it is magical! There seems to be no limit … Is that so? Let’s see if it works with Sokoban.

Application of Genetic Algorithms to the Sokoban game.

Remember two weeks ago, when I challenged you with the development of a Dijkstra-based Sokoban solver?

Figure 8: Example of a Sokoban level

Well, I couldn’t resist but develop one myself in Python3. I spent a lot of time making it work and then optimizing it. I used it on a few simple examples with 2 to 4 boxes and the result was amazing: the algorithm issued the best solution in less than a second! Perfect, I nailed it! No need for little ants, electronic brains nor for Darwin.

I ran it on examples with bigger boards and with more boxes and it made me sad. The performance dramatically declined: 1 minute with 5 moves, 1 hour with 6 boxes. And, after one day, I am still waiting for the result for 7 boxes! Imagine how many light-years will be necessary to solve the problem in the above figure? This comes from the fact that the Dijkstra based algorithm goes to all the possible states, a state being a position for Sokoman and for each of the boxes. And the number of states increases exponentially with the number of cells and the number of boxes, as for the Travelling Salesman Problem.

What to do now? Give up? No! Since it worked for TSP, why not try Genetic Algorithms on Sokoban? Remember that the problem is to find a list of moves (up, down, right, left) for “Sokoman” to put every box on a collection point. It is quite straightforward to build a DNA-like representation of a potential solution as a list of moves.

Figure 9: Human DNA sequence vs Sokoman’s list of moves

Great, we’ve got our DNA-like encoding! And since we do not have the same constraint as for TSP (It is possible to change a move independently of the others), standard crossover and mutation mechanisms apply. Last thing to do, find an evaluation function!

Let’s think: the purpose of the game being to have every box on a collection point, it naturally came to my mind to evaluate a potential solution as the maximum number of boxes on collection points that can be found on a situation along “Sokoman” travel.

It turned out that it did not work at all: too many candidate solutions were given the same score, so the selection process was inefficient. My second idea was to use a smoother distance function as the sum of the from each box to the nearest collection points and the distance of a collection point to its nearest box. A winning solution would be one with distance 0.

And it did not perform much better. I looked for bugs in my code, tried to tune some parameters, but nothing. I couldn’t understand why it did not work until I found the following Sokoban puzzle.

Figure 10: Sokoban puzzle where all boxes are on collection points except one

For this puzzle, all boxes are on collection points, except one that is at a distance 1 of the last collection points. So, the total distance is 1. Only the winning solutions would do better. So once again, the evaluation function gave the same score to all solutions, except if, by pure chance, we find the right one.

To sum up…

What I wanted to illustrate with the few paragraphs above is that the performance of a genetic algorithm strongly depends on the accuracy of the evaluation function. We did not illustrate it, but this is also true for the way the potential solutions are coded as DNA-like sequences. For Sokoban, I could not find a good evaluation function, but I am still fighting for it! Try if you want …

For complex problems where all combinations must be explored (we will discuss complexity in a few weeks), exact problem solvers work fine when the size is small, but their computation time quickly become out of control when the size increases. Reciprocally, adaptative algorithms such as ACO or Genetic Algorithm do not necessarily provide the best solution to the problem, but its computation time remains reasonable when the complexity increases.

Using one of the others is a question of what you expect. If you want to solve a Sokoban puzzle, you are only interested by “distance 0” situations. All “good” situations (distance 1 or 2) are of no interest. Conversely, if you are facing the Travelling Salesman Problem (TSP), I guess you don’t necessarily need to find the best solution; any solution is fine if you come home before dessert 😊.

That’s it for this week, and I hope you enjoyed it. Next week, we will continue our exploration. I will present you some interesting “problem specific” algorithms!