Mersenne twister разогревается против воспроизводимости

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

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

Согласно qaru.site/info/139891/... и qaru.site/info/274776/..., Merrenne 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};
}

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

EDIT: с помощью разных исполнений. Я имею в виду перезапуск исполняемого файла.

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

Возможное решение # 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 адаптирована из qaru.site/info/111326/...

#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

Ответ 1

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

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

Ответ 2

Я думаю, что вам нужно только сохранить начальное семя (в вашем случае массив 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 - это равномерно распределенный генератор случайных чисел, генерирующий недетерминированные случайные числа.

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

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

EDIT:

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

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

Ответ 3

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

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

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

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