JavaScript의 가중치 랜덤 알고리즘

ℹ️ Examples are from the javascript-algorithms repository

"가중 랜덤"이란 무엇입니까?

항목 목록이 있다고 가정해 보겠습니다. 항목은 무엇이든 될 수 있습니다. 예를 들어, 먹고 싶은 과일과 채소 목록이 있을 수 있습니다. [ '🍌', '🍎', '🥕' ] .

가중치 목록은 각 항목의 가중치(또는 확률 또는 중요도)를 나타냅니다. 무게는 숫자입니다. 예를 들어 [3, 7, 1]과 같은 가중치는 다음과 같습니다.

자주 먹고싶다 🍎 apples ( 7/3 + 7 + 1 = 11 ),

그럼 bananas 🍌 덜 자주 먹고 싶다(3번 중 11번만),

번

과 carrots 🥕은 정말 싫어합니다(1번 중 11번만 먹고 싶습니다).

If we speak in terms of probabilities than the weights list might be an array of floats that sum up to 1 (i.e. [0.1, 0.5, 0.2, 0.2]).

이 경우 Weighted Random은 목록에서 항목을 무작위로 반환하는 기능이며 각 항목의 가중치를 고려하므로 가중치가 높은 항목이 더 자주 선택됩니다.

기능 인터페이스의 예:

const items =   [ '🍌', '🍎', '🥕' ];
const weights = [  3,    7,    1  ];

function weightedRandom(items, weights) {
  // implementation goes here ...
}

const nextSnackToEat = weightedRandom(items, weights); // Could be '🍎'

가중 랜덤의 적용

Genetic Algorithm에서 가중 랜덤은 "선택"단계에서 사용되며, 짝짓기와 다음 세대를 생산하기 위한 적합도 점수를 기반으로 가장 적합하고 강한 개체를 선택해야 합니다. Self-Parking Car in 500 Lines of Code 기사에서 예를 찾을 수 있습니다.

Recurrent Neural Networks (RNN)에서 다음 문자 확률을 기반으로 (문장을 형성하기 위해) 다음에 선택할 문자를 결정하려고 할 때. Recipe Generation using Recurrent Neural Network (RNN) Jupyter 노트북에서 예제를 찾을 수 있습니다.

Nginx Load Balancing에서 더 높은 가중치를 가진 서버에 HTTP 요청을 더 자주 전송합니다.

그리고 더...

알고리즘

직접적인 접근 방식은 다음과 같습니다.

목록의 각 항목을 가중치에 따라 반복하십시오.

목록에서 임의의 항목을 선택하십시오.

예를 들어 과일과 채소의 경우 크기가 3 + 7 + 1 = 11인 다음 목록을 생성할 수 있습니다.

const items =   [ '🍌', '🍎', '🥕' ];
const weights = [  3,    7,    1  ];

// Repeating the items based on weights.
const weightedItems = [
  '🍌', '🍌', '🍌',
  '🍎', '🍎', '🍎', '🍎', '🍎', '🍎', '🍎',
  '🥕',
];

// And now just pick the random item from weightedItems array.

그러나 보시다시피 이 접근 방식은 개체가 무거울 경우와 weightedItems 목록에서 반복할 개체가 많은 경우에 많은 메모리가 필요할 수 있습니다.

보다 효율적인 접근 방식은 다음과 같습니다.

각 항목에 대한 누적 가중치 목록을 준비합니다(즉, 원래 cumulativeWeights 목록과 동일한 수의 요소를 가질 weights 목록). 우리의 경우 다음과 같이 보일 것입니다: cumulativeWeights = [3, 3 + 7, 3 + 7 + 1] = [3, 10, 11]

randomNumber에서 가장 높은 누적 가중치 값까지 난수 0을 생성합니다. 우리의 경우 난수는 [0..11] 범위에 있습니다. randomNumber = 8 가 있다고 가정해 보겠습니다.

왼쪽에서 오른쪽으로 cumulativeWeights 목록을 살펴보고 randomNumber 보다 높거나 같은 첫 번째 요소를 선택하십시오. 이러한 요소의 인덱스는 items 배열에서 항목을 선택하는 데 사용할 것입니다.

이 접근 방식의 이면에 있는 아이디어는 더 높은 가중치가 더 많은 숫자 공간을 "점유"한다는 것입니다. 따라서 난수가 "높은 가중치 숫자 버킷"에 포함될 가능성이 더 높습니다.

const weights =           [3, 7,  1 ];
const cumulativeWeights = [3, 10, 11];

// In a pseudo-representation we may think about the cumulativeWeights array like this.
const pseudoCumulativeWeights = [
  1, 2, 3,               // <-- [3] numbers
  4, 5, 6, 7, 8, 9, 10,  // <-- [7] numbers
  11,                    // <-- [1] number
];

다음은 weightedRandom 기능이 구현되는 방법의 예입니다.

/**
 * Picks the random item based on its weight.
 * The items with higher weight will be picked more often (with a higher probability).
 *
 * For example:
 * - items = ['banana', 'orange', 'apple']
 * - weights = [0, 0.2, 0.8]
 * - weightedRandom(items, weights) in 80% of cases will return 'apple', in 20% of cases will return
 * 'orange' and it will never return 'banana' (because probability of picking the banana is 0%)
 *
 * @param {any[]} items
 * @param {number[]} weights
 * @returns {{item: any, index: number}}
 */
export default function weightedRandom(items, weights) {
  if (items.length !== weights.length) {
    throw new Error('Items and weights must be of the same size');
  }

  if (!items.length) {
    throw new Error('Items must not be empty');
  }

  // Preparing the cumulative weights array.
  // For example:
  // - weights = [1, 4, 3]
  // - cumulativeWeights = [1, 5, 8]
  const cumulativeWeights = [];
  for (let i = 0; i < weights.length; i += 1) {
    cumulativeWeights[i] = weights[i] + (cumulativeWeights[i - 1] || 0);
  }

  // Getting the random number in a range of [0...sum(weights)]
  // For example:
  // - weights = [1, 4, 3]
  // - maxCumulativeWeight = 8
  // - range for the random number is [0...8]
  const maxCumulativeWeight = cumulativeWeights[cumulativeWeights.length - 1];
  const randomNumber = maxCumulativeWeight * Math.random();

  // Picking the random item based on its weight.
  // The items with higher weight will be picked more often.
  for (let itemIndex = 0; itemIndex < items.length; itemIndex += 1) {
    if (cumulativeWeights[itemIndex] >= randomNumber) {
      return {
        item: items[itemIndex],
        index: itemIndex,
      };
    }
  }
}

구현

weightedRandom() 함수의 구현을 위해 weightedRandom.js 파일을 확인하십시오.

weightedRandom.test.js 파일에서 테스트 케이스를 확인하십시오.