纸上的概率密度函数，使用C ++实现，未按预期工作 [英] Probability density function from a paper, implemented using C++, not working as intended

问题描述

因此，我正在实现一种启发式算法，并且遇到了此功能.

So i'm implementing a heuristic algorithm, and i've come across this function.

我有一个1到n的数组(C上为0到n-1，w/e).我想选择一些要复制到另一个数组的元素.给定参数y(0< y< = 1)，我想要分布其平均值为(y * n)的数字.这意味着每当我调用此函数时，它就会给我一个介于0到n之间的数字，并且这些数字的平均值为y​​ * n.

I have an array of 1 to n (0 to n-1 on C, w/e). I want to choose a number of elements i'll copy to another array. Given a parameter y, (0 < y <= 1), i want to have a distribution of numbers whose average is (y * n). That means that whenever i call this function, it gives me a number, between 0 and n, and the average of these numbers is y*n.

根据作者，"l"是一个随机数:0< l ＜ n.在我的测试代码上，其当前生成的0 <= l< = n.而且我有正确的代码，但是我已经花了几个小时弄乱了这个代码，而且我懒于将其编码回来.

According to the author, "l" is a random number: 0 < l < n . On my test code its currently generating 0 <= l <= n. And i had the right code, but i'm messing with this for hours now, and i'm lazy to code it back.

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

So i coded the first part of the function, for y <= 0.5 I set y to 0.2, and n to 100. That means it had to return a number between 0 and 99, with average 20. And the results aren't between 0 and n, but some floats. And the bigger n is, smaller this float is.

这是C测试代码. "x"是"l"参数.

This is the C test code. "x" is the "l" parameter.

//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个小数点被截断):

And here are some results (5 decimals truncated):

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-Cunning-Ant-System

第6页和第7页.

或在Google上搜索"cAS:狡猾的蚂蚁系统".

or search "cAS: cunning ant system" on google.

那我在做什么错呢?我不相信作者是错的，因为有超过5篇论文描述了该功能.

So what am i doing wrong? i don't believe the author is wrong, because there are more than 5 papers describing this same function.

所有帮助我的人的互联网.这对我的工作很重要.

all my internets to whoever helps me. This is important to my work.

谢谢:)

推荐答案

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

dmckee is actually correct, but I thought that I would elaborate more and try to explain away some of the confusion here. I could definitely fail. f_s(l), the function you have in your pretty formula above, is the probability distribution function. It tells you, for a given input l between 0 and n, the probability that l is the segment length. The sum (integral) for all values between 0 and n should be equal to 1.

第7页顶部的图形使这一点感到困惑.它绘制了l与f_s(l)的关系，但是您必须注意它所带来的杂散因素.您会注意到底部的值从0变为1，但侧面的系数为x n，这意味着l值实际上从0变为n.另外，在y轴上有一个x 1/n，这意味着这些值实际上不会上升到大约3，而是上升到3/n.

The graph at the top of page 7 confuses this point. It plots l vs. f_s(l), but you have to watch out for the stray factors it puts on the side. You notice that the values on the bottom go from 0 to 1, but there is a factor of x n on the side, which means that the l values actually go from 0 to n. Also, on the y-axis there is a x 1/n which means these values don't actually go up to about 3, they go to 3/n.

那你现在怎么办?好吧，您需要通过对l上的概率分布函数进行积分来解决累积分布函数，这实际上还算不错(我使用Wolfram Mathematica Online Integrator在Wolfram Mathematica Online Integrator上做到了这一点，方法是将x用作l并且仅使用y< = 0.5)的等式.但是，那是使用不定积分，并且您实际上是沿着从0到l的x进行积分.如果我们将结果方程式设置为等于某个变量(例如z)，那么现在的目标是要解决l作为z的函数的问题. z这里是一个介于0和1之间的随机数.如果愿意，您可以尝试对此部分使用符号求解器.然后，您不仅实现了从该分布中随机选择l的目标，而且还实现了必杀技.

So what do you do now? Well, you need to solve for the cumulative distribution function by integrating the probability distribution function over l which actually turns out to be not too bad (I did it with the Wolfram Mathematica Online Integrator by using x for l and using only the equation for y <= .5). That however was using an indefinite integral and you are really integration along x from 0 to l. If we set the resulting equation equal to some variable (z for instance), the goal now is to solve for l as a function of z. z here is a random number between 0 and 1. You can try using a symbolic solver for this part if you would like (I would). Then you have not only achieved your goal of being able to pick random ls from this distribution, you have also achieved nirvana.

完成的工作更多

我会帮助更多.我尝试做关于y <= .5的事情，但是我使用的符号代数系统无法进行求逆(某些其他系统可能可以做到).但是，后来我决定尝试使用.5< 5的等式. y< =1.事实证明这要容易得多.如果将f_s(l)中的l更改为x，我会得到

I'll help a little bit more. I tried doing what I said about for y <= .5, but the symbolic algebra system I was using wasn't able to do the inversion (some other system might be able to). However, then I decided to try using the equation for .5 < y <= 1. This turns out to be much easier. If I change l to x in f_s(l) I get

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

通过x从0到l进行积分(使用Mathematica的在线积分器):

Integrating this over x from 0 to l I got (using Mathematica's Online Integrator):

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

在这种事情上，没有比这更好的了.如果将其设置为z并求解l，我得到:

It doesn't get much nicer than that with this sort of thing. If I set this equal to z and solve for l I get:

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

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

One quick check is for y = 1. In this case, we get l = n no matter what z is. So far so good. Now, you just generate z (a random number between 0 and 1) and you get an l that is distributed as you desired for .5 < y <= 1. But wait, looking at the graph on page 7 you notice that the probability distribution function is symmetric. That means that we can use the above result to find the value for 0 < y <= .5. We just change l -> n-l and y -> 1-y and get

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

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

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

Anyway, that should solve your problem unless I made some error somewhere. Good luck.

这篇关于纸上的概率密度函数，使用C ++实现，未按预期工作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！