A Fpga-based Hardware Design Of Improved Genetic Algorithm

Genetic Algorithm(GA) is a new subject.Its application began to flourish since the eighties of the twenty's century.It exists natural parallel characteristic.Parallel Genetic Algorithm(PGA) is an important branch of GA and more and more specialists pay attention to it.Aiming at the insufficient of trational parallel genetic algotithm both in premature convergence and long execution time,an improved parallel genetic algorithm was proposed in this paper, and also apply this kind of algorithm on FPGA device,rising the computation speed of PGA from the face of hardware implementation.The main research work and innovative points of this work are as follows:(1) Combining the inherently parallel characteristic of GA and the capability for parallelization of field programmable gate(FPGA) together,an improved parallel GA based on FPGA is proposed.This improved PGA is composed of muti-population,different population evolves independently with this novel PGA.According to apply transfer operator ,It migrates the best individual between different population termly to accelerate all population together evolving and restrain the premature phenomena of the population.(2) According to the characteristic of hardware implementation,choose the binary-coded genetic algorithm approach as a key step of this the design, and also select the proportional selection operator to avoid the gene deletion, which improve the global convergence and computational efficiency,At the same time using two-point crossover operator to tansfer some genes,thus generating a new individual, and finally using mutation operator to adjust the part of individual genes In the whole encoded string value, then make the the individual is more close to the optimal solution from the local point of view, thus increasing the local search ability of genetic algorithms.(3) In accordance with the mind of hardware modularity,setup a reliable and effective module-based GA design method,including the whole hardware architecture,dividing each sub-system into many modules,pipeline operation and so on.(4) Introducing working process of each module explicitly and using hardware description language to program for function implementation.All procedures of design which contain function simulation,synthesis, palce and route,timing simulation and download are worked under the ISE10.1 integrated environment of Xilinx. Finally, verify the correctness of the design.(5) Following the proposed module-based design method, the paper completes the design and implementation of a FPGA-based parallel GA. Aiming at idiographic testing function, the experiment shows that this kind of hardware implementation method,not only has a simple structure ,but also improved the speed of algorithm a lot more than software.It sets a basis for the application of GA on real-time,high-speed occasion.