论文中的概率密度函数,使用 C++ 实现,未按预期工作
-
29-09-2019 - |
题
所以我正在实现一个启发式算法,并且我遇到了这个函数。
我有一个 1 到 n 的数组(C 上的 0 到 n-1,w/e)。我想选择一些要复制到另一个数组的元素。给定参数 y (0 < y <= 1),我希望得到平均值为 (y * n) 的数字分布。这意味着每当我调用这个函数时,它都会给我一个介于 0 和 n 之间的数字,这些数字的平均值是 y*n。
根据作者的说法,“l”是一个随机数:0 < l < n 。在我的测试代码中,它当前生成 0 <= l <= n。我有正确的代码,但我已经搞乱了几个小时了,而且我懒得把它编码回来。
因此,我对函数的第一部分进行了编码,因为y <= 0.5 i将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:狡猾的蚂蚁系统”在谷歌上。
那么我做错了什么?我不认为作者是错的,因为有超过 5 篇论文描述了这个相同的功能。
我所有的互联网给任何帮助我的人。这对我的工作很重要。
谢谢 :)
解决方案
dmckee 实际上是正确的,但我想我应该详细说明一下,并尝试解释这里的一些混乱。我肯定会失败。 f_s(l)
, ,上面漂亮公式中的函数是概率分布函数。它告诉你,对于给定的输入 l
在 0 和 n 之间,概率 l
是段长度。0 到 n 之间所有值的总和(积分)应等于 1。
第 7 页顶部的图表混淆了这一点。它绘制了 l
与 f_s(l)
, ,但你必须留意它所带来的杂散因素。您注意到底部的值从 0 到 1,但有一个因子 x n
在侧面,这意味着 l
值实际上从 0 到 n。另外,在 y 轴上有一个 x 1/n
这意味着这些值实际上不会达到 3 左右,而是达到 3/n。
那你现在做什么?那么,您需要通过对概率分布函数进行积分来求解累积分布函数 l
事实证明这并不算太糟糕(我通过 Wolfram Mathematica Online Integrator 使用 x 来做到这一点 l
并仅使用 y <= .5 的方程)。然而,这是使用不定积分,并且您实际上是沿着 x 从 0 到 l
. 。如果我们将所得方程设置为等于某个变量(例如 z),那么现在的目标是求解 l
作为 z 的函数。这里的 z 是 0 到 1 之间的随机数。如果您愿意(我愿意),您可以尝试在这部分使用符号求解器。那么你不仅达到了能够随机选择的目标 l
从这个发行版中,你也获得了涅槃。
还完成了一些工作
我会多帮忙一点。我尝试按照我所说的 y <= .5 进行操作,但是我使用的符号代数系统无法进行反转(其他一些系统可能可以)。然而,后来我决定尝试使用 0.5 < y <= 1 的方程。事实证明这要容易得多。如果我改变 l
到 x 中 f_s(l)
我明白了
y / n / (1 - y) * (x / n)^((2 * y - 1) / (1 - y))
将其与 x 从 0 积分到 l
我得到(使用 Mathematica 的在线积分器):
(l / n)^(y / (1 - y))
对于这种事情来说,没有比这更好的了。如果我将其设置为 z 并求解 l
我得到:
l = n * z^(1 / y - 1) for .5 < y <= 1
一项快速检查是 y = 1。在这种情况下,我们得到 l = n
不管 z 是什么。到目前为止,一切都很好。现在,您只需生成 z(0 到 1 之间的随机数)即可得到 l
根据您的需要进行分布,0.5 < y <= 1。但是等等,看看第 7 页的图表,您会注意到概率分布函数是对称的。这意味着我们可以使用上面的结果来找到 0 < y <= .5 的值。我们只是改变 l
-> n-l
和 y
-> 1-y
并得到
n - l = n * z^(1 / (1 - y) - 1)
l = n * (1 - z^(1 / (1 - y) - 1)) for 0 < y <= .5
不管怎样,这应该可以解决你的问题,除非我在某个地方犯了一些错误。祝你好运。
其他提示
您可能会误解对您的期望。
给定一个(适当归一化的)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)
, ,并使用它们作为参数, x
, , 到 G^{-1}
. 。结果应该介于 [0,1)
, ,并应根据 f_s
.
就像贾斯汀说的,你可以使用计算机代数系统来进行数学计算。
鉴于对于所描述的任何值 l、y、n,您称为 p1 和 p2 的项都在 [0,1) 中,而 exp 在 [1,..) 中,使得 pow(p2, exp) 也在 [0, 1)因此我不明白你如何获得范围为 [0,n) 的输出