Saturday, December 15, 2018

Roulette Wheel Selection Using SQL

Roulette wheel selection is a very useful algorithm found in many applications such as Genetic Algorithm(GA). In GA solutions with higher fitness values are given larger probabilities of being selected to produce children, just like natural evolution. I implemented an Oracle SQL version of the Roulette wheel selection algorithm.
The first step is to calculate for each record the cumulative value for the variable that the selection will be based on, such as fitness function, probability or other. I used sum() over(order by) analytics function. Make sure the "order by" is using a unique key so that the cumulative value is also unique.
 create table tbl as select id, num, sum(num) over(order by id) as cum_count
  from t_mydata;

The following is the roulette wheel selection scripts.
create table t_rw(sel number);

  mx number;
  rnd  number;
  x number;
   select max(cum_count) into mx from tbl;
  for i in 1..10000 loop
     execute immediate 'select ora_hash(:1,:2) from dual '
          into rnd using i, mx;
     select min(cum_count) into x from tbl where cum_count >= rnd;
     insert into t_rw(sel) values(x);
     end loop;

create view v_selected as select a.* from tbl a, t_rw b where a.cum_count=b.sel;

In the above scripts, ora_hash() generates a uniformly distributed random number between 0 and maximum cum_count. The selected cum_count is inserted into t_rw. The final result is the view v_selected which is based on the inner join of table tbl and t_rw.

No comments: