Genex - Genetic Algorithms in Elixir

Hey all,

I wanted to get some experience writing libraries in Elixir, so I started a project today called Genex.

Genex is a simple library that makes it easy to write Genetic Algorithms in Elixir. All you have to do is specify some parameters, define a few functions, and then run the algorithm.

This library is VERY new (I literally just started it today). So it doesn’t have sufficient tests, documentation, or really much of anything yet. It is NOWHERE near finished.

I was looking for suggestions, tips, ideas, etc. for the rest of the way forward. I know Elixir isn’t really the best language for this stuff, but it’s a fun little project. I’ve had fun messing around solving very basic optimization problems with it.

Let me know what you guys think! If you want to contribute, send me a message!

10 Likes

To anybody following this project:

v0.1.0 was just released and published to Hex.

Documentation
Package

This version includes a few basic selection, crossover, and mutation methods, a text visualization module, and a Genealogy tree implementation. It has many limitations and many more features are in the works; however, this is a usable working version.

Enjoy!

3 Likes

v0.1.1

Documentation
Package

What’s New

  • Bug Fixes
  • Finalized Implementation of Selection, Mutation, and Crossover Functions
  • Improved Documentation

What’s Next

  • Adding Statistics to Population Struct
  • Support for multiple Populations and Migration between Populations
  • More comprehensive documentation
2 Likes

v0.1.2

Documentation
Package

What’s New

  • Bug Fixes
  • Improved Documentation (Including full customization guide)
  • Statistics collection using built in or 3rd party modules
  • Implementation of Crossover Rate, Mutation Rate, and Radiation as overridable functions to change with population parameters

What’s Next

  • PERFORMANCE

From the start of this project, I understood Elixir and the BEAM are not ideal for this kind of application; however, I am really falling in love with the simplicity Elixir and this Library can offer to these kinds of problems. That being said, I know this library’s performance will likely never rival DEAP or similar implementations in languages like C or Rust; however, I know the performance itself can be improved.

If you check out some of the benchmarks in the Git Repository, you’ll see how hopelessly slow a lot of the evolutionary operators are. I’m considering 3 options for solving this problem:

  1. Parallelization using Task API or Flow as well as scrutinizing my implementations of the various algorithms. This is probably the route I’m going to explore first and settle with for the next release.
  2. NIFs. My research tells me this is an absolutely ideal use case for NIFs. Essentially, we just need the evolutionary operators (crossover, mutation, selection) implemented as NIFs. The operators just need to perform computation on large lists really fast and return the result. This seems like an ideal use case for NIFs. If anybody has experience writing them in Rust or C, please shoot me a message so we can discuss!
  3. Ports. This option doesn’t make much sense in my opinion although if anybody can make an argument for it, I’d be willing to listen.

If you’re writing anything cool with Genex or just playing around - please let me know! I don’t expect this library to be very popular but it’s been a lot of fun to work on :slight_smile:

6 Likes

Ideal use-case for Rust (and the Rustler library). :slight_smile:

Don’t forget to look at the Matrax or whatever it was called library, it exposes some BLAS NIF functionality!

Interesting project, years ago I played with genetic algorithms and it was quite fun.
I’d also go for the combination with Rust.

If only I had time…

3 Likes

v0.1.4

Documentation
Package

What’s New

  • Bug fixes
  • 3.51x Performance Improvement in single_point crossover
  • 2.35x Performance Improvement in two_point crossover
  • Addition of benchmark/0 function to benchmark your algorithm
  • Addition of track_history? flag to turn off and on the Genealogy tree feature (see problems for why).

What’s Next

  • Exploring the idea of using the Matrex library per @OvermindDL1 suggestion. Representing the Populations and Chromosomes as matrices gives access to their REALLY fast matrix functions.
  • Also began messing around with implementing the operators as NIFs last night. 2 problems I ran into: Rustler’s current release doesn’t support Erlang 22. Not a huge problem because their master branch does, more a minor inconvenience. 2nd problem is it was my first experience with Rust and I couldn’t write anything efficient to save my life :slight_smile:.

Problems

  • I had to add the track_history? flag because I couldn’t get Benchee to play nicely with the current Genealogy tree implementation. The Genealogy tree is just an Erlang digraph. The problem is Benchee runs in it’s own process and Erlang digraph’s are protected by default. I thought it would be an easy fix - considering you can make ETS table’s public - however, digraph’s protection options are only :protected and :private. If anybody has a workaround for this, I’d love to hear it!

Thanks!

6 Likes

v0.2.0

Documentation
Package

What’s New

  • Bug Fixes
  • Changed to libgraph for Genealogy Tree
  • Added ability to export Genealogy to DOT file
  • Removed track_history? flag
  • Added a WHOLE bunch of tests so it should be pretty stable
  • Improved Documentation
  • Additional helper methods for evolutionary operators

What’s Next

  • Configuration on run call instead of at Module definition (allows for comparison of the same problem without having to define another module).
  • Still looking into performance, bear with me while I learn Rust :slight_smile:
  • Logbook which basically stores EVERY population that ever existed throughout the algorithm run time. Probably will just use ETS to start with configuration options for Redis or whatever else people want to use.

I’ve been making releases basically consistently once a day; however, I’ll be heading back to school tomorrow so the rate of development will slow down a bit. I have some plans for future features, but I won’t be able to commit as much time as I have to it in the coming weeks.

1 Like

Yeah I relate there, except I work for a college instead of being a student (so done with that well over a decade ago!), we’ve been crazy getting everything ready for the new semester, like everything needed updates… ^.^

Love watching this develop! When I get time I’m planning to experiment, I love genetic algorithms and it’s been years since I’ve messed with it. ^.^

Love watching this develop! When I get time I’m planning to experiment, I love genetic algorithms and it’s been years since I’ve messed with it. ^.^

I appreciate the support! The library has been a lot of fun to mess around with. I’ve had a good time just coming up with examples and playing with the different options. Whenever you do get the chance to experiment, I’d love to hear what you come up with!!

1 Like

You might be interested in these:

2 Likes

I know it’s just hot air until I actually do it but when/if I find the time I’d like to do a Knapsack example.

1 Like

Thanks for putting this in here! I’m trying to formulate how I can seamlessly integrate this into my library/if it’s even worth it.

Anybody have any thoughts?

Check out the Knapsack example I just pushed to master. I think it’s got some flaws. The optimal answer is 15 I believe. Let me know if you can improve it!

Also beware that the code might look slightly different as I’m working through some changes with the library right now.

Stay tuned!

1 Like

I have submitted a small PR for you to examine the Knapsack problem. It is of course sensitive to the pseudo-random nature of the algorithm and for the test problems it sometimes finds the optimum and others times not.

3 Likes

A quick decision I would like some input on.

I have rewritten the way in which algorithms are configured in the library. The new way allows for configuration outside of the module which in turn supports the ability to configure the same problem with different parameters for easier comparison. The new style is also more “Elixir-y” in that it supports piping configuration options into the run function.

One thing I like about this is that it can help separate the algorithm from the problem definition. I’ve always viewed the implementation module as your definition and encoding of your problem and I believe this style does a better job separating the “how” from the “what.” That being said, this might not always make sense in cases where some parts of the algorithm are included in the implementation module (like a custom crossover method).

Basically, my question is: does it make sense to require configuration be done OUTSIDE of the implementation module rather than inside? Is there room for both configuration styles? Which makes more sense to you?

Old Style

defmodule MyGA do
   use Genex, crossover_type: :two_point
                       ...other opts...

New Style

defmodule MyGA do
   use Genex
   ...Implementation...
end

[population_size: 1000]
|> use_crossover(:two_point)
|> use_selection(:random)
|> MyGA.run()
2 Likes

My preference after playing around with the code is the New Style. There would be a temptation to (falsely) tinker with the basic algorithm parts in order to “tune” a particular problem and tie its formulation too much to the solution approach. Other optimisation libraries keep the problem definition separate from the algorithm chosen to solve that problem.

1 Like

Hey guys, sorry I haven’t been able to put much time into this library due to school; however, I have a quick announcement and update.

First, I added a new function interactive/2 up on the master branch for creating Interactive Genetic Algorithms. Basically, you call interactive/2 in your fitness_function/1 definition.

The function accepts chromosome and view which is a function for displaying the Chromosome struct. It defaults to IO.inspect.

This came from a paper I read on Web Design Optimization using GAs. Basically, each Chromosome is displayed to a user and THEY determine the fitness based on some arbitrary criteria. In the case of web pages, it was on how appealing the page looked.

This concept was pretty cool to me so I added the functionality to Genex. You can see the example in the examples directory.

v1.0 Update

I am pushing towards v1.0 slowly but surely. This will include major restructuring of the library and introduce a bunch of new and exciting concepts including Multi-Objective Optimization, Multiple Populations, Customizable Evolutions, different reinsertion strategies, etc. I’m also working on a Web Visualizer of GAs using Phoenix Live View.

I expect v1.0 to be pretty full featured and well-tested when it’s released, and because my time is limited with school, I don’t anticipate it will be out for another month or two.

I plan to use this library for some Academic Research (not just trivial examples like I have been), so expect some pretty cool things in the near future!

If anybody wants to help out, let me know!

5 Likes