I was getting cozy in my chair, still blowing my hot tea, when I found this bug in page 1:
130 trillion paths → 1.3 trillion paths.
Quite a lot paths as well, but still, it’s a two-order magnitude error.
fceruti
code-shoily
Good catch. Post an erratum maybe?
Update: Added the link here for future reference. Also, clicking erratum on my pdf sent me to the book link and then I had to click again to get to the DevTalk link.
2
code-shoily
I wanted to try out some VegaLite on this and these are what I got:
Without Mutation:
With Mutation:
I did not configure the chart for look pretty though, just added:
chart =
Vl.new(width: 400, height: 400)
|> Vl.mark(:line)
|> Vl.encode_field(:x, "x", type: :quantitative)
|> Vl.encode_field(:y, "y", type: :quantitative)
|> Kino.VegaLite.new()
|> Kino.render()
and tweaked the algorithm to look like:
algorithm = fn population, iter, algorithm ->
best = Enum.max_by(population, &Enum.sum/1)
IO.write("\rCurrent Best (# #{iter}): " <> Integer.to_string(Enum.sum(best)))
Kino.VegaLite.push(chart, %{x: iter, y: Integer.to_string(Enum.sum(best))})
if Enum.sum(best) == 1000 do
best
else
population
|> evaluate.()
|> selection.()
|> crossover.()
|> mutation.()
|> algorithm.(iter + 1, algorithm)
end
end
The one without mutation nearly broke my LiveBook though
3
stevensonmt
I think the algorithm will always run until it reaches the terminating condition, right? The only terminating condition was for Enum.sum(best) == 1000 so it should run until it hits that or maybe hits some sort of timeout. On my machine it definitely slowed down in progress around 950 but eventually reached 1000.
My notes as I was going through chapter 1:
Basic concept/flow of genetic algorithm:
- Initialize population
- Evaluate population (apply fitness function)
- Select parents
- Create children (crossover)
- Mutate children (introduce randomness)
- Loop back to evaluate
Population size (i.e., number of chormosomes)
- larger population → longer transformation step
- smaller population → more generations needed to produce soln and more
likely to have premature convergence
Premature convergence
- focusing on solution that appears “good enough” when more optimal solutions exist
- Mutation helps fight premature convergence
Initial example shows how to get to a solution when you know what the answer is, but how
will genetic algorithms work when you don’t know the solution ahead of time? ??
- Fitness functions should be sorting/ordering (?)
Single point crossover I assume is faster per generation but may lead to more generations needed if initial population is small.
Mutation
Mutation probability in example is 5%.
- Impact of higher/lower probability of mutation?
- I assume higher probability leads to slower optimization as higher chance of undoing
progress, however it might serve to counterbalance low initial population size/diversity
- I assume higher probability leads to slower optimization as higher chance of undoing
- The example mutation shuffles entire chromosome. How does single gene mutation or transposition mutation impact performance?
- Again, I assume that broader mutations lead to more diversity and can offset small initial
population size at expense of potentially requiring more generations to acheive optimal solution
- Again, I assume that broader mutations lead to more diversity and can offset small initial
4
code-shoily
Chapter 1 is read!
This was a great read. I don’t have any prior exposure to genetic algorithm, other than my university AI course that happened 20 years ago. So, this was quite a fun experience for me.
My initial reaction was to read the prose first and take a stab at the code later, but the way the example was arranged, I felt it would be more convenient if I experiment with each function and their result on a shell, and what better shell than LiveBook?
I experimented with each artifacts (i.e. population, evaluate, selection, crossover, mutation (when it appeared after the interval), algorithm). I even came up with an acronym (P.E.S.C.A), until M for mutation came along and mutated my acronym into an unpronounceable one. I keep thinking evaluate could evaluation to belong to same parts of speech class as all other functions (or selection → select, mutation → mutate etc). Or maybe that’s just me.
I really liked how, for the first time in my life, I understood what an AI book is trying to tell me in one run. The writing style is enjoyable and the introductory elements fit right in. The presentation, both in terms of english and code, are very easy to visualize. I have not seen any genetic algorithm code in other languages but I felt like both the recursion and piped workflow is perfect representation. I eagerly await reading next chapters to see if this can turn into a generic pattern for larger set of problems.
I have discussed the code running completely without mutate (or is it mutation?) at all attempts I made (contrary to what the book said), but one update is that, when I tried the same on 10, 100 on REPLIT (1 CPU, OTP 24 etc), then it kept dancing around 82, 87 for 200k iterations 
… but that aside, running all the code is strongly recommended if you ask me, even better with LiveBook. It gives a “feel” for what the author is trying to explain.
That’s my brief summary of my experience with chapter 1. A bunch of things I would like to do (Please folks, tell me if this would be futile):
- Create a repository of livemds for the code
- Try using the
Nxdata structures and functions to solve the same problems, who knows, if chapter permits,Explore? - Produce
VegaLitecharts. - Benchmark things on different backends (I will admit, I don’t even know what backends will do for these problems)
Anyways, I will try to pick one or more of those and share it with y’all. That’ll be all for my chapter 1. I briefly read chapter 2 and already like the way it built upon Chapter 1. Thank you @AstonJ and @stevensonmt for doing this.
4
stevensonmt
stevensonmt
What do you mean by iterator here? I’m mostly familiar with that in the context of Rust and think of anything that’s Enumerable in Elixir as being roughly analogous to Rust iterators via the Enum module.
2
code-shoily
My bad with quick typing on the phone. I mean ‘iteration-counter’ - something that keeps track of each iteration (I mean, every time algorithm is called). Thank you for catching this.
2
fceruti
code-shoily
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