1

我正在尝试实现一个随机蚁群优化算法，但我无法确定如何根据概率实现运动选择。

到目前为止，我已经实现的标准（贪婪）版本是，在图的顶点处的蚂蚁是m边集，将根据以下标准选择下一个顶点：iG = (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 - 进行选择的最佳方法是什么？我应该只是随机选择一个顶点，然后在 (0,1) 范围内j生成一个随机数，如果，选择顶点？或者，还有更好的方法？rr >= P(j)j

4

2 回答 2

0

查看问题陈述，我认为您不是试图访问所有节点（连接到i(say) ），而是基于某些概率分布的一些节点。举个例子：

您有一个节点i，连接到它的是 5 个节点，a1...a5，概率p1...p5为 ，因此sum(p_i) = 1。不，假设您考虑的概率精度是小数点后 2 位。此外，您不想访问所有 5 个节点，而只访问k其中的一个。可以说，在这个例子中，k = 2. 因此，由于小数点后 2 位是您的概率精度，因此添加 3 以增加normality随机函数中的概率分布。（就性能而言，您可以将这个 3 更改为您选择的任何数字）（由于您没有标记任何语言，我将以 javanextInt()生成随机数的函数为例。）

让我们给出一些值：

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……等等。你明白了。

于 2015-10-09T07:45:25.983 回答
0

您尝试实现的是加权随机选择，具体取决于解决方案组件的概率，或ACO 项上的随机比例选择规则。这是在 Isula 框架上执行此规则的片段：

double value = random.nextDouble();
while (componentWithProbabilitiesIterator.hasNext()) {
    Map.Entry<C, Double> componentWithProbability = componentWithProbabilitiesIterator
            .next();

    Double probability = componentWithProbability.getValue();  
    total += probability;

    if (total >= value) {
        nextNode = componentWithProbability.getKey();
        getAnt().visitNode(nextNode);
        return true;
    }
}

您只需要生成一个介于 0 和 1 之间的随机值（存储在 中value），然后开始累积分量的概率（在total变量上）。当total超过定义的阈值时value，我们已经找到要添加到解决方案中的组件。

于 2016-04-01T22:02:24.820 回答