Build Status |
|
Coverage Status |
|
codecov.io |
|
Documentation |
|
License |
|
BRKGA-MP-IPR 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 Python version is very flexible and suitable for prototyping. However, it is not as fast as the C++ version or the Julia version. Moreover, due to Python Interpreter limitations (see https://wiki.python.org/moin/GlobalInterpreterLock), real multithread is not possible, defeating the BRKGA's capability of parallel decoding, which speeds up the optimization by large paces.
If Python is not suitable to you, we may find useful the C++ version or the Julia version of this framework. 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.
If you are not familiar with how BRKGA works, take a look on Standard BRKGA and Multi-Parent BRKGA. In the future, we will provide a Prime on BRKGA-MP section.
BRKGA-MP-IPR was developed using >= Python 3.7.2, especially using the new
enum
capabilities. The parameters' loading and writing functions may fail
on Python 3.6 or previous versions. However, the main algorithm functions
work fine on Python 3.6, by providing BrkgaParams manually (or implementing
your own parameter loading).
Assuming you have the correct Python version, the installation is pretty straightforward using Pypi:
$ pip3.7 search brkga
brkga-mp-ipr (0.9) - The Multi-Parent Biased Random-Key Genetic Algorithm with Implict Path Relink
$ pip3.7 install brkga-mp-ipr
Collecting brkga-mp-ipr
...
Installing collected packages: brkga-mp-ipr
Successfully installed brkga-mp-ipr-0.9
$ python3.7
Python 3.7.5 (default, Oct 19 2019, 01:20:12)
Type "help", "copyright", "credits" or "license" for more information.
>>> from brkga_mp_ipr.types_io import load_configuration
>>> from brkga_mp_ipr.algorithm import BrkgaMpIpr
>>> BrkgaMpIpr
<class 'brkga_mp_ipr.algorithm.BrkgaMpIpr'>
>>> load_configuration
<function load_configuration at 0x10620e320>
>>> help(load_configuration)
Help on function load_configuration in module brkga_mp_ipr.types_io:
load_configuration(configuration_file: str) -> (<class 'brkga_mp_ipr.types.BrkgaParams'>, <class 'brkga_mp_ipr.types.ExternalControlParams'>)
Loads the parameters from `configuration_file` returning them as a tuple.
Args:
configuration_file (str): plain text file containing the configuration.
Returns:
A tuple containing a `BrkgaParams` and a `ExternalControlParams` object.
Raises:
IsADirectoryError: If `configuration_file` is a folder.
FileNotFoundError: If `configuration_file` does not exist.
LoadError: In cases of missing data or bad-formatted data.
BRKGA-MP-IPR also provides a thorough unit testing that aims to harden and make the code ready for production environments. You can use builtin unittest, or yet pytest or Tox.
:information_source: NOTE: The tests take about 10 minutes, mainly because the permutation path relink.
:warning: Warning: It is a hard test to test algorithms that use random signals. In BRKGA-MP-IPR, the tests are carefully designed to ensure repeatability. For that, we use the Mersenne Twister [1] [2] as our standard random generator number engine, particularly the version that comes with Python 3.7. 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).
The best way to keep it short is to look in the
examples
folder
on the git repo.
Let's take a look into
main_minimal.py
,
which solves the
Traveling Salesman Problem (TSP).
This is a trimmed copy:
import sys
from brkga_mp_ipr.enums import Sense
from brkga_mp_ipr.types_io import load_configuration
from brkga_mp_ipr.algorithm import BrkgaMpIpr
from tsp_instance import TSPInstance
from tsp_decoder import TSPDecoder
def main() -> None:
if len(sys.argv) < 4:
print("Usage: python main_minimal.py <seed> <config-file> "
"<num-generations> <tsp-instance-file>")
sys.exit(1)
seed = int(sys.argv[1])
configuration_file = sys.argv[2]
num_generations = int(sys.argv[3])
instance_file = sys.argv[4]
instance = TSPInstance(instance_file)
decoder = TSPDecoder(instance)
brkga_params, _ = load_configuration(configuration_file)
brkga = BrkgaMpIpr(
decoder=decoder,
sense=Sense.MINIMIZE,
seed=seed,
chromosome_size=instance.num_nodes,
params=brkga_params
)
brkga.initialize()
brkga.evolve(num_generations)
best_cost = brkga.get_best_fitness()
print(f"Best cost: {best_cost}")
if __name__ == "__main__":
main()
You can identify the following basic steps:
Create a data structure to hold your input data which is passed to the
decoder function (example
tsp_instance.py
).
Note that you may not implement a data/instance class but load all needed
information directly on your decoder;
Create a decoder class. The decode()
method from this class
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
tsp_decoder.py
).
Note that the decode()
method must have the following signature:
def decode(self, chromosome: BaseChromosome, rewrite: bool) -> float
where BaseChromosome
is a class inhereted from list
. In other words,
you can tread chromosome
as a simple list of floats;
Load the instance and other relevant data, and instantiate the decoder;
Read the algorithm parameters using load_configuration()
or create
a BrkgaParams object by hand;
Create a BrkgaMpIpr
algorithm object;
Call initialize()
to init the BRKGA state;
Call evolve()
to optimize;
Call get_best_fitness()
and/or get_best_chromosome()
to
retrieve the best solution.
main_minimal.py
provides a very minimal example to understand the necessary steps to use the
BRKGA-MP-IPR framework. However,
main_complete.py
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.
Check out the complete tutorial and API documentation: https://ceandrade.github.io/brkga_mp_ipr_python
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 Journal of Operational Research, volume 289, number 1, pages 17–30, 2021. DOI https://doi.org/10.1016/j.ejor.2019.11.037
Check it out the full license.
Coding side:
Implement the remaining population manipulation methods and tests (short term);
Implement the path relinking methods and tests (long term).
CI and tests side:
Documentation side: