Collective Intelligence: Ants colony solving TSP

According to wikipedia:

“Collective intelligence is a shared or group intelligence that emerges from the collaboration and competition of many individuals and appears in consensus decision making in bacteria, animals, humans and computer networks”.

This article describes, how to make the ants, find the solution for TSP problem. Implemented in Python. Get the source from GitHUb.

The algorithms based on the collective intelligence have some “interesting” properties:

• decentralization
  
• parallelism
  
• flexibility, adaptability
  
• "robustness" (failures)
  
• auto-organization

These algorithms are inspired by the nature. Here are some examples of collective intelligence which can be observed in the nature:

1. The swallows settle on wires before they are taking of for the next destination. There is no leader in the group. The decision whether to take of is taken collectively. The probability for the swallow to take of is getting higher when there are more swallows in the air. If the other swallows do not join, the swallow will again settle down on the wire. At one point the number of the swallows in the air reaches the “break-point” when all the swallows decide to take of.
   
2. The bees perform a special “dance” to show their peers where the foot-source is. This dance gives the information about the angle of the food source position with respect to the sun. All the bees do perform the dance when coming back in, which makes the algorithm adaptive.
   
3. When the ant founds food, he lays down a "positive pheromone" on his way back. This pheromone evaporates during the time. The other ants sniff for this pheromone when choosing their route and prefer to go in places where the concentration of the pheromone is higher. The shorter the path to the food source is, more pheromone stays on the track before it evaporates. The more pheromone there is, more ants take this path. When there is a obstacle in the route – the algorithm adapts easily to knew situation. Again the shortest route to evict the obstacle is chosen in the shortest time. Some details here.

There exist several applications of collective intelligence in engineering and optimization. The ants example has applications specially in routing. One of the basic problems which can be solved using an Ant colony is Travelling Salesman Problem.

Travelling Salesman Problem

Travelling Salesman Problem is a classical problem in the field of graph theory. Given n cities the salesman has to visit all of the nodes, come back to his starting location and and minimize traveled distance. Although the problem is NP - hard, several heuristic algorithms exists which obtain suitable results in polynomial time.

Ant colony algorithm for TSP

Ant colony algorithm was introduced in year 1997 by Italian researcher Marco Dorigo.

On the beginning the ants start to explore the graph. They choose their nodes randomly, until they visit all of the nodes. A this point the ant starts to copy his path back to his starting point. While he copies the path, on each edge he lays down certain amount of pheromone inversely proportional to the length of the tour. When each ant starts new route in each node he will compute the probability to choose an edge to continue his route. The probability of choosing edge e in each step is computed as follows.

• π_e  corresponds to the value of pheromone on the edge e.
  
• η_e corresponds to the quality of the route. We can estimate this value by the length of the edge η_e = 1/d_e where d_e is the length of the edge.
  
• J_e is a set of all the edges which the ant can use for his next step - includes all the edges except the one for which we compute the probability.
  
• α and β are coefficients used to manage the impact of the length of the finished route to affect the decision other ants.
  
• The amount of pheromone given to a certain edge is l = 1/routeLength^k, where k is a coefficient to amplify the impact of the length of the route to the decision.
  
• During the time the pheromone evaporates on the edges. The evaporation can be expressed as: π_e = (1-ρ)π_e

The implementation in Python

Most of what I have learned and presented here was done during Collective Intelligence intensive course at Telecom ParisTech done by Jean-Luis Dessales, being part of the Athens program. The implementation was done in Python but as a module to a EvoLife program, which is a custom tool developed by Jean-Luis Dessales for scientific observations on genetic algorithms and collective intelligence algorithms. I have decided to make a stand-alone python program by taking the important bits out just for the Ants colony algorithm. I do almost never work in python, so for anyone out there if you see any big wrongdoing against the python culture, naming conventions etc, let me know.

The most important bits are in the Ant class.

self.Action = 'SearchNextNode'
self.Node
self.Path = []
self.PathLength = 0
self.ToVisit = []
self.Visited = []

The Action field remembers the Ant’s actual state. Each action has a corresponding method associated with it. The Node field holds the actual field. In ToVisit and Visited the ant stores the Nodes that he had already visited or that he needs to visit in order to achieve TSP completeness. Here is the “move” method which is called repetitively for each ant:

def moves(self):
#here is the ants move - one of the following actions is always selected
if self.Action == 'GoToNode':
self.goToNode()
if self.Action == 'SearchNextNode':
self.searchNextNode()
if self.Action == 'ReturnToStart':
self.returnToStart()
if self.Action == "GoToFirst":
self.goToFirst()

The most important of these method is searchNextNode, where the ant searches for his next edges to explore. In this method the behavior described in previous paragraph has to be defined.

def searchNextNode(self):
nodeindex = self.Node.Id        
#the maximal probability
pMax = 0
p = 0

#Try to select the best node by the pheromones in the direction
#have to iterate over all nodes
for i in range(NbNodes):
if i!=self.Node.Id and self.Visited[i]==0:
d = Land.Distances[self.Node.Id][i]

#get the value of pheromon on the edge
pi = Land.Edges[self.Node.Id][i]

#To prevent division by zero and get some info
#when d = 0 there would be problem in computation of d
if d==0:
print i
print self.Node.Id

#the quality of the route
nij = 1/d

pselected = math.pow(pi,alfa) * math.pow(nij,beta)

#normalization
#compute the sum of other options
sum = 0
for j in range(NbNodes):
if j!=self.Node.Id and self.Visited[j]==0 and j!=i:
dj = Land.Distances[self.Node.Id][j]
pij = Land.Edges[self.Node.Id][j]
nj = 1/dj
pj = math.pow(pij,alfa) * math.pow(nj,beta)
sum+=pj
if sum>0:
p = pselected/sum

#if we have a new best path - then remember the index
if p > pMax:
pMax = p
nodeindex = i

We have to iterate over all the neighbor nodes in order to choose the right one. For each node the probability of taking the edge going to this node is computed according to the formula given in previous paragraph. Some remarks: the value of the pheromone on each edge is stored in a global array:  Land.Edge[nodeFrom][nodeTo]. Also the distances between all nodes are pre-calculated in Land.Distance[nodeFrom][nodeTo].

There is quite a lot of code, regarding the visualisation. The TkInter library was used for drawing. Also the PIL library has to be installed. It should not take too long the figure out the responsibility of each class.

The results

Here is how the resulting program looks like:

And here is the evolution of creating the final decision. First all edges have some amount of pheromone and during the time, the preferred edges are chosen. Because the ants choose the edges randomly on the beginning, the result is never assumed the same. The following three images show the evolution which resulted in quite not optimal solution.

The quality of the solution depends heavily on the values of the coefficients. These values can be changed in the Program.py file:

#level of pheromone to show
PToShow = 0.004
#factor which lowers the value given to a path on function of the paths length
k=1
#evaporation factor
theta = 0.07
#parameter which amplifies the value of the pheromon on the edge (pi^alfa)
alfa = 4
#parameter which amplifies the impact of the quality of the route  ni^beta; ni=1/de
beta = 2.5

Putting aside the coefficients described above, there is also PToShow value, which determines what is the minimal value of pheromone on the edge, in order for the edge to be dotted in the picture.

Before this implementation, I had one before – which was not at all efficient but quite funny. In this implementation the ants, could move freely around – there was no notion of edges. The ants simply took a directions towards a certain node and when they got close enough to it, they considered the node as reached and continued for the other one. This was useless, but I saved these funny graphics with the ants moving all around:

And the ants finding the solution:

The source code

Download it here.

As said before, the source was created as a module to a larger program and later taken out to be executable isolated. Therefor there still is quite a lot of refactoring which could be done, but I do not consider it necessary, since the purpose is merely to present the Ant colony algorithm.

CodeProject

Graph theory in Latex

For one of my previous posts, I needed some images of graphs. Initially I have taught, that I will just draw them in Inkscape or some other tool, but after a while I have decided to do something more clever – which might maybe serve me in the future – draw the graphs in Latex. After a quick search I have found this blog:

http://graphtheoryinlatex.wordpress.com/ and older posts from the same author: http://graphtheoryinlatex.blogspot.com/

This blog is about drawing graphs in TeX. So what do you need:

TikZ – a graphic system for Tex

Tkz-graph – style with basic graph drawing macros.

Tkz-berge – style with more complex drawing – such as predefined graphs (full graphs, bipartite graphs, grids etc.)

Some TeX editor. I am using Inlage. Which is not expensive and takes care for downloading all the necessary packages.

So here are the graphs and variants which I have used in the previous post:

Graph with 4 edges in a circle:

\begin{tikzpicture}
\GraphInit[vstyle=Welsh]
\SetGraphUnit{2}
\Vertices{circle}{A,B,C,D}
\Edges(A,B,C,D,A,C)
\SetVertexNoLabel
\end{tikzpicture}

Coloring some of the nodes:

\begin{tikzpicture}
\GraphInit[vstyle=Classic]
\SetGraphUnit{2}
\Vertices{circle}{A,B,C,D}
\Edges(A,B,C,D,A,C)
\SetVertexNoLabel
\AddVertexColor{red}{B,D}
\AddVertexColor{green}{A}
\AddVertexColor{blue}{C}
\end{tikzpicture}  

 

Graph with labeled edges

\begin{tikzpicture}
\GraphInit[vstyle=Welsh]
\SetGraphUnit{2}
\Vertices{circle}{A,B,C,D,E}
\SetUpEdge[style={->}]
\Edges[label=1](A,B)
\Edges[label=1](B,C)
\Edges[label=1](C,D)
\Edges[label=$1$](D,E)
\Edges[label=x1](A,C)
\Edges[label=x2](A,D)
\Edges[label=x3](A,E)
\SetVertexNoLabel
\end{tikzpicture}

Graph with positioned vertices.

Using the EA, NOEA and similar macros (EA = East of first vertex define the second vertex, NOEA = Northeast of…)

\begin{tikzpicture}
\SetGraphUnit{2}
\GraphInit[vstyle=Normal]
\Vertex{S}
\NOEA(S){A} \SOEA(S){B}
\EA(A){T1} \EA(B){T2}
\SOEA(T1){F}
\Edges[label=1](S,A)
\Edges[label=1](S,B)
\Edges[label=4](A,T1)
\Edges[label=2](B,T2)
\Edges[label=1](T1,F)
\Edges[label=1](T2,F)
\Edges[style={pos=.25},label=3](A,T2)
\Edges[style={pos=.25},label=2](B,T1)
%Could use this for bending%
\tikzset{EdgeStyle/.append style = {bend left}}
\end{tikzpicture}

Bipartite graph using the berge styles:

\begin{tikzpicture}
\grCompleteBipartite[RA=4,RB=3,RS=6]{2}{2}
\end{tikzpicture}

For now I am content that I have found this blog and actually I have to say, that drawing graphs in TeX is much easier than I have expected.

Applications of Graph Theory

Graph Theory is just a beautiful part of mathematics. Not only Computer Science is heavily based on Graph Theory. There are a lot of applications of Graph Theory in Operational Research, Combinatorial Optimization, Bioinformatics.
For my personal clasification I have separated the tasks, which you can solve using Graph Theory into two groups:

• Obvious applications – I mean, that the analogy between the graph and the problem is quite easy to imagine (maps, cities, relations etc.). In this post you can find the following:
  • Vehicle Routing Problem
    
  • Graph coloring
    
  • Map coloring
  
  
• Hidden applications - Tasks which you would never assume can be solved using Graph Theory. Than you see one of them, and than you think: “Wow, I wonder who came up with that one…”. I will provide the following ones in this post:
  • Image or 3D model reconstruction from projections
    
  • Prove of NP hardness of Integer Linear Programming
    
  • Register allocation
    
  • Approximation of data, data compression
    
  • Task scheduling
  
  

Obvious applications

Here are some examples of problems for which the creation of the graph to model the problem is quite easy and obvious.

Vehicle routing problem and other variants of TSP

There is a whole set of problems, which are just variations of Traveling Salesman Problem. Vehicle Routing Problem (VRP) can be characterized by following description:

• We are provided with a set of trucks, each of a certain capacity
  
• Set of customers, each with certain need of the goods
  
• The central repository, where the goods are stored

The tasks is to root the trucks, to distribute the goods to the clients and minimalize the distance. I have written a blog and a web utility which is able to solve the problem using two algorithms:

• Clark & Wright Savings Algorithm
  
• The Sweep Algorithm

You can find more algorithms for solving VRP here.

Graph coloring problem

Given a graph, we want to decide, whether it is possible to color each of the vertices in the graph in such way, that none of the vertices which are sharing and edge have the same color. Many real world problems can be formulated as Graph coloring problem. Ne first one of the Map coloring.

Map coloring

One of the first application is the map coloring problem. It has been proven, that each map can be colored using 4 colors. This problem can be converted to graph coloring problem by placing the vertex inside each country or region in the map. Two vertices are connected if and only if the two countries have a common border. More over here.

Hidden applications

There are tasks and problems for which you would not intuitively search the solution by applying graph theory. Here are some of them:

Image reconstruction from X-Rays – Computer tomography.

Tomography is a technique used to reconstruct an image or 3D model from series of projections, subsequently taken from different angles. When using technologies such as the x-rays, the image take from an angle gives for each pixel the total thickness of the scanned object. The questions is than how to reconstruct the image from several taken images which are containing only the thicknesses.

As described in great book "Network Flows – Theory, Algorithms and Applications”, concrete example of computer tomography is the “Reconstruction of the Left Ventricle from x-Rays projections”. This problem can be solved using the application of network flows theory. This method is applicable only to problems where the scanned object has a uniform structure. As mentioned in the book this assumes that the well-working Ventricle is filled uniformly with blood and dye mixture.

The following graphics was taken from the book. It explains the method on two dimensional image. Using two projections of the project, we obtain vectors which are containing for each pixel (or other unit) the probable mass hidden behind this pixel. Now is up to us to find out how this mass is distributed  - that means where are the ‘1’ in the picture. The more projections we have, the better results we can obtain.

The problems is thus simplified to the problem of constructing binary matrix from the projection sums. This problem is a special case of the feasible flow problem.

The following image shows similar very simplified task, which I have taken from the Combinatorial Optimization course offered as part of Open Informatics program at CTU Prague.

The whole problem can be seen as the question of finding the feasible flow in a network (G, b, u, l,c). So what does network consist of:

• Graph G
  
• s – sources – the nodes which provide the fluid into the network – the nodes with positive values
  
• t – appliances (or sinks) – the nodes which consume the fluid – the nodes with negative values
  
• u – upper bound for the flow of each edge
  
• l – lower bound for the flow of each edge
  
• c – the actual flow in each edge – the one for which we are looking. The task is to find the values of c for each edge, in order to satisfy all sinks.

Here is the graph G which corresponds to the projections sumR and sumC from the previous image. Each edge in the graph corresponds to one pixel, connecting the two projections. The sumR are being sources in this network and the sumC edges are sinks.

For each edge the lower bound l(e) = 0, upper bound u(e) = 1 and we are looking for values of values of c(e), in order to for the flow to be feasible and also minimal. The edges which are used in the feasible and minimal flow are pixels which will have ‘1’ value in them.

Proving NP’s ness of some problems such as Integer Linear Programming

The graph coloring problem has been already mentioned above. We are trying to color each node of the graph in such a way, that nodes with same color cannot be connected by an edge.

Integer Linear Programming (ILP) is NP-hard problem. This can be proven by the polynomial reduction of Graph coloring problem to the ILP problem. Concretely we can say, that for each graph which can be colored using 3 colors, we are able to construct an ILP problem, which has a solution. From the theoretical point of view saying “we are able to construct” means that there is a polynomial reduction of Graph coloring problem to ILP problem. Polynomial reduction proves that:

1. If Graph Coloring is NP-hard problem, than ILP is also NP hard problem.

Polynomial reduction has to satisfy two conditions in order to prove the NP-hardness:

1. The reduction algorithm – the construction of one problem from another has to be performed in polynomial time
   
2. For each instance graph which can be colored with 3 colors an instance of ILP can be constructed which has a solution

Here is the reduction algorithm (the algorithm which explains how to define an ILP problem to given graph):

In the beginning we have a graph colored using 3 colors. We will try to create an instance of ILP out of this graph. That means we have to define the variables and the equations which build the ILP problem. We can do this in 3 steps.

• Create N variables x_ncolor == 1 <=> the node n has the color c, where N is the number of nodes. 
  
• For each node in the graph add en equation to the ILP system:
  • x_nred + x_nblue + n_ngreen = 1
• for each edge e = {n_i, n_j} in the graph add following three equations in the system: 
  • x_nired + x_njred <= 1
    
  • x_niblue + x_njblue <= 1
    
  • x_nigreen + x_njgreen <= 1
  
  

Here is an example, we have an simple graph:

Now the first set of equations, which states, that each edge can have at most one color:

The following set of equations, which states, that nodes sharing edge cannot have the same color:

Now because the ILP problem can be reduced to graph coloring problem, we know, that this problem has solution, when the graph can be colored with three colors. Here is the solution:

Which corresponds to:

The coloring of the graph is NP hard, so also ILP is NP hard. If you wonder how to prove that NP graph coloring is NP hard: there is a polynomial reduction from one special type of SAT problem.

Register allocation

Register allocation is the process of assigning possibly infinite set of variables of assembly program to a finite set of registers which are available in the processor. Not all variables are used at the same time, so several variables can share a register (if not this mapping would not be possible). Even this problem is solved using graph coloring. For each variable a vertex is created. Vertices are connected if variables “live” in the program at the same time. The number of colors given to color the graph is equal to number of registers.

Approximation of the data – data compression

This technique is used in order to approximate the data which has to be stored while minimizing the loses of precision.

For example a data which represents taken temperatures during the time and builds a nice graph. However if this data was taken at high frequency, there might be too many records. The idea is to minimize the number of records, while keeping most of the information about the evolvement of the temperature.

The shortest path algorithm can be used to solve this problem. For instance the blue line in the following graphics represents the data to be stored. It is 10 values: the time x and Temperature( x) at the time x. The green and red line represent possible approximations, when we are leaving out one or two nodes. Of course there are several nodes which can be left out and the shortest path algorithm can help us to find which ones can be left out.

We can construct a full graph, which will contain 5 nodes, representing the 5 data points (the times x). Each edge represents the “precision loose” which we pay, when we take the direct path between the two nodes of the edge instead of passing the traditional way. The following picture represents the partial graph – the skipping edges start only in the first node ( A ). The edge with value x1 corresponds to the red line in the graph etc. The graph should be also filled with other edges starting in B and C (the only edge going from D to E is already present and there are no edges starting in E), but I have left them out for simplicity.

 

So without compression  we have the simple path: A,B,C,D,E = 1 + 1 + 1 + 1 = 4

Taking the red edge and the rest of the path: A,C,D,E = 1 + 1 + 1+ x1

Taking the green edge and the rest of the path: A, D, E = 1 + 1 + x2

The values of the edges in the standard path should be the lowest (here all of them have value 1). On the other hand values of edges which will make us loose more precision should be the greatest. Then of course we can introduce some bonus to motivate the algorithm to take less edges (better compression). All this constraints can be modeled using heuristics.

One possible heuristics to evaluate the value of the edge is to measure the distance between the real data and the estimated date. For instance the value of the second point is 5. If we estimate the value using the red line (leaving out the second point) the corresponding value on the red line is 3. The distance between these two values is: 2.

If we use the the green line instead then the distance between the estimated value f’( x) and the real value f( x) is 1. On the other hand the green line also estimates the second point 3 point. And we see that the distance for the second point will be more or less 1.5. So we should add these distance together. So we get:

x1 = 2

x2 = 2.5

This is just a proposition. We could also multiply it by some coefficient to obtain some reasonable results.

With the developed and evaluated graph, finding the shortest path in the full graph from the node A to the node E will give us the best “size/precision” ratio.

Task scheduling

In this problem we have a group of workers and group of tasks. Each task can be processed by each worker. However the workers do not have the same performance on all tasks – the time for the processing of each task differs for each worker.

Let’s take a look at very simple example, we have two workers (A,B) and two tasks (T1,T2). The values in the table represent the processing time, that the worker needs for the given task.

This can be solved as finding the cheapest flow in the following graph.

Not that each edge has two values: u/c. The ‘u’ represents the capacity of the edge – it is always one. The ‘c’ represents the cost of the edge. Finding the cheapest flow in this graph from S to F will give us the best assignment of workers to tasks.

Other interesting applications

• Development of custom processors for minimization of resources – data path optimization.
  
• Scheduling on parallel processors – application of maximal flow finding problem.

Vehicle Routing Problem

One of my school assignments this semester was to implement some of the algorithms which solve the Vehicle Routing Problem.

UPDATE: I have moved the source code to GitHub. Get it or fork the project.

In VRP you have a depot and a set of customers. You have a fleet of vehicles which can serve this customers. Each customer can have an exact demand on quantity of goods and each vehicle can have capacity which is able to serve. This is easily modeled as Graph Theory Problem. The problem is NP hard. However there are several algorithms described for this problem (heuristics,genetics). To know more about variants and different solutions check this source.

I decided to implement Clarks & Wrights and Sweep algorithm. I build my solution in JAVA but later I decided that it would be cool to have some way to visualize the results. Then I decided to use GWT-MAPS API to visualize real world problems. Soon I wanted also to visualize the random generated graph problems so I included the GWT-INCUBATOR API to show some small graphs.

Check the program here

Basic functions

• Compute the routes using Clark & Wright or Sweep algorithm
• Generate random VRP - including distance matrix, node positions and demands of each node
• Compute distance matrix from real world data using Google MAPS API

Basic usage
The input for this utility to compute the vehicle rows has to be specified as follows:

[route count]
[distance matrix]
[customer demand;address;x coordinate;y coordinate]

After loading the site you can see example problem of 3 customers. You can run Clark & Wright or Sweep algorithm and you will obtained the routes of the VRP in the OUTPUT window. Before running the algorithm you should set the capacity of the vehicles - in this situation all the vehicles have the same capacity. The output has the following format:

[number of routes]
[depo city1 city2 ... cityN depo]
...
[depo->city1->city2 ... cityN->depo]
...

You can visualize the output either on Graph or on MAP - if you working with real world cities and addresses than you visualize on map. If you are working just with sample data the you can visualize on the graph.

Generating distance matrix for real world cities
To generate the distance for several cities for which you know only the addresses u will enter in the INPUT box on each line one city and then click on "Generate distance matrix". Also you can see that on the MAP tab all the routes network connecting all the cities has been visualized:

Now you need to modify the input - more specifically modify the amounts of goods requested by each city. The DEPOT is always in the first city, so there the demand would be zero. Let's say your customer in Milano wants 15 units, in Paris 20 units and in Prague 13 units.



Now again you can just run the desired algorithm and view the results. For example after running the Clark & Wright algorithm you should get the following output:



Now you can visualize these routes in the MAP.


Generating and visualizing random problem
To generate random GRAPH VPR Problem you have to specify:

- Number of nodes.
- Constant by which the random value(0-1) would be multiplied to obtain desired amount for each city.
- Constant by which the random value(0-1) would be multiplied to obtain random coordinates of the city.

After you will obtain the desired INPUT.



Now you can run one of the algorithms(eg. SWEEP) and you will obtain the OUTPUT - the routes of the vehicle.



Now because this is randomly generated problem it is good to visualize it in the GRAPH:


THE ISSUES
The clear method of the canvas to visualize the points is not working fine - generating new VRP problem will not erase the points of the old VRP problem. The main issue is that this application uses the GWT Canvas, which was a part of GWT incubator. It also uses the Google Maps binding for GWT.

Since I have wrote the application there have been several changes in the situation about GWT and plugins:

• Canvas is now part of the GWT 3. So theoretically the application could be rewritten using GWT 3.
• Google Maps are now in version 2. However the GWT binding for Maps v3 has not yet been released – there are however some open-source initiatives.

So  what to do now? I have kept the code as it is: using maps v2 and the ancient Canvas project. If anyone feels motivated for moving the application to GWT 3 (changing Canvas and Maps binding) just fork it away on GitHub.

About the source code

On GitHub you can currently download two packages:

• Java-only package. That is a basic library and executable program which can solve the VRP without the visualization.
• GWT packages. Contains the classes which perform the VRP solving and the visualization using GWT.

The classes from the Java-only package are copied to the GWT project. That is because they have to be presented at compile time – the classes cannot be included as a JAR file. If anyone knows how to reuse a code in GWT projects without doubling it – let me know.

The  code is of a very poor quality. At time when I have wrote it I simply did not care about the readability and also I did not know Java that well.