Mersenne Twister预热与可重复性

Question

我目前的C++11项目需要执行M次模拟。对于每个模拟 m = 1, ..., M，我使用一个如下构造的 std::mt19937 对象随机生成数据集：

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

根据https://dev59.com/I2Up5IYBdhLWcg3wHUvi#15509942和https://dev59.com/HWUp5IYBdhLWcg3w8bJB#14924350，梅森旋转算法（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};
}

在我的情况下，问题是我需要结果的可重复性，也就是说，在不同的执行中，对于每个模拟，数据集必须相同。这就是为什么在我的当前解决方案中，我使用当前模拟来生成Mersenne Twister PRNG的种子。在我看来，使用 std::random_device 会防止数据相同（据我所知，这正是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://dev59.com/zHE95IYBdhLWcg3wkegf#10632725

#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

- Ilio Catallo

---

你不能只从PRNG中读取一定量的数据吗？ - CodesInChaos

你的意思是说，当你请求新数据时，伪随机序列的质量会提高吗？我的目标是在初始化阶段明确考虑 std::mt19937::state_size，同时保持可重复性。 - Ilio Catallo

所有随机数生成器都有一个成员函数discard(n)，用于向前推进内部状态，就好像调用了operator() n次。 - Xeo

在“possible 2”中，std::hash<unsigned int> 不够好。你试图克服的 MT 的问题是它需要很多非零位的种子数据，否则它的内部状态大部分为 0，并输出糟糕的数据。 std::hash 并不是解决这个问题的正确哈希类型。最多它仍然只提供 64 位的种子数据，而且它比这更糟，因为它很可能是恒等操作。如果你使用例如 m 的 SHA256 哈希值，那么你可能会成功。 - Steve Jessop

我知道我晚了，但我终于有机会纠正第二个解决方案。 - Ilio Catallo

Answer 1

两种选择：

1. 遵循您拥有的建议，但是不要使用 std::random_device r; 生成MT的种子序列，而是使用用 m 种子种植的另一个PRNG。选择一个不像MT那样需要在使用小的种子数据时进行预热的PRNG：我认为LCG可能会做到这一点。为了超级保险起见，您甚至可以使用基于安全哈希的PRNG。如果您听说过密码学中的“密钥拉伸”，则这非常类似。实际上，您可以使用标准的密钥拉伸算法，但是您将使用它生成长种子序列，而不是大型密钥材料。

2. 继续使用 m 来种植您的MT，但在开始模拟之前丢弃大量的数据。也就是说，忽略使用强种子的建议，而是运行MT足够长的时间使其达到良好的内部状态。我不知道需要丢弃多少数据，但我希望互联网能够解答这个问题。

- Steve Jessop

---

问题在于他在每次运行时都使用std::random_device来为Mersenne Twister生成种子，这将（实质上）永远不会产生可重复的效果。他确实可以使用另一个不需要预热阶段的PNRG，但仍然不能在每次运行时生成新的种子。他必须生成一次种子并在运行之间将其存储在某个地方以实现可重复性。显然，它不需要是强种子。 - André Neves

好的，我以为他正在考虑使用上面的代码片段。无论如何，我确实理解他想要有M组种子，如果他想要使用良好的种子，他可以使用random_device而不会有任何问题，他只需要为每个数据集存储它。我记得一种“便宜”的方法是不使用强种子，也不必存储它，但仍然相对随机，就是使用数据集（或某些部分）的哈希作为MT（或其他PNRG）的种子。这样，他就不需要存储它，因为对于每个数据集来说，它都是确定性的。 - André Neves

@AndréNeves：同意，他可以存储真正的随机数据。事实上，他不需要文件/数据库/任何东西，他可以生成它们一次并编译它们（资源文件，转换为十六进制并粘贴到源代码中，等等）。对m进行单个哈希是密钥拉伸的退化情况--对于密码学来说不够好，但在这里足够好，前提是哈希的大小与std::mt19937::state_size相比不太小。如果太小，则另一种即兴的密钥拉伸算法是将m，m+M，m+2M的哈希连接起来，直到您拥有足够的数据。 - Steve Jessop

是的，他可以将种子存储为资源文件或直接存储在代码中，但这可能过于静态甚至是硬编码的。无论如何，我想哈希作为种子是一个不错的解决方案，唯一可能的问题就是长度，正如你所提到的，但这很容易被规避。 - André Neves

首先，非常感谢您对我的问题进行了如此多的讨论。关于您的建议，数据集将从PRNG开始生成。如果我正确理解您的想法，您建议通过计算数据集上某种哈希值来初始化PRNG。关键是在获得PRNG之前，我无法生成数据集。 - Ilio Catallo

Answer 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是一种产生不确定性随机数的均匀分布整数随机数生成器。”

因此，如果它不确定，您就无法重现由其产生的值序列。话虽如此，只需将其简单地用于生成好的随机种子即可，然后存储以供重新运行使用。

希望这有所帮助。 编辑：

在与@SteveJessop讨论后，我们得出结论：数据集（或其中一部分）的简单哈希将足以用作您需要的良好种子。这允许以确定性的方式每次运行模拟都生成相同的种子。如@Steve所提到的，您必须确保哈希的大小与std :: mt19937 :: state_size 不太小。如果太小，那么您可以连接m、m+M、m+2M等的哈希，直到获得足够的数据。

我将更新的答案发布在这里，因为使用哈希的想法是我的，但我会向@SteveJessop的答案投票，因为他做出了贡献。

- André Neves

---

我需要创建M个不同的数据集，这些数据集将用于M个不同的模拟中。我需要这些数据集是独立的，即每个数据集都是使用PRNG生成的，其种子对于特定的模拟是唯一的。我的当前解决方案通过使用从1到M的一系列种子来实现唯一性。看起来你建议在代码开头创建一个“主”种子序列q，以便在每个模拟中使用discard(n)修改结果为std::mt19937，其中n对于每个模拟都是不同的。对吗？ - Ilio Catallo

您需要为想要再现的每个模拟创建一个_master_种子序列(seed_data数组)和一个_master_ n。所以，如果我理解正确，您将有M个不同的_master_ seed_data和 M个n，每个模拟一个。对于每个模拟，您将调用seed(seed_data)，然后调用discard(n)。您可以创建大小为M的数组以获得您的M组参数集，然后使用seed(seed_data_array[i])更新您的std::mt19937实例，然后调用discard(n_array[i])，其中i是数据集标识符(0..M-1)。 - André Neves

所以问题在于从M个不同的主种子序列和n中获取。我编辑了原始问题，强调通过“不同的执行”重新启动可执行文件。 - Ilio Catallo

您需要以持久的方式（例如文件、数据库）存储M个主种子序列和n，以便在重新启动可执行文件时可以加载它们。因此，您可以使用一个简单的参数，当为true时运行模拟并生成主种子数据，当为false时仅读取主种子数据并有效地再现模拟。 - André Neves

Answer 3

你链接的答案中有一条评论指出：

巧合的是，C++11的默认种子序列是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};
}

- bames53