Skip to content

Instantly share code, notes, and snippets.

@philtomson
Created March 5, 2012 22:56
Show Gist options
  • Save philtomson/1981803 to your computer and use it in GitHub Desktop.
Save philtomson/1981803 to your computer and use it in GitHub Desktop.
Random proportional selection ideas
(*
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