LOGISPLAN is developed using optimization techniques based on genetic algorithms. The application of genetic algorithms optimization, can solve NP-Complete, these problems require a practically infinite time to be resolved and, by the techniques used by Evolution Algorithms, can be solved in minutes. Features: An algorithm is an organized series of steps that describes the process to be followed, to solve a specific problem. Genetic algorithms have several characteristics that make them particularly suitable for solving complex problems.
- Genetic algorithms are so named because they are inspired by biological evolution and its genetic and molecular basis.
- These are algorithms evolve a population of individuals subject to random actions similar to those that operate in biological evolution (mutation and genetic recombination), as well as a selection, according to some criterion, in terms of which it is decided what most suitable individuals, who survive, and which are less fit, which are discarded.
- Genetic algorithms eliminate one of the biggest obstacles to the classic design of programs is the need to specify in advance all the features and peculiarities of a problem and the actions required to address them.
- Using genetic algorithms can solve problems that are revealed even impossible to define as it applies to the verbose multiplicity of potential variants.
- Undertake the solution of complex problems with a structure also of enormous complexity inherent potential, so that, as it were, probe the complexity with complexity. To use an analogy, would be to cast a net of sensors over a landscape of valleys and peaks (minimum and maximum evaluation function), instead of proceeding to sequential measurements with certain criteria, which is what we usually do specific algorithms classics.
- The whole evolutionary process employed by nature is a process that works with a high degree of parallelism: all contemporary individuals in a population are subject to both the evaluation function of environment (environment, predators, etc..) and survive, reproduce and die without interference on the simultaneity of such events. By using a similar mechanism, genetic algorithms, but generally are implemented on computers sequentially, due to intrinsic nature of a design very suitable to operate in parallel processing. With the development that undoubtedly will in future systems with large numbers of parallel processors, these algorithms are well suited for deployment in such systems, leading to benefits in performance.
- Many algorithms are designed for the case where the coefficients involved in the problem will be fixed. For example, for allocations of the problem, dealing with such people matching jobs suitable to their respective profiles, the Hungarian algorithm (classic method used for its solution) is the constancy of the coefficients. This means that if the values used for the calculation and the environment conditions change during the process, the method should be stopped and restarted again. Genetic algorithms, however, reorient its own intrinsic automatically the new target and continue the process of convergence towards the optimum dictated by the new conditions. We can therefore say that genetic algorithms are able to converge to the optimal solutions even when the coefficients vary as a result of the provision of allocations. On the issue of allocations, the Hungarian method can not consider the case where the coefficient of a person changes depending on the position occupied by another, as when a person is assigned to a post in the same section in working spouse, for example, the genetic algorithm adapts equally well to the circumstances of the problem.
- Genetic algorithms emerged in the 70s by the hand of John Henry Holland and David Goldberg and since then its application in solving search and optimization problems has been strongly contrasted.
Operation: A genetic algorithm may have several variations, depending on how they apply genetic operators (crossover, mutation), of how the selection is made and how they decide the replacement of individuals to form the new population. An outline of basic operation is summarized in the following steps:
- Initialization: We randomly generated initial population, which consists of a set of chromosomes that represent possible solutions to the problem. Failure to do so randomly, it is important to ensure that within the initial population, it has the structural diversity of these solutions have a representation of the majority of the population as possible or at least avoid premature convergence.
- Assessment: For each of the chromosomes of this population will apply depending on ability to know how "good" is the solution that is being codified.
- End Condition: The genetic algorithm should stop when it reaches the optimal solution, but it is usually unknown, so must use other criteria for detention. Normally we use two criteria: genetic algorithm running on a maximum number of iterations (generations) or stop when there is no change in the population. Until the End meets the condition is as follows:
- Selection: After knowing the fitness of each chromosome is necessary to select the chromosomes to be crossed in the next generation. The chromosomes with better fitness are more likely to be selected.
- Crossover: The crossover is the main genetic operator, represents the sexual reproduction, operates on two chromosomes at once to generate two descendants that combines features of both parental chromosomes.
- Mutation: random change of the chromosome of individuals, and allows to reach areas of the search space that were not covered by the individuals of the current population.
- Replacement: once applied genetic operators, the best individuals are selected to form the next generation population.
|
