Genetic Algoritms

Rating:Article rated 7 user / s
Written by: admin day of4/18/2011In the category Různé "
Views:This article has been shown 8275 times

Genetic algorithm is one of the heuristic method that is easily used where there is no exact algorithm for finding the exact solution .


   The idea on which these approaches are based comes from evolutionary biology , when we try to imitate the application of techniques of evolutionary processes such as inheritance, natural selection , mutation , crossover , and others to achieve solutions to complex problems . These approaches began to appear in the early 60s of the last century and come from Darwin's theory of evolution of species. Theoretical aspects suitable for application in the field of computer science were elaborated in his book Adaptation in Natural and Artificial Systems, which was written in 1975 by John Henry Holland and is generally regarded as the founder in this area. This technique can divide as follows :


genetic algorithms
genetic Programming
evolutionary Strategy
evolutionary programming
grammatical Evolution


By genetic algorithm


Initialization of the population - the new population is usually composed of randomly generated individuals
With a selection methods are selected individuals from the population according to certain criteria , usually based on their fitness
The selected individuals are generating new individuals by using the following methods:
cross - swapping parts between individuals themselves
mutation - a random change of the individual
reproduction, elitism - Copy individual to another population unchanged
Calculation of the fitness of each newly created individuals
Repeat from step two , unless either end condition
If the exit condition , take the fittest individual and send it as a program output




basic concepts
Genotype (s ) ) - General genetic information


Phenotype ( phenotype ) - a particular case of representation of genetic information


Chromosome ( genome) - General genetic information is represented by a sequence of symbols from some alphabet ( real numbers, characters, or a combination thereof , etc.)


The individual ( Individual) - the carrier of genetic information


Gen ( Gene ) - the location ( position ) on a chromosome


Allele ( Allele ) - specific symbolism , which takes gene on chromosome


Parent ( Parent ) - an individual selected by selection, then entering the recombination


Son ( Offspring ) - an individual who emerges from the recombination of two or more offspring


Rating ( Fitness ) - evaluation of the individual that determines its survival


Intersection ( crossover ) - from two or more individuals created new individual or individuals , their combinations


Mutation ( Mutation ) - random change in allele or alleles of genes in the chromosome


Recombination ( Recombination ) - marking the crossing and mutation


Selection ( Selection) - selection of individuals for the next generation or recombination


Generation (Generation ) - a group of individuals , who through the development


Population ( Population ) - a more general expression for a group of individuals


Migration (Migration ) - the movement of individuals between populations


Adding , readd ( Réinsertion ) - transition individuals to the next generation without crossover or mutation


Scheme ( Scheme) - a prescription for chromosome has identified certain genes






The design of the individual




a) Coding
    Method of coding the individual plays an important role in the success or failure of the genetic algorithm in the particular job . The most widely used way of encoding is a binary encoding for many reasons . Thus expressed chromosome contains genes which have values ​​of 0 or 1 values ​​are different alleles of a gene , ie values ​​, where the gene may be located. For example tab. 1 represents us scrambling population of two individuals.




Tab. Method 1 encoding individuals




Tab. 2 Comparison of binary and Gray code


   This encoding method has one drawback and that is often a big change individual slight changes in the chromosome. For example, if an individual is the distance from the beginning of a coordinate system , the change bit on the high position of the chromosome , although a slight change in individuals, but in the context of the coordinate system, it's a big change in the distance. The disadvantage of this type can be handled on Gray code where two adjacent values ​​encoded in this type of code differs by only one bit. This fact can be seen in tab. Second
    Generally, however, can be encoded using individual characters or real numbers . This method is often used where it works with big numbers and binary representation would form a very long chain. In the area of ​​planning and a variety of combinatorial problems permutation encoding is used , often depends on the order, and the numbers are not repeated in the chromosome .
b ) The evaluation fitness function
    Rating individuals can be done on the basis of the objective function , but also in many other ways . If for example we have a sufficiently large population , it can be divided into two individual and mutually compared.
c ) Scheme of chromosome
    Diagram of the chromosome is a string of length l over the set of symbols for a given chromosome , extended placeholder , which is most commonly referred to * . The scheme can therefore be thought of as a template that describes a subset of the symbols of length l diagram contains an as yet unidentified for a position in the chromosome . We say that the string is an instance of the schema , where all the symbols are the same chain, and the schema that is specified in the schema . Number of designated positions is defined as the order of the scheme. Diagrams are an important tool in analyzing the behavior of a genetic algorithm.


Tab. 3 Wiring and their possible instance.


Sampling ( selection)




   These methods should mimic the process of natural selection. For this reason, the process of reproduction chosen stronger individuals and they are reproduced at the expense of the weaker ones . Just as in nature is that offspring gets mostly good characteristics from their parents. Basic principles while respecting the diversity that there must also be maintained. As in nature , each male chance for every female , no matter how good it is individual , and there must be the basic principle remains. Undue preference for certain individuals - the stronger , could mean a deadlock in a local minimum , while excessive diversity ( diversivita ) would not guarantee a fast convergence to the optimum.
a) The roulette selection
            At the beginning of the summed fitness function of each individual and the size of each individual's fitness function indicates the notional size of the slices on the roulette wheel in Figure 1 When selecting individuals is applied to a random selection of individuals. If an individual is selected , it will fall on the ball of the roulette wheel and proceed to the next generation . The probability that the individual will be selected , can be described as follows:
 ( 2 )
   Where i Є { 1 ... N} , N being the number of individuals of the population, f (i) is the evaluation of the i-th individual, and the sum of f ( j ) denotes the sum of the evaluation of the population.
   To simplify the location of the imaginary balls on the roulette wheel introduce the cumulative valuation tab. 4 , it is possible to generate random placement of balls in the interval < 0, 1 > .
 
Tab. 4 Cumulative assessment


   Thus are successively selected as new individuals depending on to which the interval we ball falls . Suppose that we generate numbers 0.1213 , 0.5522 , 0.2876 and 0.9622 , then we get two individual number 1, once an individual number 2 and 4 , these will be continued reproduction.


 
FIG. 1 Representation of the sectors using the roulette wheel


   This type of selection mechanism favors the fittest and some types of specific tasks can quickly get stuck in local optima .


   This type of selection is similar to the previous one small difference. When selection is not generated the same number of random numbers , such as individuals , but is generated only one random number from the interval < 0, 1 > , which is then divided by the number of individuals . This number defines us first selected individual. Others are selected in consecutive intervals of constant length of 1 / N , where N is the number of individuals that we want to select . This diversity is partially resolved , so the method does not favor the individual with the best ratings.
b ) Tournament selection
   This is a much used method , the main advantage is the simplicity implementations, while maintaining the conditions of the selection mechanism. The stocks are selected individuals , may not be generally only two and they are subject to a duel , individuals with higher valuation to survive and advance to the next round. Based on this fact, the fulfillment of the condition to survive better ranking individuals , but is met diverzivita because individuals are randomly chosen to fight . The selection is also possible to insert random, thus winning the individual postop or not, as shown in the Table . 5th
 
Tab. 5 Selection of specimens by clashes
c ) According to the order
   This method was designed to suppress the influence of supernormal individuals in a population . Individuals are sorted in ascending order according to their ranking . The selection is then carried out on the basis of an individual's position in this list. There are two basic types of linear and non-linear selection.
d ) Local selection
   Each individual has their own designated area, which we call the local environment , and may enter into recombination only with individuals from this area. The first step of the method is the selection of half the population. This selection is performed by some other selection methods . Then pre- selected individuals defined by their surroundings. This neighborhood is defined with respect to a structure in which the population is distributed . Subsequently, the originally selected individuals are recombined with some individuals from their surroundings , again you can use any of the selection mechanisms. Here is a brief excerpt :


linear
full circle , half circle
two-dimensional
Full cross , half cross
full star half star
three-dimensional and more complex with any combination of the preceding structures
e ) The cut selection
   This method has a simple character , choosing from a sorted list of individuals according to their ranking . Select only a certain number of the best . The method is suitable for very large populations . Threshold for scraping trunction threshold ( cutting threshold) is generally set between 10 and 50% .
f ) Elitism
   Especially in small populations can result in the selection of individuals that best selection for recombination. For this reason, it is practical to use elitism , which removes one or more of the fittest individuals who then forwarded directly to the new generation .


operators crossing


   Based on the cross are created by new individuals who were not part of the population. Creating individual is performed so that the part of individuals who enter into recombination , the creation of new . Crossing individuals among them should respect an individual's fitness by selection methods described in the previous section . Thus may arise uncreated combination of solutions and the genetic algorithm is thus often emerge from the particular local minima. The success of each operator depends on the particular task. Among the most basic crossover operators include binary operators , we have them in several variants.
a) Single-point crossover
   Based on the selection mechanism , let us have chosen two chromosomes , it is possible to generate a random number between 0 and K -1, where K represents the length of the chromosome. Does not generate in the range of up to , because we should limit the last position and the two chromosomes would remain unchanged. Tab. 6 shows us the process of mixing for k = 3
 
Tab. 6 One-point crossover for K = 3


b ) Two-and multi-point crossover
    Two-point crossover is similar to the single-point , only the second point there is no confusion genes. This can be seen in Tab. 7th
 
Tab. 7 Two-point crosses for points 4 and 7


   In a similar way, the multi-point crossover . Every odd point determines the position from which the genes and chromosomes screening every even crossing point then the point where there is an interruption of confusion genes , as shown in Table . 8th
 
Tab. 8 Multi crossing points 4 , 5, 6 and 10


c ) Uniform crossing
    This type of cross generalizes the previous two and uses the intersecting mask that is the same length as entering chromosomes . Following this , any point potential point of crossing. At all positions the masks are generated allele values ​​0 or 1 These figures indicate that parental chromosome transmit specific chromosome genes the offspring. Intersecting mask the other parent is the inverse of the mask intersecting the first parent . Consider the method of construction descendant tab. 9th Each gene descendant obtained is randomly chosen with a certain probability . The first gene of the first child has a value of the first ancestor of the gene when in the mask intersecting the first gene allele 1, where the allele intersecting the mask is 0, the gene has a first descendant gene by gene second ancestor.
 
Tab. 9 Uniform crossover


   Some of the specific tasks using the permutation encoding. This means that none of the genes, chromosomes may have the same value , then it would not be a permutation . In previous techniques generally can not prevent a certain value , or vice versa dwell missing. They must use a corrective procedure that creates correctly formed permutations . For this reason , the following operators.


d ) crossed with a partial assignment
    First exchange substring defined by crossing points , other genes still remain available , as shown in Tab. 10 are occupied by a? . Along with this exchange, it is necessary to store the genes that participated in the exchange in the form of rewriting rules for the subsequent repair of the newly created chromosome. In the next step of the parental chromosomes overwrite genes that do not operate in the newly formed chromosomes conflict and vacancies are applied rewriting rules .
 
Tab. 10 To create new chromosomes


e ) cross-over recombination edges
    This operator is well applicable to the traveling salesman problem . Based on the two parental chromosomes, the individual genes of these chromosomes to dump their neighbors . Each gene thus obtains a list of four genes. Subsequently, the construction of a new individual is performed so that for each gene are randomly chosen its neighbors from its list of neighbors. Priority is given to the neighbor who has a list of neighbors as possible. The first gene of the new chromosome is randomly selected. After placement of a new gene into a chromosome of the table will delete this gene from the gene and the table of the lists of neighbors for each gene . Of the two parental genes, thus producing only one descendant .
   Last domain crossing operators are individuals containing real numbers. These operators include Central crossing , line crossing and Advanced liner crossing.
    


operators mutation


   Mutations brings to the newly formed chromosomes after crossing random element changes. Just as in nature are not copies of offspring from their parents accurate picture , but some genes recombine randomly change their information . Based on this operator, we can get the scanned PROSTR to solutions that are based on cross achievable. Mutations can also help improve the population where as only one strong individual , and the rest is weaker individuals .
a) Binary mutation
    In this type of mutation occurs in the binary encoding genes changed from 1 to 0 or vice versa.
 
Tab. 11 represents the possibility of change of 5% for each gene


   The frequency of mutations can be increased in stagnant population and the subsequent improvement again return to its original value . It is also possible mutation in the initialization set higher as the number of iterations to decrease it . This can be understood by first crawl the state space in breadth and later try to improve rather promising solutions .
b ) Real and Integer operators mutation
   There are a number of mutation operators real or integer values. These include :
 
Random replacement - replacing the original alleles random value
Additive change - add or subtract randomly generated values ​​to the original allele.
Multiplicative change - multiplying or dividing values ​​randomly generated number .


 c ) Replacement mutations
    This type of mutation is well applicable to the permutation encoding, where the random change in allele could mean repeating values ​​in the chromosome and in addition , the initial number dropped . Therefore, you can use the following techniques when the random positions of the two genes exchanged tab. 12th
 
Tab. 12 As you can see , this operator can be used in all types of coding
(binary, real , integer and permutation ) .


d ) Sliding mutation
            The chromosome is randomly selected and the gene is moved to a randomly generated position that we shift the position of genes , where we put in place , where we take . Tab. 13 we represent this type of mutation. As you can see , this operator can be used for all types of coding.
 
Tab. 13 Sliding mutation


e ) Inverse mutation
    In Tab. 14 shows how the operator works . First, they are randomly selected two genes in a chromosome and will subsequently inverting section between these genes . The operator can therefore also be used for permutation encoding.
 
Tab. 14 Inverse mutation


restocking




   This operator comes after a series of selection , crossover and mutation. If it is produced more or less individuals than in the original population , it is necessary to be remedied . To this end, several approaches are used .




Parallel Genetic Algorithms
      
   This form of genetic algorithms have been designed to accelerate the calculation of solution sought . There are three main models of parallel genetic algorithms , and Migration , Global and Diffuse model.
a) The migration model
   The population is divided into multiple podpopulací Figure 2 These podpopulace evolve independently of the other a specified number of iterations. After calculating all the iterations leads to the migration of a number of individuals from each podpopulace to another podpopulace . Based on the type of selection of individuals for exchange and the exchange of individuals determines the way the diversity and transformation of information , which may occur between podpopulacemi . On this basis, we divide migration models. Implementation of the migration model, we ensure faster achievement of optimum at less evaluation -functioning compared with only one population .
 
FIG. 2 Migration model


b ) The global model
    This model does not divide the population to more podpopulací , but divides the calculation process of genetic algorithm into parallel threads. The control process (master ) performs the selection and evaluation assigns individuals , other processes such as crossover , mutation and fitness calculation functions are distributed to child processes (slave ) Figure 3
 
FIG. 3 Global model


c ) The diffusion model
   Each individual is managed separately and individuals enter crossing with other individuals only in their neighborhood . As shown in Figure 4
 
FIG. 4 Diffusion model population


Source: Prata , Stephen : Mastery of C + +
          Kajanek , Petr ; Covered , Josef : Introduction to genetic algorithms
          Ondřej Škrabal : Genetic algorithms and scheduling ; thesis

How do you rate this article?


Readers Reactions

Connect your own comment

Name:
E-mail:
Comments
Insert Cancel
 
 
2010 © Schedule Monitor - make it cheaper. All rights reserved.