并行遗传算法的FPGA硬件实现研究

Research on the FPGA Hardware Implementation of Parallel Genetic Algorithm

提出基于FPGA的并行遗传算法的硬件实现系统,从硬件实现角度提高遗传算法的收敛速度.硬件系统划分4个子系统,每个子系统同步而单独地运行一个群体大小为M的简单遗传算法,在简单遗传算法每代结束时,总控制器从4个子系统中选取1个最佳个体,然后复制到与其物理相邻的2个子系统中,实现子系统之间的信息交换.每个子系统采用5段流水线处理技术,即将子系统划分为解码操作、适应度计算、预选操作、随机地址比例选择操作以及交叉-变异操作5个单元.为了解决各段速度瓶颈,适应度计算采用4个具有加速模块的Nios处理器,预选操作采用M个取整电路,交叉-变异操作采用1个交叉部件和1个变异部件,解码操作采用2个解码部件的内部并行处理方式.用遗传算法标准测试函数测试该硬件系统,实验数据表明,由FPGA硬件实现的并行遗传算法同由软件实现的遗传算法相比,收敛速度大幅度提高,约2个数量级.

In this paper, propose a implementation technique of parallel genetic algorithms （GAs） based on FPGA device, aiming at raising computation speed of simple genetic algorithm （SGA） from the face of hardware implementation. The hardware system is divided into four sub-systems, on which a simple genetic algorithm with the population being M separately and synchronously runs, when ending of a generation of SGA, the main controller selects the best individual from the four sub-systems, and copy it to the two others physically connecting to the sub-system containing the best individual. Each sub-system is implemented by means of a five-cascade pipeline, i.e., dividing each sub-system into decoding operation, fitness computation, preselecting operation, proportional selection with random address and crossover-mutation operation. In order to escape speed bottle-neck of each cascade, the fitness computation unit is implemented by 4 CPUs named Nios II in FPGA device and equip with a accelerating custom logical circuit, preselection unit by M circuit components functioning as round-up number, crossover-mutation operation unit by a crossover operation component and a mutation operation component, decoding operation unit by 2 Decoders, all of which run concurrently. At last, employ standards test functionⅡof genetic algorithm to test the hardware system, the experiment results show that parallel genetic algorithms implemented by FPGA hardware device runs faster 100 times or so than simple genetic algorithms implemented by software.