WWW.DISSERS.RU


...
    !

Pages:     | 1 |   ...   | 13 | 14 || 16 | 17 |   ...   | 54 |

The fact that the definition of gene implies the concept of a unit of minimum relative information as far as a functional unit and that it corresponds to the structural unit of basic molecular DNA and by association can be considered as the basic unit of mutation and of heredity, has taken it directly to trying to simulate genetic algorithms using DNA.

Overview of Genetic Algorithms Genetic Algorithms are adaptive heuristic search algorithm premised on the evolutionary ideas of natural selection and genetic. The basic concept of GA is designed to simulate processes in natural system necessary for evolution, specifically those that follow the principles first laid down by Charles Darwin of survival of the fittest.

As such they represent an intelligent exploitation of a random search within a defined search space to solve a problem.

First pioneered by John Holland in the 60s [Holland, 1975], Genetic Algorithms has been widely studied, experimented and applied in many fields in engineering worlds. Not only does GAs provide an alternative method to solving problem, it consistently outperforms other traditional methods in most of the problems link. Many of the real world problems involved finding optimal parameters, which might prove difficult for traditional methods but ideal for GAs.

GAs are based on an analogy with the genetic structure and behaviour of chromosomes within a population of individuals using the following foundations:

Individuals in a population compete for resources and mates.

Those individuals most successful in each 'competition' will produce more offspring than those individuals that perform poorly.

Genes from good' individuals propagate throughout the population so that two good parents will sometimes produce offspring that are better than either parent.

Thus each successive generation will become more suited to their environment. After an initial population is randomly generated, the algorithm evolves the through three operators: selection which equates to survival of the fittest; crossover which represents mating between individuals; mutation which introduces random modifications.

Selection Operator: gives preference to better individuals, allowing them to pass on their genes to the next generation. The goodness of each individual depends on its fitness. Fitness may be determined by an objective function or by a subjective judgement.

Crossover Operator: prime distinguished factor of GA from other optimization techniques. Two individuals are chosen from the population using the selection operator. A crossover site along the bit strings is randomly chosen. The values of the two strings are exchanged up to this point. If S1=000000 and s2=111111 and the crossover point is 2 then S1'=110000 and s2'=001111. The two new offspring created from this mating are put into the next generation of the population. By recombining portions of good individuals, this process is likely to create even better individuals.

Mutation Operator: with some low probability, a portion of the new individuals will have some of their bits flipped.

Its purpose is to maintain diversity within the population and inhibit premature convergence. Mutation alone induces a random walk through the search space. Mutation and selection (without crossover) create parallel, noise-tolerant, hill-climbing algorithms.

Fourth International Conference I.TECH 2006 One of the basic arguments of the theory of evolution is that individuals that show similarities are related. Based on this principle, Holland observed that certain groups of individuals with particular similarities in some positions in their chains had good common properties whilst others were worse. Abstracting this idea Holland defines the concept of scheme (H) in one binarian coding with chains of length, thus;

H = h -1 h0 {0, 1, *} H = { s -1 s0 / h j * s j = h j } In other words, one scheme represents a certain subgroup of the population in which the individuals differentiate themselves at most in the position of the asterisks.

For example, the scheme H = 10 01 correspond with the chain group {100010, 100011, 101010, 101011} At the same time any group of chains defines a scheme, suffise to consider the J-th Coordinate.

j : { 0, 1 } { 0, 1 } s - 1 s 0 | s j And to define the scheme H thus;

0 if j ( H ) = { 0 } h j = 1 if j ( H ) = { 1 } * if j ( H ) = { 0, 1 } In fact, the group of chains that can be generated by crossing the elements of the group C is exactly H. For example if C = {001011, 011111} then each chain of H = 0 * 1 * 11 can be generated by crossing the elements of C, even 011011 y 001111, that were not initially in C.

Obviously in some schemes their elements show more likeness between themselves than in others. To quantify this idea there are two concepts; The order of a scheme which is the number of fixed alleles in the scheme and the length of definition which is the distance between the first and the last of the fixed alleles. For example if H = 00 * *1*, then o(H) = 3 y (H) = 4.

In essence, Hollands scheme theorem affirms that the algorithm drives the search for the optimum through certain subgroups of the population. In other words, explores the space of search through those areas that on average are more adequate.

Given that during the reproduction a chromosome is selected with a probability proportional to fitness f (s) f (s), s P(t) where P(t) denotes the population t-th. Then if we start from a population of N elements the spected number of representatives of H in the following iteration is E (n ( H, t + 1 ) ) = n ( H, t ). N. f ( H, t ) f (s), s P(t) where E denotes the operator hope, n(H, t) is the number of chains in the scheme Knowledge Engineering In the generation t-th and s H f (s) f ( H, t ) = n ( H, t ) is the average value of the scheme in that generation. If we now consider the action of the operators of crossing and mutation the previous equation is transformed in:

f ( H, t ) E (n ( H, t + 1 ) ) = n ( H, t ). [ 1 ( H ) ] f where:

s H f (s) f = N Represents the average fitness of the population and (H) depends of the structure of H and the probabilities of crossing and mutation, pc y pm, but not of t, Because:

( H ) = p c. ( H ). ( 1 p m ) ( H ) - This expression, ignoring the terms of grade 2 in Newtons binomial, and because pm _ 0.01, turns into the final formula of the fundamental Theorem of genetic algorithms (or Theorem of schemes):

f ( H, t ) ( H ) E (n ( H, t + 1 ) ) = n ( H, t ). [ 1 p c. ( H ). p m ] f - Thus, we have that if H is a scheme with a fitness level greater tan the average of the population it is hoped to increase the number of chains with the structure of H in the following generation as long as a(alpha) is small. In other words, the principle of this theorems can be interpreted saying that short schemes of lower order with greater fitness than the average increase the number of representatives in the successive generations This type of schemes that seem to play an important role in the way that GAs act, are known as building blocks.

It seems then tha by juxtaposing solid blocks of small size, increasingly better individuals could be built. This leads us to think that functions that can be defined utilising short schemes of lower order and high suitabilty would be easy to optimise for the Gas [Mitchell, 1994] This affirmation, known as the hypothesis of the building blocks [Holland, 2000] seems very reasonable. In fact, GAs have been designed for various applications are empirical evidence that for different types of problems such hypothesis is correct.

DNA Simulation of Genetic Algorithms The construction of a genetic algorithm for the resolution of an optimisation problem requires the definition of the genetic architecture. In this sense the election the manner of coding of the individuals represents an important point to obtain the correct solution.

The said coding must be done in a way that each chain allows the storage of information corresponding to an individual of a genetic algorithm. [Gonzlez, 2002] Later on the bits will be represented independently of the position that they are in. [Lipton, 1995] Given that the genetic composition of an individual constitutes a multyfactorial variable, the definition of the individual within a population will be dependent of the problem to be dealt with, that is, an individual has Fourth International Conference I.TECH 2006 a genome that must comply with a number of prerequisites subordinate to the problem, to be considered suitable within that population.

The process of representation of the genes as a minimum unit of information requires the analysing of the problem in question with the purpose of stipulating the number of bits assigned to the mentioned gene.

A gene will be represented as a whole of three fields; the percentage of Timine of the gene will be proportional to the fitness that represents the central field:

ENC(X) FITNESS xy ENC(Y) With the purpose of mapping such fields for later processing the recombining DNA will bring a linker between fields in a way that can be recognised by restriction endonucleases. [Bonen, 1996] Given that PCR will be used for the amplification of the DNA, each individual will carry at the same time, at both ends of the chain a sequence that will hybridise with a specific primer in the annealing phase (hybridization).

The fitness must be embedded in the coding of the individuals and given its definition will be determined by the content in G+C which implies that the fitness of an individual will be directly related with the fusion temperature and hence would be identifiable by spectophotometry (A ) and separable by electrophoresis techniques (DGDE) [Macek 1997].

It is possible then to detect the perfect candidate by means of DGDE as it would be the one the possible candidates to present the greater number of GC pairs and therefore has the greater electrophotometric mobility.

The identification of the individuals of the population requires the tailing of the recombinant with a specific field that identifies the individual in a unique manner, the coding of this field will be done by means of the following function:

CODE: N {G, C} * Where N is the totallity of the natural numbers. It will receive a number corresponding to an individual within a population and returns a sequence of nucleotides.

The identification of the individuals in the mating zone requires again the inclusion of a field (Nm) which will be determined again by the function CODE.

The generation of the initial population has as an objective obtaining an aleatory population with a number of individulas equal to the size of the population. The complexity of the sinthesis of the sequence will be directly related to the number of genes used for the representation of the individuals within the genetic algorithm.

Basically it consists of a recombinant by means of a union of compatible fragments digested with restriction endonucleases.

The final format would look as follows:

PCR-primer Np REp XY RE0 XY RE1 .. REn-1 XY REp Np -1 PCR-primer Knowledge Engineering The selection of individuals will be done by means of specific probes of the problem in question and the isolation of the individuals will be achieved by means of electrophoretic techniques (DGDE).

After selection, the individual will be introduced in the mating zone. For this he must be modified adding a specific field of such zone. In the event that a crossing of individuals is required, it is done in a temporal test tube containing the pair of individuals.

The mutation will be induced on each of the individuals results of the crossings operation in the genes in which the mutation frequency surpasses others obtained at ramdom and consists in the substitution of a gene by its complement in bases.

Later ill adapted individuals from the mating zone will be eliminated and will be substituted by the created recombinants. To determine the finalisation of the algorithm in each iteration the average of population adaptation is calculated. Once the convergence of the population is reached the best individual will be analysed by means of radioactive marking (o etching) techniques.

Fitness Computation on TSP Problem The TSP is interesting not only from a theoretical point of view, many practical applications can be modelled as a travelling salesman problem or as variants of it, for example, pen movement of a plotter, drilling of printed circuit boards (PCB), real-world routing of school buses, airlines, delivery trucks and postal carriers. Researchers have tracked TSPs to study biomolecular pathways, to route a computer networks' parallel processing, to advance cryptography, to determine the order of thousands of exposures needed in X-ray crystallography and to determine routes searching for forest fires (which is a multiple-salesman problem partitioned into single TSPs).

Therefore, there is a tremendous need for algorithms.

In the last two decades an enormous progress has been made with respect to solving travelling salesman problems to optimality which, of course, is the ultimate goal of every researcher. One of landmarks in the search for optimal solutions is a 3038-city problem. This progress is only party due to the increasing hardware power of computers. Above all, it was made possible by the development of mathematical theory and of efficient algorithms.

There are strong relations between the constraints of the problem, the representation adopted and the genetic operators that can be used with it. The goal of travelling Salesman Problem is to devise a travel plan (a tour) which minimises the total distance travelled. TSP is NP-hard (NP stands for non-deterministic polynomial time) - it is generally believed cannot be solved (exactly) in time polynomial.

TSP Solution using a DNA Genetic Algorithms Simulation. Fitness Computation.

Applying the previous protocol to the TSP of four cities in which the total size of the population is 256 (N) and the number of arches 6 (M) the individuals will be coded with an amount T inversily proportional to the length of the arches. The resulting sequence is shown in fig 1:

arch Distance Number of nucleotides Fitness Nucleotides of G AB 1 40 1 BC 1 40 1 CD 4 40 4 BD 3 40 3 AD 2 40 2 AC 6 40 6 Figure 1.- Results of TSP simulation Fourth International Conference I.TECH 2006 The final format would look like this:

Pages:     | 1 |   ...   | 13 | 14 || 16 | 17 |   ...   | 54 |



2011 www.dissers.ru -

, .
, , , , 1-2 .