BrkgaMpIpr.jl - Julia version
|Travis Build Status|
|AppVeyor Build Status|
BrkgaMpIpr.jl provides a very easy-to-use framework for the Multi-Parent Biased Random-Key Genetic Algorithm with Implict Path Relink (BRKGA-MP-IPR). Assuming that your have a decoder to your problem, we can setup, run, and extract the value of the best solution in less than 5 commands (obvisiously, you may need few other lines fo code to do a proper test).
This Julia version provides a framework as fast as C/C++, as easy-to-code as Python, and it is much cheaper (indeed, free) than Matlab. Unit and coverage tests are fully implemented, and all pseudo-random test data were carefully crafted to guarantee reproducibility (although it is possible that some tests fail because of different versions of the random number generator). Therefore, BrkgaMpIpr.jl should be suitable to be used in production environments.
If Julia is not suitable to you, we may find useful the C++ version We are also developing a Python version which is in its earlier stages. At this moment, we have no plans to implement the BRKGA-MP-IPR in other languages such as Java or C#. But if you want to do so, you are must welcome. But please, keep the API as close as possible to the C++ API (or Julia API in case you decide go C), and use the best coding and documentation practices of your chosen language/framework.
💻 Installation and tests
ℹ️NOTE: BrkgaMpIpr.jl was developed using Julia 1.2, but it should work fine on any Julia >= 1.0. Versions <= 0.6 are not supported.|
BrkgaMpIpr.jl can be installed using the Julia package manager.
From the Julia REPL, type
] to enter the Pkg REPL mode and run
pkg> add BrkgaMpIpr
Or, just use
julia> import Pkg; Pkg.add("BrkgaMpIpr")
BrkgaMpIpr.jl also provides a thorough unit testing that aims to harden and make the code ready for production environments. From Pkg REPL, just run
pkg> test BrkgaMpIpr
ℹ️NOTE: The tests take about 10 minutes, mainly because the permutation path relink.
Although BrkgaMpIpr should work fine on Julia >= 1.2, some tests can fail. This issue occurs because BrkgaMpIpr uses the JLD package to save the population and results. JLD uses the HDF5 package, which produces slightly different binaries of different Julia versions. Although the tests may fail in those cases, BrkgaMpIpr is functional for regular usage. In the table below, you can see the testing fails due to JDL binary incompatibility.
|Julia version||Windows||Linux||Mac OS X|
⚠️Warning: Some timing tests may fail when carried out on virtual machines and containers. The reason is that in such environments, the code runs much slower than on bare metal, and some control loops take much time to finish before the time stop. Usually, the difference is a few seconds, but it is enough to break some tests.
⚠️Warning: It is a hard test to test algorithms that use random signals. In BrkgaMpIpr.jl, the tests are carefully designed to ensure repeatability. For that, we use the Mersenne Twister   as our standard random generator number engine, particularly the version that comes with Julia. However, it may happen that such engine has slightly different implementations across platforms and, therefore, the tests may fail. The current version was tested on 64-bit platforms (Mac OS X, GNU/Linux, and Windows 10).
⚡ Usage - TL;DR
using BrkgaMpIpr include("tsp_instance.jl") include("tsp_decoder.jl") if length(ARGS) < 4 println("Usage: julia main_minimal.jl <seed> <config-file> " * "<num-generations> <tsp-instance-file>") exit(1) end seed = parse(Int64, ARGS) configuration_file = ARGS num_generations = parse(Int64, ARGS) instance_file = ARGS instance = TSP_Instance(instance_file) brkga_data, control_params = build_brkga( instance, tsp_decode!, MINIMIZE, seed, instance.num_nodes, configuration_file ) initialize!(brkga_data) evolve!(brkga_data, num_generations) best_cost = get_best_fitness(brkga_data) @show best_cost
You can identify the following basic steps:
Create a data structure inherited from
AbstractInstanceto hold your input data. This object is passed to the decoder function (example
Implement a decoder function. This function translates a chromosome (array of numbers in the interval [0,1]) to a solution for your problem. The decoder must return the solution value or cost to be used as fitness by BRKGA (example
Load the instance and other relevant data;
build_brkgato create a
BrkgaDatathat represents the internal state of the BRKGA-MP-IPR algorithm;
initialize!to init the BRKGA state;
get_best_chromosometo retrieve the best solution.
provides a very minimal example to understand the necessary steps to use the
BRKGA-MP-IPR framework. However,
provides a full-featured code, handy for scientific use, such as
experimentation and paper writing. This code allows fine-grained control of
the optimization, shows several features of BRKGA-MP-IPR such as the resets,
chromosome injection, and others. It also logs
all optimization steps, creating outputs easy to be parsed. You should use
this code for serious business and experimentation.
📚 Tutorial and full documentation
Check out the complete tutorial and API documentation: https://ceandrade.github.io/BrkgaMpIpr.jl
✒️ License and Citing
BRKGA-MP-IPR uses a permissive BSD-like license and it can be used as it pleases you. And since this framework is also part of an academic effort, we kindly ask you to remember to cite the originating paper of this work. Indeed, Clause 4 estipulates that "all publications, softwares, or any other materials mentioning features or use of this software (as a whole package or any parts of it) and/or the data used to test it must cite the following article explicitly:":
C.E. Andrade. R.F. Toso, J.F. Gonçalves, M.G.C. Resende. The Multi-Parent Biased Random-key Genetic Algorithm with Implicit Path Relinking. European Jornal of Operational Research, volume 289, number 1, pages 17–30, 2021. DOI https://doi.org/10.1016/j.ejor.2019.11.037