代码之家 › 专栏 › 技术社区 › Boris Gorelik

约束N维空间的有效随机抽样

genetic-algorithm language-agnostic algorithm

2

Boris Gorelik · 技术社区 · 14 年前

我将要优化一个由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)相同。

2 回复 | 直到 14 年前

1

Amit Prakash 14 年前

如果您处理的是实值变量,那么用两个相同的样本来获取是不太可能的。但是,您的问题是您的样品不均匀。你更可能选择(0.5,0.5)而不是(1.0,0)。解决这一问题的一个方法是二次采样。基本上你要做的是,当你沿着某一点缩小空间时,你缩小了选择空间的概率。

所以基本上,你要做的就是把单位立方体内所有的点映射到同一个方向上,映射到一个点上。这些点在同一方向上形成一条线。直线越长,选择投影点的概率就越大。因此,你想用直线长度的倒数来偏移选择点的概率。

下面是可以执行此操作的代码(假设您要查找的X_是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;
    }

2

0

Community CDub 8 年前

这里有相同的功能 provided 早些时候 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