algorithm - 蚁群算法的怪异行为

我开发了aco算法。我认为它无法正常运行...这将很难解释，但我会尽力而为。

问题在于信息素水平是 float 的。我认为，必须越来越多地增加最佳路径上的信息素水平，但是在我的程序中却没有。
Optimal path是一条路径，它是通过在起始顶点和目标顶点之间的边缘上找到最大信息素水平而构建的。

例子:

1 5 3
4 5 10
0 0 0

Optimal path将是1 -> 2 -> 3。

权重矩阵:

 0 3 10
 0 0 3
 0 0 0

最佳路径是:1 -> 2 -> 3 (length: 6)另一条路径(不是最佳路径):1 -> 3 (length: 10)
10只 Ant 后的信息素水平:

0 5 1
0 0 3
0 0 0

最佳路径:1 -> 2 -> 3
20只 Ant 后的信息素水平(另加10种):

0 1 5
0 0 1
0 0 0

最佳路径:1 -> 3
30只 Ant 后的信息素水平:

0 4 1
0 0 3
0 0 0

最佳路径:1 -> 2 -> 3
30只 Ant 后的信息素水平:

0 4 6
0 0 2
0 0 0

最佳路径:1 -> 3
这只是一个例子，但是它代表了我程序中信息素矩阵的样子。

我的程序的伪代码:

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
}

那么，为什么我程序中的信息素水平会 float ？最佳途径为什么没有大多数信息素水平？我了解此算法中存在概率因子，但是无论如何它都必须显示正确的结果。

我在程序中正在做什么？ Here，您可以找到我程序的完整主循环源。

1)Main cycle是一个循环，直到有任何可用于当前迭代的 Ant 为止。

1.1)在这个周期中，我有another cycle(内部周期)，它将被触发直到当前 Ant 有顶点要去(它们不能被当前 Ant 访问)。

在内部循环中，我这样做:

1.1.1)Calculating denominator of the equation below

该公式将计算选择ij路径的概率(i是当前节点，j是下一个节点)。

代码:

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

另外，我将所有概率添加到一个区间中，这将有助于我决定选择哪个顶点。

代码:

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

代码:

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

如果是的话(这意味着该 Ant 找到了目标顶点)，我正在这样做:

1.1.5.1)Getting length of current ant path

代码:

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

代码:

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:

代码:

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

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

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

最佳答案

选择遵循的路径时，您的代码始终选择随机阈值以下的第一个相邻顶点。我不确定这应该如何表示 Ant 向具有更多信息素的顶点移动。此方法将在信息素浓度相对较低(低于0.5)的区域中起作用。但是，在信息素浓度较高的区域中 (接近或高于1)，因为您的random()号在0到1之间，所以您将回到，始终选择第一个可用的顶点。这可能就是为什么您不收敛的原因。

关于algorithm - 蚁群算法的怪异行为，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23630596/