Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Strange behaviour of ant colony algorithm

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;
    }
}
like image 961
Sharikov Vladislav Avatar asked May 13 '14 11:05

Sharikov Vladislav


1 Answers

When picking the followed path, your code always select the first neighbouring vertex below a random threshold. I'm not sure how this is supposed to represent ants going towards vertices with more pheromone. This method will work to a degree in area where pheromone concentration is relatively low (below 0.5). However, in areas where pheromone concentration is high (near or above 1), because your random() number is between 0 and 1, you will be back to always picking the first available vertex. This is probably why you do not converge.

like image 171
zeFrenchy Avatar answered Oct 17 '22 21:10

zeFrenchy