genetic

commit c3c36069005cf599e8e8aa4a47613d7421738c66
parent c7452ccbad5e1a9b4f85bcd3c20287d2197413a0
Author: dracuxan <[email protected]>
Date:   Tue,  7 Apr 2026 16:25:47 +0530

new: selection algorithms

Diffstat:
M
genetic/lib/genetic.ex
 | 
36
+++++++++++++++++++++++++++---------
A
genetic/lib/toolbox/selection.ex
 | 
65
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
genetic/scripts/one_max.exs
 | 
14
+++++++-------
M
genetic/scripts/speller.exs
 | 
8
++++----

4 files changed, 103 insertions(+), 20 deletions(-)
diff --git a/genetic/lib/genetic.ex b/genetic/lib/genetic.ex
@@ -23,10 +23,29 @@ defmodule Genetic do
     |> Enum.sort_by(& &1.fitness, :desc)
   end
 
-  def select(population, _opts \\ []) do
-    population
-    |> Enum.chunk_every(2)
-    |> Enum.map(&List.to_tuple/1)
+  def select(population, opts \\ []) do
+    select_fn =
+      Keyword.get(opts, :selection_type, &Toolbox.Selection.elite/2)
+
+    select_rate = Keyword.get(opts, :selection_rate, 0.8)
+    n = round(length(population) * select_rate)
+    n = if rem(n, 2) == 0, do: n, else: n + 1
+
+    parents =
+      select_fn
+      |> apply([population, n])
+
+    leftover =
+      population
+      |> MapSet.new()
+      |> MapSet.difference(MapSet.new(parents))
+
+    parents =
+      parents
+      |> Enum.chunk_every(2)
+      |> Enum.map(&List.to_tuple(&1))
+
+    {parents, MapSet.to_list(leftover)}
   end
 
   def crossover(population, _opts \\ []) do
@@ -66,13 +85,12 @@ defmodule Genetic do
     if problem.terminate?(population, generation) do
       best
     else
-      generation = generation + 1
+      {parents, leftover} = select(population)
+      children = crossover(parents, opts)
 
-      population
-      |> select(opts)
-      |> crossover(opts)
+      (children ++ leftover)
       |> mutation(opts)
-      |> evolve(problem, generation, opts)
+      |> evolve(problem, generation + 1, opts)
     end
   end
 end
diff --git a/genetic/lib/toolbox/selection.ex b/genetic/lib/toolbox/selection.ex
@@ -0,0 +1,65 @@
+defmodule Toolbox.Selection do
+  def elite(population, n) do
+    population
+    |> Enum.take(n)
+  end
+
+  def random(population, n) do
+    population
+    |> Enum.take_random(n)
+  end
+
+  def tournament(population, n) do
+    tournsize = :rand.uniform(n)
+
+    0..(n - 1)
+    |> Enum.map(fn _ ->
+      population
+      |> Enum.take_random(tournsize)
+      |> Enum.max_by(& &1.fitness)
+    end)
+  end
+
+  def tournament_no_dup(population, n) do
+    tournsize = :rand.uniform(n)
+    selected = MapSet.new()
+    tournament_helper(population, n, tournsize, selected)
+  end
+
+  defp tournament_helper(population, n, tournsize, selected) do
+    if MapSet.size(selected) == n do
+      MapSet.to_list(selected)
+    else
+      chosen =
+        population
+        |> Enum.take_random(tournsize)
+        |> Enum.max_by(& &1.fitness)
+
+      tournament_helper(population, n, tournsize, MapSet.put(selected, chosen))
+    end
+  end
+
+  def roulette(population, n) do
+    sum_fitness =
+      population
+      |> Enum.map(& &1.fitness)
+      |> Enum.sum()
+
+    0..(n - 1)
+    |> Enum.map(fn _ ->
+      u = :rand.uniform() * sum_fitness
+
+      population
+      |> Enum.reduce_while(
+        0,
+        fn x, sum ->
+          if x.fitness + sum > u do
+            {:halt, x}
+          else
+            {:cont, x.fitness + sum}
+          end
+        end
+      )
+    end)
+  end
+end
diff --git a/genetic/scripts/one_max.exs b/genetic/scripts/one_max.exs
@@ -4,8 +4,8 @@ defmodule OneMax do
 
   @impl true
   def genotype do
-    genes = Enum.map(1..30, fn _ -> Enum.random(0..1) end)
-    %Chromosome{genes: genes, size: 30}
+    genes = Enum.map(1..1000, fn _ -> Enum.random(0..1) end)
+    %Chromosome{genes: genes, size: 1000}
   end
 
   @impl true
@@ -14,9 +14,9 @@ defmodule OneMax do
   end
 
   @impl true
-  def terminate?(_population, generation) do
-    # best = Enum.max_by(population, &OneMax.fitness_function/1)
-    # best.fitness == 30
+  def terminate?(population, _generation) do
+    best = Enum.max_by(population, &OneMax.fitness_function/1)
+    best.fitness == 1000
 
     # best = Enum.min_by(population, &OneMax.fitness_function/1)
     # best.fitness == 0
@@ -29,9 +29,9 @@ defmodule OneMax do
     #
     # avg >= 15
 
-    generation == 100
+    # generation == 100
   end
 end
 
-soln = Genetic.run(OneMax)
+soln = Genetic.run(OneMax, selection_type: &Toolbox.Selection.elite/2)
 IO.puts("\nfinal answer: #{inspect(soln.genes)}")
diff --git a/genetic/scripts/speller.exs b/genetic/scripts/speller.exs
@@ -6,14 +6,14 @@ defmodule Speller do
   def genotype do
     genes =
       Stream.repeatedly(fn -> Enum.random(?a..?z) end)
-      |> Enum.take(8)
+      |> Enum.take(10)
 
-    %Chromosome{genes: genes, size: 8}
+    %Chromosome{genes: genes, size: 10}
   end
 
   @impl true
   def fitness_function(chromosome) do
-    target = "dracuxan"
+    target = "abcdefghij"
     guess = List.to_string(chromosome.genes)
     String.jaro_distance(target, guess)
   end
@@ -25,5 +25,5 @@ defmodule Speller do
   end
 end
 
-soln = Genetic.run(Speller)
+soln = Genetic.run(Speller, selection_type: &Toolbox.Selection.roulette/2)
 IO.puts("\nfinal answer: #{inspect(soln)}")