This extension adds the ability to do roulette wheel selection in NetLogo. It provides a simpler way to accomplish the same thing as the Lottery Example from the NetLogo Models Library.
Which primitive to use depends on whether you want to select an item from a list or from an agenset. It also depends on whether you want one or many items and, if you want many, if repeats are allowed or not. The following table summarizes the situation:
| From an AgentSet | From a List | |
|---|---|---|
| One item | rnd:weighted-one-of | rnd:weighted-one-of-list |
| Many items, without repeats | rnd:weighted-n-of | rnd:weighted-n-of-list |
| Many items, with repeats | rnd:weighted-n-of-with-repeats | rnd:weighted-n-of-list-with-repeats |
(Note: the initial version of the extension had a single set of primitives for both lists and agentsets, but it turned out to be confusing, so we changed it. If you were using the old version of the extension, you will need to modify your code to use the new primitives.)
In all cases, you will need to provide two things to the primitive:
If you want to select more than one items, you will also need to tell it:
The extension uses Keith Schwarz’s implementation of Vose’s Alias Method (see Schwarz’s Darts, Dice, and Coins page). Assuming you are choosing n candidates for a collection of size m with repeats, this method has an initialization cost of O(m) followed by a cost of O(1) for each item you pick, so O(m + n) overall.
For example, in the following code:
let candidates n-values 500 [ [n] -> n ]
rnd:weighted-n-of-list-with-repeats 100 candidates [ [w] -> w ]
n-values 100 [ rnd:weighted-one-of-list candidates [ [w] -> w ] ]
…the line using rnd:weighted-n-of-list-with-repeats will likely run 100 times faster than the line using a combination of n-values and rnd:weighted-one-of-list. This is because rnd:weighted-n-of-list-with-repeats only initializes the algorithm once and rnd:weighted-one-of does it each time it is called.
(Note that composing n-values with rnd:weighted-one-of-list does not preserve the order of the original candidate list, while rnd:weighted-n-of-list-with-repeats does.)
Things are a bit more complicated if you are choosing without repeats, however. In this case, the algorithm may have to discard some picks because the candidates have already been selected. When this starts happening too often (maybe because some weights are much bigger than others), the extension re-initializes the algorithm with the already-picked candidates excluded. This should not happen too often, however, so while picking without repeats has an upper bound of O(m * n) in theory, it should usually not be much more than O(m + n) in practice.
The previous remarks apply to agentset primitives as much as they apply to list primitives.
Reports a random agent from agentset.
The probability of each agent being picked is proportional to the weight given by the reporter for that agent. The weights must not be negative.
If the agentset is empty, it reports nobody.
Here is a full rewrite of the Lottery Example model using the rnd:weighted-one-of primitive:
extensions [ rnd ]
to setup
clear-all
; create a turtle on every fifth patch
ask patches with [ pxcor mod 5 = 0 and pycor mod 5 = 0 ] [
sprout 1 [
set size 2 + random 6 ; vary the size of the turtles
set label 0 ; start them out with no wins
set color color - 2 ; make turtles darker so the labels stand out
]
]
reset-ticks
end
to go
ask rnd:weighted-one-of turtles [ size ] [
set label label + 1
]
tick
end
Reports an agentset of the given size randomly chosen from the agentset, with no repeats.
The probability of each agent being picked is proportional to the weight given by the reporter for that agent. The weights must be non-negative numbers.
It is an error for size to be greater than the size of the agentset.
If, at some point during the selection, there remains only candidates with a weight of 0.0, they all have an equal probability of getting picked.
Reports a list of the given size randomly chosen from the agentset, with repeats. (Why a list instead of an agentset? Because an agentset cannot contain the same agent more than once.)
The probability of each agent being picked is proportional to the weight given by the reporter for that agent. The weights must be non-negative numbers.
It is not an error for size to be greater than the size of the agentset, but there has to be at least one candidate.
If, at some point during the selection, there remains only candidates with a weight of 0.0, they all have an equal probability of getting picked.
If all weights are 0.0, each candidate has an equal probability of being picked.
Reports a random item from list.
The probability of each item being picked is proportional to the weight given by the anonymous-reporter for that item. The weights must not be negative. The first argument passed to the anonymous procedure refers to the list item. (See the Anonymous Procedures section of the Programming Guide for more details.)
It is an error for the list to be empty.
A common way to use the primitive is to have a list of lists, where the first item of each sublist is the thing you want to choose and the second item is the weight. Here is a short example:
let pairs [ [ "A" 0.2 ] [ "B" 0.8 ] ]
repeat 25 [
; report the first item of the pair selected using
; the second item (i.e., `last p`) as the weight
type first rnd:weighted-one-of-list pairs [ [p] -> last p ]
]
This should print B roughly four times more often than it prints A.
If you happen to have your items and your weights in two separate lists, you can combine them into pairs by using a combination of map and list:
let items [ "A" "B" "C" ]
let weights [ 0.1 0.2 0.7 ]
let pairs (map list items weights)
Since we apply map to both the items list and the weights list, the parentheses are needed in (map list items weights). We also use the concise anonymous procedure syntax (see the programming guide) to pass list as the reporter for map. The same thing could have been written (map [ [a b] -> list a b ] items weights).
Reports a list of the given size randomly chosen from the list of candidates, with no repeats.
The probability of each item being picked is proportional to the weight given by the anonymous-reporter for that item. The weights must not be negative. The first argument passed to the anonymous procedure refers to the list item. (See the Anonymous Procedures section of the Programming Guide for more details.)
It is an error for size to be greater than the size of the list of candidates.
If, at some point during the selection, there remains only candidates with a weight of 0.0, they all have an equal probability of getting picked.
The items in the resulting list appear in the same order that they appeared in the list of candidates. (If you want them in random order, use shuffle on the result).
Example:
let candidates n-values 8 [ [n] -> 2 ^ (n + 1) ] ; make a list with the powers of two
print rnd:weighted-n-of-list 4 candidates [ [w] -> w ]
This should print a list of four numbers, where the bigger numbers (32, 64, 128, 256) have a much better chance to show up than the smaller ones (2, 4, 8, 16).
Reports a list of the given size randomly chosen from the list of candidates, with repeats.
The probability of each item being picked is proportional to the weight given by the anonymous-reporter for that item. The weights must not be negative. The first argument passed to the anonymous procedure refers to the list item. (See the Anonymous Procedures section of the Programming Guide for more details.)
It is not an error for size to be greater than the size of the list of candidates, but there has to be at least one candidate.
If, at some point during the selection, there remains only candidates with a weight of 0.0, they all have an equal probability of getting picked.
If all weights are 0.0, each candidate has an equal probability of being picked.
The items in the resulting list appear in the same order that they appeared in the list of candidates. (If you want them in random order, use shuffle on the result).
Example:
let pairs [ [ "A" 0.2 ] [ "B" 0.8 ] ]
print map first rnd:weighted-n-of-list-with-repeats 25 pairs [ [p] -> last p ]
This should print a list of 25 As and Bs, with roughly four times as many Bs than As.