ES2278516A1 - Digital circuit for implementing genetic algorithm, comprises circuit generation algorithm and genetic circuit evaluator, where circuit generation includes random number generator, logic function, two multiplexers and recorder - Google Patents

Abstract

Digital circuit that implements a genetic algorithm for the configuration of general purpose circuits. Digital circuit that implements a genetic algorithm for configuring general-purpose circuits, providing a new configuration in each unit of time and estimating the degree of adaptation of said circuit, and comprising a genetic algorithm generation circuit and an evaluation circuit, characterized in that said genetic algorithm generation circuit comprises at least one random number generator, an XOR logic function, a first multiplexer, a register and a second multiplexer, and said evaluation circuit comprises at least one estimation circuit adapter, a multiplexer, a register and a comparator.

Description

Digital circuit that implements an algorithm Genetic for configuration of purpose circuits general.

The present invention relates to a circuit digital that implements a genetic algorithm for configuration of general purpose circuits. Said invention is optimized. for real time applications.

Background of the invention

John Holland described the idea of using the genetics as a model to solve computer problems, in its 1975 monograph entitled "Adaptation in natural and Artificial Systems ", in Spanish" Adaptation in natural systems and artificial. "

Holland suggested that starting from several gene sets (chromosomes) chosen randomly and from of a methodology to determine if a chromosome is better than another, an optimal solution can be obtained from mechanisms of crossing, mutation and selection of the genes of those chromosomes.

Programming using genetic algorithms It is therefore based on natural selection processes where the genetic code of each new generation of individuals possesses certain mutated genes that make the new individual not identical to previous. Only those that best adapt to the environment will be the that are selected for the next generation.

Genetic algorithms provide an effective method to converge towards solutions in a large universe of possible values. The advantage they provide over any other optimization mechanism is that they can be applied to any type of system or valuation metric without changing the procedures of the
algorithm.

The genetic algorithms are widely applied in evolutionary computing, which is a fast field growth within artificial intelligence. Characterized for being superior to sequential trial and error algorithms when it comes to computing time, hence the interest in use genetic algorithms in system programming that They operate in real time.

Most genetic architectures that are know use the software for genetic network programming neuronal or other systems (as in Schemmel's article J, et al. "A VLSI Implementation of an Analog Neural Network suited for Genetic Algorithms ", 4 ^ th International Conference on Evolvable Systems ICES'01). These systems of application of Software-based algorithms present the great disadvantage of their slowness, as well as the lack of reliability due to the fact of being a sequential process So, a program compiled into a processor that sequentially executes the present instructions in a memory it is likely to fail radically if any bit of its memory changes its value in an unwanted way (known processes as SEU or Single Event Upset). These SEUs may be due to the exposure of the circuit to the surrounding radiation and are a problem growing in space applications, electronic devices to commercial flight board or even manufactured devices using current technologies (with typical lengths shorter than the hundred nanometers) even when they are operating at the level of sea. Another drawback of systems that use software to the genetic programming of neural networks is that they lose part of the redundancy and fault tolerance characteristics of the parallel computation of the network that they have to configure when they depend of a sequential learning process.

There are also several proposals for implementation of genetic algorithms in hardware with the intention to accelerate the processing speed of said devices. In the US5970487 by J. Barry Shackleford et al. "Genetic Algorithm Machine and its Production Method, and Method for Executing a Genetic Algorithm "an implementation is presented hardware at the logic gate level with all its own functions of a genetic algorithm (creation, memorization, selection, crossing, mutation, gene evaluation). In WO02071209 patent of Peter Martin "Evolutionary Programming of Configurable Logic Devices "presents the implementation of a genetic algorithm in a hardware description language (Handel-C) which is then compiled into an FPGA (Field Programmable Gate Array). Nevertheless, the above-mentioned hardware implementations do not They are optimized for real-time applications.

Description of the invention

With the digital circuit of the invention, They manage to solve the aforementioned problems.

The digital circuit of the invention is of the type that implements a genetic algorithm for configuring general purpose circuits (CPG), which provides a new configuration in each unit of time and estimates the degree of adaptation of said circuit, and comprises a circuit of Generation of genetic algorithms (CGAG) and an evaluation circuit (CE). It is characterized in that said CGAG comprises at least one random number generator (GNA), an XOR logic function, a first multiplexer, a register and a second multiplexer and because said CE comprises at least one adaptation estimation circuit (CEA), a multiplexer, a register and a
comparator

The advantage of this invention (with respect to hardware implementations mentioned above) is the largest speed of execution when implementing a genetic algorithm simplified. Said digital circuit is optimized for only one configuration (or chromosome) which is mutated, fit (or adaptation) and is compared to the best configuration achieved up to the moment.

When using only one individual, the crossover processes, selection or use of a memory for the storage of all individuals (a typical population can around one hundred individuals) as in US5970487 already mentioned. In this way the hardware used is minimized, avoids the need to use RAM with which the execution of the algorithm is faster and much less sensitive to environments of radiation like those already mentioned (thus minimizing the impact of SEU). A solution designed to take full advantage is presented the high speed and reliability properties derived from parallelism present in neural networks or automatons cell phones, which are possible examples of applications for said invention. It is therefore an optimized solution for applications that need to work in real time.

The global operation of the digital circuit is the next: The configuration of the CPG is changed by one equal to the best obtained so far except in some values randomly selected by a GNA.

The behavior of the new generation is evaluated in the EC evaluation circuit comparing the new behavior with the expected. When the EC finds that the new configuration is better, then the setting value is stored in a register and the CGAG genetic algorithm generation circuit stores the new configuration in substitution of the previous one.

The architecture can be programmed to work in the operating mode (with a fixed configuration) or in the learning mode (using mutations of the best selected settings every certain unit of time).

The proposed architecture can be used to the programming of neural networks, cellular automatons, FPGAs or even of microprocessors. Neural networks and automata cell phones consist of a set of interconnected elements in where each element performs a simple operation, but what positions to work in cooperation perform complex functions such as pattern recognition, real-time image processing, identification of time series, etc. In principle there is no established methodology for programming such networks (no the same goes for processors that do have a methodology well established). A feasible option is the application of Genetic algorithms to network configuration. The architecture proposal can also be applied to change the program stored in the memory of a microprocessor.

Preferably the digital circuit of the The present invention is characterized in that the CE comparator imply any type of inequality of the type f (A)> g (B), where A is the adjustment value of the new setting, B is the setting value of the setting better, while f and g are any two functions.

Choosing appropriate functions when comparing setting values of the settings can reduce the probability of falling to local lows, that is to say reduce the likelihood of ending up in solutions far from the optimal solution (or global minimum).

Brief description of the drawings

For greater understanding of how much has been exposed some drawings are accompanied in which, schematically and only to non-limiting example title, a case study of realization.

In these drawings:

Figure 1 is a state diagram of the proposed digital circuit;

Figure 2 is a schematic of the digital circuit proposed;

Figure 3 is a block diagram of the proposed digital circuit;

Figures 4 and 5 correspond to a function example, where the whole set of configurations that can be used in the CPG and its corresponding values of adjustment.

Description of a preferred embodiment

As shown in figure 2, the circuit digital 6 that implements the genetic algorithm consists of two basic blocks, the genetic algorithm generation circuit (CGAG) 9 and the evaluation circuit (CE) 10.

As shown in Figure 3, CGAG 9 generates a new configuration (or chromosome) starting from the best found so far (binary number stored in the output of record 14). Using a random number generator 11 that it can be a "Linear Feedback Shift Register" (LFSR) or a chaotic circuit, performs a logical function 12 (which can be the XOR function) with the best configuration obtained so far. The result is a new configuration (binary block output XOR 12) which is the same as the previous one except in those cases in which GNA 11 provides a high voltage value (in the case that 12 be an XOR block). The new configuration (mutated chromosome) is applied to CPG 7 when control signal 20 of multiplexer 15 It has a high voltage value (selection of learning mode).

A diagram of states is shown in Figure 1 learning mode to clarify the sequence of functions executed. The last best chromosome stored in memory 1 is randomly mutated 2 and its setting evaluated 3, the value is compared of adjustment of the mutated chromosome with the last adjustment value better chromosome 4 and finally the chromosome is selected with greater setting value 5.

When signal 20 is a low voltage (mode operation) the best configuration found until the moment (and that is stored in the output of register 14) is loaded to CPG 7. At the moment when the evaluation circuit 10 find that the new configuration is better than the previous one, the mutated chromosome overwrites the previous value of better configuration. This is done by a multiplexer 13 that is controlled by CE 10. Global clock 31 controls the time during which each New configuration is evaluated.

EC 10 assesses the level of adaptation experienced by the CPG 7. A circuit for estimating the adaptation (CEA) 16 compares the behavior of CPG 7 with the expected (to be chosen by the designer). The result of this evaluation is compared with the adjustment value obtained from the best configuration achieved so far and that is stored in registration 18. When the new configuration is better, the output from comparator 19 indicates to multiplexers 13 and 17 that they have to change the old values for better configuration and better fit For the new values. At the end of the configuration time (controlled by clock 31) the values provided on departure of the multiplexers are stored in registers 14 and 18.

In genetic algorithms a sexual reproduction (crossing of two chromosomes chosen from one population) to try to avoid falling into local minimums, that is, non-optimal solutions to the problem in question. The invention presented does not use chromosome crossing with the idea of simplifying algorithm implementation, so the probability of falling in local minima it should be greater than in the algorithms where use the crossover (since a population of chromosomes is not used diverse and located in different points of the search space). To solve this problem, a type of comparison in (19) quite flexible of the type f (A)> g (B), where A is the adjustment value of the new setting, B is the setting value of the setting better, while f and g are any two functions.

A proposal is described in Figures 4 and 5 concrete comparison function where 22 represents all the set of configurations that can be used in the CPG and 21 represents their corresponding adjustment values. If you are in a local minimum 23 and the current setting B does not change until the setting value of the new configuration A is better than the value of adjustment of B, then the probability of jump 28 (thanks to the mutation) from the local minimum to the global minimum 24 is small (since mutations always occur from a single setting). On the other hand, if a certain worsening is tolerated in the adjustment value B, that is, an inequality of the type A> B-X (where X 27 designates the degree of tolerance), then the jump probability 29 from the minimum local to global increase (since mutations occur from of several configurations and the cone of attraction of the global minimum is older).

Claims (5)

1. Digital circuit (6) that implements a genetic algorithm to configure general purpose circuits (7), which provides a new configuration in each unit of time and estimate the degree of adaptation of said circuit (7), and that it comprises a circuit for generating genetic algorithms (9) and a evaluation circuit (10); characterized in that said genetic algorithm generation circuit (9) comprises at least one random number generator (11), an XOR logic function (12), a first multiplexer (13), a register (14) and a second multiplexer (15); and said evaluation circuit (10) comprises the minus an adaptation estimation circuit (16), a multiplexer (17), a record (18) and a comparator (19). 2. Digital circuit (6) according to claim 1, characterized in that the random number generator (11) is a "Linear Feedback Shift Register". 3. Digital circuit (6) according to claim 1, characterized in that the random number generator (11) is a chaotic circuit. 4. Digital circuit (6) according to claims 1, 2 or 3, characterized in that the output of the random number generator (11) and the best configuration are combined with any type of logic circuit in order to obtain a mutation of the initial configuration. 5. Digital circuit (6) according to claims 1, 2, 3 or 4, characterized in that the comparator (19) of the evaluation circuit (10) implies any type of inequality of the type f (A)> g ( B), where A is the adjustment value of the new configuration, B is the adjustment value of the best configuration, while f and g are any two functions.