我开发了一种aco算法。我认为它没有正常工作...很难解释,但我会试着说明。
问题在于信息素水平在浮动。我认为,在最佳路径上的信息素水平必须越来越高,但在我的程序中并非如此。
“最优路径”是通过查找起始顶点和目标顶点之间边缘上的最大信息素水平来构建的路径。
例如:
最佳路径为:
最佳路径:
30只蚂蚁后信息素水平:
30只蚂蚁后的信息素水平:
我程序的伪代码:
所以,为什么我的程序中信息素水平会浮动?为什么最佳路径没有最高的信息素水平?我知道这个算法有概率因素,但它必须显示正确的结果。
我在我的程序里做了什么?这里你可以找到我的程序完整的主循环源代码。
1) 主循环是一个循环,一直运行直到当前迭代中没有可用的蚂蚁为止。
1.1) 在这个循环中,我有另一个循环(内部循环),它将一直执行,直到当前蚂蚁有要前往的顶点(这些顶点不能被当前蚂蚁访问过)。
在内部循环中,我做了以下操作:
1.1.1) 计算下面方程式的分母。
1.1.3) 根据代码的前一部分定义的
问题在于信息素水平在浮动。我认为,在最佳路径上的信息素水平必须越来越高,但在我的程序中并非如此。
“最优路径”是通过查找起始顶点和目标顶点之间边缘上的最大信息素水平来构建的路径。
例如:
1 5 3
4 5 10
0 0 0
最优路径
将是1 -> 2 -> 3
。
权重矩阵:
0 3 10
0 0 3
0 0 0
最佳路径为:
1 -> 2 -> 3 (长度:6)
另一条路径(不是最优):1 -> 3 (长度: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) 根据代码的前一部分定义的
intervals
数组,从0到1创建随机数并选择顶点
代码: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;
}
}