Genetic Algorithms in Elixir Book Club!

Elixir Framework Forums Nx Forum
,
21

Chapter 2

Okay, so chapter 1 mostly introduced genetic algorithms and this population > evaluate > selection > crossover > mutation workflow, but had a lot of the parameters hard-coded, and it was presented as a stand-alone exs script. By the time I finished it, I knew what was coming in chapter 2.

So, we took everything learnt in chapter 1, and modularized it in chapter 2. Lift the hard-coded values and turn them into (hyper)parameters, inject the genotype and fitness function, and have the solution run while punching everything in.

All in all, a nice supplement to chapter 1, quite a few new concepts to learn (Hyper-parameters!). And learned a new word: Genotype.

No, I looked up genotype and saw the definition read as:

In a broad sense, the term “genotype” refers to the genetic makeup of an organism ; in other words, it describes an organism’s complete set of genes. In a more narrow sense, the term can be used to refer to the alleles, or variant forms of a gene, that are carried by an organism.

I was wondering why the function name wasn’t something like make_chromosome or something like that, but this term seemed to be a good fit for the purpose!

Error?

On page 27, when run was defined, we see fitness_function as the first argument. However, on page 28 when it introduces the opt parameter, it has genotype as the first argument (We see the same thing at the bottom of that page too as run receives code). However, on page 30, when run is called to form solution, we see soln = Genetic.run(fitness_function, genotype, max_fitness), fitness_function is back at number 1 position. Update: Looks like someone already reported this one here!

Looking at how population gets the first spot for other functions and fitness_function being second, I feel it should also be the case for run. But even if not, the function got different signatures here.

Looking forward to starting next weekend, I’ll get back with update once done with that.

2 Likes
22

I will join in as much as I can, sounds really interesting.

4 Likes
23

That’s a good catch on Chapter 2, but the way individual problems gets addressed is refactored in Chapter 3 so that the order of parameters is not an issue when Genetic.run is called.

You’ve hit on something that I’ll mention when I put together my thoughts more cleanly, but coming from a medical/biology background the metaphor is slightly skewed. As you’ve pointed out a genotype refers to the makeup of an organism, not of an individual chromosome. And populations are collections of organisms, not collections of chromosomes. So really the Russian doll terminology should be population -> organism -> chromosome -> gene -> allele. It’s not a substantive issue and probably not something specific to this book, but it requires a little shift in my head every time.

2 Likes
24

I’m curious if you’re aware of any movement to use Erlang in this type of problem. Given how @AstonJ has categorized this thread in the Nx Forum I’m assuming the book is headed toward using that library extensively. If not, are there any particular features of Elixir that make Nx possible where it would not be in Erlang?

3 Likes
25

I haven’t read the book myself, but I put the thread here as generally I feel the Nx section is a good fit for all ML/A.I type threads (would you agree?)

1 Like
26

Now that you folks bring it, I remembered a question I asked myself when I last picked this book.

How much of this book will change due to the arrival of the Nx mix of tools? Beyond just converting all Enum into Nx?

This might as well be a silly question as I don’t have much exposure to ML, but in general I see Python folks bring Numpy/Pandas the moment they smell a puff of data. Does interfacing with any C++ backend for genetic algorithm via Nx feel like a feasible direction to aim at?

Again, I might be asking this entirely prematurely, some stuff can perfectly be done through standard lib.

5 Likes
27

Certainly seems reasonable. And if nothing else explorers can maybe add to the book by experimenting with Nx if the authors don’t go that route. (I haven’t gotten past chapter 4 and don’t have access at work right now to check if the book already uses Nx or not.)

3 Likes
28

The book is actually what spawned the idea for Nx. Unless it was updated for a second edition (which I’m unaware of), I don’t think it has Nx code.

I’d be more than happy to help with translating things to Nx, though. I probably won’t have enough time to actually participate in the book club, but I can help with code :slight_smile:

6 Likes
29

Sounds like a perfect example of a virtuous cycle!

3 Likes
30

Would love to have the livebook repository along with visualizations. It’ll help to understand the algorithms better.

5 Likes
31

I honestly don’t know. I have mainly so far done it for personal interest.

From what I can see and through some simple tests Nx seems to work well with Erlang. I have at least testade the simple examples given in the “Nx for absolute beginners” and “Up and running Nx”. I made a very simple Erlang module called nx which just passes all the calls through to Nx. As there a re no macros in Nx there are no problems calling it from Erlang.

The thing to remember is that Elixir runs on top of Erlang/BEAM so everything it does goes through them so it can all be done directly from Erlang. The question is more what the interface looks like. As soon as it includes Elixir macros then it becomes more complex to handle. And the module names don’t help. :wink:

I must also admit I have another interest. I have been testing from LFE :smile: This is about the same as for Erlang but if I ever get to the stage of needing macros then LFE is much easier than Erlang. And I like the parentheses. :wink:

We shall see how it goes with the book.

3 Likes
32

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 Likes
33

5 posts were split to a new topic: Nx for LFE and other BEAM languages

34

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 Like
35

Hi Andre, welcome! :smiley:

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

39

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 Likes
40

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 Likes
41

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 Likes
42

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 Like
43

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 Like