A simple genetic algorithm for optimization
- Javier Burguete Tolosa (jburguete@eead.csic.es)
- Borja Latorre Garcés (borja.latorre@csic.es)
- configure.ac: configure generator
- Makefile.in: Makefile generator
- build.sh: simplified building shell script
- README.md: This file
- *.h: Header files
- *.c: Source files
- Doxyfile: configuration file to generate doxygen documentation
- gcc or clang to compile the source code
- make to build the executable file
- autoconf to generate the Makefile in different operative systems
- automake to check the operative system
- pkg-config to find the libraries to compile
- gsl to generate random numbers
- glib extended utilities of C to work with data, lists, mapped files, regular expressions, using multicores in shared memory machines, ...
- openmpi or mpich to run in parallelized tasks on multiple computers
- doxygen standard comments format to generate documentation
- latex to build the PDF manuals
On Fedora Linux 38, in order to use OpenMPI compilation, do in a terminal (in 64 bits version):
$ export PATH=$PATH:/usr/lib64/openmpi/bin with MPIC (in 64 bits version): $ export PATH=$PATH:/usr/lib64/mpich/bin
On Microsoft Windows systems you have to install MSYS2 and the required libraries and utilities. You can follow detailed instructions in install-unix
On NetBSD 9.3, to compile with last GCC version you have to do first on the building terminal:
$ export PATH=/usr/pkg/gcc9/bin:$PATH"
On OpenBSD 7.6 you have to do first on the building terminal to select adequate versions and deactivate OpenMPI (does not link) building with CLang:
$ export AUTOCONF_VERSION=2.69 AUTOMAKE_VERSION=1.16 CC=clang
On OpenIndiana Hipster, in order to enable OpenMPI compilation, do in a terminal:
$ export PATH=$PATH:/usr/lib/openmpi/gcc/bin
On OpenSUSE Linux 15.5, in order to enable OpenMPI compilation, in 64 bits version do in a terminal:
$ export PATH=$PATH:/usr/lib64/mpi/gcc/openmpi/bin
This software has been built and tested in the following operative systems:
- Arch Linux
- Debian Linux 12
- Devuan Linux 4
- Dragonfly BSD 6.4.0
- Fedora Linux 38
- FreeBSD 13.2
- Gentoo Linux
- Linux Mint DE 5
- MacOS Ventura + Homebrew
- Manjaro Linux
- Microsoft Windows 10 + MSYS2
- NetBSD 9.3
- OpenBSD 7.6
- OpenInidiana Hipster
- OpenSUSE Linux 15.5
- Ubuntu Linux 23.04
Probably, it can be built in other systems, distributions, or versions but it has not been tested
Download this repository and execute on a terminal:
$ git clone https://github.com/jburguete/genetic.git
$ cd genetic/3.0.1
$ ./build.sh
FINAL VERSION
Optionally, a final compact version without debug information can be built doing on the terminal:
$ make strip
To build dynamically this algorithm in other programs:
-
Build the binary code (follows the former section steps)
-
Link in your source directory the latest code version i.e.
$ cd YOUR_PROGRAM_PATH
$ ln -s PATH_TO_GENETIC/3.0.1 genetic
- Include the genetic headers in your source code files:
#include "genetic/genetic.h"
- Link the dynamic library in your source directory:
$ ln -s genetic/libgenetic.so or in Windows systems: $ ln -s genetic/libgenetic.dll
- Link the genetic library with your code to build the executable file i.e.
$ gcc YOUR_CODE.c -L. -Wl,-rpath=. -lgenetic `pkg-config --libs gsl`
MAIN FUNCTION
The prototype of the main function is:
int genetic_algorithm(
unsigned int nvariables,
GeneticVariable *variable,
unsigned int population,
unsigned int ngenerations,
double mutation_ratio,
double reproduction_ratio,
double adaptation_ratio,
const gsl_rng_type *type_random,
unsigned long random_seed,
unsigned int type_reproduction,
unsigned int type_selection_mutation,
unsigned int type_selection_reproduction,
double thresold,
double (*simulate_entity)(Entity*),
char **best_genome,
double **best_variables,
double *best_objective);where the parameters are:
- nvariables: variables number
- genetic_variable: array of data to define each variable. The fields of the
data structure are:
- maximum: maximum value
- minimum: minimum value
- nbits: number of bits to encode
- population: population size
- ngenerations: number of generations
- mutation_ratio: mutation probability
- reproduction_ratio: reproduction probability
- adaptation_ratio: adaptation probability
- type_random: type of GSL random numbers generator algorithm. See the
GSL documentation.
Valid algorithms are:
- gsl_rgn_mt19937 (default value)
- gsl_rng_taus
- gsl_rgn_gfsr4
- gsl_rgn_ranlxs0
- gsl_rgn_ranlxs1
- gsl_rgn_mrg
- gsl_rgn_ranlux
- gsl_rgn_ranlxd1
- gsl_rgn_ranlxs2
- gsl_rgn_cmrg
- gsl_rgn_ranlux389
- gsl_rgn_ranlxd2
- random_seed: seed to the GSL random numbers generator algorithm (0 uses the default GSL seed)
- type_reproduction: type of reproduction algorithm. Valid values are:
- REPRODUCTION_TYPE_MIXING (default value): the son genome is a random mixing between mother and father genomes in each bit
- REPRODUCTION_TYPE_SINGLEPOINTS: the son genome is equal to mother genome previous to a random point and next it is equal to the father genome
- REPRODUCTION_TYPE_DOUBLEPOINTS: the son genome is equal to father genome between two random points and equal to the mother genome in the rest
- type_selection_mutation: type of algorithm to select the mothers to
create sons with a mutation. The mutation inverts a random bit in the son
genome. Valid values are:
- SELECTION_MUTATION_TYPE_LINEARRANK (default value): the mother is selected randomly between the survival entities assigning a linear probabiltiy higher for better entities
- SELECTION_MUTATION_TYPE_RANDOM: the mother is selected randomly between the survival entities
- SELECTION_MUTATION_TYPE_BESTOF2: the mother is the best of two randomly selected between the survival entities
- SELECTION_MUTATION_TYPE_BESTOF3: the mother is the best of three randomly selected between the survival entities
- SELECTION_MUTATION_TYPE_BEST: the mother is the best of the survival entities
- type_selection_reproduction: type of algorithm to select the parents to reproduce
- type_selection_adaptation: type of algorithm to select the mothers to
create sons with a adaptation. An adaption inverts a random bit between the
lowest significative bits. Valid values are:
- SELECTION_ADAPTATION_TYPE_LINEARRANK (default value): the mother is selected randomly between the survival entities assigning a linear probabiltiy higher for better entities
- SELECTION_ADAPTATION_TYPE_RANDOM: the mother is selected randomly between the survival entities
- SELECTION_ADAPTATION_TYPE_BESTOF2: the mother is the best of two randomly selected between the survival entities
- SELECTION_ADAPTATION_TYPE_BESTOF3: the mother is the best of three randomly selected between the survival entities
- SELECTION_ADAPTATION_TYPE_BEST: the mother is the best of the survival entities
- thresold: thresold in objective function to finish the simulations
- simulate_entity: pointer to the function to perform each simulation
- best_genome: new generated best genome
- best_variables: new generated best variables array
- best_objective: obtained best objective function value
CONVENIENT FUNCTION USING DEFAULT ALGORITHMS
If using default algorithms is considered, the following convenient simplified function can be used:
int genetic_algorithm_default(
unsigned int nvariables,
GeneticVariable *variable,
unsigned int population,
unsigned int ngenerations,
double mutation_ratio,
double reproduction_ratio,
double adaptation_ratio,
unsigned long random_seed,
double thresold,
double (*simulate_entity)(Entity*),
char **best_genome,
double **best_variables,
double *best_objective);Exec on a terminal:
$ cd genetic/3.0.1
$ doxygen
$ cd latex
$ make