Улучшение качества генерации случайных чисел в Qt 5.3

В настоящее время я реализую генератор случайных чисел в Qt5.3 как часть экспериментов с генетическим алгоритмом. Я пробовал несколько методов, но лучший, кажется, это:

  // Seed the random generator with current time
  QTime time = QTime::currentTime();
  qsrand((uint)time.msec());

И затем эта функция для генерации случайных чисел:

int MainWindow::getRandomNo(int low, int high)
{
    return qrand() % ((high + 1) - low) + low;
}

Из-за характера этих экспериментов важен случайный характер этих чисел. Есть ли способ улучшить качество выборки случайных чисел? После статистического анализа генератор случайных чисел Qt демонстрирует типичные шаблоны, которые можно найти в старых системах генерации случайных чисел.

Используемый выше метод основан на текущем времени в качестве начального значения для генератора чисел. Есть ли способ улучшить начальное число, чтобы случайные последовательности были менее подвержены закономерностям? Буду крайне признателен за любую помощь.


c++ random qt seeding qt5.3
person Adam893    schedule 03.10.2014    source источник
comment
Есть ли причина не использовать <random> ? Это намного прочнее.   -  person MSalters    schedule 03.10.2014
comment
Похоже, он страдает от тех же проблем с шаблонами - почти предсказуемо, учитывая достаточно большой размер выборки.   -  person Adam893    schedule 03.10.2014
comment
Каждый PRNG предсказуем при достаточно большом размере выборки. Но достаточно большой далеко не возможен с хорошими алгоритмами. Вы вообще смотрели доступные? cplusplus.com/reference/random   -  person deviantfan    schedule 03.10.2014
comment
Это конкретное приложение представляет собой симуляцию эволюционного процесса и, как таковое, будет работать тем лучше, чем более случайным является ввод. Генераторы случайных чисел, о которых вы упомянули, великолепны, но в том-то и проблема, что они слишком хороши. Сгенерированные случайные последовательности слишком равномерно распределены, чтобы быть полезными. Нужна система, которая может генерировать настоящую случайную последовательность. Единственное, что хотя бы приблизилось к этому, — это аппаратный генератор случайных чисел. До сих пор лучшее, что я нашел, - это Qt в моем вопросе, использующем часы в качестве семени.   -  person Adam893    schedule 03.10.2014
comment
Нет такой вещи, как ГСЧ, которая была бы слишком хороша. Mersenne Twister предоставит вам любую последовательность чисел с (почти) одинаковой вероятностью. Даже такая последовательность, как 0 - 0 - 0 - 0 - 0   -  person B. Decoster    schedule 03.10.2014
comment
@ Adam893: слишком равномерное распределение является свойством настоящей случайной последовательности. Или вы думаете, что истинная случайная последовательность должна иметь в себе какой-то шаблон?   -  person Siyuan Ren    schedule 04.10.2014
comment
Я подозреваю, что вам нужно неравномерное распределение, и это тоже предусмотрено <random>.   -  person MSalters    schedule 04.10.2014
comment
Большое спасибо за все ответы. Я понимаю путаницу в том, что я прошу, трудно передать точную проблему без некоторых базовых знаний о ГА!   -  person Adam893    schedule 07.10.2014

Ответы (3)


arrow_upward
2
arrow_downward

Используйте MT.

Вы можете получить реализацию здесь:

Я столкнулся с той же проблемой несколько лет назад в программном обеспечении Delphi, и переход на MT решил мою проблему. Но проверьте список в документации по ускорению для получения более подробной информации о различиях между алгоритмами ГСЧ.

person Simon Warta    schedule 04.10.2014
comment
Вы упускаете самое очевидное место для поиска: <random>. Вам не нужна дополнительная библиотека. - person MSalters; 04.10.2014
comment
Я рад, что нашел кого-то, кто понимает проблему! Спасибо за подсказку по MT, это имеет большое значение. - person Adam893; 07.10.2014
comment
@ Adam893: Поскольку вы спросили, все указали вам на «случайный» заголовок. Вуаля, есть реализация МП. Но тогда ты говорил, что это слишком хорошо...? - person deviantfan; 08.10.2014

arrow_upward
1
arrow_downward

Настройка вашего начального числа на самом деле не повлияет на качество сгенерированных чисел, а только на определенный порядок сгенерированных чисел. Вам нужно будет использовать лучший алгоритм для генерации случайных чисел.

Кроме того, то, как вы используете сгенерированные числа, немного предвзято. С вашей функцией getRandomNo будет небольшой уклон в сторону меньших чисел. Например, если qrand возвращает значение в диапазоне 0..2^32-1, а у вас есть low=0 и high=2^32-2, то использование % будет означать, что 0 будет возвращаться (приблизительно) в два раза чаще, чем любое другое число.

Улучшением было бы попробовать что-то вроде этого:

Пусть n будет положительным целым числом, где вы хотите случайное целое число в диапазоне 0..n-1, пусть m будет наименьшей степенью 2, большей или равной n.

unsigned int myrand( unsigned int n, unsigned int m )
{
    unsigned int i = qrand() % m; /* or (qrand() & (m-1)) */
    while ( i >= n )
    {
        i = qrand() % m;
    }

    return i;
}

Это будет медленнее, но ожидаемое количество итераций равно 2. Кроме того, если вы используете один и тот же диапазон несколько раз, вы можете предварительно вычислить m.

person dohashi    schedule 03.10.2014

arrow_upward
1
arrow_downward

поправка к ответу dohashi может состоять в том, чтобы взять m в качестве первого простого числа, большего или равного n

person H.B    schedule 04.01.2015