Individual

In the context of genetic algorithms (GAs), individuals are the basic building blocks that make up the population within the algorithm. An individual, also referred to as a chromosome or solution, represents a potential solution to the problem being addressed. In the genetic algorithm framework, solutions are encoded as strings of parameters or values, and each individual in the population is a unique combination of these encoded values. These individuals collectively form the genetic diversity of the population, embodying different potential solutions to the optimization problem.

The genetic material of an individual is subject to genetic operations such as crossover and mutation during the evolution process. Crossover involves recombining genetic material from two parent individuals to create offspring, mimicking the process of genetic recombination in biological reproduction. Mutation introduces small, random changes to an individual’s genetic makeup, ensuring that the population maintains diversity and preventing the algorithm from converging prematurely to suboptimal solutions. The combination of these genetic operations allows the algorithm to explore a wide range of potential solutions and adapt to the evolving landscape of the solution space.

The fitness of an individual is a crucial concept in genetic algorithms, representing how well a particular solution performs in solving the given problem. The evaluation of fitness guides the selection process, determining which individuals are more likely to be chosen for reproduction and passing their genetic material to the next generation. The overarching objective is for the population to evolve over successive generations, with the fitter individuals having a higher probability of being selected and contributing to the overall improvement of the population’s solution quality. Through the interactions of individuals, genetic algorithms harness the principles of natural selection to iteratively refine and enhance the population until satisfactory solutions to the optimization problem are achieved.

Encoding

The first characteristic about an individual that has to be taken into account is the encoding used to represent the values of the genes. Mango allows for three encodings:

  • Binary.

  • Integer.

  • Real.

Binary encoding

The binary encoding is a widely used encoding in genetic algorithms. It is used to represent values that can be either true or false, or 0 and 1. The binary encoding is the most efficient encoding in terms of memory usage, as it only requires one bit to represent each gene. However, it is also the most restrictive encoding, as it can only represent a limited number of values. For example, a binary encoding of 8 bits can only represent 256 different values.

This encoding limits the type of crossover methods that can be used and only applies a very simple type of mutation, the bit-flip.

Integer encoding

The integer encoding is used to represent integer values. It is more flexible than the binary encoding, as it can represent a larger number of values. However, it is also less efficient in terms of memory usage, as it requires more bits to represent each gene. The restriction of having each gene an integer value can have a negative impact on the exploration part of the algorithm if the range of possible values that can be chosen is big (more than 8 possibilities can start to be a problem).

This encoding, as the binary encoding, limits the typo of crossovers that can be used.

This encoding is also very sensible to the generation of the initial population, as if some integer values are not present in the initial population is possible that they will never be generated by the crossover methods and we are dependent on them appearing through the mutation process (unreliable).

Real encoding

The real encoding is used to represent real values. It is the most flexible encoding, as it can represent a very large number of values. However, it is also the least efficient in terms of memory usage, as it requires more bits to represent each gene.

This encoding allows the better range for exploring the solution space and allows for almost all crossover methods to be used, but as with the integer encoding, if the range of possible values for each gene is big it can make convergence harder for the genetic algorithm.

Mutation

The mutation process is used to introduce new genetic material into the population, ensuring that the population maintains diversity and preventing the algorithm from converging prematurely to suboptimal solutions. The mutation process is applied to each individual in the population with a certain probability, and it involves randomly changing the value of one or more genes in the individual’s genetic material. The mutation process is a crucial component of genetic algorithms, as it allows the algorithm to explore a wide range of potential solutions and adapt to the evolving landscape of the solution space.

The mutation processes depends heavily on the encoding used by the individual. The random change for each type of mutation is as follows:

Binary:

gene_position = randint(0, self.gene_length - 1)
self.genes[gene_position] = 1 - self.genes[gene_position]

This mutation process is called bit-flip. A random gene is selected and its value is flipped.

It is implemented on mutate_binary.

Integer:

gene_position = randint(0, self.gene_length - 1)
self.genes[gene_position] = randint(self.min_value, self.max_value)

This mutation process is called random-resetting. A random gene is selected and its value is changed to a random value between the minimum and maximum values allowed.

It is implemented on mutate_integer.

Real:

gene_position = randint(0, self.gene_length - 1)
self.genes[gene_position] = uniform(self.min_value, self.max_value)

This mutation process is called random-resetting. A random gene is selected and its value is changed to a random value between the minimum and maximum values allowed.

It is implemented on mutate_real.

Implementation

In mango’s implementation of an individual we provide a base class (Individual) that can be used as is or extended to create a custom individual that either implements more functionalities or overrides the existing ones.

The base class has the following attributes:

  • config: The configuration of the genetic algorithm passed to the individual.

  • encoding: The encoding used by the individual.

  • fitness: The fitness value of the individual.

  • genes: The genes of the individual.

  • idx: The internal index of the individual in the population.

  • parents: The parents of the individual.

The base class has also some methods that can be overriden in case further customization is needed: