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

Для ИИ я использую случайные значения, чтобы решить, какое действие выполнить дальше (только когда нет ничего основанного на правилах). Некоторые действия следует выбирать чаще, чем другие.

Идея состоит в том, чтобы определить группу вероятностей и выбрать действие из вероятностей 2 в два раза чаще, чем действие с 1, действие 4 с вероятностью в пять раз выше.

action prob
0         1
1         2 (twice as often than 1)
2         2
3         2
4         5 (5 times morer often than 1)

Есть ли известный алгоритм такого поведения или более математический подход?

Моя тестовая реализация несколько неудобна. Я бы предпочел избежать внутреннего цикла.

public static void main(String[] args) {
    int[] counts = new int[5];
    int[] props = { 1 ,2 ,2 ,2 ,5 };
    int sum = 0;
    for (int i = 0; i < props.length ; i++) {
        sum += props[i];
    }
    for ( int i = 0 ; i < 100 ; i++ ) {
        int rand = (int) (Math.random() * sum);
        for ( int j = 0 ; j < props.length ; j++ ) {
            if ( rand - props[j] <= 0 ) {
                counts[j] = counts[j] + 1;
            }
        }
    }
    for ( int j = 0 ; j < props.length ; j++ ) {
        System.out.println( "count " + j + "=" + counts[j] );
    }
}

В зависимости от тестового прогона он дает такие результаты, как:

count 0=14
count 1=25
count 2=25
count 3=25
count 4=50

java algorithm math probability language-agnostic
person stacker    schedule 16.08.2015    source источник

Ответы (2)


arrow_upward
2
arrow_downward

вы хотите решить уравнение:

p0 + p1 + p2 + p3 + p4 = 1
p0 = p
p1 = 2p
p2 = 2p
p3 = 2p
p4 = 5p

Это набор линейных уравнений, и его довольно легко решить с помощью линейной алгебры.

В этом примере:

p + 2p + 2p + 2p + 5p = 1
12p = 1
p = 1/12
p0 = 1/12
p1 = p2 = p3 = 2/12
p5 = 5/12

Вы можете использовать одно равномерно распределенное число в [0,1) x, чтобы выбрать, какое событие произойдет, установив массив:

aux[0] = 0
aux[i] = aux[0] + p_{i-1}

так что в вашем примере:

aux = [0,1/12,3/12,5/12,7/12,1]

Затем нарисуйте значение для x и выполните двоичный поиск по i, чтобы найти ближайшее значение, которое больше, чем x, и это ваше событие.

person amit    schedule 16.08.2015

arrow_upward
3
arrow_downward

Как насчет массива со значениями, где более распространенные значения появляются чаще:

int[] actions = {0, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4, 4} // 12 values.

Затем вы можете просто сделать

int action = actions[Math.random() * actions.length]

чтобы получить взвешенное случайное действие.

person saagarjha    schedule 16.08.2015
comment
Я думаю, что перетасовка actions элементов даст лучшее взвешенное распределение. - person John; 16.08.2015
comment
На самом деле это не имеет значения, так как Math.random() распределен равномерно, верно? Конечно, можешь, если хочешь. - person saagarjha; 16.08.2015
comment
Зависит от того, насколько точный рандом вам нужен. Это не совсем неформально, и линейный конгруэнтный генератор не является наиболее точным вариантом. Это может показаться вам интересным: stackoverflow.com/ вопросы/453479/как-хорошо-используется-java-util-random - person John; 16.08.2015
comment
Это может быть немного придиркой :) Я проголосовал за ответ. - person John; 16.08.2015
comment
В любом случае, как вы планируете перетасовать actions? Разве вам не пришлось бы использовать Math.random()? - person saagarjha; 16.08.2015
comment
Должен, нет. Буду ли я ? Вероятно. Я понимаю, к чему вы клоните, но я предложил не ставить одинаковые веса рядом друг с другом, вот и все. - person John; 16.08.2015