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!
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.
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:
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.
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!
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
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 .
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!
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
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.
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!!
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.
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.
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()
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.
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!
Hey everbody, I’m not sure if anybody actually uses this library, but I have a ton of fun developing it and I’ve used it for some research projects too.
Anyway, I’ve just released the beta version of v1.0.0. It’s beta because there’s not much documentation or testing done, but the design of the library will pretty much remain the same. v1.0 has some major breaking changes, but it’s super powerful and I’m really excited about what you can do with Genex right now.
What’s New
Changed encoding/0 to genotype/0. Semantic change for correctness.
New Crossover, Selection, Mutation Operators.
Support for Multi-Objective Optimization
Ability to fully customize every step of an evolution.
Hall of Fame to track best solutions.
Ability to save and load evolutions.
Ability to represent solutions as any Enum datatype.
Addition of several convenient generation functions.
Addition of several benchmark functions for GP, SOC, MOC, Binary GAs, etc.
Addition of penalty functions for constraint problems.
Addition of interactive genetic algorithms.
Ability to create custom visualizations through visualization behaviour.
What’s Next
I have a lot of really cool things planned, but my time is pretty off and on with school and other obligations. I plan to start posting about some of the awesome things you can do with Genex soon, time willing.
If anybody wants to see anything in particular added in, or has any questions about the library, please feel free to reach out to me. I hope somebody out there finds some use out of this, if only to mess around and have fun!
I probably already told you this buy I did a genetic algorithm in university for the backpack problem (in Java, don’t laugh that’s all I knew at the time) and it was a ton of fun. I truly think the potential of genetic algorithms has yet to be realized. Thanks for this.
