Функция плотности вероятности из статьи, реализованная с использованием C ++, не работает должным образом

Question

Итак, я реализую эвристический алгоритм, и я столкнулся с этой функцией.

У меня есть массив от 1 до n (от 0 до n-1 на C, w / e). Я хочу выбрать количество элементов, которые я скопирую в другой массив. Учитывая параметр y, (0

По мнению автора, «l» - это случайное число: 0

Итак, я кодировал первую часть функции, для y <= 0.5 Я установил y на 0.2, а n на 100. Это означает, что он должен был возвращать число от 0 до 99, в среднем 20. И результаты не между 0 и n, но некоторые плавающие. И чем больше n, тем меньше это число. </p>

Это код теста 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: хитрая система муравьев" в Google.

Так что я делаю не так? я не верю, что автор ошибается, потому что есть более 5 работ, описывающих эту функцию.

все мои интернеты тому, кто мне помогает. Это важно для моей работы.

Спасибо:)

Answer 1

Вы можете неправильно понять, что от вас ожидают.

Учитывая (должным образом нормализованный) PDF и желая генерировать случайное распределение в соответствии с ним, вы формируете кумулятивное распределение вероятностей (CDF) путем интеграции PDF, затем инвертируете 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.

Как сказал Джастин, вы можете использовать систему компьютерной алгебры для математики.

Answer 2

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, используя x для l и используя толькоуравнение для у <= .5).Это, однако, использовало неопределенный интеграл, и вы действительно интегрируете по x от 0 до <code>l.Если мы установим результирующее уравнение равным некоторой переменной (например, z), цель теперь состоит в том, чтобы решить для l как функцию от z.z здесь - случайное число от 0 до 1. Вы можете попробовать использовать символический решатель для этой части, если хотите (я хотел бы).Тогда вы не только достигли своей цели, выбирая случайные l с из этого распределения, вы также достигли нирваны.

Еще немного проделанной работы

Я помогу немного больше.Я попытался сделать то, о чем говорил, для y <= .5, но система символической алгебры, которую я использовал, не смогла сделать инверсию (какая-то другая система могла бы это сделать).Однако тогда я решил попробовать использовать уравнение для .5 <y <= 1. Это оказалось намного проще.Если я изменяю <code>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, которое распределяется так, как вам нужно для .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

В любом случае, это должно решить вашу проблему, если я где-то не ошибся.Удачи.

Answer 3

Учитывая, что для любых значений l, y, n, как описано, термины, которые вы называете p1 и p2, оба находятся в [0,1), а exp находится в [1, ..), делая pow (p2, exp) также в [0,1) Таким образом, я не вижу, как вы могли бы получить вывод с диапазоном [0, n)