algorithm - 实现随机 ACO 算法

Question

我正在尝试实现随机蚁群优化算法，但我在弄清楚如何根据概率实现移动选择时遇到了问题。

到目前为止我实现的标准(贪心)版本是在图 G = (V,E ) 其中E是边的集合(i, j)，将根据以下标准选择下一个顶点j :

j = argmax(<fitness function for j>) 
such that j is connected to i

我遇到的问题是尝试实现它的随机版本，所以现在选择新顶点的标准 j 是:

P(j) = <fitness function for j>/sum(<fitness function for J>)
where P(j) is the probability of choosing vertex j,
such j is connected to i,
and J is the set of all vertices connected to i

我理解它背后的数学原理，但我只是不知道应该如何实际实现它。

比方说，如果我有 3 个顶点连接到 i，每个顶点的概率分别为 0.2、0.3、0.5 - 进行选择的最佳方法是什么？我是否应该随机选择一个顶点 j，然后生成范围 (0,1) 内的随机数 r 并且如果 r >= P(j)，选择顶点 j?或者有更好的方法吗？

Answer 1

查看问题陈述，我认为您并不是要访问所有节点(连接到 i (say) )，而是基于某种概率分布的某些节点。让我们举个例子:

你有一个节点 i 并且连接到它的是 5 个节点，a1...a5，概率为 p1...p5 ，这样 sum(p_i) = 1。不，假设您考虑的概率精度是小数点后 2 位。此外，您不想访问所有 5 个节点，而只想访问其中的 k。比方说，在这个例子中，k = 2。因此，由于小数点后 2 位是您的概率精度，因此将其加 3 以增加随机函数中概率分布的正态性。 (你可以把这个 3 改成你选择的任意数字，就性能而言)数。)

让我们给出一些值:

p1...p5 = {0.17, 0.11, 0.45, 0.03, 0.24}

现在，在从 1 到 k 的循环中，从 (0...10^5) 生成一个随机数。 {5 = 2 + 3，即。精度 + 3}。如果生成的数字是从 0 到 16999，则使用节点 a1，17000 到 27999，使用 a2，28000 到 72999，使用 a3...等等。你明白了。