tvanderpol

tvanderpol

Genetic Algorithms in Elixir: First stab at Ch1 algorithm converges just fine? (p28)

I’ve got something of the opposite of the usual problem - my code doesn’t fail in the way the text suggests it should (when it suggests premature convergence is the cause).

I’ve ran the code a fair bit and did some debug print injecting and such but I can’t really see anything out of the ordinary - it converges on the correct answer almost instantly if I run it without any additional debug and it takes a reasonable amount of generations from what I can tell by poking at it.

Now I am clear to continue the chapter as-is, and I understand the argument being made, but I don’t understand how the algorithm is meant to fail (I do in the abstract but I mean the code as written) and that’s bugging me.

Marked As Solved

seanmor5

seanmor5

Author of Genetic Algorithms in Elixir

There was a mistake in my version of the code that forced early convergence with smaller populations that isn’t present in the book’s transcription of the code.

To better demonstrate premature convergence: set chromosome size to 1000 and population size to 100. You’ll notice your version without mutation converges much slower than with mutation. You can continue to decrease the population size further and further and you’ll reach a point where progress completely stops.

Sorry about the confusion!

Also Liked

christhekeele

christhekeele

This was on quite a new Macbook, which may be influencing results from what’s expected.

MacBook Pro (16-inch, 2019)
2.4 GHz 8-Core Intel Core i9
32 GB 2667 MHz DDR4
Erlang/OTP 22 [erts-10.7.2] [64-bit] [smp:16:16]
Elixir 1.10.3

tvanderpol

tvanderpol

Perfect, thank you for responding so fast! That helps my understanding of exactly how it fails a lot.

christhekeele

christhekeele

I noticed this in the B1 edition as well!

Re:

$ elixir one_max.exs
Current Best: 32

But wait, what’s going on here? Why is the algorithm stopping on a best fitness below 42? No matter how many times you run it, the algorithm will almost always certainly stop improving below 42. The problem is premature convergence.

At this point, the chapter’s example code looks like:

Code to Date
population = for _ <- 1..10, do: for _ <- 1..42, do: Enum.random(0..1)

evaluate = fn population ->
  Enum.sort_by(population, &Enum.sum(&1), &>=/2)
end

selection = fn population ->
  population
  |> Enum.chunk_every(2)
  |> Enum.map(&List.to_tuple(&1))
end

crossover = fn population ->
  Enum.reduce(population, [], fn {p1, p2}, acc ->
    cx_point = :rand.uniform(42)
    {{h1, t1}, {h2, t2}} = {Enum.split(p1, cx_point), Enum.split(p2, cx_point)}
    [h1 ++ t2 | [h2 ++ t1 | acc]]
  end)
end

algorithm = fn population, algorithm ->
  best = Enum.max_by(population, &Enum.sum(&1))
  IO.write("\rCurrent Best: " <> Integer.to_string(Enum.sum(best)))
  if Enum.sum(best) == 42 do
    best
  else
    population
    |> evaluate.()
    |> selection.()
    |> crossover.()
    |> algorithm.(algorithm)
  end
end

solution = algorithm.(population, algorithm)
IO.write("\n Answer is \n")
IO.inspect solution

I parameterized it thusly:

Tunable version
-population = for _ <- 1..10, do: for _ <- 1..42, do: Enum.random(0..1)
+problem_size = 42
+population_size = 100
+
+population = for _ <- 1..population_size, do: for _ <- 1..problem_size, do: Enum.random(0..1)

 evaluate = fn population ->
   Enum.sort_by(population, &Enum.sum(&1), &>=/2)
 end

 selection = fn population ->
   population
   |> Enum.chunk_every(2)
   |> Enum.map(&List.to_tuple(&1))
 end

 crossover = fn population ->
   Enum.reduce(population, [], fn {p1, p2}, acc ->
-    cx_point = :rand.uniform(42)
+    cx_point = :rand.uniform(problem_size)
     {{h1, t1}, {h2, t2}} = {Enum.split(p1, cx_point), Enum.split(p2, cx_point)}
     [h1 ++ t2 | [h2 ++ t1 | acc]]
   end)
 end

 algorithm = fn population, algorithm ->
   best = Enum.max_by(population, &Enum.sum(&1))
   IO.write("\rCurrent Best: " <> Integer.to_string(Enum.sum(best)))
-  if Enum.sum(best) == 42 do
+  if Enum.sum(best) == problem_size do
     best
   else
     population
     |> evaluate.()
     |> selection.()
     |> crossover.()
     |> algorithm.(algorithm)
   end
 end

 solution = algorithm.(population, algorithm)
 IO.write("\n Answer is \n")
 IO.inspect solution

In my experimentation, with problem_size = 42, not only did population_size = 100 always converge on the best answer, but even as low as population_size = 8 consistently converged. I started seeing the need for mutation around population_size = 6, which normally gets stuck around 35.

Alternatively, increasing the size of the problem to problem_size = 420 usually converged correctly, but with enough time to watch things work. problem_size = 4200 consistently gets stuck around 2400, as the narrative of the chapter wants it to.

Where Next?

Popular Pragmatic Bookshelf topics Top

belgoros
Following the steps described in Chapter 6 of the book, I’m stuck with running the migration as described on page 84: bundle exec sequel...
New
lirux
Hi Jamis, I think there’s an issue with a test on chapter 6. I own the ebook, version P1.0 Feb. 2019. This test doesn’t pass for me: ...
New
brian-m-ops
#book-python-testing-with-pytest-second-edition Hi. Thanks for writing the book. I am just learning so this might just of been an issue ...
New
AndyDavis3416
@noelrappin Running the webpack dev server, I receive the following warning: ERROR in tsconfig.json TS18003: No inputs were found in c...
New
jskubick
I’m running Android Studio “Arctic Fox” 2020.3.1 Patch 2, and I’m embarrassed to admit that I only made it to page 8 before running into ...
New
digitalbias
Title: Build a Weather Station with Elixir and Nerves: Problem connecting to Postgres with Grafana on (page 64) If you follow the defau...
New
dsmith42
Hey there, I’m enjoying this book and have learned a few things alredayd. However, in Chapter 4 I believe we are meant to see the “&gt;...
New
adamwoolhether
Is there any place where we can discuss the solutions to some of the exercises? I can figure most of them out, but am having trouble with...
New
andreheijstek
After running /bin/setup, the first error was: The foreman' command exists in these Ruby versions: That was easy to fix: gem install fore...
New
davetron5000
Hello faithful readers! If you have tried to follow along in the book, you are asked to start up the dev environment via dx/build and ar...
New

Other popular topics Top

AstonJ
Curious to know which languages and frameworks you’re all thinking about learning next :upside_down_face: Perhaps if there’s enough peop...
New
New
AstonJ
I have seen the keycaps I want - they are due for a group-buy this week but won’t be delivered until October next year!!! :rofl: The Ser...
New
AstonJ
This looks like a stunning keycap set :orange_heart: A LEGENDARY KEYBOARD LIVES ON When you bought an Apple Macintosh computer in the e...
New
AstonJ
Continuing the discussion from Thinking about learning Crystal, let’s discuss - I was wondering which languages don’t GC - maybe we can c...
New
foxtrottwist
A few weeks ago I started using Warp a terminal written in rust. Though in it’s current state of development there are a few caveats (tab...
New
First poster: joeb
The File System Access API with Origin Private File System. WebKit supports new API that makes it possible for web apps to create, open,...
New
PragmaticBookshelf
Author Spotlight Jamis Buck @jamis This month, we have the pleasure of spotlighting author Jamis Buck, who has written Mazes for Prog...
New
New
Fl4m3Ph03n1x
Background Lately I am in a quest to find a good quality TTS ai generation tool to run locally in order to create audio for some videos I...
New

Sub Categories: