genetic

genetic algorithm framework
git clone [email protected]:dracuxan/genetic.git
Log | Files | Refs | README

genetic.ex (3876B)

      1 defmodule Genetic do
      2   alias Types.Chromosome
      3 
      4   def run(problem, opts \\ []) do
      5     population = initialize(&problem.genotype/0, opts)
      6 
      7     population
      8     |> evolve(problem, 0, opts)
      9   end
     10 
     11   def initialize(genotype, opts \\ []) do
     12     init_fn = Keyword.get(opts, :initialization_type, &Toolbox.Initialize.random/2)
     13     population = apply(init_fn, [genotype, opts])
     14     Utilities.Genealogy.add_chromosomes(population)
     15     population
     16   end
     17 
     18   def evaluate(population, fitness_function, _opts \\ []) do
     19     population
     20     |> pmap(fn chromosome ->
     21       fitness = fitness_function.(chromosome)
     22       age = 1
     23       %Chromosome{genes: chromosome.genes, fitness: fitness, age: age}
     24     end)
     25     |> Enum.sort_by(& &1.fitness, :desc)
     26   end
     27 
     28   def select(population, opts \\ []) do
     29     select_fn =
     30       Keyword.get(opts, :selection_type, &Toolbox.Selection.elite/2)
     31 
     32     select_rate = Keyword.get(opts, :selection_rate, 0.8)
     33     n = round(length(population) * select_rate)
     34     n = if rem(n, 2) == 0, do: n, else: n - 1
     35 
     36     parents =
     37       select_fn
     38       |> apply([population, n])
     39 
     40     leftover =
     41       population
     42       |> MapSet.new()
     43       |> MapSet.difference(MapSet.new(parents))
     44 
     45     parents =
     46       parents
     47       |> Enum.chunk_every(2)
     48       |> pmap(&List.to_tuple(&1))
     49 
     50     {parents, MapSet.to_list(leftover)}
     51   end
     52 
     53   def crossover(population, opts \\ []) do
     54     crossover_fn =
     55       Keyword.get(
     56         opts,
     57         :crossover_type,
     58         &Toolbox.Crossover.single_point/3
     59       )
     60 
     61     population
     62     |> Enum.reduce(
     63       [],
     64       fn {p1, p2}, acc ->
     65         {c1, c2} = apply(crossover_fn, [p1, p2, opts])
     66         Utilities.Genealogy.add_chromosome(p1, p2, c1)
     67         Utilities.Genealogy.add_chromosome(p1, p2, c2)
     68         [c1, c2 | acc]
     69       end
     70     )
     71   end
     72 
     73   def mutation(population, opts \\ []) do
     74     mutation_fn = Keyword.get(opts, :mutation_type, &Toolbox.Mutation.scramble/2)
     75     mutation_rate = Keyword.get(opts, :mutation_rate, 0.05)
     76     n = floor(length(population) * mutation_rate)
     77 
     78     population
     79     |> Enum.take_random(n)
     80     |> pmap(&apply(mutation_fn, [&1, opts]))
     81   end
     82 
     83   def evolve(population, problem, generation, opts \\ []) do
     84     population = evaluate(population, &problem.fitness_function/1, opts)
     85     statistics(population, generation, opts)
     86     best = hd(population)
     87     # fit_str = best.fitness |> :erlang.float_to_binary(decimals: 4)
     88     fit_str = best.fitness
     89     IO.write("\rcurrent best: #{fit_str}\tgeneration: #{generation}  ")
     90 
     91     if problem.terminate?(population, generation) do
     92       {best, generation}
     93     else
     94       {parents, leftover} = select(population, opts)
     95       children = crossover(parents, opts)
     96       mutants = mutation(population, opts)
     97       offsprings = children ++ mutants
     98       new_population = reinsertion(parents, offsprings, leftover, opts)
     99       evolve(new_population, problem, generation + 1, opts)
    100     end
    101   end
    102 
    103   def reinsertion(parents, offsprings, leftover, opts \\ []) do
    104     strategy =
    105       Keyword.get(
    106         opts,
    107         :reinsertion_strategy,
    108         &Toolbox.Reinsertion.uniform/4
    109       )
    110 
    111     apply(strategy, [parents, offsprings, leftover, opts])
    112   end
    113 
    114   def pmap(collection, func) do
    115     collection
    116     |> Enum.map(&Task.async(fn -> func.(&1) end))
    117     |> Enum.map(&Task.await(&1))
    118   end
    119 
    120   def statistics(population, generation, opts \\ []) do
    121     default_stats = [
    122       min_fitness: &Enum.min_by(&1, fn c -> c.fitness end).fitness,
    123       max_fitness: &Enum.max_by(&1, fn c -> c.fitness end).fitness,
    124       mean_fitness: &(Enum.sum(Enum.map(&1, fn c -> c.fitness end)) / length(population))
    125     ]
    126 
    127     stats = Keyword.get(opts, :statistics, default_stats)
    128 
    129     stats_map =
    130       stats
    131       |> Enum.reduce(
    132         %{},
    133         fn {key, func}, acc ->
    134           Map.put(acc, key, func.(population))
    135         end
    136       )
    137 
    138     Utilities.Statistics.insert(generation, stats_map)
    139   end
    140 end