Thank you, that helped me find my mistake: I had written for _ < 1..100 instead of for _ <- 1..100
rvirding
Creator of Erlang
2
code-shoily
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
stevensonmt
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 -> sumcan be rewritten aszip_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. 
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
rvirding
Creator of Erlang
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
seanmor5
Author of Genetic Algorithms in Elixir
I am glad to see so many people enjoying the book
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
6
stevensonmt
Sorry for letting the momentum slow on this thread. Life, 
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.
-
https://ecs.wgtn.ac.nz/foswiki/pub/Main/TechnicalReportSeries/ECSTR09-10.pdf
-
Higher selection pressure leads to faster convergence
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 thinkToolboxmodule would define some sort of behaviour for implementing strategies. So maybe there’s aselectioncallback but also amutationandcrossovercallback. Then you implement some defaults with likeToolbox.Selectionmodule 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
polvalente
Nx Core Team
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
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
stevensonmt
polvalente
Nx Core Team
Nx.Random is built on top of a stateless PRNG concept, so the key is what carries the state forward, but in a functional way. In general, the functions you’ll normally use will Nx.Random.split the key so that it can be used for whatever inside, and the other half is passed forward.
You can think of it as if each :rand call returned a new seed for you to pass into :rand.seed before calling the next function, in a deterministic way.
3
stevensonmt
Finished chapter 6. Super interesting and I appreciated the invitation to do implementations of other crossover strategies as an exercise. Here are my implementations for messy single point, multipoint, and cycle crossover strategies. Could do with some guards/specs because the implementations depend on the chromosome definition used in the book. Tips/critiques welcome!
def messy_single_point(p1, p2) do
cx1 = :rand.uniform(length(p1.genes) - 1)
cx2 = :rand.uniform(length(p2.genes) - 1)
{h1, t1} = Enum.split(p1.genes, cx1)
{h2, t2} = Enum.split(p2.genes, cx2)
c1 = h1 ++ t2
c2 = h2 ++ t1
{%Chromosome{genes: c1, size: length(c1)}, %Chromosome{genes: c2, size: length(c2)}}
end
def multipoint(p1, p2, k) do
cxs =
Stream.repeatedly(fn -> :rand.uniform(length(p1.genes) - 1) end)
|> Enum.take(k)
cxs
|> Enum.reduce({p1.genes, p2.genes}, fn cx, {c1, c2} ->
[{h1, t1}, {h2, t2}] = Enum.map([c1, c2], &Enum.split(&1, cx))
{h1 ++ t2, h2 ++ t1}
end)
|> Tuple.to_list()
|> Enum.map(fn genes -> %Chromosome{genes: genes, size: length(genes)} end)
|> List.to_tuple()
end
def cycle(p1, p2) do
[arr1, arr2] =
[p1.genes, p2.genes]
|> Enum.map(fn list ->
list |> Enum.with_index() |> Map.new(fn {v, k} -> {k, v} end)
end)
cycle_helper(arr1, arr2, 0, %{}, %{})
end
defp cycle_helper(arr1, arr2, ndx, c1, c2) do
if arr1[ndx] in Map.values(c1) do
cycle_completed(arr1, arr2, c1, c2)
else
v1 = Map.get(arr1, ndx)
v2 = Map.get(arr2, ndx)
c1 = Map.put(c1, ndx, v1)
c2 = Map.put(c2, ndx, v2)
ndx = find_index(v1, arr2)
cycle_helper(arr1, arr2, ndx, c1, c2)
end
end
defp cycle_completed(arr1, arr2, c1, c2) do
[{arr2, c1}, {arr1, c2}]
|> Enum.map(fn {p, c} ->
p
|> Enum.reduce(c, fn {k, v}, acc ->
Map.put_new(acc, k, v)
end)
end)
|> Enum.map(fn map -> map |> Enum.sort_by(fn {k, _v} -> k end) |> Enum.map(&elem(&1, 1)) end)
|> Enum.map(fn genes -> %Chromosome{genes: genes, size: length(genes)} end)
|> List.to_tuple()
end
defp find_index(val, arr) do
arr |> Enum.find(fn {_k, v} -> v == val end) |> elem(0)
end
I leaned heavily on this paper for the cycle implementation, and of course the author’s own Genex lib for the messy single point implementation.
2