What are genetic algorithms?
Genetic algorithms are a branch of artificial intelligence used to solve complex optimisation problems. Genetic algorithms emerged in the 1970s through the work of John Henry Holland and David Goldberg. Since then, their use in solving search and optimisation problems has been extensively validated. LOGISPLAN is developed using optimisation techniques based on genetic algorithms.
An algorithm is an organised series of steps describing the process to follow in order to solve a specific problem.
Genetic algorithms emerged in the 1970s through the work of John Henry Holland and David Goldberg. Since then, their use in solving search and optimisation problems has been extensively validated.
Genetic algorithms are so called because they are inspired by biological evolution and its genetic and molecular basis.
These algorithms evolve a population of individuals by subjecting it to random actions similar to those involved in biological evolution, such as mutations and genetic recombination, as well as to selection according to a given criterion. This criterion determines which individuals are the fittest and survive, and which are less fit and are discarded.
They tackle highly complex problems whose intrinsic structure may itself be enormously complex. In a sense, they probe complexity with complexity. By analogy, it is like casting a mesh of probes over a landscape of valleys and peaks, representing the minima and maxima of the evaluation function, rather than taking sequential measurements according to fixed criteria, as classical specialised algorithms usually do.
The application of genetic algorithms to optimisation makes it possible to solve NP-complete problems. Such problems would require a virtually infinite amount of time to solve and, using the techniques employed by Evolution Algorithms, can be solved in just a few minutes.
Advantages
Genetic algorithms have several characteristics that make them particularly suitable for solving highly complex problems.
Solving complex problems
- They remove one of the greatest obstacles to traditional program design: the need to specify in advance every characteristic and particular feature of a problem, together with all the actions required to address them.
- Genetic algorithms can even solve problems that prove impossible to define exhaustively because of the vast number of their potential variants.
Parallelisation
The entire evolutionary process used by nature operates with a very high degree of parallelism. All contemporary individuals in a population are simultaneously subject to the environment's evaluation function, including environmental conditions and predators. They survive, reproduce and die without interfering with the simultaneity of these events. By using a similar mechanism, genetic algorithms, although generally implemented sequentially on computers, are intrinsically well suited to parallel processing. Today, we can take advantage of systems with large numbers of processors working in parallel, and these algorithms are particularly suitable for implementation on such systems, with the resulting performance benefits.
Adaptability to changes during the optimisation process
Many algorithms are designed for cases in which the coefficients involved in the problem remain fixed. For example, in the assignment problem, which may involve matching people to jobs according to their respective profiles, the Hungarian algorithm, the classical method used to solve it, assumes that the coefficients remain constant. This means that if the values used in the calculation and the surrounding conditions change during the process, the method must be stopped and restarted.
Genetic algorithms, however, are intrinsically designed to redirect themselves automatically towards the new objective and continue converging on the optimum dictated by the new conditions. We can therefore say that genetic algorithms are capable of converging on optimal solutions even when the coefficients vary as a result of the assignments made. In the assignment problem, the Hungarian method cannot take account of cases where the assignment coefficient for one person changes depending on the position occupied by another, for example when someone is assigned to a role in the same department as their spouse. A genetic algorithm adapts equally well to such circumstances.
How they work
A genetic algorithm can take different forms depending on how the genetic operators, such as crossover and mutation, are applied, how selection is performed, and how the replacement of individuals is decided when forming the new population.
A basic operating scheme can be summarised in the following steps:
Initialisation
The initial population is generated randomly. It consists of a set of chromosomes representing possible solutions to the problem. If it is not generated randomly, it is important to ensure that the initial population contains sufficient structural diversity among these solutions. This is necessary to represent as much of the possible population as possible and to avoid premature convergence.
Evaluation
The fitness function is applied to each chromosome in the population to determine how 'good' the encoded solution is.
Termination condition
The genetic algorithm should stop when the optimal solution is reached. As this solution is generally unknown, other stopping criteria must be used. Two criteria are commonly applied: running the genetic algorithm for a maximum number of iterations, or generations, or stopping it when the population no longer changes. Until the termination condition is met, the following steps are performed:
- Selection: Once the fitness of each chromosome is known, the chromosomes that will undergo crossover in the next generation are selected. Chromosomes with greater fitness have a higher probability of being selected.
- Crossover: Crossover is the main genetic operator. It represents sexual reproduction and operates on two chromosomes at a time to generate two offspring that combine characteristics from both parent chromosomes.
- Mutation: Randomly modifies part of an individual's chromosome. It is used to make it possible to reach areas of the search space that were not covered by the individuals in the current population.
- Replacement: Once the genetic operators have been applied, the best individuals are selected to form the population of the next generation.
The optimisation engine of the LOGISPLAN system is developed using techniques based on genetic algorithms.