Introduction
Genetic Algorithms (GAs) are adaptive methods that can be used to solve search and optimization problems.
GAs are capable of creating solutions to real world problems. The evolution of these solutions to optimal values of the problem depends largely on the proper coding of them.
In nature, individuals in a population compete with each other in the quest for resources such as food, water and shelter. Even members of the same species often compete in the search for a partner. Individuals who are more successful in surviving and attracting mates are more likely to generate large numbers of offspring. On the contrary some gifted individuals produce fewer offspring. This means that the genes best adapted individuals in successive generations from spreading to a growing number of individuals.
The combination of good features from different ancestors can sometimes produce offspring "knew people", whose adaptation is far greater than any of his ancestors. In this way, species evolve characteristics making increasingly better adapted to the environment in which they live.
Why Use Genetic Algorithms?
The reason for the growing interest in the AG is that these are global and robust method of finding solutions to problems. The main advantage of these features is the balance struck between efficiency and effectiveness in solving different and very complex problems of large dimensions.
What leads to the AG versus other traditional search algorithms is that they differ from those in the following aspects:
- Work with a codification of a set of parameters, not the parameters themselves.
- Work with a set of points, not a single point and its environment (it's global search technique is). Use a subset of the total space for information on the search universe, through
evaluations of the function optimized. These assessments are used efficiently to classify subsets according to their suitability.
- Do not need specific knowledge to solve the problem that is not subject to restrictions. E.g. it can be applied to non-continuous functions, which opens up a wide range of applications that cannot be treated by traditional methods.
- They use probabilistic operators, instead of the usual deterministic operators of traditional techniques.
General algorithm of Genetic Algorithms
Genetic algorithms are not too difficult to program or understand, since they are biologically based. Thinking in terms of the evolution of real life can help you understand them. General algorithm:
Create a random initial state.
An initial population is created from a random selection of solutions that are analogous to chromosomes. This is a difference to the situation of artificial intelligence systems, where the initial state is already a given problem.
Evaluate Fitness
A fitness value is assigned to each solution (chromosome) depending on how close this really solves the problem (thus arriving at the solution of the problem).
Mutation
The chromosomes with higher fitness value are more likely to play "children" (which may or may not mutate after reproduction). The offspring is a product of father and mother, whose membership consists of a combination of genes from them, this process is known as crossover or crossover.
Next Generation
If the new generation contains a solution that produces an output close enough or equal to the desired response, then the problem has been resolved. If this is not the case, then the new generation goes through the same process as their parents did. This will continue until a solution is reached.
The Simple Genetic Algorithm
Development
During the early years of the representation type used was always binary, because it fits perfectly the type of operation and type of operators used in an AG. However, the binary representations are not always effective as it began to use other representations.
In general, a representation must be able to identify the constituent characteristics of a set of solutions, so that different representations lead to different perspectives and hence different solutions.
For the next application will use the basic model that represents the binary state of each cell of the DataGridView.
Genetic Algorithms Application
With the following application demonstrates the basic operation of a genetic algorithm.
The program will evolve as generations to solve the given problem.
Figure 1 Interface
The program shows three DataGridViews which indicate the target (problem solving); the "citizen" is better suited in the initial population, i.e. one that is closer to the desired solution and finally the result given by each generation.
The program is based on the algorithm described above summarize the three basic functions: Calcular_adaptacion (), q_sort (), kill ().
Calcular_adaptacion ()
It consists of giving each "citizen" a numeric value that represents the degree of adaptation to the objective, i.e., how similar is this. Where 0 is the maximum rate of similarity.
q_sort ()
QuickSort sorting algorithm is used to obtain the "citizen" is better suited.
mate ()
This is the main method in the program, is where the whole process of evolution as it encompasses the selection of parents, crossover and mutation, so the whole creation of the new generation.
The method begins with the selection of parents for which the method of elitism.
Elitism is the simplest form of selection, taking the bodies or chromosomes that have the highest values of adaptation, in this case 10% of them, and the others are discarded. The offspring will have the characteristics of the best adapted, they are passed to an alternate arrangement that facilitates the handling of bodies.
The selection of parents is done randomly, based on previously selected agencies and is a cross between them to generate a new organism.
Subsequently generates the mutation, the mutation can introduce new genetic information in the population. Sometimes this information will be useful, but others can be harmful.
To place the mutation using the mutation ratio indicates the probability that a gene change your information, in this case we use a ratio of 15%.
Parent selection, crossover and mutation
Copy the new generation to use it again
Fig 2 Aplication Running
I also added the algorithm of James Matthews for a "Hello World!" Genetic Algorithm. You can access the sample coded clicking in "Archivo / Consola".
You can see the source code in C here: http://www.generation5.org/content/2003/gahelloworld.asp
Conclusions
The variety of applications for a genetic algorithm is impressive, ranging from the use of simple mathematical equations to works of art (Mona Lisa and genetic algorithms http://alt1040.com/2010/11/mona-lisa-algoritmos-geneticos-y-html5).
Fig. 3 Evolution of a Smile
As shown in Figure 3 by using genetic algorithms and irregular polygons can become quite acceptable approximations.
One of the main advantages of the GA can be seen in its simplicity, since it requires very little information about the search space as it works on a set of solutions encoded parameters (hypotheses or individuals).
It has been observed in the same way that the AG are indicated to solve all kinds of problems that can be expressed as an optimization problem which defines a proper representation of solutions and for the function to be optimized. We seek a solution by approximation of the population, rather than the nearest point to point.
References
[1] http://www.elrincondelprogramador.com/default.asp?pag=articulos/
leer.asp&id=6
[2] http://www.monografias.com/trabajos-pdf/algoritmos-geneticos/algoritmos-geneticos.pdf
[3] http://www.generation5.org/
[4] Algoritmos Genéticos – Lamia Hamdan Medina
[5] Introducción a los algoritmos genéticos y sus aplicaciones -
ww.uv.es/asepuma/X/J24C. pdf