Strange behaviour of ant colony algorithm

Question

I developed an aco algorithm. I think it is not working properly... it will be hard to explain, but I will try.

The problem is pheromone level is floating. I assume, that pheromone level on the best path must be increased more and more, but in my programm it is not.

Optimal path is a path, which is built by finding maximum pheromone level on edges between start vertex and goal vertex.

Example:

1 5 3
4 5 10
0 0 0

Optimal path will be 1 -> 2 -> 3.

Weight matrix:

 0 3 10
 0 0 3
 0 0 0

Best path is: 1 -> 2 -> 3 (length: 6) Another path (not optimal): 1 -> 3 (length: 10)

Pheromone levels after 10 ants:

0 5 1 
0 0 3
0 0 0

Optimal path: 1 -> 2 -> 3

Pheromone levels after 20 ants (10 more):

0 1 5 
0 0 1
0 0 0

Optimal path: 1 -> 3

Pheromone levels after 30 ants:

0 4 1 
0 0 3
0 0 0

Optimal path: 1 -> 2 -> 3

Pheromone levels after 30 ants:

0 4 6 
0 0 2
0 0 0

Optimal path: 1 -> 3

This is just an example, but it represents what the pheromones matrix in my program look like.

Pseudocode of my programm:

init alpha, beta and other coef's

while antCount do
{
    current = start
    // + init visited array for current ant, some others variables

    while vertexAvailable(current) do
    {
        find probabilities to go to 1
            or another vertex

        generate random number, choose next
            vertex depending on it,
            defining nextVertex

        current = nextVertex

        if current == stop then
        {
            get path length

            update pheromones on path of current
                ant depending on path length
        }
    }

    evaporation of pheromones

    antCount = antCount - 1
}

So, why are pheromone levels in my program floating? Why doesn't the best path have most pheromone levels? I understand that there is probability factor in this algorithm, but it have to show correct result anyway.

What I am doing in my program? Here you can find full main loop source of my program.

1) Main cycle is a cycle, which will until there are any ants available for current iteration.

1.1) In this cycle I have another cycle (inner cycle), which will be fired until current ant have vertexes to go to them (vertexes mustn't be visited by current ant).

In inner cycle I do this:

1.1.1) Calculating denominator of the equation below

main formula

This formula will calculate probability of selecting ij path (i is current node, j is next node).

Code:

var denom = 0;

for(col in graph[currentVertex])
{
    // этот цикл формирует знаменатель формулы

    var weight = graph[currentVertex][col];

    if(weight != 0 && visited[col] != true)
    {
        var tau = pheromone[currentVertex][col];

        denom = denom + getAttractiveness(tau, weight);
    }
}

1.1.2) Calculating numerator of the formula above and getting probability of selecting each vertex available from current

Also, there I adding all probabilites to an interval, which will help me to decide what vertex to choose.

Code:

for(col in graph[currentVertex])
{
    var weight = graph[currentVertex][col];

    if(weight != 0 && visited[col] != true)
    {
        var tau = pheromone[currentVertex][col];

        var nom = getAttractiveness(tau, weight);

        var probability = nom/denom;

        intervals[col] = probability+intervals.last;

        intervals.last = probability+intervals.last;
    }
}

1.1.3) Creating random number from 0 to 1 and selecting vertex based on intervals array, defined in previous part of the code

Code:

var rand = Math.random();
var nextVertex = 0;

for(vertex in intervals)
{
    if (rand < intervals[vertex])
    {
        nextVertex = parseInt(vertex,10);
        break;
    }
}

1.1.4) Some instructions, setting helpers (path helper, visited helped) etc

1.1.5) Next step, I am checking if founded vertex is goal vertex

If yes (that means, that ant found goal vertex) I am doing this:

1.1.5.1) Getting length of current ant path

Code:

var length = 0;

while(source = pathCopy.pop())
{
    console.log("dest: " + dest + " source: " + source);
    length = length + graph[source][dest];

    dest = source;
}

1.1.5.2) Updating pheromone level on this path

Code:

var deltaTau = 5/length;
var dest = path.pop();
var source;

while(source = path.pop())
{
    var oldPheromone = pheromone[source][dest];

    // обновление феромона формула 3
    var newPheromone = oldPheromone+deltaTau;

    // console.log('pheromone levels: old =
    //      '+oldPheromone+' new = ' + newPheromone);

    pheromone[source][dest] = newPheromone;

    dest = source;
}

1.2) At the end of main cycle I am doing evaporation of pheromone levels:

Code:

for(row in pheromone)
{
    for(col in pheromone[row])
    {
        var oldPheromone = pheromone[row][col];

        // обновление феромона формула 3
        var newPheromone = (1-ktau)*oldPheromone;

        pheromone[row][col] = newPheromone;
    }
}

Strange behaviour of ant colony algorithm

Answers (1)

Related Questions