6

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

我有一个 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，我将 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 篇论文描述了相同的功能。

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

谢谢 ：）

4

3 回答 3

6

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

给定一个（正确归一化的）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 并调用 result G^{-1}(x)。为此，您可能需要选择一个特定的 gamma 值。

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

正如贾斯汀所说，您可以使用计算机代数系统进行数学运算。

于 2010-11-05T04:14:38.313 回答
4

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

第 7 页顶部的图表混淆了这一点。它绘制lvs. f_s(l)，但你必须注意它放在一边的杂散因素。您注意到底部的值从 0 变为 1，但x n侧面有一个因子，这意味着这些l值实际上是从 0 变为 n。此外，在 y 轴上有一个x 1/n，这意味着这些值实际上不会上升到大约 3，它们会上升到 3/n。

那你现在怎么办？好吧，您需要通过积分概率分布函数来求解累积分布函数l，实际上结果还不错（我使用 Wolfram Mathematica 在线积分器通过使用 xl和仅使用 y <= .5)。但是，那是使用不定积分，您实际上是沿 x 从 0 到 的积分l。如果我们将得到的方程设置为等于某个变量（例如 z），那么现在的目标是求解lz 的函数。z 这里是一个介于 0 和 1 之间的随机数。如果您愿意（我愿意），您可以尝试对这部分使用符号求解器。那么您不仅实现了能够l从该分布中选择随机 s 的目标，而且还实现了涅槃。

完成了更多的工作

我会多帮忙一点。我尝试按照我所说的 y <= .5，但我使用的符号代数系统无法进行反转（其他一些系统可能能够）。然而，后来我决定尝试使用 .5 < y <= 1 的方程。事实证明这要容易得多。如果我更改l为 x inf_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

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

于 2010-11-05T04:50:02.773 回答
0

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

于 2010-11-05T04:06:13.623 回答