PyGenAlgo: A simple and powerful toolkit for genetic algorithms.

"Genetic Algorithms (GA), are meta heuristic algorithms inspired by the process of natural selection and belong to a larger class of evolutionary algorithms (EA)."

-- (From Wikipedia, the free encyclopedia)

This repository implements a genetic algorithm (GA) in Python3 programming language, using only Numpy and Joblib as additional libraries. The basic approach offers a "StandardGA" class, where the whole population of chromosomes is replaced by a new one at the end of each iteration (or epoch). More recently, a new computational model was added named "IslandModelGA" class that offers a new genetic operator (MigrationOperator), that allows for periodic migration of the best individuals, among the (co-evolving) different island populations.

NOTE: For computationally expensive fitness functions the StandardGA class provides the option of parallel evaluation (of the individual chromosomes), by setting in the method run(..., parallel=True). However, for fast fitness functions this will actually cause the algorithm to execute slower (due to the time required to open and close the parallel pool). So the default setting here is "parallel=False". Regarding the IslandModelGA, this is running in parallel mode by definition.

NEWS: Recently a new feature was added "adapt_probs: (bool)". This option if enabled, will allow the crossover and mutation probabilities to adapt according to the convergence of the population to a single solution. This uses the average Hamming distance to set a threshold value and either increase or decrease the genetic probabilities by a pre-defined amount.

The current implementation offers a variety of genetic operators including:

• Selection operators:

  • Linear Rank Selector
  • Random Selector
  • Roulette Wheel Selector
  • Stochastic Universal Selector
  • Tournament Selector
  • Truncation Selector
  • Boltzmann Selector

• Crossover operators:

  • Single-Point Crossover
  • Multi-Point Crossover
  • Uniform Crossover
  • Order Crossover (OX1)
  • Partially Mapped Crossover (PMX)
  • Position Based Crossover (POS)

• Mutation operators:

  • Random Mutator
  • Shuffle Mutator
  • Inverse Mutator
  • Gaussian Mutator
  • Swap Mutator
  • Flip Mutator

• Migration operators

  • Clockwise Migrator
  • Random Migrator

• Meta operators

  • Meta Crossover
  • Meta Mutator
  • Meta Migration

(NOTE: Meta operators call randomly the other operators (crossover/mutation/migration) from a predefined set, with equal probability.)

Incorporating additional genetic operators is easily facilitated by inheriting from the base classes: - SelectionOperator - CrossoverOperator - MutationOperator - MigrationOperator

and implementing the basic interface as described therein. In the examples that follow I show how one can use this code to run a GA for optimization problems (maximization/minimization) with and without constraints. The project is ongoing so new things might come along the way.

Installation

There are two options to install the software.

The easiest way is to visit the GitHub web-page of the project and simply download the source code in zip format. This option does not require a prior installation of git on the computer.

Alternatively one can clone the project directly using git as follows:

git clone https://github.com/vrettasm/PyGeneticAlgorithms.git

Required packages

The recommended version is Python 3.10 (and above). To simplify the required packages just use:

pip install -r requirements.txt

Fitness function

The most important thing the user has to do is to define the "fitness function". A template is provided here, in addition to the examples below.

```python from pygenalgo.genome.chromosome import Chromosome

Fitness function