计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (20): 9-13.

• 博士论坛 • 上一篇    下一篇

遗传算法的FPGA硬件实现

周艳聪1,2,顾军华3,董永峰3,刘恩海3   

  1. 1.河北工业大学 电气工程学院,天津 300130
    2.天津商业大学 信息工程学院,天津 300134
    3.河北工业大学 计算机科学与软件学院,天津 300130
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-07-11 发布日期:2011-07-11

Hardware implementation of genetic algorithm based on FPGA

ZHOU Yancong1,2,GU Junhua3,DONG Yongfeng3,LIU Enhai3   

  1. 1.School of Electrical Engineering,Hebei University of Technology,Tianjin 300130,China
    2.School of Information Engineering,Tianjin University of Commerce,Tianjin 300134,China
    3.School of Computer Science and Engineering,Hebei University of Technology,Tianjin 300130,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2011-07-11 Published:2011-07-11

摘要: 针对遗传算法软件实现速度慢、效率低的缺点,提出了便于算法实现的串行和流水线两种硬件实现方案。详细描述了设计方案,选择算子、交叉变异算子结构,种群以及适应度的存储和流水线结构,并在流水线中引入并行机制。利用函数极值和旅行商问题分别对方案的资源耗费、运行速度的有效性进行了验证。实验结果显示,这两种硬件实现方法结构简单,资源耗费少,运算速度和运行效率较软件实现大大提高,运行速度平均提升2~3个数量级,为算法在一些实时性要求较高的场合得到应用提供了良好基础。

关键词: 遗传算法, 现场可编程门阵列, 流水线, 旅行商问题, 全局优化

Abstract: To overcome the shortcoming of low speed and low efficiency of genetic algorithm’s software implementation,two hardware implementation schemes of serial and pipelining realization are put forward.The overall design and structure of genetic operators——selection,crossover and mutation,individual population and fitness memory are given.Other parallel mechanisms are also added to the pipelining structure.The optimal solution of function and classical travel sales problem are used to verify the effect of the schemes on resource consumption and running speed.The experimental results show that the schemes have simple structure,low resource consumption,higher running speed and efficiency than software’s implementation.On average the running speed can be advanced 2 to 3 orders.It sets a good basis for the application of genetic algorithm on real time and high speed system.

Key words: Genetic Algorithm(GA), Field Programmable Fate Arrays(FPGA), pipelining, Travel Sales Problem(TSP), global optimization