论文部分内容阅读
遗传算法(GA)作为一门新兴学科,从二十世纪八十代开始迅速发展。遗传算法存在自然并行性,而并行遗传算法作为GA的一个重要分支,也得到越来越多专家们的重视。本论文针对传统并行遗传算法容易早熟并且收敛速度慢的问题,提出一种改进的并行遗传算法。并将这种算法应用到FPGA中,从硬件实现的角度提高算法的收敛速度。本论文的主要工作和创新点有以下几个方面:(1)将遗传算法天然的并行性与FPGA (Field Programmable Gate Array)本质上的并行特性结合起来,提出了一种基于FPGA的改进的并行遗传算法。该算法由几个独立的子群体组成,各个子群体并行的、独立的运行改进的并行遗传算法,当进化到满足迁移条件时,通过迁移算子的引用,在子群体之间进行最优个体的迁移,促进群体的共同进化,并抑制群体早熟。(2)采用FPGA进行硬件实现的特点,本论文选取二进制编码的方法作为设计遗传算法的关键步骤,选取比例选择算子来避免基因缺失,提高全局收敛性和计算效率,同时采用双点交叉的交叉算子进行部分基因的变换,从而产生新的个体,最后使用变异算子来调整个体编码串中的部分基因值,从局部的角度出发使个体更加逼近最优解,从而提高了遗传算法的局部搜索能力。(3)依据硬件模块化的思想,建立一个可靠、有效的模块化的改进遗传算法的设计流程,包括整个硬件体系结构、子种群内部的模块划分和流水线操作等步骤。(4)详细介绍各个功能模块的工作过程,利用硬件描述语言编写各个模块的源代码。并在Xilinx公司ISE10.1的集成环境下完成功能仿真、综合、布局布线、时序仿真、下载等一系列步骤,最终验证设计的正确性。(5)按照本论文提出的模块化设计思路完成了一个基于FPGA的改进的并行遗传算法的模块化设计与实现,利用具体的测试函数检验算法性能。实验表明,利用硬件来实现改进的并行遗传算法,不仅结构简单,而且大大提高了算法的运算速度,为算法在实时、高速场合的应用打下基础。