Random proportional selection ideas

roulette.ml

(* 

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.