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.