Мерсенна твистер разогрев против воспроизводимости

Question

Мерсенна твистер разогрев против воспроизводимости

В моем текущем проекте C ++ 11 мне нужно выполнить M симуляций. Для каждой симуляции m = 1, ..., MЯ случайно генерирую набор данных, используя std::mt19937 Объект, построенный следующим образом:

std::mt19937 generator(m);
DatasetFactory dsf(generator);

В соответствии с https://stackoverflow.com/a/15509942/1849221 а также https://stackoverflow.com/a/14924350/1849221, Mersenne Twister PRNG получает выгоду от фазы разогрева, которая в настоящее время отсутствует в моем коде. Для удобства сообщу предложенный фрагмент кода:

#include <random>

std::mt19937 get_prng() {
std::uint_least32_t seed_data[std::mt19937::state_size];
std::random_device r;
std::generate_n(seed_data, std::mt19937::state_size, std::ref(r));
std::seed_seq q(std::begin(seed_data), std::end(seed_data));
return std::mt19937{q};
}

Проблема в моем случае заключается в том, что мне нужна воспроизводимость результатов, т. Е. Среди разных исполнений, для каждого моделирования набор данных должен быть одинаковым. Вот почему в моем текущем решении я использую текущую симуляцию для заполнения PRNG Mersenne Twister. Мне кажется, что использование std::random_device предотвращает совпадение данных (AFAIK, это точное назначение std::random_device).

РЕДАКТИРОВАТЬ: от разные исполнения Я имею в виду перезапуск исполняемого файла.

Как я могу ввести вышеупомянутую фазу прогрева в моем коде, не влияя на воспроизводимость? Благодарю.

Возможное решение № 1

Вот предварительная реализация, основанная на втором предложении @SteveJessop

#include <random>

std::mt19937 get_generator(unsigned int seed) {
std::minstd_rand0 lc_generator(seed);
std::uint_least32_t seed_data[std::mt19937::state_size];

std::generate_n(seed_data, std::mt19937::state_size, std::ref(lc_generator));
std::seed_seq q(std::begin(seed_data), std::end(seed_data));
return std::mt19937{q};
}

Возможное решение № 2

Вот предварительная реализация, основанная на совместном вкладе @SteveJassop и @ AndréNeve. sha256 функция адаптирована из https://stackoverflow.com/a/10632725/1849221

#include <openssl/sha.h>
#include <sstream>
#include <iomanip>
#include <random>

std::string sha256(const std::string str) {
unsigned char hash[SHA256_DIGEST_LENGTH];
SHA256_CTX sha256;
SHA256_Init(&sha256);
SHA256_Update(&sha256, str.c_str(), str.size());
SHA256_Final(hash, &sha256);

std::stringstream ss;
for(int i = 0; i < SHA256_DIGEST_LENGTH; i++)
ss << std::hex << std::setw(2) << std::setfill('0') << (int)hash[i];

return ss.str();
}

std::mt19937 get_generator(unsigned int seed) {
std::string seed_str = sha256(std::to_string(seed));
std::seed_seq q(seed_str.begin(), seed_str.end());
return std::mt19937{q};
}

Компилировать с: -I/opt/ssl/include/ -L/opt/ssl/lib/ -lcrypto

15

c++c++11 mersenne-twister prng random

Решение

Другие решения

Я думаю, что вам нужно хранить только начальное семя (в вашем случае std::uint_least32_t seed_data[std::mt19937::state_size] массив) и число n шагов разминки, которые вы сделали (например, используя discard(n) как уже упоминалось) для каждого прогона / моделирования вы хотите воспроизвести.

С помощью этой информации вы всегда можете создать новый экземпляр MT, заполнив его предыдущим seed_data и запустить его для того же n разогрев шагов. Это будет генерировать ту же последовательность значений и далее, так как экземпляр MT будет иметь то же внутреннее состояние, когда закончится прогрев.

Когда вы упоминаете std::random_device Что касается воспроизводимости, я считаю, что в вашем коде он просто используется для генерации начальных данных. Если бы вы использовали его в качестве источник случайных чисел, то вы не сможете получить воспроизводимые результаты. Поскольку вы используете его только для генерации семян, проблем не должно быть. Ты только не может генерировать новое семя каждый раз, если вы хотите воспроизвести ценности!

Из определения std::random_device:

«std :: random_device — это генератор случайных чисел с равномерно распределенными целыми числами, который генерирует недетерминированные случайные числа».

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

Надеюсь это поможет

РЕДАКТИРОВАТЬ :

После обсуждения с @SteveJessop мы пришли к выводу, что простого хэша набора данных (или его части) будет достаточно для использования в качестве достойного начального числа для нужной вам цели. Это позволяет детерминистическим способом генерировать одни и те же семена каждый раз, когда вы запускаете симуляции. Как уже упоминалось @Steve, вам нужно будет гарантировать, что размер хеша не слишком мал по сравнению с std::mt19937::state_size, Если он слишком мал, вы можете объединять хэши m, m + M, m + 2M, … пока у вас не будет достаточно данных, как он предложил.

Я публикую обновленный ответ здесь, так как идея использования хэша была моей, но я добавлю ответ @ SteveJessop, потому что он внес свой вклад.

4

Комментарий к одному из ответов, на который вы ссылаетесь, указывает:

По совпадению, по умолчанию C ++ 11 seed_seq является последовательностью разминки Mersenne Twister (хотя существующие реализации, например, libc ++ mt19937, используют более простую разминку, когда предоставляется начальное значение с одним значением)

Таким образом, вы можете использовать ваши текущие фиксированные семена с std::seed_seq сделать разминку для вас.

std::mt19937 get_prng(int seed) {
std::seed_seq q{seed, maybe, some, extra, fixed, values};
return std::mt19937{q};
}

0

Источник

Accepted Answer

Два варианта:

Следуйте предложению, которое вы имеете, но вместо того, чтобы использовать std::random_device r; чтобы сгенерировать последовательность семян для MT, используйте другой PRNG, засеянный m, Выберите тот, который не страдает, как MT, от необходимости прогрева при использовании с небольшими начальными данными: я подозреваю, что LCG, вероятно, подойдет. Для массового перебора вы можете даже использовать PRNG на основе безопасного хэша. Это очень похоже на «растяжение ключа» в криптографии, если вы слышали об этом. Фактически вы могли бы использовать стандартный алгоритм растягивания ключа, но вы используете его для генерации длинной последовательности начальных чисел, а не материала большого ключа.
Продолжайте использовать m посеять твой МТ, но discard большое постоянное количество данных перед началом моделирования. То есть игнорируйте совет использовать сильное начальное число и вместо этого запускать MT достаточно долго, чтобы он достиг приличного внутреннего состояния. Я не знаю, сколько данных вам нужно отбросить, но я ожидаю, что Интернет знает.

5