蚁群算法的奇怪行为

Question

我开发了一个aco算法.我认为它不能正常工作......很难解释,但我会尝试.

问题是信息素水平浮动.我认为,最佳路径上的信息素水平必须越来越高,但在我的程序中它并非如此.

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只蚂蚁后的信息素水平:

0 5 1 
0 0 3
0 0 0

最佳路径: 1 -> 2 -> 3

---

20只蚂蚁后的信息素水平(10多个):

0 1 5 
0 0 1
0 0 0

最佳路径: 1 -> 3

---

30只蚂蚁后的信息素水平:

0 4 1 
0 0 3
0 0 0

最佳路径: 1 -> 2 -> 3

---

30只蚂蚁后的信息素水平:

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
}

那么,为什么程序中的信息素水平会浮动？为什么最好的路径没有最多的信息素水平？我知道这个算法存在概率因素,但无论如何它必须显示正确的结果.

---

我在我的课程中做了什么？在这里,您可以找到我的程序的完整主循环源.

1)主循环是一个循环,直到有任何蚂蚁可用于当前迭代.

1.1)在这个循环中,我有另一个循环(内循环),它将被触发,直到当前的蚂蚁有顶点去它们(当前的蚂蚁不能访问顶点).

在内循环中,我这样做:

1.1.1)计算下面等式的分母

该公式将计算选择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)计算上面公式的分子并获得从当前选择每个顶点的概率

此外,我将所有概率添加到一个区间,这将帮助我决定选择哪个顶点.

码:

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)创建从0到1的随机数,并根据intervals在前一部分代码中定义的数组选择顶点

码:

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

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

1.1.4)一些说明,设置助手(路径助手,访问帮助)等

1.1.5)下一步,我正在检查建立的顶点是否是目标顶点

如果是(这意味着,那个蚂蚁找到了目标顶点)我这样做:

1.1.5.1)获取当前蚂蚁路径的长度

码:

var length = 0;

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

    dest = source;
}

1.1.5.2)更新此路径上的信息素水平

码:

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)在主循环结束时,我正在做信息素水平的蒸发:

码:

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

        // ?????????? ???????? ??????? 3
        var newPheromone = (1-ktau)*oldPheromone;

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

Answer 1

选择遵循的路径时，您的代码始终选择低于随机阈值的第一个相邻顶点。我不确定这应该如何代表蚂蚁走向具有更多信息素的顶点。此方法在信息素浓度相对较低（低于 0.5）的地区会在一定程度上发挥作用。然而，在信息素浓度较高（接近或高于 1）的区域，由于您的random()数字介于 0 和 1 之间，因此您将回到始终选择第一个可用顶点的状态。这可能就是您不收敛的原因。