Dzhura V. P. «Hardware implementation of the compact genetic algorithms in the language of design VHDL» Abstract

Master of DonNTU:    Dzhura Valery Petrovich
Fuculty:    Computer Information Technologies and Automation
Speciality:    Computing ingineering
Theme:    «Hardware implementation of compact genetic algorithms in the ЯOA VHDL»
Leader:    Skobtsov V. Y.

INTRODUCTION

idea of genetic algorithms aided design systems in active development, along with other lines. For the first time this idea was proposed by Louis S. and D. Raulinsom in 1991 and experimentally verified in the field of digital circuits. In the future, the proposed methods have been developed and refined, and have been used in many automated systems design equipment. There is currently no burgeoning develops one of the most promising directions in this area associated with designing samorekonfiguriruemyh hardware and auto design schemes, the realization of dynamic reconfiguration in mobile systems, building rekonfiguriruemyh hardware on a single crystal BIS. etc.

Using genetic algorithms (GA) as a mechanism for automatic design schemes for rekonfiguriruemyh platforms, was named evolutionary hardware (Evolvable Hardware) which also used a synonym for several general direction, known as evolutionary Electronics (Evolutionary Electronics) .

In most cases, genetic algorithms act as software modules, which is modeled GA program, and only the final decision obtained through GA, is used to evolyutsionirovaniya scheme. For autonomous decisions and tasks related to the construction of evolution of hardware, software implementation GA is unacceptable for a variety of criteria. The very existence of self-exclude the possibility of using software solutions running on a PC or cluster method. On the other hand, autonomous system, usually operate in real time, placing some requirements on time characteristics used algorithms, therefore, the use of software models cease to be relevant.

Scientific research essence

Relevance of work connected with the growing interest application genetic algorithms in the autonomous systems, improving performance of genetic algorithms and vremeemkih development of new directions in the design of hardware, known as evolutionary hardware funds. As a consequence of extending the scope of the most acute issue to develop techniques improve effectiveness of genetic algorithms on a set of criteria. The solution of such issues advocated hardware implementation genetic algorithms.

Modern trends in the development of the scope of GA cause expansion of techniques for design and development of new techniques to enhance the effectiveness of genetic algorithms. These methodologies will be demanded as in the study of new application areas GA and practical application solutions for end - tasks. The proposed approach is the solution to improving the efficiency of genetic algorithms is one of the most promising methods to improve the efficiency and expand areas of application not only to review goals genetic search, but the tasks for which required considerable time costs. In doing so, the main purpose supports the development of methodology for constructing the facility, the maximum optimized under a specific class of problems, universal within this class, and using modern methods of hardware implementation (konveyerizatsiya, during the computation, firmware principle of governance, providing the clients rekonfigurirovaniya parameters of the operation and organization of the algorithm, etc.).

The graduate work purpose

The purpose of hardware design implementation kompaknyh genetic algorithms. Rate all the pluses and minuses of hardware implementation of the compact genetic algorithms.

1. BACKGROUND

1.1. Evolutionary theory

Evolutionary theory asserts that each species develops and changes purposefully in order to best adapt to the environment. In the evolution of many species of insects and fish purchased protective coloring, hedgehog became immune through needles, a man came into possession of sophisticated nervous system. We can say that evolution - a process of optimization of all living organisms. Consider what the same nature means does this optimization.

main mechanism of evolution - that natural selection. Its essence is that more attuned beings have more opportunities for survival and reproduction, and thus have more offspring than poorly adapted species. In doing so through the transfer of genetic information (genetic inheritance) descendants inherit from their parents' basic quality. Thus, the descendants of the strengths of individuals will also be relatively well adapted, and their share in the total mass of individuals will increase. Following a change of a few tens or hundreds of generations of average fitness specimens of that species markedly increased.

To make understandable principles of genetic algorithms, also explained how the mechanisms of genetic inheritance in nature. In every cell of every animal contains the entire genetic information of this species. This information is recorded as a set of very long DNA molecules (DezoksiriboNukleinovaya acid). Each molecule of DNA - a chain consisting of four types of nucleotide molecules, referred to A, T, C and G. Actually, the order of the information has nucleotides in DNA. Thus, the genetic code of individuals - it's just a long string of characters, using only 4 letters. In animal cell each DNA molecule is surrounded by shell - such education is called chromosomes.

Each innate quality specimens (eye color, hereditary diseases, hair type, etc.) encoded part of a chromosome, called the genome of the property. For example, eye color gene contains information encoded a certain eye color. Different values of a gene called alleles.

When breeding animals occurs merger of two parental sex cells and their DNA interact, forming a DNA descendants. The main method of interaction - crossover (cross-over, interbreeding). When crossover DNA ancestors are divided into two parts, and then share their halves.

When inheritance possible mutation because of radioactivity or other influences, which may result in some change in sexual cells genes of one parent. Affected genes are transferred father and give it new properties. If these new properties are useful, they are likely to persist in this form - while improving fitness happen tend species.

1.2. The natural selection and genetic inheritance

key role in the evolutionary theory of natural selection plays. Its essence is that the most adapted species survive better and have more offspring than less adapted. Note that in itself is not yet natural selection ensures the development of biological species. Indeed, if we assume that all descendants born roughly the same, the different generations will differ only in size but not on the device. It is therefore very important to examine how the inheritance occurs, ie, as the descendant properties depend on the characteristics of parents.

Basic Law inheritance intuitively understood by everyone - it is that descendants like parents. In particular, the descendants of more adapted parents are likely to be one of the fittest in his generation. To understand the basis of similarity this, we need a little deeper into the structure of animal cells into the world of genes and chromosomes.

in almost every cell of every animal there is a set of chromosomes, bearing information about this animal. The bulk of chromosomes - thread of DNA (deoxyribonucleic acid molecule), which consists of four types of special compounds - nucleotides, going in sequence. Nucleotides marked A, T, C and G, and it is their sequence encodes all the genetic features of the organism. More precisely, DNA determines which chemical reactions will occur in this cell, how it will evolve and what functions to perform.

Gen - this piece of DNA chain, which is responsible for determining the properties of individuals, such as eye color, hair type, skin color, etc. The entire set of human genetic traits coded by approximately 60 thousand genes, the total length of more than 90 million nucleotides.

There are two kinds of cells: sex (such as the spermatozoon and the egg) and somatic. In every human somatic cell contains 46 chromosomes. These 46 chromosomes - in fact, 23 pairs, each pair of chromosomes received from his father, and the second - from the mother. The pair of chromosomes otvechyut for the same signs - for example, the paternal chromosome gene may contain a black eye, and her maternal steam - goluboglazosti gene. There are certain laws that govern the participation of certain genes in the development of species. In particular, in our example will chernoglazym descendant, as the blue eye gene is "weak" (recessive) and suppressed the genome of any other colour.

In sex chromosomes only 23 cells, and they are unpaired. When insemination occurs merger of male and female sex cells and cell embryo is formed, with just 46 chromosomes. What properties descendant receives from his father, and what - from mother? It depends on what sex cells involved in insemination. The fact is that the process of sex cells (the so-called meiosis) in the body accidentally exposed, which the descendants still differ greatly from their parents. In meiosis, in particular, the following occurs: somatic cell chromosomes pair up converging, then their DNA threads torn in several places and random chromosomes exchange parts (Figure 1.2.1).

Animation on the theme «Hardware implementation of the compact genetic algorithms to VHDL». Conditional krossingovera scheme.

Figure 1.2.1. Conditional krossingovera scheme. (Count 6, delay 50 ms, size file 10 kb)

This process ensures the emergence of new versions of chromosomes and is called "krossingover." Each of the newly emerged chromosome will then inside one of the sex cells, and its genetic information can be realized in the descendants of this species.

second important factor influencing heredity, - this mutation, which are expressed in changes in some sections of DNA. Random mutation and can also be caused by various external factors, such as radiation exposure. If a mutation occurred in sex cell, the modified gene can transfer father and manifest in the form of a hereditary disease or in other new properties descendants. It is believed that this mutation are the cause of emergence of new species, and defines krossingover already variability within species (such as genetic differences between humans).

1.3. The objectives of optimizing

As already noted above, evolution - is a process of continuous optimization of biological species. Now we are able to understand how this process occurs. A natural selection ensures that the most adapted species will sufficiently large offspring, but through genetic inheritance, we can be sure that part of the progeny not only maintain high fitness parents, but will have, and some new properties. If these new properties are helpful, then they are most likely move in the next generation. Thus, there is accumulation of useful qualities and gradually increase the adaptability of biological species in general. Knowing how we solve the problem of optimization of species in nature, we now apply a similar method for solving various real problems.

Tasks optimization - the most common and important class of targets for practice. They have to deal with each one of us either in the home, distributing their time between different cases, either at work, seeking maximum speed of the program or a maximum return on the company - depending on the post. Among these challenges is solved by a simple, but there are such exact solution which is practically impossible to find.

Introduce symbols and cite a few classic examples. Typically, the optimization problem we can control multiple parameters (denote their values through x1, x2, ..., xn, but our goal is to maximize (or minimizing) of a function, f (x1, x2, ..., xn) Depending on these parameters. Function f called target function. For example, if you want to maximize goal function "profit company, the parameters will be manageable number of employees, production, advertising costs, the prices of end products, etc. It is important to note That these parameters are bound to each other - particularly in reducing the number of staff likely to fall and output.

course, mathematicians have long engaged in similar tasks and have developed several methods to solve them. If the target function is smooth enough and has only one local maximum (unimodal), the optimal solution can be obtained using gradient descent. The idea of this method is that the optimal solution is produced iterations. Establish random starting point and later in the cycle has shifted this point on small step, the step is made in the direction in which the task function is growing fastest. The disadvantage gradient algorithm are too high requirements to function - in practice unimodal occurs very rarely, and for improper function gradient method often leads to suboptimal response. Similar problems arise with the use of other mathematical methods. In many important tasks parameters can only take certain values, all the remaining points of the task function is not defined. Of course, in this case, there can be no question about its smoothness and requires a fundamentally different approach.

classic example of such a problem, known as a "challenge travelling salesman" (Traveling Salesman Problem, TSP), is formulated as follows: travelling salesman required bypass several cities, visiting each once, and return to the starting point. We need to find the shortest route.

The easiest way to find the best solution - to go all possible settings. You do not need to make any assumptions about the properties of trust functions, and you can simply ask through the table. However, in a way to solve the task of travelling salesman for at least 20 towns need to go about 1019 routes, which is unrealistic for any Computing Centre. Thus, there is a need for a new method of optimization suitable for practice. The next section will show how the mechanisms can be applied to the evolutionary process of our objectives. In fact, we organise an artificial evolution in the world specially built.

1.4. The work of genetic algorithm

Imagine yourself artificial world inhabited myriad creatures (animals), with each specimen - this is a solution to a problem. Let's take a more tailored specimen, the better the appropriate decision (the more value it gives objective function). Then the objective of maximizing objective function is to find a more tailored beings. Of course, we can not settle into our virtual world for all beings as soon as they are too numerous. Instead, it will consider many generations that replace each other. Now, if we can harness natural selection and genetic inheritance, then received Wednesday will obey the laws of evolution. The purpose of this artificial evolution will be to create the best solutions. Obviously, evolution - an endless process by which individuals fitness gradually increased. Forced to stop this process through a long period of time after the start and selecting the fittest specimen in the current generation do not get absolutely accurate, but close to the optimal response. That is the idea of genetic algorithm. Now we proceed to precise definitions and describe the work of genetic algorithm in detail.

To talk about genetic inheritance, you need to give our particular chromosomes. In the genetic algorithm chromosome - is some numerical vector, which is responsible selects a parameter, a set of chromosomes that determines beings solution to a problem. What exactly vectors should be considered in a specific task, the user decides to himself. Each of the entries is called a vector chromosome genome.

simple genetic algorithm randomly generates the initial population. The work of genetic algorithm is an iterative process that continues until not be executed given number of generations, or any other criterion for stopping. In each generation of genetic algorithm is implemented in proportion to the selection of accessories, and krossingover single mutation. First, proportional selection appoints each structure probability Ps (and) the equal treatment of its adaptation to the combined populations of fitness:

(1.4.1)

Then happens selection (replacement) n all specimens for further genetic processing, respectively largest Ps (i).

With such a selection of members of the population with a high fixtures are more likely to be chosen more often than individuals with low device. After selection, n randomly selected specimens are divided into n/2 pair. For each pair with a probability of Ps can be applied krossingover. Accordingly, with a probability of 1-Ps krossingover not happening and unchanged beings moving to phase mutation. If krossingover happens received descendants replace parents and taken over by mutation.

now define the notion of responsible and krossingoveru mutations in the genetic algorithm.

Mutatsiya - this transformation chromosomes, which accidentally alters one or more of its positions (genes). The most common type of mutation - random change only one of the genes of chromosome.

Krossingover (in the literature on genetic algorithms also used the name of crossover or interbreeding) - this operation, in which two chromosomes is generated by one or more new chromosomes. Single krosingover works as follows. First, randomly selected one of the l-1 break points. (Point of the gap - between neighbouring plot bats in a row.) Both parental structure at that point will break into two segments. Then, the relevant segments of different parents together and went two genotype descendants.

For example, suppose a parent consists of 10 zeros and the other - with 10 units. Let out of 9 possible points gap elected point 3. Parents and their descendants are shown below.

Parent 1 0000000000 000 ~ 0000000 -> 111 ~ 0000000 1110000000 descendant 1

Parent 2 1111111111 111 ~ 1111111 -> 000 ~ 1111111 0001111111 descendant 2

Once ends krossingovera stage, performed mutation operators. The line, which applies to the mutation, each bit with a probability Pm changes to the opposite. The population received after the mutation writes atop the old one generation and the cycle ends. Next-generation processed in this manner: selection, krossingover and mutation.

Currently, researchers offer other operators gene selection and mutation krossingovera. Below are the most common.

Elite selection methods guarantee that the selection necessarily be the best or the best surviving members of the population together. The most prevalent procedure for compulsory preservation of only one better beings, if it is not like other through the selection process, krossingovera and mutation. Elitism may be introduced in virtually any standard method of selection.

Dvuhtochechny krossingover krossingover and uniform - a decent alternative to single-operator. In the two-krossingovere selected two points gap, and parental chromosomes exchange segment, located between these points. In krossingovere uniform, every bit the first parent inherits the first descendant with a given probability, otherwise this bit transmitted second father. And vice versa.

Flowchart genetic algorithm is depicted in Fig. 1.4.1. First, generated initial population of individuals (individuals), that is some set of solutions of the problem. Typically, this will be done randomly. Then modeled reproduction within the population. To this end, several pairs of randomly selected individuals, there is interbreeding between chromosomes in each pair, and the new chromosomes are moving in the population of the new generation. In the genetic algorithm remains the basic principle of natural selection - the adaptation of the individual (more than corresponding value target function), the more likely he will take part in breeding. Now modelled mutations - in a few randomly selected special new generation change some genes. Old population partially or entirely destroyed and proceed to the next generation. The population in most of the next generation implementations genetic algorithms contains the same number of individuals, how many primary, but because the selection of fitness in it, on average, above. Now described the selection process, and mutation breeding has been repeated for this population, etc.

Ilustration on the theme «Hardware implementation of the compact genetic algorithms to VHDL». Flowchart genetic algorithm.

Figure 1.4.1. Flowchart genetic algorithm.

1.5. The use of genetic algorithms

Genetic algorithms are applied in different forms to address many scientific and technical problems. Genetic algorithms are used to create other computational structures, such as sorting machines or networks. In machine learning they are used when designing neural networks or management robots. They are also used in modeling development in different subject areas, including biological (ecology, immunology and genetics popular) and social (such as economy and political system) system.

Nonetheless, perhaps the popular use of genetic algorithms optimization multiparameter functions. Most real problems can be formulated as the search for the optimal value, where value - a complex function that depends on certain input parameters. In some cases, need to find those values of the parameters under which achieved the exact value of a function. In other cases, the exact optimum is not needed - a decision can be considered any value, the best for a specified amount. In this case, genetic algorithms - an acceptable method to find "acceptable" values. The strength of genetic algorithm is its ability to manipulate while many parameters, which is used in hundreds of applications, including aircraft design, nastraivanii parameters of the search algorithms and persistent state systems of nonlinear differential equations.

Genetic algorithms are an effective search procedure, which competes with other procedures. The effectiveness of genetic algorithms is heavily dependent on such details as a method of coding solutions, operators nastraivaniya parameters of individual success criteria.

1.6. Advantages and disadvantages of genetic algorithms

advantages of genetic algorithms:

• They do not require any information on the surface of the answer;

• Gaps, existing on the surface of response have little effect on fully effective optimization;

• They stand to falling into the local optima;

• They work well in addressing the problems of large-scale optimization;

• There may be used for a broad class of problems;

• Simple and transparent in the implementation;

• There may be used in problems with the changing environment.

not desirable and problematic use GA:

• Where necessary to find a precise global optimum;

• Execution time high evaluation function;

• It is necessary to find the solution to everything, not one of them;

• configuration is not simple (encoding solutions).

2. METHODS OF MATHEMATICAL SIMULATION

Genetic algorithm consists of three operations: reproduction, interbreeding, mutation.

Reproduction is a process of selecting K * NN lines population G (t) for further genetic operations. The selection is done randomly, with the likelihood of selecting a string S _i ^t proportional to its value:

selection process is repeated K * NN times. The estimated number of copies line S _i ^t in the population G (t +1) equals

Operation reproduction increases the overall value of the follow population by increasing the number of the most valuable lines.

Letin the population G (t) contains n (H, t) lines, satisfying scheme H. Then, as a result of reproduction number of lines that meet the scheme H in the population G (t +1) will be equal to n (H, t +1):

. (1)

using the expression for the average values of the population F _avg (G (t)) and podpopulyatsii F _avg (G _H (t)), you can write a formula (1) in the form of:

. (2)

average value podpopulyatsii corresponding pattern H, can be represented as follows: , where c - some value . Then the formula (2) will view:

Suppose that the value in changing c t does not change, then, starting with t = 0, we get: , Ie in this case the number of schemes (rows population G (t), the relevant scheme) changes in geometric progression. In general we can say that the process of changing the representatives of the scheme as well approximated by an exponential trend.

Thus, as a result of those transactions replacement scheme, for which the average value podpopulyatsii are above average in the population, increase the number of its representatives.

Reproduction operates with strings already present in this population, and will not in itself capable of opening new areas of search. For this purpose, using breeding operation.

Skreschivanie is a process of random exchange values of the relevant elements for arbitrarily formed pairs of strings. To do this, selected at the stage of reproduction line randomly grouped in pairs. Then, each pair with a given probability p _skr subjected to cross. When crossing occurs random selection position separator d (d = 1, 2, ..., l-1, where l - the length of the line). Then the value of the first elements d first line written to the relevant elements of the second, and values the first d elements second line - the first in the relevant elements. As a result, we get two new lines, each of which is a combination of the two parental lines.

Operation crossover creates new lines by some combination of the most valuable elements in the population G (t) lines. The resulting lines can result in superior to the value of parental lines.

Consider some scheme H, which will determine the order o (H) - the number of fixed positions and determining the length of the scheme d (H) - the distance (number of positions) between the first and last fixed positions. Suppose that before the operation crossover line was representative of the scheme S H, i.e. . Assume that the line S ¹ S obtained from the line as a result of crossover. Row S ¹ H will be representative of the scheme, if the position with the splitter does not have the crossover between fixed positions scheme. The likelihood that the position would be a separator between the fixed positions of the scheme, is: .

Uchtem that interbreeding occurs with probability p _c, and that even if the position separator will occur between fixed positions scheme, line S ¹ may be a representative of the scheme H, if the line had received two representatives crossover scheme H. Then the probability p _{s, 1} that line S ¹ is a representative scheme H, given by: .

Believing independence reproduction and breeding operations, to assess the cumulative effect of these operations, ie H number of schemes in the population G (t +1):

Since the opening of new areas in search operations breeding occurs only through peregruppirovaniya available in the population of combinations of characters, then using only this operation, some potentially good area could not be a consideration. To prevent similar situations applies operation mutations.

Mutatsiya is a process of random changes in the values of the line. For this line, resulting in the crossover stage, poelementno reviewed, and each element with a given probability of mutation p _mutah may mutate, that is change the value of any random character permissible for this position. The operation allows mutations to find new combinations of traits that enhance the value of lines population.

Assume that mutation to a string S ¹ was representative of the scheme H, i.e. . Assume that the line S ² obtained from a string S ¹ as a result of mutation. Row S ² H will be representative of the scheme, if none of the elements of line, fixed positions related scheme, has not been tampered with.

Given that the mutation occurs with probability p _mutah, the probability p _s2 that line S ² is a representative scheme H, given by: , where o (H) - the number of fixed positions scheme H.

Believing independence operations of reproduction, mutation breeding and assess the cumulative effect of these operations, ie H number of schemes in the population G (t +1):

. (3)

Because, for small values p _m approximately can be considered , just (3) can be written as:

Thus, schemes, which determines the length and small order, and for which the corresponding podpopulyatsiya average value is in excess of the average value of the population, exponentially increases the number of representatives in subsequent generations.

Obviously, the effectiveness of the operation described crossover greatly depend on how coding lines. This feature is useful for tasks optimization functions on numerical sets. However, if a function is set on an arbitrary set, for example, on the set of combinations of signs of the facility where all the signs on the same preference, the method described above crossover is not quite correct, because the likelihood of conservation values of the groups signs depends on the distance between elements in the group line of code, and this violates the principle of equal preference signs. Therefore, for such tasks breeding operation is anticipated to produce by sharing parts are not lines, but individual elements. In doing so sets a number of positions n _P (n _ON (1, 2,…, l)), which defines the number of lines for which exchange values. The number of positions n _P can be set directly or accidentally determined for each pair of lines. Next to each pair of lines (S ¹, S ²) _i, where i - number of couples randomly selected n _P rooms n _{i, j} (n _{i, j O} (1, 2,…, l); j About 1 ( , 2,…, n _P)). Then for the rows of couples (S ¹, S ²) _i exchange values elements numbered n _{i, j} , Ie each element with the number n _{i, j} S ^{line 1} assigned the value of the element with the number n _{i, j} S ^{line 2} And the element number n _{i, j} S ^{line 2} assigned the value of the element with the number n _{i, j} S ^{line 1}.

Suppose that before the operation crossover line was representative of the scheme S H, i.e. , a string S ¹ S obtained from the line as a result poelementnogo crossover. The probability p ^' _{s, 1} that line S ¹ will be representative of the scheme H, equal to:

where o (H) - the number of fixed positions scheme H.

The combined effect of operations poelementnogo reproduction and breeding, and mutations, that is H number of schemes in the population G (t +1) given by:

Thus, when poelementnom crossover speed increases representatives scheme in subsequent generations depends on the average value of the scheme and the number of fixed positions and does not depend on the distance between them and therefore does not depend on the order of the elements in line.

So, as a result of the above operations receive K * NN new lines, which are either entirely new form population G (t +1) (with K = 1), replacing all lines while the population G (t ), Or form part of the population G (t +1), replacing a K * NN least valuable lines of the previous population.

As can be seen from the description of the algorithm, the law probability distribution functions of the target values determined and adjusted by using a set of (population) Rows containing the best values in the sense of trust functions combination of elements.

3. APPARATNAYA REALIZATION GENNYH ALGORITMOV

3.1. Requirements for the design of genetic algorithms

new direction using genetic algorithms - Building dynamically rekonfiguriruemyh hardware, which is produced evolutionary change architecture system in real time, in accordance with the changing external factors. In implementing such systems, as GA rule acts as an external hardware module or integrated into a single crystal with rekonfiguriruemoy hardware system. When this realization, in addition to the requirements of speed and autonomy, additional requirements were small size Square crystal-occupied algorithm and a small energy consumption. These parameters are relevant not only for autonomous or dynamically rekonfiguriruemyh hardware systems, but also for the entire class of systems where possible GA application.

This can be attributed to growing interest in genetic models algorithms adapted to the hardware itself to the implementation and realization of hardware GA. As an example could be considered work hardware implementation of the compact genetic algorithm and consideration of family compact genetic algorithms for Embedded evolutionary hardware.

3.2. Hardware solutions on the example of a compact genetic algorithm

Work on the hardware implementation of the compact genetic algorithm is considering moving from software realization compact GA Hardware execution on the examples of algorithm to FPGA firm Xilinx. As a result, hardware implemented compact GA performs one of the three generation of bar cycle for the problem one-max. The number of strokes to generate depends on the task optimization. More complex tasks require 3 + e cycles, where e number of cycles used in assessing the value of individual fitness function. In implementing size n population and the length of chromosome set as 256 and 32 respectively and can not be changed in the operation. By Synthesis results for the problem one-max, 15210 equivalent project uses valves, the maximum frequency operation 23,57 M Hz, there was increasing the speed compared with software version in 1000.

This algorithm was also considered by John and Gallagherom refined for use in evolutionary hardware, for example, use an algorithm in the scheme of management, which rekonfiguriruemaya analog neural network changes online, to manage physical processes. The structure of the compact GA were added some genetic operators, such a strategy elitism, operator of mutation and scheme perevyborki better solutions (champion resampling), as well as changes were made in the structure of the algorithm, which enabled to obtain a qualitatively new results when testing algorithms DeDzhonga. The main slope, with hardware implementation of this work has been to reduce power and space required for crystal placement algorithm. The algorithm was implemented using hardware description language VHDL and tested on debugging FPGA motherboards with the family firm Xilinx VirtexII (xc2v 1000) and XC4000 BORG. For wide chromosome in 32 bits and size population to 255 individuals, with the task of one-max, on technical parameters were achieved results comparable to results of a hardware implementation compact GA. In doing so, the algorithm exceeded compact GA on the efficiency and the application.

3.3. Hardware implementation of the compact genetic algorithm

Compact GA, as PBIL, modifies vector probability, but in addition to phase krossingovera here also ignored and phase mutation that allows you to focus all attention on the mechanism breeding, which is based on tournament selection method for animals. In addition, a compact model GA ultimate population and requires less computational resources. The diagram compact gene algorithm is presented below:

Figure 3.3.1 The diagram compact gene algorithm

Policy scheme crossover and mutation are presented in figures 3.3.2, 3.3.3.

Figure 3.3.2. The circuit diagram crossover

Figure 3.3.3. The circuit diagram mutation

CONCLUSION

Bibliography

1. [Louis et al., 1991] Louis, S. J. and Rawlins, J. E., Designer genetic algorithms: genetic algorithms in structure design // ICGA-91, in Proceedings of the Fourth International Conference on Genetic Algorithms, Belew, K..K. and Booker, L.B., Eds., Booker, Morgan Kaufman, San Manteo, CA, 1991, 53.

2. [Rawlins et al., 1993] J.E. Rawlins and S.J. Louis. Syntactic Analysis of Convergence in Genetic Algorithms, Foundations of Genetic Algorithms // 2 ed. by L.D. Whitley, San Mateo, CA: Morgan Kaufmann, pp. 141, 1993.

3. [Sidhu et al., 2000] R. Sidhu, S. Wadhwa, A. Mei and V. K. Prasanna. A Self-Reconfigurable Gate Array Archtecture// Field-Programmable Logic and Applications. The Roadmap to Reconfigurable Computing. 10th International Conference, FPL 2000, Villach, Austria, August 27-30, 2000 Proceedings.

4. [Smit et al., 2002] Gerard J.M. Smit, Paul J.M. Havinga, Lodewijk T. Smit, Paul M. Heysters, Michel A.J. Rosien. Dynamic Reconfiguration in Mobile Systems //Field-Programmable Logic and Applications. 12th International Conference, FPL 2002 Lisbon, Portugal 2002 Proceedings, pp 171-181.

5. [Kajitani et al., 1998] I. Kajitani, T. Hoshino, D. Nishikawa, H. Yokoi, S. Nakaya, T. Yamauchi, T. Inuo, N. Kajihara, M. Iwata, D. Keymeulen, T. Higuchi. A gate-level EHW chip: Implementing GA operations and reconfigurable hardware on a single LSI// Evolvable Systems: From Biology to Hardware, Lecture Notes in Computer Science 1478 (Proc. of ICES1998), pp. 1-12, Springer Verlag, 1998.

6. [Chatchawit et al., 2001] A. Chatchawit and C. Prabhas, A Hardware Implementation of the Compact Genetic Algorithm, in Proceedings of the 2001 IEEE Congress on Evolutionary Computation// Seoul, Korea, May 27-30, 2001, pp.624-629.

7. [Курейчик 2004 и др.] V.М. Kureichik, V.V. Kureichik, L.А. Gladkov. Genetic Algorithm // Rostov-na-Donu, RosIzdat 2004 y. 400 pp.

8. [Blondet et al., 2003] B. Blondet, P. James-Roxby, E. Keller, S. McMillan, P. Sundararajan. A Self-reconfiguring Platform // Field-Programmable Logic and Applications. 13th International Conference, FPL 2003 Proceedings, pp. 565-574.

9. [Higuchi et al., 1993] T. Higuchi et al. Evolvable hardware: A first step towards building a Darwin machine. In Proc. of the 2nd Int. Conference on Simulated Behaviour, pages 417-424. MIT Press, 1993.

10. [Sakanashi et al., 1999] H. Sakanashi, M. Tanaka, M. Iwata, D. Keymeulen, M. Murakawa, I. Kajitani and T. Higuchi. Evolvable Hardware Chips and their Applications// Proc. of the 1999 IEEE Systems, Man, and Cybernetics Conference (SMC'99), pp. V559-V564, 1999.

11. [Scott et al., 2001] Stephen D. Scott, Ashok Samal, Sharad Seth. HGA: A Hardware-Based Genetic Algorithm // Dept. of Computer Science Washington University St. Louis, MO 63130-4899, 7 p. 2001.

12. [Chatchawit et al., 2001] A. Chatchawit and C. Prabhas, A Hardware Implementation of the Compact Genetic Algorithm, in Proceedings of the 2001 IEEE Congress on Evolutionary Computation// Seoul, Korea, May 27-30, 2001, pp.624-629.

13. [Gallagher et al., 2004] John C. Gallagher, Saranyan Vigraham and Gregory Kramer. A Family of Compact Genetic Algorithms for Intrinsic Evolvable Hardware // IEEE Transactions on Evolutionary Computation, vol. 8, No. 2, April, 2004

14. [Zebulum et al., 2002] R.S. Zebulum, M.A. Pacheco, M.M. Vellasco. Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms// USA, CRC Press LLC, 2002

15. [Harik et al., 1999] G. Harik, F. Lobo and D. Goldberg. The Compact genetic Algorithm // IEEE Transactions on Evolutionary Computation, vol. 3, Nov, 1999, pp. 287-309

16. [Brown et al., 1992] Stephen D. Brown, Robert J. Francis, Jonathat Rose, Zvonko G. Vranesic. Field-Programmable Gate Arrays // Kluwer Academic Publishers, USA 1992. 206 s.

17. [DeJong 1975] K.A. DeJong. An analysis of the behavior of a class of genetic adaptive systems // Ph.D. dissertation, Univ. Michigan, Ann Arbor, MI, 1775

18. [Muhlenbein 1998] H. Muhlenbein. The Equation for Response to Selection and its Use for Prediction// Evolutionary Computation, May 1998, pp.303-346.

19. [Takashi et al., 1999] Iwamoto Takashi, Yasuda Mitsuhiro, Shackleford J Barry, Okushi Etsuko. Genetic algorithm machine and its production method, and method for executing a genetic algorithm Patent number: US5970487, Application number: US19970910103 19970813, 1999.

20. [Lection on EC 2007] [Lection on EC

21. [g-u-t.chat.ru] http://g-u-t.chat.ru/ga/oper.htm - Genetic algorithms: basic operations

22. [Струнков, PC Week RE 1999] http://www.neuroproject.ru/gene.htm - What is genetic algorithms Timothy Strunkov, PC Week RE, 19/99

23. [www.victoria.lviv] http://www.victoria.lviv.ua/html/oio - Topic 10. Popular pro genetic algorithms

Note

At this point in time, degree work is under construction. Completion is scheduled in December of 2008.