约束n维空间的高效随机采样

Question

我即将优化由 n 个（n>=1，通常 n=4）个非负变量定义的问题。这不是一个 n 维问题，因为所有变量的总和需要为 1。

最直接的方法是对每个 x_i 扫描整个范围 0<=x_i<1，然后将所有值归一化为总和所有 x 的。然而，这种方法引入了冗余，这对于许多依赖解空间随机采样的优化算法（遗传算法、禁忌搜索等）来说是一个问题。是否有任何替代算法可以执行此任务？

冗余是什么意思？

以二维情况为例。如果没有约束，这将是一个二维问题，需要优化两个变量。然而，由于要求 X1 + X2 == 0，因此只需要优化一个变量，因为 X2 由 X1 决定，反之亦然。如果决定独立扫描 X1 和 X2 并将它们归一化为 1，那么许多候选解决方案对于问题来说都是相同的。例如（X1==0.1，X2==0.1）与（X1==0.5，X2==0.5）相同。

Answer 1

如果您处理的是实值变量，则不太可能获得两个相同的样本。但是，您确实存在样品不均匀的问题。您更有可能选择 (0.5, 0.5) 而不是 (1.0, 0)。解决这个问题的一种方法是二次采样。基本上，你所做的就是当你沿着某个点缩小空间时，你就缩小了选择它的概率。

所以基本上你要做的就是映射单位立方体内满足同一方向的所有点，映射到单个点。这些点在同一方向上形成一条线。线越长，您选择投影点的概率就越大。因此，您希望通过该线的长度的倒数来偏置选择点的概率。

下面是可以做到这一点的代码（假设您正在寻找 x_is 的总和为 1）：

while(true) {
      maximum = 0;
      norm = 0;
      sum = 0;
      for (i = 0; i < N; i++) {
         x[i] = random(0,1);
         maximum = max(x[i], max);
         sum += x[i];
         norm += x[i] * x[i];
      }
      norm = sqrt(norm);
      length_of_line = norm/maximum;
      sample_probability = 1/length_of_line;

      if (sum == 0 || random(0,1) > sample_probability) {
        continue;
      } else {
      for (i = 0; i < N; i++) {
         x[i] = x[i] /sum;
      } 
      return x;
    }

Answer 2

这是之前提供的相同的函数Amit Prakash，翻译为 python

import numpy as np

def f(N):
    while(True):
        count += 1
        x = np.random.rand(N)
        mxm = np.max(x)
        theSum = np.sum(x)
        nrm = np.sqrt(np.sum(x * x))
        length_of_line = nrm / mxm
        sample_probability = 1 / length_of_line
        if theSum == 0 or rand() > sample_probability:
            continue
        else:
            x = x / theSum
        return x