Introduction
LOGISPLAN is developed using optimization techniques based on genetic algorithms.
An algorithm is a series of organized steps that describes the process that must be followed in order to solve a specific problem.
Genetic algorithms emerged in the 1970s by John Henry Holland and David Goldberg. Since then, its application in solving search and optimization problems has been strongly verified.
Genetic algorithms are so named because they are inspired by biological evolution and its genetic-molecular basis.
These algorithms make a population of individuals evolve by subjecting it to random actions similar to those that act in biological evolution (mutations and genetic recombinations); as well as a Selection, according to some criterion, according to which it is decided which are the most adapted individuals, who survive, and which are the least fit, who are discarded.
They undertake the solution of highly complex problems with an intrinsic structure also of enormous potential complexity. As it were, they probe complexity with complexity. To use a simile, it would be equivalent to casting a mesh of probes over a landscape of valleys and peaks (minimums and maximums of the evaluation function), instead of proceeding to sequential measurements with certain criteria, which is what specific algorithms usually do. classics.
The application of genetic algorithms in optimization, allow solving problems of the NP-Complete type. This type of problem would take practically infinite time to be solved and, through the techniques used by Evolution Algorithms, can be resolved in a few minutes.
Advantages
Genetic Algorithms have several characteristics that make them especially suitable for solving highly complex problems.
Solving complex problems
- They remove one of the biggest obstacles to classic program design. This is the need for the specification in advance of all the characteristics and peculiarities of a problem and the actions required to address them.
- By means of Genetic Algorithms it is possible to solve even problems that are revealed of impossible definition as far as the neat multiplicity of its potential variants is concerned.
Parallelization
The entire evolutionary process used by nature is a process that works with a very high degree of parallelism. All contemporary individuals of a population are subjected at the same time to the function of evaluating the environment (environment, predators, etc.). These survive, reproduce and die without interference as to the simultaneity of such events. By using a similar mechanism, genetic algorithms, although generally implemented in computers sequentially, obey by their intrinsic nature a very apt design to operate in parallel process. Currently we can take advantage of systems with a large number of processors in parallel, and these algorithms are very suitable for implementation in such systems, with the consequent benefit in performance.
Adaptability to changes during the optimization process
Many algorithms are designed for the case in which the coefficients involved in the problem remain fixed. Thus, for example, in the case of the assignment problem, which tries to match, for example, people to jobs by adapting their respective profiles, the Hungarian algorithm (the classical method used for its solution) assumes the constancy of the coefficients. This means that if the values used for the calculation and the environmental conditions change during the process, the method used must be suspended and restarted again.
Genetic algorithms, however, automatically reorient the new target by their own intrinsic design, and continue the process of convergence toward the optimum dictated by the new conditions. We can therefore say that genetic algorithms are capable of converging towards optimal solutions even when the coefficients vary as a consequence of the arrangement of the assignments. In the allocation problem, the Hungarian method does not allow for the case where the allocation coefficient of one person changes as a function of the position held by another, as occurs when a person is assigned to a position in the same section in that your spouse works, for example; the genetic algorithm is equally well suited to these problem circumstances.
Functioning
A genetic algorithm can have different variations, depending on how genetic operators are applied (crossing, mutation), how the selection is made and how the replacement of individuals is decided to form the new population.
A basic operation scheme is summarized in the following steps:
Initialization
The initial population is randomly generated. This is built by a set of chromosomes which represent the possible solutions to the problem. In case of not doing it randomly, it is important to guarantee that within the initial population, there is the structural diversity of these solutions. It is important to have a representation of as much of the population as possible. Premature convergence should be avoided.
Evaluation
The fitness function will be applied to each chromosome in this population to find out how "good" the solution being encoded is.
Term condition
The genetic algorithm should be stopped when the optimal solution is reached. This is generally unknown, so other detention criteria must be used. Two criteria are normally used: run the genetic algorithm a maximum number of iterations (generations) or stop it when there are no changes in the population. As long as the termination condition is not met, the following is done:
- Selection: After knowing the aptitude of each chromosome, we proceed to choose the chromosomes that will be crossed in the next generation. Chromosomes with better fitness are more likely to be selected.
- Crossing: Crossing is the main genetic operator. Represents sexual reproduction, operates on two chromosomes at the same time to generate two offspring where the characteristics of both parent chromosomes are combined.
- Mutation: randomly modifies part of the chromosome of individuals. They are used to reach areas of the search space that were not covered by the individuals of the current population.
- Replacement: once the genetic operators have been applied, the best individuals are selected to form the population of the next generation.