Created
March 5, 2012 22:56
-
-
Save philtomson/1981803 to your computer and use it in GitHub Desktop.
Random proportional selection ideas
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(* | |
In Ruby: | |
Say that you have a hash 'events' whose keys are the events you are | |
interested in and the values are the corresponding weights: | |
e.g. | |
events = { | |
"event1" => 5, | |
"event2" => 17, | |
"event3" => 6, | |
"event4" => 13 | |
} | |
Solution: | |
tot = 0; events.each { |event, weight| tot += weight } | |
val = rand tot | |
event = events.each do |event, weight| | |
val -= weight; | |
return event if val < 0 | |
end | |
*) | |
(* Another approach in Ruby: | |
def roulette(population, n) | |
probs = population.map { |gene| gene.probability } # TODO: Implement this | |
selected = [] | |
n.times do | |
r, inc = rand * probs.max, 0 # pick a random number and select the individual | |
# corresponding to that roulette-wheel area | |
population.each_index do |i| | |
if r < (inc += probs[i]) | |
selected << population[i] | |
# make selection not pick sample twice | |
population.delete_at i | |
probs.delete_at i | |
break | |
end | |
end | |
end | |
return selected | |
end | |
*) | |
(*And this from my aco code: *) | |
let prop_sel lst = | |
let total = List.fold_left (fun accum p -> (snd p) +. accum) 0.0 lst in | |
let randtot = Random.float total in | |
let rec sel_loop v mlst = match mlst with | |
[] -> raise Empty_list (*fst (List.nth lst 0) *) | |
| x :: xs -> if ( (v -. snd x) <= 0.0 ) then x | |
else sel_loop (v -. snd x) xs in | |
sel_loop randtot lst ;; | |
let choose_by_exploration pt dest_list pm = | |
let denom = List.fold_left ( fun accum pt' -> accum +. PherMatrix.quality_factor pm (pt, pt')) 0.0 dest_list in | |
let prob_list = List.map ( fun pt' -> (pt,pt'), (PherMatrix.quality_factor pm (pt,pt')/. denom )) dest_list in | |
fst (prop_sel prob_list) ;; | |
How about an entirely integer based approach? | |
Example: | |
Desired target = 4 | |
eval abs | |
value delta slots probability of selection: | |
-------+----------+----------+--------------------------- | |
7 -> 3 (4-3)=1 1/14 | |
3 -> 1 (4-1)=3 3/14 | |
5 -> 1 (4-1)=3 3/14 | |
7 -> 3 (4-3)=1 1/14 | |
4 -> 0 (4-0)=4 4/14 | |
2 -> 2 (4-2)=2 2/14 | |
+ | |
total: ----- | |
14 resulting array: [| 7;3;3;3;5;5;5;7;4;4;4;4;2;2 |] | |
index with random number between 0 and 13 | |
Advantage: once you've created the array it's very fast | |
DOWNSIDE: It's good for this example where the deltas are relatively small... not so good if they're much bigger which would lead to a very large | |
selection array. |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment