GA - Custom Integer Selection with Roulette Wheel

80 Views Asked by At

What I need to do:

Get population of n chromosomes, calculate goodness/fitness of each chromosome, random select with weights, and return the best chromosome from a population. In my case n is 10, and chromosome is an array of integer numbers from 1 to 3.

Example: [1,3,2,1,1,1,2,3,3,2,1...k]. (k is 81)

How Selection with Roulette Wheel works link:

Parents are selected according to their fitness. The better the chromosomes are, the more chances to be selected they have. Imagine a roulette wheel where are placed all chromosomes in the population, every has its place big accordingly to its fitness function.

enter image description here

Then a marble is thrown there and selects the chromosome. Chromosome with bigger fitness will be selected more times.

This can be simulated by following algorithm.

  1. [Sum] Calculate sum of all chromosome fitnesses in population - sum S.
  2. [Select] Generate random number from interval (0,S) - r.
  3. [Loop] Go through the population and sum fitnesses from 0 - sum s. When the sum s is greater then r, stop and return the chromosome where you are.

How can I write custom Roulette selection with chromosomes with integer numbers?


This function I found is only for one chromosome link in population:

% ---------------------------------------------------------
% Roulette Wheel Selection Algorithm. A set of weights
% represents the probability of selection of each
% individual in a group of choices. It returns the index
% of the chosen individual.
% Usage example:
% fortune_wheel ([1 5 3 15 8 1])
%    most probable result is 4 (weights 15)
% ---------------------------------------------------------
function choice = fortune_wheel(weights)
  accumulation = cumsum(weights);
  p = rand() * accumulation(end);
  chosen_index = -1;
  for index = 1 : length(accumulation)
    if (accumulation(index) > p)
      chosen_index = index;
      break;
    end
  end
  choice = chosen_index;

I don't know how to write goodness/fitness function for evaluating the whole chromosome and then iterate which is the best solution?

I need something like this but with integer numbers:

enter image description here

Please, any idea is welcomed.

EDIT: What I came up with:

function [ selected_chromosome ] = RouletteWheelSelection( population )
% ---------------------------------------------------------
% Roulette Wheel Selection Algorithm. A set of weights
% represents the probability of selection of each
% individual in a group of choices. It returns the chosen chromosome.
% ---------------------------------------------------------
  struct_size = size(population.chromosomes);
  num_of_chromosomes = struct_size(1);

  for cnt = 1:num_of_chromosomes
      qk = cumsum(population.chromosomes(cnt,:));
      goodness(cnt) = sum(qk);
  end

  total_goodness = sum(goodness);
  for cnt2 = 1:num_of_chromosomes
      probabilities(cnt2) = goodness(cnt2) / total_goodness;
  end

  index = sum(rand >= cumsum([0, probabilities]));

  selected_chromosome = population.chromosomes(index, :);
end
0

There are 0 best solutions below