2

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
  • 1
    The linked Q&A *should* answer your question. If you have trouble converting those answers into your own code, let me know. – Cris Luengo Jun 20 '19 at 15:26
  • @CrisLuengo I can see the correlation between our questions, but how can I use that in my problem. Can you explain a bit more? Thank you –  Jun 20 '19 at 17:33
  • 1
    I imagine you have `chromosomes={[1,2,3,...], [2,1,3,...], ...}`, determine their goodness, `goodness=[5.6, 13.1, 2.8, ...]`, then do `prob=goodness/sum(goodness)` and apply any of the random selection methods shown in the linked Q&A. The random selection returns an array `[1,4,5,2,3,2,6,...]`, these are the indices into the `chromosomes` array. That is, each chromosome is identified by an integer in the range 1 to `length(chromosomes)`. – Cris Luengo Jun 20 '19 at 17:48
  • @CrisLuengo Thank you for your help, it's a bit clearer to me now, but I have some questions. What is the right way to calculate goodness of the entire chromosome? And after I got an array `[1,4,5,2,3,2,6,...]`, the biggest number (in my case 10, the number of population) is the best chromosome? –  Jun 20 '19 at 18:38
  • The goodness? That is something you have already defined, no? That is wholly up to you. You need a definition first, then you can figure out how to compute it. Your best chromosome is the one with the largest goodness, you don’t need to draw random numbers to test that. But if you want to add that randomness, then the chromosome that is picked most often (I.e. the number that appears most in that list) is the best one. – Cris Luengo Jun 20 '19 at 18:57
  • @CrisLuengo Ok, Chris. You helped a lot. Thanks –  Jun 20 '19 at 20:58

0 Answers0