約束n維空間的高效隨機採樣

我即將優化n（n> = 1，通常n = 4）非負變量定義的問題。這不是一個n維問題，因爲所有變量的和必須是1.約束n維空間的高效隨機採樣

最直接的方法是每個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）相同。

來源

2010-10-21 Boris Gorelik

出於好奇：你在談論什麼樣的'冗餘'？我對這個領域並不熟悉。 – 2010-10-21 11:28:02

您可能還有更多的運氣在一個專門的SE站點（有一個關於統計的單獨站點，IIRC） – 2010-10-21 11:30:04

很多有趣的單詞大多是不必要的，但完全缺少的是算法的目標。標題「約束n維空間的高效隨機採樣」表示一個n維問題，然後在第一段中被駁斥。我不確定這些值的總和如何與問題空間的維度相關，也許你可以解釋一下。 – Lazarus 2010-10-21 11:34:03

如果你正在處理實值變量，那麼到達2個相同的樣本是不太可能的。但是，您確實有問題，您的樣品不會一致。你比（1.0，0）更可能選擇（0.5,0.5）。解決這個問題的一個方面是子採樣。基本上你所做的是當你沿着某個點收縮空間時，你縮小了選擇它的可能性。

因此，基本上你在做的是映射單位立方體內所有滿足同一方向的點，映射到單個點。這些點在同一個方向上形成一條線。線越長，您選擇投影點的概率就越大。因此，您希望通過該行長度的倒數來選擇點的概率。

這是可以做到這一點的代碼（假設你正在尋找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; 
    }

來源

2010-10-21 17:44:29

這裏是相同的功能provided早些時候Amit Prakash，翻譯成蟒蛇

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

來源

2011-07-12 14:59:12

約束n維空間的高效隨機採樣

回答

相關問題