commit a6df082f4d832e98fb633590939adaf90f4726ec
parent 1f36b04ae4e0a9265ec327b1954af2adc0704b69
Author: dracuxan <[email protected]>
Date: Fri, 24 Apr 2026 11:26:00 +0530
upd: optimizations using paralellizations and nifs
Diffstat:
8 files changed, 105 insertions(+), 22 deletions(-)
diff --git a/.gitignore b/.gitignore
@@ -27,3 +27,5 @@ genetic-*.tar
games/
*.dot
+
+priv/
diff --git a/lib/genetic.ex b/lib/genetic.ex
@@ -1,5 +1,12 @@
defmodule Genetic do
alias Types.Chromosome
+ @on_load :load_nif
+ def load_nif do
+ path = ~c"./priv/genetic"
+ :erlang.load_nif(path, 0)
+ end
+
+ def xor96, do: 0
def run(problem, opts \\ []) do
population = initialize(&problem.genotype/0, opts)
@@ -10,14 +17,14 @@ defmodule Genetic do
def initialize(genotype, opts \\ []) do
population_size = Keyword.get(opts, :population_size, 100)
- population = Enum.map(1..population_size, fn _ -> genotype.() end)
+ population = pmap(1..population_size, fn _ -> genotype.() end)
Utilities.Genealogy.add_chromosomes(population)
population
end
def evaluate(population, fitness_function, _opts \\ []) do
population
- |> Enum.map(fn chromosome ->
+ |> pmap(fn chromosome ->
fitness = fitness_function.(chromosome)
age = 1
%Chromosome{genes: chromosome.genes, fitness: fitness, age: age}
@@ -45,13 +52,13 @@ defmodule Genetic do
parents =
parents
|> Enum.chunk_every(2)
- |> Enum.map(&List.to_tuple(&1))
+ |> pmap(&List.to_tuple(&1))
{parents, MapSet.to_list(leftover)}
end
def crossover(population, opts \\ []) do
- crossover_fn = Keyword.get(opts, :crossover_type, &Toolbox.Crossover.order_one/3)
+ crossover_fn = Keyword.get(opts, :crossover_type, &Toolbox.Crossover.single_point/3)
population
|> Enum.reduce(
@@ -72,7 +79,7 @@ defmodule Genetic do
population
|> Enum.take_random(n)
- |> Enum.map(&apply(mutation_fn, [&1, opts]))
+ |> pmap(&apply(mutation_fn, [&1, opts]))
end
def evolve(population, problem, generation, opts \\ []) do
@@ -100,6 +107,12 @@ defmodule Genetic do
apply(strategy, [parents, offsprings, leftover, opts])
end
+ def pmap(collection, func) do
+ collection
+ |> Enum.map(&Task.async(fn -> func.(&1) end))
+ |> Enum.map(&Task.await(&1))
+ end
+
def statistics(population, generation, opts \\ []) do
default_stats = [
min_fitness: &Enum.min_by(&1, fn c -> c.fitness end).fitness,
diff --git a/lib/toolbox/crossover.ex b/lib/toolbox/crossover.ex
@@ -31,7 +31,7 @@ defmodule Toolbox.Crossover do
end
def single_point(p1, p2, _opts \\ []) do
- cx_point = :rand.uniform(length(p1.genes) - 1)
+ cx_point = rem(Genetic.xor96(), length(p1.genes))
{{head1, tail1}, {head2, tail2}} =
{Enum.split(p1.genes, cx_point), Enum.split(p2.genes, cx_point)}
diff --git a/mix.exs b/mix.exs
@@ -1,3 +1,27 @@
+defmodule Mix.Tasks.Compile.Cnif do
+ use Mix.Task.Compiler
+
+ def run(_args) do
+ File.mkdir_p!("priv")
+
+ {output, code} =
+ System.cmd(
+ "gcc",
+ [
+ "-fpic",
+ "-shared",
+ "-o",
+ "priv/genetic.so",
+ "src/genetic.c"
+ ],
+ stderr_to_stdout: true
+ )
+
+ IO.puts(output)
+ if code == 0, do: :ok, else: {:error, []}
+ end
+end
+
defmodule Genetic.MixProject do
use Mix.Project
@@ -7,6 +31,7 @@ defmodule Genetic.MixProject do
version: "0.1.0",
elixir: "~> 1.18",
start_permanent: Mix.env() == :prod,
+ compilers: [:cnif] ++ Mix.compilers(),
deps: deps()
]
end
@@ -24,6 +49,8 @@ defmodule Genetic.MixProject do
[
{:libgraph, "~> 0.16.0"},
{:gnuplot, "~> 1.22"},
+ {:benchee, "~> 1.5.0"},
+ {:exprof, "~> 0.2.4"},
{:alex, "~> 0.3.2"}
]
end
diff --git a/mix.lock b/mix.lock
@@ -1,11 +1,16 @@
%{
"alex": {:hex, :alex, "0.3.2", "b6fa1d744783707e1ff068ecdef2eb993f9b05a2ebe9c97ba67b05902c0aaa9c", [:mix], [], "hexpm", "9d40610d06857f5a321923f28c44ca08575ad64594cbbfa4352eb115e5c0566e"},
+ "benchee": {:hex, :benchee, "1.5.0", "4d812c31d54b0ec0167e91278e7de3f596324a78a096fd3d0bea68bb0c513b10", [:mix], [{:deep_merge, "~> 1.0", [hex: :deep_merge, repo: "hexpm", optional: false]}, {:statistex, "~> 1.1", [hex: :statistex, repo: "hexpm", optional: false]}, {:table, "~> 0.1.0", [hex: :table, repo: "hexpm", optional: true]}], "hexpm", "5b075393aea81b8ae74eadd1c28b1d87e8a63696c649d8293db7c4df3eb67535"},
+ "deep_merge": {:hex, :deep_merge, "1.0.0", "b4aa1a0d1acac393bdf38b2291af38cb1d4a52806cf7a4906f718e1feb5ee961", [:mix], [], "hexpm", "ce708e5f094b9cd4e8f2be4f00d2f4250c4095be93f8cd6d018c753894885430"},
"earmark_parser": {:hex, :earmark_parser, "1.4.44", "f20830dd6b5c77afe2b063777ddbbff09f9759396500cdbe7523efd58d7a339c", [:mix], [], "hexpm", "4778ac752b4701a5599215f7030989c989ffdc4f6df457c5f36938cc2d2a2750"},
"ex_doc": {:hex, :ex_doc, "0.40.1", "67542e4b6dde74811cfd580e2c0149b78010fd13001fda7cfeb2b2c2ffb1344d", [:mix], [{:earmark_parser, "~> 1.4.44", [hex: :earmark_parser, repo: "hexpm", optional: false]}, {:makeup_c, ">= 0.1.0", [hex: :makeup_c, repo: "hexpm", optional: true]}, {:makeup_elixir, "~> 0.14 or ~> 1.0", [hex: :makeup_elixir, repo: "hexpm", optional: false]}, {:makeup_erlang, "~> 0.1 or ~> 1.0", [hex: :makeup_erlang, repo: "hexpm", optional: false]}, {:makeup_html, ">= 0.1.0", [hex: :makeup_html, repo: "hexpm", optional: true]}], "hexpm", "bcef0e2d360d93ac19f01a85d58f91752d930c0a30e2681145feea6bd3516e00"},
+ "exprintf": {:hex, :exprintf, "0.2.1", "b7e895dfb00520cfb7fc1671303b63b37dc3897c59be7cbf1ae62f766a8a0314", [:mix], [], "hexpm", "20a0e8c880be90e56a77fcc82533c5d60c643915c7ce0cc8aa1e06ed6001da28"},
+ "exprof": {:hex, :exprof, "0.2.4", "13ddc0575a6d24b52e7c6809d2a46e9ad63a4dd179628698cdbb6c1f6e497c98", [:mix], [{:exprintf, "~> 0.2", [hex: :exprintf, repo: "hexpm", optional: false]}], "hexpm", "0884bcb66afc421c75d749156acbb99034cc7db6d3b116c32e36f32551106957"},
"gnuplot": {:hex, :gnuplot, "1.22.270", "541da1d4be2acbcb2a53105a7c2f31d91127811858b522c1a2290ed5844b9624", [:mix], [{:ex_doc, "~> 0.28", [hex: :ex_doc, repo: "hexpm", optional: false]}], "hexpm", "2870982804ac79a93eebf31c07a507a1825bc23c782907da48d653cf970a4d41"},
"libgraph": {:hex, :libgraph, "0.16.0", "3936f3eca6ef826e08880230f806bfea13193e49bf153f93edcf0239d4fd1d07", [:mix], [], "hexpm", "41ca92240e8a4138c30a7e06466acc709b0cbb795c643e9e17174a178982d6bf"},
"makeup": {:hex, :makeup, "1.2.1", "e90ac1c65589ef354378def3ba19d401e739ee7ee06fb47f94c687016e3713d1", [:mix], [{:nimble_parsec, "~> 1.4", [hex: :nimble_parsec, repo: "hexpm", optional: false]}], "hexpm", "d36484867b0bae0fea568d10131197a4c2e47056a6fbe84922bf6ba71c8d17ce"},
"makeup_elixir": {:hex, :makeup_elixir, "1.0.1", "e928a4f984e795e41e3abd27bfc09f51db16ab8ba1aebdba2b3a575437efafc2", [:mix], [{:makeup, "~> 1.0", [hex: :makeup, repo: "hexpm", optional: false]}, {:nimble_parsec, "~> 1.2.3 or ~> 1.3", [hex: :nimble_parsec, repo: "hexpm", optional: false]}], "hexpm", "7284900d412a3e5cfd97fdaed4f5ed389b8f2b4cb49efc0eb3bd10e2febf9507"},
"makeup_erlang": {:hex, :makeup_erlang, "1.0.3", "4252d5d4098da7415c390e847c814bad3764c94a814a0b4245176215615e1035", [:mix], [{:makeup, "~> 1.0", [hex: :makeup, repo: "hexpm", optional: false]}], "hexpm", "953297c02582a33411ac6208f2c6e55f0e870df7f80da724ed613f10e6706afd"},
"nimble_parsec": {:hex, :nimble_parsec, "1.4.2", "8efba0122db06df95bfaa78f791344a89352ba04baedd3849593bfce4d0dc1c6", [:mix], [], "hexpm", "4b21398942dda052b403bbe1da991ccd03a053668d147d53fb8c4e0efe09c973"},
+ "statistex": {:hex, :statistex, "1.1.0", "7fec1eb2f580a0d2c1a05ed27396a084ab064a40cfc84246dbfb0c72a5c761e5", [:mix], [], "hexpm", "f5950ea26ad43246ba2cce54324ac394a4e7408fdcf98b8e230f503a0cba9cf5"},
}
diff --git a/scripts/cargo.exs b/scripts/cargo.exs
@@ -37,7 +37,7 @@ defmodule Cargo do
end
end
-{soln, _} = Genetic.run(Cargo, crossover_type: &Toolbox.Crossover.single_point/2)
+{soln, _} = Genetic.run(Cargo, crossover_type: &Toolbox.Crossover.single_point/3)
IO.puts("\nsolution: #{inspect(soln)}")
weight =
diff --git a/scripts/n_queens.exs b/scripts/n_queens.exs
@@ -2,7 +2,7 @@ defmodule NQueens do
alias Types.Chromosome
@behaviour Problem
- @max_queens 14
+ @max_queens 16
@target_fitness @max_queens + 1
@size @target_fitness
@@ -33,6 +33,24 @@ defmodule NQueens do
best = hd(population)
best.fitness == @target_fitness
end
+
+ def map_queens(soln) do
+ size = length(soln)
+
+ for i <- 1..size do
+ row_string =
+ for j <- 1..size do
+ if(Enum.at(soln, i) == j) do
+ " Q "
+ else
+ " . "
+ end
+ end
+ |> Enum.join()
+
+ IO.puts(row_string)
+ end
+ end
end
{soln, generation} =
@@ -43,18 +61,19 @@ end
crossover_type: &Toolbox.Crossover.order_one/3
)
-IO.puts("\nfinal answer: #{inspect(soln)}\ngenrations passed: #{generation}")
-
-stats =
- :ets.tab2list(:statistics)
- |> Enum.sort_by(fn {gen, _stat} -> gen end)
- |> Enum.map(fn {gen, stats} -> [gen, stats.mean_fitness] end)
+IO.puts("\nfinal answer: #{inspect(soln.genes)}\ngenrations passed: #{generation}")
+NQueens.map_queens(soln.genes)
-{:ok, _} =
- Gnuplot.plot(
- [
- [:set, :title, "mean fitness versus generation (n__queens)"],
- [:plot, "-", :with, :points]
- ],
- [stats]
- )
+# stats =
+# :ets.tab2list(:statistics)
+# |> Enum.sort_by(fn {gen, _stat} -> gen end)
+# |> Enum.map(fn {gen, stats} -> [gen, stats.mean_fitness] end)
+#
+# {:ok, _} =
+# Gnuplot.plot(
+# [
+# [:set, :title, "mean fitness versus generation (n__queens)"],
+# [:plot, "-", :with, :points]
+# ],
+# [stats]
+# )
diff --git a/src/genetic.c b/src/genetic.c
@@ -0,0 +1,17 @@
+#include <erl_nif.h>
+#include <inttypes.h>
+#include <stdint.h>
+
+static uint32_t x = 123456789, y = 362436069, z = 52128629;
+
+static ERL_NIF_TERM xor96(ErlNifEnv *env, int argc, const ERL_NIF_TERM argv[]) {
+ uint32_t t = (x ^ (x << 10));
+ x = y;
+ y = z;
+ z = (z ^ (z >> 26)) ^ (t ^ (t >> 5));
+
+ return enif_make_int(env, z);
+}
+
+static ErlNifFunc nif_funcs[] = {{"xor96", 0, xor96}};
+ERL_NIF_INIT(Elixir.Genetic, nif_funcs, NULL, NULL, NULL, NULL);
