stevensonmt

stevensonmt

Below are my stream of consciousness notes on Chapter 2. Overall not a lot of new meat to chew in this chapter, but I appreciate the time taken to ensure the basic concepts are established before moving into the deep end.

Ch 2

Populations should use data structures that implement Enumerable protocol.
Using List as default will be simplest form of population.

  • Initialize population

    • Random list of chromosomes (i.e., possible solutions)
    • Initialization function should be generic (i.e., not care structure used by chromosome)

  • Evaluate population

    • Apply the fitness function (i.e., sort population according to fitness criteria)
    • Fitness will be defined unique to each problem
    • population -> fitness.() -> sorted_population

  • Select parents

    • Elitism selection pairs strongest chromosomes as parents
    • This is the point my background gets in the way of the metaphor. In biology, a population is a collection of organisms. Each organism can have one or many chromosomes. Each chromosome can have one or many genes. Each gene can have one or many values. Unclear if this is just the simplest implementation of a genetic algorithm and in future chapters or more advanced implementations the additional nested structure is utilized more consistent with the biology metaphor.
    • population -> transform_into_parent_pairs.() -> population_ready_for_crossover

  • Creating children

    • Apply the crossover function to parents
    • parents -> crossover.() -> children where size(children) == size(initial_pop)

  • Mutation

    • Prevents premature convergence
    • population -> mutate.() -> x_men where mutate only affects a small % of population

  • Termination criteria

    • criteria are problem-specific
    • simplest case is reaching desired value known ahead of time (max value in one-max e.g.)

  • Hyperparameters

    • set prior to training algorithm
    • includes pop size, mutation rate, etc
    • use optional list of parameters in keyword list to allow rapidly adjusting these params
      (I would have instinctively used module attributes, but this is more opaque and less
      generic for a framework)

Using mix run <project_root>/scripts/<script>.exs is a pretty cool structure for evaluating examples using a lib.

3
Post #31
AndrGab

AndrGab

Hi @AstonJ
I have a Biomedical Science Degree in Brazil and I’m a elixir developer.
I’d like to help the project. How can I do that?
Thank you

1
Post #33
AstonJ

AstonJ OP

Hi Andre, welcome! :smiley:

In what way would you like to help? Would you like to join this book club? :blush:

0
Post #34
cjbottaro

cjbottaro

I finished chapters 1-4 last night. It went pretty quickly because I could skip everything regarding the Elixir language itself. I almost (selfishly) wished it didn’t try to teach Elixir.

I noticed a few strange paradigms…

{{h1, t1}, {h2, t2}}
  = {Enum.split(p1, cx_point),
     Enum.split(p2, cx_point)}

Seems much more readable to me like this…

{h1, t1} = Enum.split(p1, cx_point)
{h2, t2} = Enum.split(p2, cx_point)

Also the “your select() function should produce something easy for your crossover() function to consume, hence use tuples”…

population = Enum.chunk_every(population, 2)
|> Enum.map(&List.to_tuple/1)
...
Enum.reduce(population, [], fn {p1, p2}, acc -> ... end)

Why not just pattern match on a 2-element list and skip the map iteration?

population = Enum.chunk_every(population, 2)
...
Enum.reduce(population, [], fn [p1, p2], acc -> ... end)

As for the genetic algorithm material itself… love it! It’s extremely accessible. The author makes it so easy and intuitive to understand.

I was surprised to learn that genotypes are usually pretty simply (most commonly just a bitstring). I would have imagined they would get pretty complex like, structs and recursive data structures and what not. There are the tree/graph genotypes, but he said they aren’t very effective.

3
Post #38
m4hi2

m4hi2

I noticed a few strange paradigms…

{{h1, t1}, {h2, t2}}
  = {Enum.split(p1, cx_point),
     Enum.split(p2, cx_point)}

Seems much more readable to me like this…

{h1, t1} = Enum.split(p1, cx_point)
{h2, t2} = Enum.split(p2, cx_point)

I was away from elixir for almost a year and this part got me scratching my head. The way you wrote is easier to read.

2
Post #39
stevensonmt

stevensonmt

More stream of consciousness notes on the third chapter. Starting to get more interesting as I can tell by more of my notes ending in question marks. :wink:

Ch 3

What sort of problem would the age of chromosome determine fitness? Is this simply another method of preventing premature convergence? Or just a way to keep an algorithm from running forever when an optimal solution can’t be pre-defined?

Genes are typically represented using list types or other enumberable data types, like trees, sets, and arrays.

Not sure about trees, but arrays, at least the :array implementation from Erlang, do not implement Enumerable. I guess you could implement it manually. Author probably just meant arrays more generically.

  • Structs for chromosomes
    • needs fields for fitness, size, age, genes as basic foundation
    • why is size a basic need?
    • using @enforce_keys for fields that don’t have a default defined but that shouldn’t be nil is an obvious technique that I had not even realized was happening in other code I’ve read

I have no formal comp sci education, but I’ve been reading about programming and practicing writing programs for about 6 years off and on. This is probably the first time I’ve seen anyone actually define the term abstraction in the context of programming and explicitly state the purpose an abstraction should serve.

The purpose of abstraction is sto force you to think of things at different levels of specificity.

Behaviours are a contract

  • Behaviours enforce specifications by requiring certain functions be implemented
  • Callbacks are function signatures with return types
  • Since genetic algos require genotypes, fitness functions, and termination criteria, we need callbacks for all 3
    • all examples in book will use numbers for fitness but not necessary, only need to be sortable in some way

Encoding

  • Encoding = choice of data type to represent solutions
    • should not have extraneous information
  • Importance of choosing correct and sparse encoding does not seem unique to genetic algos but I appreciate the point being emphasized here as it’s something I continually struggle with
  • Reducing solutions to collections of binary representations is simplest and allows bitstring as genotype
    • People are always doing clever things with bitwise that I don’t grok, so I’m curious how much that sort of thing is going to come up in future chapters
  • Permutation also common and probably more intuitive to me
  • Real Value genotype feels inappropriately named so I must be missing something. The examples show a collection of genes with real-value alleles. Whereas permutation the entire collection of genes, i.e., the genotype, is what’s assessed.
  • Just going to ignore tree/graph genotypes but sounds very interesting from academic perspective

OneMax

Nothing particularly interesting going on here.

Speller

  • Stream.repeatedly + Enum.random is another little nugget with obvious utility that I see all the time and immediately forget whenever I could actually use it
  • Increasing population size and mutation rate did not help convergence

Generic note: using module name as parameter and then dot notation to call functions from that module – another light bulb moment for me.

Already seeing that this book is teaching me not only the specifics of genetic algorithms but some Elixir specific practices that I probably should have picked up by now.

2
Post #40
cjbottaro

cjbottaro

I tried to make a sudoku solver using what I learned from Ch 1-5 of the book. It doesn’t work… :joy: I let it run for about 20k generations and the score didn’t seem like it was moving.

Fitness is the count of rows and columns that all contain unique numbers (i.e. the count of solved rows/cols, so a score of 18 means solved). My crossover is the same as the OneMax example… which is think is the culprit.

Any ideas? I Googled and mostly it’s just code examples. Not really any solutions in plain English. There is one blog post, but his took 2.6 million generations to solve. The top Google hit is a Python example that got it in dozens of generations… :thinking:

1
Post #41
stevensonmt

stevensonmt

What are you using for the fitness function and how did you model the chromosome?

This article suggests sudoku is generally a difficult problem space for genetic algorithms.

I’m running into an issue trying to encode possible solutions as bitstrings where each spot on the grid is encoded with its index and value as <<index::8, value::4>> so that the total for each spot is 12 bits, and the total for a 9x9 puzzle is 12 * 81 = 972 bits. I had thought with this encoding I could check that randomly generated solutions matched the positions given in the puzzle input via

<<solution::972>> = encoded_solution
<<puzzle::972>> = encoded_puzzle
(solution &&& puzzle) == puzzle

but this ends up being way too inefficient due to the number of combinations that are invalid.

1
Post #42
cjbottaro

cjbottaro

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:
https://github.com/ctjacobs/sudoku-genetic-algorithm

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
Post #43
stevensonmt

stevensonmt

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
Post #44