Implementation of a genetic algorithm on a virtex-ii pro FPGA

ABSTRACT

This paper presents the implementation of a Genetic Algorithm on a XUPV2P platform with a Virtex-II Pro FPGA. A Genetic Algorithm (GA) is a search technique finding exact or approximate solutions to optimization and search problems. It is a computer simulation approach in which a population of abstract representations of candidate solutions to an optimization problem evolves toward better solutions. The aim is the optimization of a given function, called fitness function, which is evaluated upon the initial population as well as upon the solutions after successive generations. The motivation for implementing GAs in hardware stems from the fact that they are very CPU intensive while they are also intrinsically parallel algorithms and the basic operations of a GA can execute in a pipelining fashion. Our architecture incorporates a Power PC, and built-in hardcore resources like multiplier blocks and BRAMs in order to create an efficient hardware-based genetic algorithm. We have fine tuned the architecture so as to be more parallel, and added complex fitness functions. The design executes on 100 MHz and although complex in logic, it has low silicon requirements as it utilizes 16% slices, 7% BRAMs and 11% multiplier blocks, plus the Power PC of the XC2VP30 FPGA. The result is a functional prototype on which experiments for a range of different genetic parameters can be conducted. We explore the GA's behavior with real-world experiments for different fitness functions and different number of generations. Our design is the first single-chip fully embedded approach that optimizes six fitness functions, which is more than any other proposed solution, while its current implementation supports populations of up to 32 members. The experiments show that our system outperforms in terms of execution time the existing and proposed hardware systems from 23% up to 5895%.

REFERENCES

• 1: Kyrre Glette , Jim Torresen , Moritoshi Yasunaga, Online Evolution for a High-Speed Image Recognition System Implemented On a Virtex-II Pro FPGA, Proceedings of the Second NASA/ESA Conference on Adaptive Hardware and Systems, p.463-470, August 05-08, 2007 [doi>10.1109/AHS.2007.83]
• 2: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 3: G. Koonar, S. Areibi, and M. Moussa. Hardware implementation of genetic algorithms for vlsi cad design. In Computer Applications in Industry and Engineering, pages 197--200. ISCA, November 2002.
• 4: John R. Koza , Forest H. Bennett, III , Jeffrey L. Hutchings , Stephen L. Bade , Martin A. Keane , David Andre, Evolving computer programs using rapidly reconfigurable field-programmable gate arrays and genetic programming, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.209-219, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275141]
• 5: Peter Martin, A Hardware Implementation of a Genetic Programming System Using FPGAs and Handel-C, Genetic Programming and Evolvable Machines, v.2 n.4, p.317-343, December 2001 [doi>10.1023/A:1012942304464]
• 6: Stephen D. Scott , Ashok Samal , Shared Seth, HGA: a hardware-based genetic algorithm, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.53-59, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201319]
• 7: Stephen D. Scott , Ashok Samal , Shared Seth, HGA: a hardware-based genetic algorithm, Proceedings of the 1995 ACM third international symposium on Field-programmable gate arrays, p.53-59, February 12-14, 1995, Monterey, California, United States [doi>10.1145/201310.201319]
• 8: Tatsuhiro Tachibana , Yoshihiro Murata , Naoki Shibata , Keiichi Yasumoto , Minoru Ito, General Architecture for Hardware Implementation of Genetic Algorithm, Proceedings of the 14th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.291-292, April 24-26, 2006 [doi>10.1109/FCCM.2006.43]
• 9: Russell Tessier , Vaughn Betz , David Neto , Thiagaraja Gopalsamy, Power-aware RAM mapping for FPGA embedded memory blocks, Proceedings of the 2006 ACM/SIGDA 14th international symposium on Field programmable gate arrays, February 22-24, 2006, Monterey, California, USA [doi>10.1145/1117201.1117229]
• 10: Y. R. Tsoy. The influence of population size and search time limit on genetic algorithm. In The 7th Korea-Russia International Symposium on Science and Technology, pages 181--187. KORUS, June-July 2003.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles
          Subjects: Algorithms implemented in hardware

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Performance measures; Complexity measures

General Terms:
Algorithms, Design, Performance

Keywords:
fitness functions, fpga, genetic algorithm, multiplier blocks