Genetic Algorithms in Elixir Book Club!

Questions & Help Questions
, ,
61

Sorry for letting the momentum slow on this thread. Life, :person_shrugging:

Here are my thoughts on chapter 5 to try and get things moving again.

Selection is biased sampling (is it?)

  • Selection rate might be an important factor for the Sudoku problem …

Not sure I agree that selection and statistical sampling are variations on the same theme. Statistical sampling is an attempt to define or describe a population based on a limited number of individuals. Selection is about applying a definition or description to individuals to create the population you want.

  • High selection rates should slow convergence but improve diversity (I think)

Importance of Selection Pressure

  • Selection pressure of 1 is fully random? I would have thought selection pressure of 1 was fully elite while a pressure of 0 was fully randm.

One extreme, when there is no selection pressure, is completely stochastic so that the search acts just like the Monte Carlo method [8], randomly sampling the space of feasible solutions.

Types of Selection

I don’t understand how rewards based selection differs from fitness based selection. Feels like you’re just shifting the fitness function to some mapping or reducing function that accumulates rewards and then determining fitness based on those rewards. I guess it doesn’t matter that I don’t understand the difference since the author says the book will only use fitness based selection strategies.

One thing I’ve been struck by in reading this book is how many times I read something and think, “Why not do this instead?” or “Would it make sense to also do this?” and then the next page answers that exact question. For instance, this is from my notes made while reading chapter 5:

Creating a Selection Toolbox
CODE! Nice way to implement multiple strategies for the library. I think I still struggle with when to implement behaviours versus hard coding for things like this. Ideally I think Toolbox module would define some sort of behaviour for implementing strategies. So maybe there’s a selection callback but also a mutation and crossover callback. Then you implement some defaults with like Toolbox.Selection module but users of the lib can extend with their own versions without having to touch the lib code.

In chapter 6 there is absolutely a Toolbox.Crossover module being introduced.

Adjusting the Selection Rate

n = round(length(population) * select_rate)
n = if rem(n, 2) == 0, do: n, else: n + 1

looks weird to me. I don’t like the immediate rebinding. I’d rewrite as something like:

n =
  case round(length(population) * select_rate) do
    x when rem(x, 2) == 0 -> x
    x -> x + 1
  end

In getting the diff between population and parents, is using MapSet intermediate structure more efficient than just Enum.filter? I would guess only noticeably so for very large population/parent sizes.

Roulette selection is by far the slowest and most difficult algorithm to implement

Why would that be the case? Seems like it would have been a way to speed up convergence in tournament by weighting competitors towards more fit individuals.

Regarding implementation of roulette I prefer the Stream.repeatedly(...) |> Enum.take(n) pattern. I also don’t like the implementation for the “roulette wheel spin” because I believe it will be influenced by the order in which chromosomes are placed in the list. I think a more precise way of doing “weighted random” selection would be something like

population
|> Enum.reduce([], fn chromosome, weighted_population -> Enum.reduce(1..chromosome.fitness, weighted_population, fn _ -> [chromosome | weighted_population] end) end)
|> Enum.random()

I do recognize this is not an efficient implementation but it avoids unintentionally favoring items at the beginning of the list.