پیاده سازی سخت افزاری الگوریتم ژنتیک جمع و جور نخبه گرا با استفاده از ماشین آلات همراه مولد عدد شبه تصادفی

In this paper the design and implementation of two versions of the compact Genetic Algorithm (cGA), with and without mutation and elitism, and a Cellular Automata-based pseudo-random number generator on a Field Programmable Gate Arrays (FPGAs) are accomplished. The design is made using a Hardware Description Language, called VHDL. Accordingly, the obtained results show that it is viable to have this searching algorithm in hardware to be used in real time applications.

Genetic Algorithms (GAs) are very well known optimization techniques originally proposed in [1]. GA have demonstrated to be successful in the solution of complex numerical and combinatorial optimization problems, for single and multiple objectives [2] simulating natural evolution over populations of candidate solutions. GA handle a set of potential solutions instead of only one, but GA must evaluate the objective function several times, thus one of their main disadvantages is the high computing time required to solve complex problems. Some strategies have been proposed to deal with this drawback; for example, parallel implementations, efficient operators design, and hardware implementations, among others. On the other hand, compact Genetic Algorithms (cGAs), are a kind of probabilistic model-building Genetic Algorithms or Estimation Distribution Algorithms (EDAs) [3]. cGA operates on probability vectors by replacing the variation operators (crossover and mutation) that describes the distribution of a hypothetical population of solutions. It is known that the cGA obtains solutions of the same quality as the simple GA with binary representation and uniform crossover but with the advantage of an important reduction in the memory requirements, i.e. it only needs to store the probability vector (instead of the entire population) [4]. Therefore, the cGA may be useful in memory-constrained applications such as evolvable hardware [5]. Some efforts have been made in order to improve the cGA performance; for example in [6] the authors proposed using elitism, mutation and, champion resampling demonstrating the improvement without increasing the algorithm complexity. In this paper, a novel and efficient design of a cGA in a hardware platform is shown. This design presents the following features: modularity, concurrency, minimal resource consumption, real time execution, and high scalability properties. The main contributions of this work can be summarized as follows: • A very useful guide to other researchers on how using this information to develop their own implementation in the hardware of their choice. • Two pseudo-random numbers generators implemented in hardware and its evaluation in terms of the used resources and the average of iterations required to reach their the solution. Nowadays there exists different computing machines to implement parallelism, nevertheless in this study we are looking for a portable and autonomous evolvable hardware to be used in real-time tasks [7], therefore we select a FPGA to develop our design. Also, it is important to mention that the population sizes in GA are problem-dependent, however in most of the cases they are from hundreds to thousands of individuals. Some exceptions are called “micro Evolutionary Algorithms” which have especially small population sizes, i.e. from 3 to 5, but in most of the cases they need additional mechanism to maintain the diversity. The Genetic Algorithms are inherently parallel mainly due to their population-based nature. Thus, each individual of the population could be executed in a parallel manner. However, the compact Genetic Algorithm (cGA) has not a population, instead it only has a Probability Vector (PV), then, its parallelization is slightly different. In the cGA implementation considered in this work, each PV element is executed in parallel. Specifically, the tasks performed in parallel are the following: • Each PV element compares its value against a random number to generate 2 bits, one for each individual. • Each PV element updates its value. • Each PV element evaluates its value to determine if it has converged. The remaining of this paper is organized as follows: in Section 2 we present the previous related work. In Section 3 the compact Genetic Algorithm is explained. Section 4 presents our hardware design proposal. The experimental results are shown in Section 5, and finally the conclusions and future work are presented in Section 6.

While it is true that any known pseudo-random numbers generator would work, here we found that the MS-PRNG occupies almost all the resources with a relatively small binary chain. Thus, it could be useful only with very small problems. However, if the Cellular Automata-based PRNG (CA-PRNG) is applied, the design utilizes only 3% out of the FPGA resources (see Table 2 and Table 3). For the kind of problems whose objective function can be represented with binary numbers, our design is suitable to be used in real applications. So, if the complexity of the fitness function is bigger, then the designer needs to explore different ways to maintain a good balance between the velocity and the amount of FPGA resources to be used. The previously published cGA hardware implementations [8], [5], [9], [6] and [11] do not present a detailed description of their designs, i.e. they do not show the components structure (I/O ports) or the manner to synchronize them. This work presented is different to the previous ones in the following aspects: • Two random number generators are compared. • There is a detailed description of the used components. Furthermore, the presented design utilizes 6 clock cycles per one iteration for the cGA and EcGA. As a future work we plan to use these algorithms for tuning intelligent controllers, like the fuzzy visual control developed by our research group in [25]. This is a successful case where the implementation of the whole system in hardware gives an excellent performance in real time. However, one of the biggest problems is the fuzzy tuning. Therefore, we want to use our hardware version of the cGA algorithms as a self-tuning tool for these kinds of controllers. Another successful application was presented in [7].