Theory of biological evolution in modern biological genetics: the main carrier of genetic substances is chromosome (chromosome), which is mainly composed of DNA and protein. Among them, DNA is the most important genetic substance. Gene (Gene) is a piece of genetic effect, which stores genetic information, which can be accurately replicated, and mutations can also occur, and can control biological state by controlling protein synthesis. Bios themselves by replication of genes (Reproduction) The genetic selection and control of the traits when crossing (Crossover, ie gene separation, gene-separation, gene combination, and gene interchange). The genetic characteristics of the biological industry maintains the species of the biological industry to maintain relatively stability; the variation characteristics of the biological body produce new traits, so that new species (volume variable accumulation is substantial), promoting the evolution and development of biology .
Comparison of basic terms in genetics and genetics
Chromosome data, array, sequence gene (Gene) single element, allele data value, attribute, value gene (LOCUS) position, Iterator position expression type (Phenotype) parameter set, decoding structure, candidate Separation of Epistasis Nonlinearity
The chromosome can also be called a genotype individual (Individuals), and a certain amount of individual constitutes a population, and the number of individuals in the population is called the population size. The degree of adaptation of each individual on the environment is called adaptability (Fitness)
Preparation of Genetic Algorithm: 1) Data conversion operation, including the transition to genotypes and genotypes to the expression. The former is to convert the parameters in the solution to the chromosome or individual (Encoding) in the genetic space, the latter is a decoding 2) determines the appropriate degree of calculation function, and the individual value can be converted to the individual. The degree of adaptation is sufficient to fully reflect the individual's extent to which the individual is solved. Very important process!
The basic step of genetic algorithm genetic algorithm is a search algorithm with an iterative process of generating and-test. The basic process is: 1) Code, creating an initial group 2) Group in the group's individual fitness calculation 3) Assessment Adjustive 4) Selecting individual 5) Selected individuals to cross-propagation, 6) introduction of variational mechanisms during reproduction 7) Bring the new group, return to the second step
An example of a simple genetic algorithm: Y = (X-10) ^ 2 in the range of [0,31] 1) The encoding algorithm is selected to "convert X into 2-based string", the length of the string Troune 5. (The value of the allele is 0 or 1) 2) The method of calculating the appropriateness is: first decoding the individual string, converted to an INT type X value, then use Y = (X-10) ^ 2 as its adaptivity Calculate the appropriate (due to the minimum value, the smaller the result, the better the degree of adaptation) 3) Official start, first set the group size 4, then initialize the group => (in [0,31] randomly selected 4 integers Optional, encoding) 4) Calculate the adaptation Fi (due to the minimum value, a large reference line 1000, FI = 1000 - (x-10) ^ 2) 5) calculates the selection probability of each individual. Select probability It is necessary to reflect the extent of the individual. Here is a very simple method to determine the selection probability P = FI / TOTAL (FI) .6) Select. Parked according to the selection probability of all the individuals. It is a casher here. The way is eliminated. First, create a casher according to the selection probability of each individual, then select 4 times, first generate a random decimal random decimal at 0-1, and then determine that the random number is selected in that segment to select the corresponding individual. During this process, individuals who choose the probability P high will be able to be searched multiple times, and the probability is low may be eliminated.
Below is an example of a simple cassette 13% 35% 15% 37% -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- ------ | ----------------------------------------- | Individual 1 Individual 2 body 3 ^ 0.67 individual 4 Random number 0.67 falls within the end of the individual 4. The individual 4 is selected.
The selected individual will enter the pairing library (Matting Pool, Pairing Group) Preparing to start reproducing. 7) Simple cross-crossed individuals in the pairing library. Then set intersections in the paired two sides, exchange 2 individuals After the information, the next generation is produced. For example (| represents the intersection of simple strings) (0110 | 1, 1100 | 0) - Cross -> (01100, 11001) (01 | 000, 11 | 011) - Cross-Cross- -> (01011, 11000) Two parents have breeds the next generation of the same number of individuals after crossing, complicated crosswhere, cross-crossed methods, and parents can choose. The purpose It is dilated by the locus when the variation is carried out as much as possible. For example, a variation of 20,000 locus is not calculated (we now have 5 locations. That is It is said that it is necessary to evolve one of the genetics in one of the genetics.) The result of the variation is a change in the allele on the locus. The example here is to turn 0 into 1 or 1 becomes 0. At this point, we have produced a new (next-generation) group. Then return to step 4, the week, the beginning, the life will go to :) Pseudo code instance (suitable for friends who are looking at the code ~):
// init population process {individual = encode (random (0,31));}
While (app.isrun) {// calculates individual adaptation int totalf = 0; Foreach Individual in population {individual.f = 1000 - (Individual) -10) ^ 2; Totalf = Individual.f;}
// ------ Select the process, calculate the individual selection probability ----------- Foreach Individual in population {individual.p = individual.f / totalf;} // Select for (int i = 0; i <4; i ) {// selectindividual (float p) is based on the random number falling in paragraph calculation which individual function MatingPool [I] = Population [SelectIndividual (Random (0,1))];} // ------ Simple intersection ------------------------- // Due to only 4 pieces, pairs 2 FOR (INT I = 0; i <2; i ) {matingpool.parents [i] .Mother = matingpool.randompop (); matingpool.parents [i] .father = matingpool.randompop ();
// Create a new group Population.clean (); foreach parent in matingpool.parents {// Note that the variation of a locus in a locus when COPY parental chromosomes is not expressed. Child1 = Parent.mother.divheader Parent.father.divend; child2 = parent.father.divhead parent.mother.divend; population.push (child1); population.push (child2);}} Summary: The most important process in genetic algorithms is to choose and cross. Choosing the natural law that reflects the "Master Survival", while the cross must be omnifialed to the next generation as much as possible (this algorithm is critical!) The process of encoding should be able to make the encoded chromosome can fully reflect The features of individuals can be conveniently calculated. This article is some memories of the original learning, because it is necessary to use it recently. Incorrect places I hope everyone pointed out ~
