我开发了一个 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;
}
代码：
for(row in pheromone)
{
for(col in pheromone[row])
{
var oldPheromone = pheromone[row][col];
// обновление феромона формула 3
var newPheromone = (1-ktau)*oldPheromone;
pheromone[row][col] = newPheromone;
}
}