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.
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.
I’m stuck on chapter 7. The fitness function implementation is acting weird in that the chromosome does not always follow a binary digit representation, which then raises an error. I think it’s some sort of overflow happening in the Bitwise.bxor call but not sure how to troubleshoot. Here’s what I’m seeing:
GENES: [0, 1, 2, 3, 4, 5, 7, 8]
** (ArgumentError) errors were found at the given arguments:
* 1st argument: not a textual representation of an integer
:erlang.binary_to_integer("01234578", 2)
scripts/codebreaker.exs:22: Codebreaker.fitness_fun/1
My code is below. You can see I tried to use Integer.undigits first but that gives an error of invalid digit 2 in base 2.
def fitness_fun(chromosome) do
IO.inspect(chromosome.genes, label: :GENES)
target = "ILoveGeneticAlgorithsm"
encrypted = 'LIjs`B`kqlfDibjwlqmhv'
cipher = fn word, key -> Enum.map(word, &rem(Bitwise.bxor(&1, key), 32_768)) end
# key = Integer.undigits(chromosome.genes, 2)
key =
chromosome.genes
|> Enum.map_join(&Integer.to_string(&1))
|> String.to_integer(2)
guess = List.to_string(cipher.(encrypted, key))
String.jaro_distance(target, guess)
end
If I rescue the error I just end up with convergence on a bad chromosome for some reason.
I ran the author’s provided code sample for the chapter and have the same issue. Or, I did until I recompiled everything. So something is off in my actual Genetic library code not in the script itself.
Okay to ignore all that above. I had implemented a chromosome repair function that was specific to one chromosome type and it was screwing things up. So I don’t get that error but currently my code is converging on a fitness of about 0.97 and never completing. Guess I have to get through the rest of the chapter.
Dear Stephen,
It seems that you had some typos at the target and the encrypted variables. Here is the code of yours working (at in my local machine);
def fitness_function(chromosome) do
# IO.inspect(chromosome.genes, label: :GENES)
target = "ILoveGeneticAlgorithms"
encrypted = 'LIjs`B`k`qlfDibjwlqmhv'
cipher = fn word, key -> Enum.map(word, &rem(Bitwise.bxor(&1, key), 32_768)) end
# key = Integer.undigits(chromosome.genes, 2)
key =
chromosome.genes
|> Enum.map_join(&Integer.to_string(&1))
|> String.to_integer(2)
guess = List.to_string(cipher.(encrypted, key))
String.jaro_distance(target, guess)
end
A typical result I get by running this script is:
Current best: 1.09242424242424243
The Key is 2152810337942732805
Well that’s embarrassing. Thanks. It’s still weird that it returns different values for the key on different runs.
I finished chapter 7.
Integer.undigits/2 is much nicer than the provided key generation implementation, imo.
The provided scramble/2 seems inefficient due to the use of Enum.slice in 3 areas and concatenating 3 lists together which requires iterating over the genes multiple times. I came up with a way to circumvent that approach, which I think is more efficient:
def scramble(chromosome, n) do
start = :rand.uniform(n - 1)
{lo, hi} =
if start + n >= chromosome.size do
{start - n, start}
else
{start, start + n}
end
swaps =
lo..hi
|> Enum.zip(Enum.shuffle(lo..hi))
|> Map.new()
arr = :array.from_list(chromosome.genes)
genes =
0..:array.sparse_size(arr)
|> Enum.reduce(arr, fn i, gs ->
cond do
i < lo -> gs
i > hi -> gs
true ->
new_val = :array.get(swaps[i], arr)
:array.set(i, new_val, gs)
end
end)
|> :array.to_list()
%Chromosome{genes: genes, size: chromosome.size}
end
My implementations of the swap, uniform, and invert mutation strategies:
@doc "Swap can be done for any genotype"
def swap(chromosome, n \\ 1) do
arr = chromosome.genes |> :array.from_list()
genes =
1..n
|> Enum.reduce(arr, fn _i, gs ->
[swap1, swap2] =
Stream.repeatedly(fn -> :rand.uniform(:array.sparse_size(arr) - 1) end) |> Enum.take(2)
v1 = :array.get(swap1, gs)
v2 = :array.get(swap2, gs)
gs = :array.set(swap1, v2, gs)
:array.set(swap2, v1, gs)
end)
|> :array.to_list()
%Chromosome{genes: genes, size: chromosome.size}
end
@doc "Uniform applies to binary or real-value genotypes but not permutations. For binary genotypes, the genotype parameter needs to be true. No absolute maximum value is assumed, but the limit for each mutation is arbitrarily fixed at double the current maximal value. Implementation does not ensure unique values for each gene. If unique values are necessary, the genotype parameter must be :unique."
def uniform(chromosome, true) do
genes = Stream.repeatedly(fn -> :rand.uniform(2) - 1 end) |> Enum.take(chromosome.size)
%Chromosome{genes: genes, size: chromosome.size}
end
def uniform(chromosome, false) do
genes =
Stream.repeatedly(fn -> :rand.uniform(Enum.max(chromosome.genes) * 2) end)
|> Enum.take(chromosome.size)
%Chromosome{genes: genes, size: chromosome.size}
end
def uniform(chromosome, :unique) do
genes =
Stream.repeatedly(fn -> :rand.uniform(Enum.max(chromosome.genes) * 2) end)
|> Enum.reduce_while(MapSet.new(), fn n, acc ->
if MapSet.size(acc) == chromosome.size do
{:halt, acc}
else
{:cont, MapSet.put(acc, n)}
end
end)
%Chromosome{genes: genes, size: chromosome.size}
end
def uniform(chromosome), do: uniform(chromosome, false)
@doc "Invert just reverses the genes, I guess."
def invert(chromosome),
do: %Chromosome{genes: Enum.reverse(chromosome.genes), size: chromosome.size}
Chapter 8 was interesting in the sense of really opening my eyes to how complex genetic algorithms can be made to model various problems.
The actual strategies and implementations addressed in the chapter are fairly similar to things seen in the other stages of the genetic algorithm architecture, so I don’t have much to say about them.
What really piqued my interest though was a bit at the end of the chapter about local neighborhoods of chromosomes and multipopulation genetic algorithms. The author made a sort of throw-away comment that multipopulation genetic algorithms benefit from being parallelizable. That sounds like a great fit for the Elixir/BEAM ecosystem.
On a side note, one of my potential side projects for the genetic algorithm approach is actually holiday scheduling for hospital coverage with my colleagues, so the example in the book was really apt for me.
Sorry for the long delay. With issues at work and my daughter graduating high school (who knew that came with so many different parental involvement activities?) I just haven’t had a free moment. At any rate got around to finishing up chapter 9. Disappointed that it didn’t seem to advance the actual genetic algorithm topic much, but I’m always excited to see libgraph in a project. The idea of tracking population history in an ETS table explored by libgraph functions is interesting. I think this technique could be useful in other situations such as tree traversal and path-finding. The other thought I had, though, was this sort of double abstraction of an ETS table behind a GenServer interface was not quite helpful. Maybe in later chapters where this genealogy is used more the design choice will make more sense.
Going to keep talking to myself here, I guess. 
I’m moving through the book much more slowly than I would like but life has been unavoidably busy in recent weeks/months. I’ve just gotten through chapter 10 and found it really fun. Eye candy is always exciting. Plus getting a peak at the alex library and Atari game simulation is just so cool. Highly encourage everyone to push through to this bit if you aren’t familiar with alex and are interested in genetic algorithms for bots playing games.
Momma didn’t raise no quitter!
Got through chapter 11. I want to make it clear that this book is actually quite fun to get through. Life has just been bananas around here so I have not had time to keep at it.
Chapter 11 could be extracted out and really be generalized to not only a ton of Elixir practices but also software development in general. I loved the benchmarking vs profiliing distinction and walking through steps of optimization. The use of NIFs was super cool.
On to Chapter 12!
I’ve finished the book. Chapter 12 was mostly overview of things you’ve probably picked up spending any time with Elixir such as typespecs and using credo and dialyzer. The one thing I would like to see more of from this chapter was the bit on testing. I actually think a second edition of the book written as “Test Driven Development of Genetic Algorithms in Elixir” would be really nice and more reasonably model how real applications might be developed with this approach.
Chapter 13 was an interesting overview of the problem domains that genetic algorithms can contribute to as wells as other texts to further your study. Gene I. Sher. Handbook of Neuroevolution Through Erlang looks particularly interesting.
© Copyright Elixir Forum | Terms | Privacy & Cookies
