2:01 p.m.
By
Sebastian Avellaneda
Optimization by genetic algorithms
Introduction
Genetic algorithms (GAs) are adaptive methods that can
be used to solve problems search and optimization. They are based on the
genetic process of living organisms. Over generations, the populations evolve
in nature in accordance with the principles of natural selection and survival
of the strongest, postulated by Darwin (1859). By imitation of this process,
genetic algorithms are able to go creating solutions for real-world problems.
The evolution on these solutions to values optimums the problem depends largely
on proper coding of them. The basic principles of genetic algorithms were
established by Holland (1975), and are well described in several texts {Goldberg
(1989), Davis (1991), Michalewicz (1992), Reeves (1993)}.
Developed
In nature
individuals in a population compete against each other in the search for
resources such as food, water and shelter. Even members of the same species
often compete in search of a fellow. Those individuals who are more successful
in surviving and attracting peers are more likely to generate a large number of
descendants. On the contrary some gifted individuals will produce a smaller
number of descendants. This means that all the genes of the fittest individuals
in successive generations from spreading to a growing number of individuals.
The combination of good features from different ancestors can sometimes produce
super individual’s descendants, whose adaptation is far greater than any of
their ancestors. Thus, species evolve characteristics achieving increasingly
better adapted to the environment in which they live.
Genetic Algorithms use a direct analogy with the natural
behavior. They work with a population of individuals, each of which represents
a feasible solution to a given problem. Each individual is assigned a value or
punctuation, related to the goodness of the solution. In nature this is
equivalent to the degree of effectiveness of an agency to compete for specific
resources. The higher the adaptation of an individual to the problem, the
greater the probability that it is selected for breeding, crossing their
genetic material with another individual similarly selected. This crossing will
produce new offspring of the above individuals who share some of the
characteristics of their parents. The lower the adaptation of an individual,
the lower to the probability that the individual is selected for reproduction on
and therefore their genetic material to spread in successive generations.
In this way a new population of possible solutions,
which replaces the previous one and check the interesting property that
contains a higher proportion of good characteristics of comparison with the population
occurs anterior. So throughout generations good features spread through the
population. Favoring the crossing of the fittest individuals, they are being
explored the Most promising areas of the search space. If the Genetic Algorithm
has been well designed, the population will converge to optimal solution of the
problem.
The power of genetic algorithms comes from the fact
that it is a robust technique, and can deal with success a variety of problems
from different areas, including those where other methods are difficulties.
While there is no guarantee that the genetic algorithm finds the optimal
solution to the problem, there is empirical evidence that solutions are an
acceptable level in a competitive time with the rest of combinatorial
optimization algorithms. In case there are specialized to solve a particular
problem techniques, it most likely exceed the Genetic Algorithm, both in speed
and efficiency. The large field of application of genetic algorithms is related
to those problems for which there are no specialized techniques. Even in the
case where such techniques exist and work well, improvements can be made of the
same hybridizations with genetic algorithms.
The structure of this chapter is as follows: in the
next section on is introduced by means of an example the so-called Genetic
Algorithm Simple, also in known as Genetic Algorithm Canonic, to then show
different extensions and modifications thereof, relating? operators selection,
crossover, mutation and reduction as well as Genetic Algorithm hybridization
with other algorithms by Local Index search and various models of Distributed
Genetic Algorithms. In the next section on wonder why the work of genetic
algorithms, proving the theorem schemes, and referencing some theoretical work
related to their conditions sufficient to ensure the convergence of these
algorithms to the global optimum. We end the chapter, showing operator’s
crossover and mutation specific for the traveling salesman problem.
Conclusions
- · As we have seen, the main advantage of genetic algorithms lies in its simplicity. Little information about the search space is required as working on a set of solutions or coded parameters (hypotheses or individuals).
- · A solution by approximation of the population, rather than a point to point approximation is searched. With proper control we can improve the average fitness of the population, obtaining new and better individuals and, therefore, better solutions.
- A balance between effectiveness and efficiency is achieved. This balance is configurable using parameters and operations used in the algorithm. For example, lowering the threshold value get a quick fix to lose in exchange for "quality". If we increase this value, we will have a better solution in exchange for a greater time spent in the search. That is, we get a good relationship between the quality of the solution and cost.
- · Perhaps the most delicate point of all is in the definition of the evaluation function, and their effectiveness depends on good results. The remaining process is the same for all cases.
- · Programming using genetic algorithms represents a new approach that allows covering all those areas of application where we know how to solve a problem.
