genetic

commit 769a197c7643656d34a52e4e938ecf23eb11b656
parent f1a0f1b8963db3f578f815a962fd80a7089ca660
Author: dracuxan <[email protected]>
Date:   Wed,  8 Apr 2026 10:39:22 +0530

new: order-one crossover and configurations for multi crossovers

Diffstat:
M
genetic/lib/genetic.ex
 | 
18
+++++++++---------
A
genetic/lib/toolbox/crossover.ex
 | 
58
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
genetic/scripts/cargo.exs
 | 
2
+-
A
genetic/scripts/n_queens.exs
 | 
44
++++++++++++++++++++++++++++++++++++++++++++
M
genetic/scripts/one_max.exs
 | 
15
+++++++++++----

5 files changed, 123 insertions(+), 14 deletions(-)
diff --git a/genetic/lib/genetic.ex b/genetic/lib/genetic.ex
@@ -48,19 +48,19 @@ defmodule Genetic do
     {parents, MapSet.to_list(leftover)}
   end
 
-  def crossover(population, _opts \\ []) do
+  def crossover(population, opts \\ []) do
+    crossover_fn =
+      Keyword.get(
+        opts,
+        :crossover_type,
+        &Toolbox.Crossover.order_one/2
+      )
+
     population
     |> Enum.reduce(
       [],
       fn {p1, p2}, acc ->
-        cx_point = :rand.uniform(length(p1.genes))
-
-        {{h1, t1}, {h2, t2}} =
-          {Enum.split(p1.genes, cx_point), Enum.split(p2.genes, cx_point)}
-
-        {c1, c2} =
-          {%Chromosome{p1 | genes: h1 ++ t2, age: 0}, %Chromosome{p2 | genes: h2 ++ t1, age: 0}}
-
+        {c1, c2} = apply(crossover_fn, [p1, p2])
         [c1, c2 | acc]
       end
     )
diff --git a/genetic/lib/toolbox/crossover.ex b/genetic/lib/toolbox/crossover.ex
@@ -0,0 +1,58 @@
+defmodule Toolbox.Crossover do
+  alias Types.Chromosome
+
+  def order_one(p1, p2) do
+    lim = Enum.count(p1.genes) - 1
+    # random range
+    {i1, i2} =
+      [:rand.uniform(lim), :rand.uniform(lim)]
+      |> Enum.sort()
+      |> List.to_tuple()
+
+    # p2 contribution
+    slice1 = Enum.slice(p1.genes, i1..i2)
+    slice1_set = MapSet.new(slice1)
+    p2_contrib = Enum.reject(p2.genes, &MapSet.member?(slice1_set, &1))
+    {head1, tail1} = Enum.split(p2_contrib, i1)
+
+    # p1 contribution
+    slice2 = Enum.slice(p2.genes, i1..i2)
+    slice2_set = MapSet.new(slice2)
+    p1_contrib = Enum.reject(p1.genes, &MapSet.member?(slice2_set, &1))
+    {head2, tail2} = Enum.split(p1_contrib, i1)
+
+    # create and return
+    {c1, c2} = {head1 ++ slice1 ++ tail1, head2 ++ slice2 ++ tail2}
+
+    {%Chromosome{
+       genes: c1,
+       size: p1.size,
+       age: 0
+     },
+     %Chromosome{
+       genes: c2,
+       size: p2.size,
+       age: 0
+     }}
+  end
+
+  def single_point(p1, p2) do
+    cx_point = :rand.uniform(p1.size - 1)
+
+    {{head1, tail1}, {head2, tail2}} =
+      {Enum.split(p1.genes, cx_point), Enum.split(p2.genes, cx_point)}
+
+    {c1, c2} = {head1 ++ tail2, head2 ++ tail1}
+
+    {%Chromosome{
+       genes: c1,
+       size: p1.size,
+       age: 0
+     },
+     %Chromosome{
+       genes: c2,
+       size: p2.size,
+       age: 0
+     }}
+  end
+end
diff --git a/genetic/scripts/cargo.exs b/genetic/scripts/cargo.exs
@@ -37,7 +37,7 @@ defmodule Cargo do
   end
 end
 
-{soln, _} = Genetic.run(Cargo)
+{soln, _} = Genetic.run(Cargo, crossover_type: &Toolbox.Crossover.single_point/2)
 IO.puts("\nsolution: #{inspect(soln)}")
 
 weight =
diff --git a/genetic/scripts/n_queens.exs b/genetic/scripts/n_queens.exs
@@ -0,0 +1,44 @@
+defmodule NQueens do
+  alias Types.Chromosome
+  @behaviour Problem
+
+  @max_queens 16
+  @target_fitness @max_queens + 1
+  @size @target_fitness
+
+  @impl true
+  def genotype do
+    genes = Enum.shuffle(0..@max_queens)
+    %Chromosome{genes: genes, size: @size}
+  end
+
+  @impl true
+  def fitness_function(chromosome) do
+    diag_clashes =
+      for i <- 0..@max_queens, j <- 0..@max_queens do
+        if i != j do
+          dx = abs(i - j)
+          dy = abs(Enum.at(chromosome.genes, i) - Enum.at(chromosome.genes, j))
+          if dx == dy, do: 1, else: 0
+        else
+          0
+        end
+      end
+
+    length(Enum.uniq(chromosome.genes)) - Enum.sum(diag_clashes)
+  end
+
+  @impl true
+  def terminate?(population, _generation) do
+    best = hd(population)
+    best.fitness == @target_fitness
+  end
+end
+
+{soln, generation} =
+  Genetic.run(
+    NQueens,
+    crossover_type: &Toolbox.Crossover.order_one_crossover/2
+  )
+
+IO.puts("\nfinal answer: #{inspect(soln)}\ngenrations passed: #{generation}")
diff --git a/genetic/scripts/one_max.exs b/genetic/scripts/one_max.exs
@@ -1,11 +1,12 @@
 defmodule OneMax do
   alias Types.Chromosome
   @behaviour Problem
+  @max_n 30
 
   @impl true
   def genotype do
-    genes = Enum.map(1..1000, fn _ -> Enum.random(0..1) end)
-    %Chromosome{genes: genes, size: 1000}
+    genes = Enum.map(1..@max_n, fn _ -> Enum.random(0..1) end)
+    %Chromosome{genes: genes, size: @max_n}
   end
 
   @impl true
@@ -16,7 +17,7 @@ defmodule OneMax do
   @impl true
   def terminate?(population, _generation) do
     best = Enum.max_by(population, &OneMax.fitness_function/1)
-    best.fitness == 1000
+    best.fitness == @max_n
 
     # best = Enum.min_by(population, &OneMax.fitness_function/1)
     # best.fitness == 0
@@ -33,5 +34,11 @@ defmodule OneMax do
   end
 end
 
-{soln, _} = Genetic.run(OneMax, selection_type: &Toolbox.Selection.elite/2)
+{soln, generation} =
+  Genetic.run(OneMax,
+    selection_type: &Toolbox.Selection.elite/2,
+    crossover_type: &Toolbox.Crossover.single_point/2
+  )
+
 IO.puts("\nfinal answer: #{inspect(soln.genes)}")
+IO.puts("generations passed: #{generation}")