Hi everybody, I am developing a simple and fast genetic algorithm code in C++, only for real genotype ! At the moment I’m using it for mars lander optimization and it works fast and well 
In the future with your helps it can be applied to many kind of game and problems.
If anybody wants to collaborate, use it or simply give me a feedback I’ll appreciate it ! The license is MIT (free for all) and the link is:
I didn’t check every files in details. But it look pretty nice.
I have a similar thing that i copy/paste in my code everytime i need a Genetic Algorithm in a contest. But i don’t have all the features you have (like gaussian mutations).
If you are looking for tips:
If you want to be the fastest possible, you really have to use template. For example in realgen.cpp, you test many time the value of options.selection.type. Most of time, this value will never change in the life of the genetic algorithm. So you can assume you know the value at the compilation time. At the end the function to initialize your RealGen should be something like this:
RealGen ga = createRelGen<ROULETTE_WHEEL_SELECTION>(50, 2, LB, UB);
With a template, all the tests for the value of the selection type is done at the compilation time and there’s no test at all during the runtime.
I took a quick look at your code too, just to check if you did the same mistake as I had done at the beginning 
And you did !
There are a LOT of copies hidden in this simple line. I suggest replacing it with :
population = std::move(newPopulation);
or
std::swap(population, newPopulation)
Good catch. How is behaving std::move with the current compilation options ?
Isn’t it too slow ? (I have really no clue, I don’t know how it works internally, if it’s just an adress overwrite, or something more elaborate).
Other than that, I would suggest introducing methods to track improvements in your population.
I have found that an indicator such as “number of generations since last improvement found” was valuable when trying to evaluate the convergence of your algorithm.
I will also question your use of the “lower bounds” and “upper bounds” for your genes. I think you should stick to one design :
I have no doubts std::move should work fine with the compilation options, but I have not made any tests directly on the CG platform.
Thank you guys for your feedback. I’ll test the code with your tip and I will reply to everyone!
If you want to collaborate directly on guthub, you can fork and pull request the piece of code that you want to change. A guide for beginners:
https://help.github.com/categories/collaborating-with-issues-and-pull-requests/
By the way, I tested it with valgrind, callgrind, a very powerful profiler, see here:
The result is that the bottleneck of entire code is the rand() function
but every optimization are welcome! For coding game, a millisecond is very helpful for a better solution and convergence !
I’m not a GA expert, but for random numbers there are pseudonumber generators. Some are right for Genetic Algorithms. I used mainly:
static unsigned int g_seed=777778;
inline int fastrand() {
g_seed = (214013 * g_seed + 2531011);
return (g_seed >> 16) & 0x7FFF;
}
from Magus posts, and http://xoroshiro.di.unimi.it/xoroshiro128plus.c ( http://vigna.di.unimi.it/xorshift/ )
The first is faster, the second is better (better as more random) and gives 64 bits randoms (that’s why it’s slower). I needed 64 bits randoms that I can’t get with the first function.
Also sqrt and divisions can be costly. I know you are working with floating points. But maybe instead of floats you can use base 100 integers (or base 1024, removing the % for an & mask). So stat.uniformRand() < 0.5 become stat.uniformIndex(100) < 50. I don’t know if that is noticeable performance wise, it must be profiled.
In codingame it’s important to add pragmas, to enable optimizations:
#pragma GCC optimize(“Ofast,inline,omit-frame-pointer,unroll-loops”)
Also try to define as inline the core functions.
About the swap issue, I just use a population[2], and change index: population[currP] and population[newP]. So I just swap indexes. That’s 100% free of any std::move or std::swap problem.
About the swap issue, I just use a population[2], and change index: population[currP] and population[newP]. So I just swap indexes. That’s 100% free of any std::move or std::swap problem.
Same here !
Modified in newPopulation.swap(population) and it works fine ! I have a bit improvement 
Many years later I implemented a more efficient version called realGA, if you are interested take a look here:
You can also minify the code with ./minify.sh