Genetic Algorithms in Elixir Book Club!

Elixir Framework Forums Nx Forum
,
44

For modeling, I store “the board” as a map of points, and the genes are also a map of points. It’s super inefficient, but ehh, it was easy.

  def genotype(_i) do
    board = %{
      {0, 0} => 5,
      {1, 0} => 3,
      ...
    }

    genes = Enum.reduce(0..8, %{}, fn x, acc ->
      Enum.reduce(0..8, acc, fn y, acc ->
        if Map.has_key?(board, {x, y}) do
          acc
        else
          Map.put(acc, {x, y}, Enum.random(1..9))
        end
      end)
    end)

    %Chromosome{ genes: genes, extra: %{board: board} }
  end

  def fitness(%Chromosome{} = c) do
    Enum.reduce(0..8, 0, fn i, acc ->
      score_row(c, i) + score_col(c, i) + acc
    end)
  end

Where score_row and score_col return 1 if all numbers are unique, or 0 otherwise. I also experimented with score being the number of unique items in a row/col. Didn’t change anything.

Oh, also my selection is just elite.

I’m curious how this works:

Which gets the answer in only 37 generations… but I don’t really want to sift through a whole bunch of undocumented and unorganized python code. Kinda wish the readme just said the general strategy in English.

1 Like
45

I think it would be possible to have all valid rows and all valid columns but still not have all valid sub-grids.

I don’t think that’s your issue with efficiency though.

FWIW my naive solution is struggling as well. I’m just using a list of integers 1…9 with length 81 as the board. The puzzle input is processed with each wildcard/blank replaced by random integer 1…9 to generate the chromosome. Crossover is at a random point in the list. Mutation is a potential problem. The way the lib is setup in the book the mutation function is hard coded and not modifiable per problem. In this case we can’t shuffle the genes outright because the puzzle provides some fixed values. Should mutation/2 and maybe even crossover/2 be part of the behaviour callbacks?
For now I’ve just set the mutation rate to zero. I’m using a wholesale population reset if the temperature drops below a certain value and a generation limit to terminate if perfect fitness is not found. Can’t figure out why but for some reason after the first time it resets it then resets after every generation automatically unless I reset with a really high default temperature. It’s still not getting anywhere close to a full solution though. I think the best fitness I’ve seen is 7 out of a needed 27. I haven’t let it run more than a few hundred generations yet though.

1 Like
46

That’s why I store the “board” separately from the “genes”. That way I can do something like…

genes = Enum.shuffle(genes) |> Map.new()

My Problem behaviour does that!

2 Likes
47

After you shuffle the genes to a new map do you then merge the “board” map to overwrite the values at the fixed positions provided by the input?

1 Like
48

No, the genes don’t have the fixed positions at all. It’s part of the fitness calculation that (kinda) merges the the two:

  def score_row(%Chromosome{} = c, i) do
    Enum.map(0..8, fn x ->
      Map.get(c.genes, {x, i}) || Map.get(c.extra.board, {x, i})
    end)
    |> score()
  end

It’s just iterates over (x, y) points and looks in the genes, but falls back to the board.

This is probably a not a good way to do it, but it was just the first thing that came to mind, and I wanted to code up something quickly cuz I was excited to see if it would work… :slight_smile:

Keeping the board separate lets me easily shuffle genes (for mutation), or do that random crossover point technique.

2 Likes
49

Just a gentle push to ask those who have started the book to weigh in with their thoughts if they haven’t already. If the thread is analogous to an evolutionary algorithm deriving interesting insights, we need diversity of thoughts to drive the discussion. And I have too many posts here, convergence on the least fit individual is not ideal :lol:

3 Likes
50

Last weekend was crazy for me. I’ll read from tomorrow and post chapters 3 and 4 over the following few days. I skimmed throff if h the third chapter. Seems like it’s going to get better quickly

1 Like
51

This thread is making me want to read the book - I just wish I had time to move it up my reading list! :upside_down_face:

That’s good to hear - I quite like having little refreshers in books like these as I’m a huge fan of the repeat-reinforce style of learning :003:

2 Likes
52

I’m trying to only post about one chapter at a time, mostly to keep from running out of ways to keep the thread going when I get behind in reading, but I have to say chapter 5 is where things are getting really really interesting to me. Super excited for the rest of the book. I wish there were more books like this that were both language specific and problem-space/algorithm-type specific. Like the Exploring Graphs with Elixir book was great for getting familiar with graphs broadly and Elixir/Erlang libs for working with them, but I’d love a book that was really about graph algorithms (BFS, DFS, union-find, etc) in Elixir.

2 Likes
53

I hold the same sentiment about Elixir book on graphs. And also regarding these types of books in general. We do need more of these.

As for chapters 3/4. Got Good Friday weekend this one so will work on those during that time. Excited for it (as well as rest of the book)

2 Likes
54

I am a bit behind :wink: but I have finally been able to start looking at the book. Yay! :smile:

I do have one question: is there an errata for the book? Just directly entering the code in the first chapter gives me runtime errors, it complains about the _ in the initial for loops. And my elixir is not yet upto correcting it. :anguished: I mean for loops? :smile:

3 Likes
55

There is an errata.

–
I’m a bit late due to me prioritizing ramping up my OTP skills first.
Two observations after reading the first 4 chapters and skimming the rest a bit:

  1. I love how approachable the author lays out both Elixir and the topic itself.
  2. Working everything through it in my editor and also comparing with the provided code, I stumble over some things that are likely errors. So far they actually forced me to better understand the language - will try to collect them for errata :blush:
2 Likes
56

Thank you, that helped me find my mistake: I had written for _ < 1..100 instead of for _ <- 1..100

2 Likes
57

I have just finished Chapter 3. It seems like further refactoring or Chapter 2 by introducing one new form of generalization.

However I did struggle to understand the difference between genotype and phenotype. I looked into the formal definition of the latter and got confused.

I am going to take another exploration on these two terms and update this comment with whatever I learn, otherwise move on with chapter 4 tomorrow. It’s be cool if anyone can eli5 me though.

It was an enjoyable chapter, some nice refresher on Elixir, and the way concepts are introduced in very small chunk is quite nice.

1 Like
58

I think I’m going to stop with my posts of my “study notes”. If anyone cares to see them as a sort of terrible Cliff’s notes for the book the file is here.

My thoughts on chapter 4:

  • Constraint problems – TIL the term for that type of problem, really the entire motivation for me to pick up this book was frustration at solving the Einstein’s house problem on Exercism

I would have thought that creating a module attribute with a map or ETS table for looking up profits and weights would be the obvious solution, but I always feel clever when I make use of zip functions. In this case you end up zipping over the collection every time you call the fitness function, so caching the weights and profits for later access is probably a better approach.

Stylistic bike-shedding alert:

zip -> map -> sum can be rewritten as zip_reduce

If all cargo can fit the problem is trivial, so using the total available profit for ALL cargo as a termination criteria seems odd … which was apparently the author’s point LOL.

Penalty Functions

I’d like to see the penalty function defined as a private function independent of the fitness function, even if it’s only ever called by the fitness function. This would make it easier to generalize the fitness function and even include a flag in opts to apply a penalty or not.

Termination Criteria

The goal is to produce the best solution possible, even when you don’t know that it’s the absolute best.

This concept throws me off. I’m used to thinking a fundamental concept of pure functional programming that states any function passed a given input always returns the same output. It seems that you could give a genetic algo some input and end up with slightly different output. I suppose any function interfacing with :rand must be impure.

Possible errors in OneMax example for average fitness threshold. Since population is a list of Chromosome structs, you need to first map the population to an enumerable of just genes before calculating average fitness.

avg = population |> Enum.map(&Map.get(&1, :genes)) |> Enum.map(&(Enum.sum(&1) / length(&1)))

I might be wrong, but it seem to me that all three termination criteria converge on 42 and never terminate b/c the fitness function is just the sum and the Genetic module sorts by >= after applying the fitness function. To achieve convergence to minimum the fitness function needs to be changed to Enum.sum(choromosome.genes) * -1. The average is trickier. Perhaps Genetic.evaluate/3 should be passed a sorter function in addition to the fitness function. This could be included in opts keyword list.

Tracking time since last improvement → light bulb moment for me.

Schema and theorems and heuristics, oh my! Getting into the fancy words now. :slight_smile:

With multiple factor optimization applying weights to various factors makes me think these weights should be passed to the fitness function in opts. Maybe require something like fitness_factors with guards to catch that all keys in opts.fitness_factors are fields in chromosome.

Perceptual data – ranking cannot be calculated mathematically but ranking by user can transform into mathematical fitness via interactive fitness functions that require user input. Coming from a background of constantly interfacing with people to acquire, weight, and sort various types of information for deductive processing, this type of data is much more interesting to me.

@code-shoily – regarding genotype vs phenotype, think of it as the encoded data vs the data itself. For the ship cargo example, the phenotype refers to the collection of crates defined by their weight and profit, but the genotype is just the list of ones and zeroes that encode which crates are selected.

3 Likes
59

Yay! I have finally completed chapter 1, no it wasn’t difficult just couldn’t find the time. Anyway I have been amusing myself with translating it from Elixir to Erlang. Pretty straight forward once you realise exactly how all the Enum functions work. My goal is to NOT use Elixir libraries but only standard Erlang stuff. We shall see how it goes in later chapters, especially when migrating from mix to rebar3.

2 Likes
60

I am glad to see so many people enjoying the book :slight_smile:

If you end up with questions or find errata you can let me know. I don’t have a ton of time but I can try to help. If you enjoy the book, please leave a review on Amazon. It really helps!

Finally, in a little bit I hope to be able to share something for the next Machine Learning focused book club :slight_smile:

6 Likes
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.

1 Like
62

For the “weighted random” selection, if using Nx, the Nx.Random.choice function accepts an optional probability tensor that can be constructed from the fitness functions, instead of generating a flat list from those ranges. You’d have something like the code below. I’m not exactly sure of what a chromosome actually contains, but this just represents an arbitrary map with the fitness key present :slight_smile:

iex(1)> Mix.install [:nx]
:ok
iex(2)> key = Nx.Random.key(System.system_time())
#Nx.Tensor<
  u32[2]
  [391705150, 368691609]
>
iex(3)> chromosomes = [%{data: :a, fitness: 9}, %{data: :b, fitness: 1}]
[%{data: :a, fitness: 9}, %{data: :b, fitness: 1}]
iex(4)> fitness = chromosomes |> Enum.map(& &1.fitness) |> Nx.tensor()
#Nx.Tensor<
  s64[2]
  [9, 1]
>
iex(5)> probs = Nx.divide(fitness, Nx.sum(fitness))
#Nx.Tensor<
  f32[2]
  [0.8999999761581421, 0.10000000149011612]
>
iex(6)> idx = Nx.tensor([0, 1])
#Nx.Tensor<
  s64[2]
  [0, 1]
>
iex(7)> {idx, new_key} = Nx.Random.choice(key, idx, probs, samples: 5)
{#Nx.Tensor<
   s64[5]
   [0, 1, 0, 0, 0]
 >,
 #Nx.Tensor<
   u32[2]
   [3343452330, 3272391746]
 >}
iex(8)> idx |> Nx.to_list() |> Enum.map(&Enum.at(chromosomes, &1))
[
  %{data: :a, fitness: 9},
  %{data: :b, fitness: 1},
  %{data: :a, fitness: 9},
  %{data: :a, fitness: 9},
  %{data: :a, fitness: 9}
]
2 Likes
63

That’s pretty nice. What’s the key parameter doing in the Nx.Random.choice/4 call?

1 Like