Эффективная случайная выборка из ограниченного n-мерного пространства - PullRequest
Новая
       31

Эффективная случайная выборка из ограниченного n-мерного пространства

2 голосов
/ 21 октября 2010

Я собираюсь оптимизировать проблему, которая определяется n (n> = 1, обычно n = 4) неотрицательными переменными.Это не n-мерная проблема, так как сумма всех переменных должна быть равна 1.

. Наиболее простой подход - для каждого x_i сканировать весь диапазон 0 <= x_i <1, а затем нормализоватьвсе значения к сумме всех х.Тем не менее, этот подход вводит избыточность, которая является проблемой для многих алгоритмов оптимизации, которые основаны на стохастической выборке пространства решений (генетический алгоритм, поиск с запретами и другие).Есть ли альтернативный алгоритм, который может выполнить эту задачу?</p>

Что я имею в виду под избыточностью?

Возьмем в качестве примера двумерный случай.Без ограничений это была бы двумерная задача, которая потребовала бы оптимизации двух переменных.Однако из-за требования, что X1 + X2 == 0, нужно оптимизировать только одну переменную, поскольку X2 определяется X1 и наоборот.Если бы кто-то решил сканировать X1 и X2 независимо и нормализовать их к сумме 1, то многие кандидаты на решение были бы идентичны по отношению к проблеме.Например (X1 == 0,1, X2 == 0,1) идентично (X1 == 0,5, X2 == 0,5).

Ответы [ 2 ]

1 голос
/ 21 октября 2010

Если вы имеете дело с действительными значениями переменных, то получение двух выборок, которые становятся идентичными, маловероятно. Однако у вас есть проблема, что ваши образцы не будут единообразными. Вы гораздо чаще выбираете (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;
    }
0 голосов
/ 12 июля 2011

Вот та же самая функция , предоставленная ранее 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
...