论文中的概率密度函数，使用 C++ 实现，未按预期工作

Question

所以我正在实现一个启发式算法，并且我遇到了这个函数。

我有一个 1 到 n 的数组（C 上的 0 到 n-1，w/e）。我想选择一些要复制到另一个数组的元素。给定参数 y (0 < y <= 1)，我希望得到平均值为 (y * n) 的数字分布。这意味着每当我调用这个函数时，它都会给我一个介于 0 和 n 之间的数字，这些数字的平均值是 y*n。

根据作者的说法，“l”是一个随机数：0 << l <名词在我的测试代码中，它当前生成 0 <= l <= n。我有正确的代码，但我已经搞乱了几个小时了，而且我懒得把它编码回来。

所以我编写了函数的第一部分，对于 y <= 0.5 我将 y 设置为 0.2，n 设置为 100。这意味着它必须返回 0 到 99 之间的数字，平均为 20。 而且结果不是在 0 到 n 之间，而是一些浮点数。 n 越大，这个浮点数就越小。

这是C测试代码。 “x”是“l”参数。

//hate how code tag works, it's not even working now  
int n = 100;  
float y = 0.2;  
float n_copy;  

for(int i = 0 ; i < 20 ; i++)  
{  
    float x = (float) (rand()/(float)RAND_MAX);  // 0 <= x <= 1  
    x = x * n;                                // 0 <= x <= n  
    float p1 = (1 - y) / (n*y);  
    float p2 = (1 - ( x / n ));  
    float exp = (1 - (2*y)) / y;  
    p2 = pow(p2, exp);  
    n_copy = p1 * p2;  
    printf("%.5f\n", n_copy);  
}  

以下是一些结果（截断 5 位小数）：

0.03354  
0.00484  
0.00003  
0.00029  
0.00020  
0.00028  
0.00263  
0.01619  
0.00032  
0.00000  
0.03598  
0.03975    
0.00704  
0.00176  
0.00001  
0.01333  
0.03396   
0.02795  
0.00005  
0.00860 

文章为：

http://www.scribd.com/doc/3097936/cAS-The-Cunning-Ant-System

第6页和第7页。

或在谷歌上搜索“cAS：cunning ant system”。

那么我做错了什么？我不认为作者是错的，因为有超过 5 篇论文描述了这个相同的功能。

我所有的互联网给任何帮助我的人。这对我的工作很重要。

谢谢 ：）

Answer 1

您可能会误解对您的期望。

给定一个（适当归一化的）PDF，并且想要抛出与其一致的随机分布，您可以通过积分 PDF 来形成累积概率分布 (CDF)，然后反转 CDF，并使用均匀随机谓词作为反转的参数功能。

---

更详细一点。

f_s(l) 是 PDF，并已在 [0,n) 上标准化。

现在您将其积分以形成 CDF

g_s(l') = \int_0^{l'} dl f_s(l)

请注意，这是对未指定端点的定积分，我将其称为 l'。因此CDF是l'的函数。假设我们有正确的标准化，g_s(N) = 1.0。如果不是这样，我们应用一个简单的系数来修复它。

接下来反转 CDF 并调用结果 G^{-1}(x)。为此，您可能需要选择特定的伽玛值。

然后在 [0,n) 上抛出统一随机数，并将它们用作 G^{-1} 的参数 x。结果应位于[0,1)之间，并应根据f_s分布。

就像贾斯汀说的，你可以使用计算机代数系统来进行数学计算。

Answer 2

dmckee 实际上是正确的，但我想我应该详细说明一下，并尝试解释这里的一些混乱。我肯定会失败。 f_s(l)，上面漂亮公式中的函数，是概率分布函数。它告诉您，对于 0 到 n 之间的给定输入 l，l 是段长度的概率。 0 到 n 之间所有值的总和（积分）应等于 1。

第 7 页顶部的图表混淆了这一点。它绘制了 l 与 f_s(l) 的关系图，但您必须注意它放在一边的杂散因素。您注意到底部的值从 0 到 1，但侧面有一个 x n 因子，这意味着 l 值实际上从 0 到名词另外，y 轴上有一个 x 1/n，这意味着这些值实际上不会达到 3 左右，而是达到 3/n。

那你现在做什么？好吧，您需要通过在 l 上积分概率分布函数来求解累积分布函数，这实际上证明并不太糟糕（我通过使用 x 来使用 Wolfram Mathematica Online Integrator 来实现< code>l 并仅使用 y <= .5 的方程）。然而，这是使用不定积分，并且您实际上是沿着 x 从 0 到 l 进行积分。如果我们将所得方程设置为等于某个变量（例如 z），那么现在的目标是求解作为 z 函数的 l。 z 这里是 0 到 1 之间的随机数。如果您愿意（我愿意），您可以尝试在这部分使用符号求解器。那么您不仅实现了能够从该分布中随机选择 l 的目标，而且还实现了涅槃。

完成更多工作

我会提供更多帮助。我尝试按照我所说的 y <= .5 进行操作，但是我使用的符号代数系统无法进行反转（其他一些系统可能可以）。然而，后来我决定尝试使用 0.5 < 的方程。 y <= 1。事实证明这要容易得多。如果我将 f_s(l) 中的 l 更改为 x，我得到

y / n / (1 - y) * (x / n)^((2 * y - 1) / (1 - y))

Integrating this over x from 0 to l 我得到（使用 Mathematica 的在线积分器） :

(l / n)^(y / (1 - y))

对于这种事情来说，没有比这更好的了。如果我将其设置为等于 z 并求解 l，我会得到：

l = n * z^(1 / y - 1)      for .5 < y <= 1

一次快速检查是 y = 1。在这种情况下，无论 z 是什么，我们都会得到 l = n是。到目前为止，一切都很好。现在，您只需生成 z（0 到 1 之间的随机数），就会得到一个 l，它按照您的需要进行分布，即 0.5 l。 y <= 1。但是等等，查看第 7 页的图表，您会注意到概率分布函数是对称的。这意味着我们可以使用上面的结果来找到 0 << 的值。 y <= .5。我们只需更改 l -> nl 和 y -> 1-y 并得到

n - l = n * z^(1 / (1 - y) - 1)

l = n * (1 - z^(1 / (1 - y) - 1))      for 0 < y <= .5

无论如何，这应该可以解决你的问题，除非我在某个地方犯了一些错误。祝你好运。

Answer 3

鉴于对于所描述的任何值 l、y、n，您称为 p1 和 p2 的术语都在 [0,1) 中，而 exp 在 [1,..) 中，使得 pow(p2, exp) 也在 [0,1) 中1）因此我不明白你如何获得范围为 [0,n) 的输出