一种遗传算法的软硬件协同工作实现方法

摘要

本发明提供了一个遗传算法的软硬件协同工作实现方法。遗传算法是一种典型的演化算法，但是由于二进制编码的特点，利用软件实现的遗传算法求解实际问题的效率较低。硬件FPGA虽然可以提高求解的速度，但是纯硬件实现一旦实现，硬件结构不易改变，缺乏灵活性。本发明针对软件和硬件实现存在不足，提出了遗传算法的软硬件协同设计方法，它不仅可以提升运算速度，而且提高遗传算法IP核的通用性，只需在软件层改写适应值函数，就可实现类似问题的求解。软硬件协同的工作平台与纯软件，纯硬件实现相比，运用软硬件协同方法求解具有较高的效率和广泛的通用性。

说明书

技术领域

本发明涉及智能计算与软硬件协同技术，特别涉及一种使用软硬件协同来处理遗传算法的技术。

背景技术

遗传算法(Genetic Algorithm，GA)是Holland在1975年在《Adaptation in Natural andArtificial System》中首次提出的一种概率搜索算法，遗传算法通过有组织地然而是随机地信息交换来重新结合那些适应性好的串，在每一代中，利用上一代串中适应性好的位和段来生成一个新的串的群体，作为额外添加，偶尔也要在串结构中尝试用新的位和段来替代原来的部分。类似于自然进化，遗传算法通过作用于染色体上的基因，寻找好的染色体来求解问题。由于它不受搜索空间限制性假设条件的约束，不必要求诸如连续性、可微性和单峰性等假设，以及其固有的并行性，因此作为一种稳健、高效的优化算法已被广泛应用于各个领域。

而目前的遗传算法都是由纯硬件或者纯软件实现，由软件实现，算法的运算效率低下。而由纯硬件实现，只能针对某个问题进行求解，做不到通用性。这两种实现方法都有其各自的缺陷，目前急需一种可行的综合性技术方法能够改善上述技术的缺陷。

软硬件协同设计(Hardware/Software Co-designing)的思想是在硬件和软件设计过程中尽最大限度的利用其协同作用来满足系统的要求。自从软硬件协同思想提出以后，一直备受国内外研究者的关注，关于软硬件协同设计领域的研究也十分活跃。到目前为止，国内外学者已经在此方面做过很多研究，比如在遥感影像的实时效应，音频编码算法，Lattice译码算法，数字电路仿真，系统的模拟、仿真和调试等一些方面都使用过软硬件协同设计方法，并且获得比使用传统的设计方法更好的效果。因此利用软硬件协同设计方法不仅可以提高求解问题的效率，同时可以扩宽其应用领域，进一步推动软硬件协同设计的发展等。

发明内容

本发明的目的在于，利用软硬件协同工作的方式提供一种遗传算法的实现方法，使算法的计算性能得到显著的提升，并且增加计算的通用性。

本发明所提供遗传算法的软硬件协同工作实现方法，基于FPGA平台实现以下各部分，

(1)在硬件层面，建立硬件遗传算法IP核，

(2)在软件层面建立软件协同系统，用于计算适应值与随机数并向硬件遗传算法IP核提供，

(3)建立硬件遗传算法IP核与软件协同系统之间信息交互的协议，使硬件层面与软件层面之间的信息交互达到同步状态；

所述软件协同系统包括以下模块，

适应值计算模块，该模块根据实际问题提供相应的适应值函数，通过适应值函数实现个体适应值的计算；

随机数模块，该模块根据硬件需求产生一个随机数；

所述硬件遗传算法IP核包括以下模块，

总控模块，该模块提供各个模块之间调用的控制信号，从而控制整个遗传算法的流程以及数据的流向，协调各个模块在总控模块的控制信号下工作；

初始化模块，该模块随机地产生演化所需的初始种群，为遗传算法提供初始种群；

交叉选择模块，该模块实现精英选择和交叉操作的相结合，即由随机数模块提供的随机数选择两个个体作为父代个体，确定交叉点位置，进行单点交叉操作产生两个新个体，然后根据适应值计算模块提供的适应值，从新个体和父代个体中选择两个适应值最高的个体替换父代；

变异选择模块，该模块实现精英选择和变异操作的相结合，即由随机数模块提供的随机数选择一个个体作为父代个体，确定变异点位置，进行单点变异操作产生一个新个体，然后根据适应值计算模块提供的适应值，从新个体和父代个体中选择一个适应值最高的个体替换父代，；

评价模块，该模块寻找出新一代种群中具有最优适应值的个体，将具有最优适应值的个体更新到存储种群的片上内存上；并判断是否已达终止条件，若满足终止条件则停止遗传算法；

片上内存模块，该模块组织两个片上内存，分别用于存储种群和适应值；

个体控制模块，该模块是一个四选一模块，用于判断初始化模块、交叉选择模块、变异选择模块和评价模块中是哪个模块要从存储种群的片上内存中进行个体读取和存储；

适应值控制模块，该模块是一个四选一模块，用于判断初始化模块、交叉选择模块、变异选择模块和评价模块中是哪个模块要从存储适应值的片上内存中进行适应值读取和存储。

而且，评价模块判断是否已达终止条件时，所述终止条件为最优适应值在100代内不发生变化。

而且，所述新一代种群是经过交叉选择模块进行精英选择和交叉操作，然后经过变异选择模块进行精英选择和变异操作所得结果。

本发明将遗传算法中适合于硬件处理的模块如杂交、变异等使用硬件编程实现，将遗传算法中适应值评价这个通用性模块用软件来处理。它不仅可以提升运算速度，而且提高遗传算法IP核的通用性，只需在软件层改写适应值函数，就可实现类似问题的求解。软硬件协同的工作平台与纯软件或纯硬件实现相比，运用软硬件协同方法求解具有较高的效率和广泛的通用性.

附图说明

图1为本发明的原理图；

图2为本发明实施例的有限状态机图；

图3为本发明实施例的软硬件交互协议示意图。

具体实施方式

下面结合附图与实施例对本发明进行详细描述：

本实施例是在Xilinx公司提供的XC2VP30 FPGA开发板上实现，使用PowerPC(一种精简指令集架构的中央处理器)作为处理器，使用逻辑门电路构成硬件IP核，使用Xilinx BlockMemory Generator作为存储器。FPGA平台有两条总线，PLB(Processor Local Bus，处理器局部总线)和OPB(On-Chip Peripheral Bus，片上外设总线)。OPB总线连接一些低速和低性能设备，它不直接连接到处理器内核，而是通过总线桥与PLB总线上的设备(如PowerPC和片上内存)联系。具体实施时，软件层面的随机数模块和适应值计算模块由本领域技术人员采用软件模块化方案设计后安装到PowerPC中即可；硬件层面的各模块可根据工作原理采用Verilog语言描述，编译成逻辑门电路后作为硬件IP核接入OPB总线即可。在XC2VP30 FPGA开发板上建硬件IP核的时候，FPGA平台提供寄存器以便在工作流程中软硬件直接进行交互时使用。由于片上内存只能硬件访问，实施例设定了24个寄存器，记为寄存器0、2、3...23。

如图1所示，本发明的工作状态是由总控模块来实现各模块之间的调控的。如软件层面的随机数模块和适应值计算模块，硬件层面的初始化模块、交叉选择模块、变异选择模块、评价模块都和总控模块进行着信息的交互。因此总控模块是整个设计的核心部分，就好比计算机内部的CPU，它控制着整个设计的流程以及数据的流向，各模块也都是在总控模块的控制信号下有序地工作。对本IP核的设计而言，整个系统的工作状态都体现在总控模块上。各个子模块通过总控模块的控制信号进行着信息的交互。另外初始化模块、交叉选择模块、变异选择模块、评价模块均是通过适应值控制模块与个体控制模块来对片上内存进行访问。为便于实施起见，下面详细说明实施例中各个模块以供参考：

总控模块：总控模块由一个状态机构成，状态分别为IDLE、INIT、CROSS、MUT、VALUE和STOP。总控模块通过状态机的方式来控制其他模块。例如进入INIT状态则激活初始化模块进行工作，进入CROSS状态则激活交叉选择模块进行工作。

随机数模块：输入为硬件层面中初始化模块、交叉选择模块或变异选择模块发来的请求信号，输出为一定数量的随机数。实施例采用C语言实现，具体为调用C语言的库函数rand，并且对所获得的随机数进行范围处理再输出。

适应值计算模块：输入为个体，输出为计算得到的适应值。采用C语言实现，具体实现为针对所求问题对二进制编码形式的个体进行计算。具体实施时，可以事先根据实际问题在该模块中设置相应的适应值函数，例如实施例为0-1背包问题。

初始化模块：模块完成遗传算法的第一阶段的初始化工作，具体实现为产生种群大小个二进制编码形式的个体，并且计算相应的适应值。本发明实施例中设定种群的大小为32，即包括32个个体，这些个体构成第一代种群。初始化模块将这些个体与对应的适应值保存在片上内存中(所有个体存入存储种群的片上内存，相应适应值存入存储适应值的片上内存)，最后通知总控模块任务完成。

交叉选择模块：交叉选择模块在获得总控模块启动信号之后启动。启动之后首先发出随机数请求信号(本实施例中为将寄存器1中CROSS_RAN位置为1)并开始等待、在软件层面的随机数模块检测到该信号(CROSS_RAN＝1)之后立即使用rand函数产生3个随机数，其中两个用于选择个体作为父代个体，另一个用于获得杂交点。并且将随机数写入指定的寄存器(实施例中为寄存器20)中，当随机数模块完成之后给总控模块返回完成信号(实施例中为将寄存器1中CROSS_RAN_DONE位置为1)。交叉选择模块在获得该高电平信号(CROSS_RAN_DONE＝1)之后继续工作。交叉选择模块再从指定位置(寄存器20)读取随机数，然后通知个体控制模块从存储个体的片上内存进行个体的读取，并且通知适应值控制模块从存储适应值的片上内存读取相应的适应值。交叉选择模块再根据获得的杂交点对两个个体进行杂交。实施例所采用杂交方式为单点杂交，如两个个体分别为0xffff与0x0000，杂交点为8。则杂交获得结果为0x00ff与0xff00。杂交结束之后，将新生成的两个个体依次保存在指定适应值计算内存地址(实施例为寄存器7、8、9、10、11)。然后再将请求适应值计算信号置为1(实施例中为寄存器1中的req_fit位)。适应值计算模块在检测到该高电平信号(req_fit＝1)之后从指定适应值计算内存地址(寄存器7、8、9、10、11)读取个体并且进行相应的计算，然后将结果保存在指定内存地址(实施例中为寄存器12)并且发送完成信号(实施例中为寄存器0的fit_done位置为高)。交叉选择模块获得完成信号(fit_done＝1)之后从保持适应值的指定内存地址(寄存器12)读取到适应值之后，从父代个体(两个)和子代个体(两个)中选择其中两个适应值最高的个体存入存储种群的片上内存，相应适应值也存入存储适应值的片上内存。最后交叉选择模块发送完成信号。

变异选择模块：变异选择模块在获得总控模块启动信号之后启动。启动之后首先发出随机数请求信号(本实施例中为将寄存器1中MUT_RAN位置为1)并开始等待，在软件层面的随机数模块获得该信号(MUT_RAN＝1)之后立即使用rand函数产生2个随机数，其中一个用于选择个体作为父代个体，另一个用于获得变异点，并且将随机数写入指定的寄存器(实施例中为寄存器20)中。当随机数模块完成之后给总控模块返回完成信号(本实施例中为将寄存器1中MUT_RAN_DONE位置为1)。变异选择模块在获得该高电平信号(MUT_RAN_DONE＝1)之后继续工作。变异选择模块再从指定位置(寄存器20)读取随机数，然后通知个体控制模块从存储个体的片上内存进行个体的读取，并且通知适应值控制模块从存储适应值的片上内存读取相应的适应值。交叉选择模块再根据获得的变异点对选择的这个个体进行单点变异。如原始的父代个体为0xff00，变异点为1，则变异得到新个体为0xff01。待变异结束后，将新生成的个体保存在指定适应值计算内存地址(实施例为寄存器7、8、9、10、11)，然后再将请求适应值计算信号置为1(实施例中为寄存器1中的req_fit位)。适应值计算模块在检测到该高电平信号(req_fit＝1)之后从适应值计算内存地址(寄存器7、8、9、10、11)读取个体并且进行相应的计算，然后将结果保存在适应值内存地址(实施例中为第12寄存器)并且发送完成信号(实施例中为第0寄存器的fit_done位置为高)。变异选择模块获得完成信号(fit_done＝1)之后从适应值内存地址(寄存器12)读取到适应值之后，从父代个体(一个)与子代个体(一个)中选择适应值最好的个体存入存储种群的片上内存，相应适应值也存入存储适应值的片上内存。最后变异选择模块发送完成信号。

评价模块：具体操作为比较新一代种群中具有最优适应值的个体与上一代种群中具有最优适应值的个体的适应值大小比较。如前者适应值更大，则将前者替换后者并且将计数器置0。否则就保存不变，并且将计数器加1。实施例中，存储种群的片上内存除存储32个个体外，还单独提供一个专用空间存储具有最优适应值的个体，替换时更新该空间即可。存储适应值的片上内存也单独提供一个专用空间存储相应最优适应值，替换个体时也进行相应更新。当计数器大于预设值(实施例为100)时，说明最优适应值在100代内未发生变化，则通知总控模块停机。具体实施时，可以每进行一次交叉选择、一次变异选择，将结果作为新一代；还可以设定交替运用交叉选择和变异选择得到下一代，例如进行一次交叉选择后结果作为新一代，进行一次变异选择后结果作为下一个新一代，再进行一次交叉选择后结果作为新一代...甚至设计一个函数，由函数决定通过交叉选择还是变异选择得到下一代。实施例设定，进行一次交叉选择，然后进行一次变异选择，再将结果作为新一代，这样可以综合两种进化方式优点。具体实施时，也可以相反，进行一次变异选择，然后进行一次交叉选择，再将结果作为新一代。

个体控制模块：由于实施例中有4个模块需要读取片上内存模块中存储种群的片上内存，该模块为四选一模块。实施例通过使用片上内存模块的4个模块的不同优先级别，来确定哪个模块通过使用片上内存模块获取个体，具体优先级为初始化模块＞交叉选择模块＞变异选择模块＞评价模块；

适应值控制模块：由于实施例中有4个模块需要读取片上内存模块中存储适应值的片上内存，该模块为四选一模块。实施例通过使用片上内存模块的4个模块的不同优先级别，来确定哪个模块使用通过使用片上内存模块获取适应值，具体优先级为初始化模块＞交叉选择模块＞编译模块＞评价模块；

片上内存模块：为了快速的读取个体信息所产生存储种群的的片上内存，具体实现为使用Xilinx公司的Block Memory Generator生成的(种群大小+1)*个体串长(实施例为33*50的双口片上内存。Xilinx Block Memory Generator提供AB两个端口，实施例将A端口用于读取，B端口用于写入。适应值的存储对应于个体，实现方式一致：为了快速的读取适应值信息所产生存储适应值的片上内存，具体实现为使用Xilinx公司的Block Memory Generator生成的(种群大小+1)*适应值大小(实施例为33*32)的双口片上内存。Xilinx Block MemoryGenerator提供AB两个端口，实施例将A端口用于读取，B端口用于写入。除了存储种群的个体和相应适应值外，实施例特别多设置1个个体和相应适应值存储位置，就是为了存放种群中具有最优适应值的个体，以及该个体的适应值。

如图2所示，整个设计分成六个状态。以下系统是指本发明的整个软硬件结合方案。

IDLE：空闲状态，系统复位后进入该状态。空闲状态由硬件层面的总控模块进行控制处理。系统在时钟上升沿时检查是否有外部运行信号(如switch开关)。在系统获得高电平信号之后开始运行，否则一直循环等待。开始运行之后即转入初始化状态(INIT)。

INIT：初始化状态，完成本系统的初始化工作，初始化工作具体包含了生成种群，评价种群个体的适应值。首先由总控模块发送信号至软件层面，即将寄存器0的init标记位置为1。软件层面当检测到init标记位为1时，则开始使用随机数模块(调用rand函数)开始产生种群大小个的随机数，并且将结果送到软件层面的适应值计算模块进行评价计算。待评价结束之后，适应值计算模块将个体及其适应值放在指定位置(实施例中将个体存放在寄存器2、3、4、5、6中，适应值存放在寄存器12中)，然后将寄存器0中的init_done标记位置为1。即发送完成信号通知总控模块。总控模块在收到完成信号之后，再发送信号通知初始化模块去指定寄存器(寄存器2、3、4、5、6、12)读取个体与适应值并且将个体与适应值存储在片上内存中，所有个体存入存储种群的片上内存，相应适应值存入存储适应值的片上内存。当初始化模块完成种群大小个个体的初始化工作之后，初始化模块发送初始化结束信号给总控模块进入CROSS状态。

CROSS：交叉状态，完成本系统中的交叉选择操作。具体为总控模块发送信号调用交叉选择模块开始工作。并且在该状态进行等待。待收到交叉选择模块的完成信号之后，进入MUT状态。

MUT：变异状态，完成本系统中的变异选择操作。具体为总控模块发送信号调用变异选择模块开始工作。并且在该状态进行等待。待收到变异选择模块的完成信号之后，进入VALUE状态。

VALUE：评估状态，完成本系统中的评估和停机判断工作。评价模块用来判断从杂交和变异种获得的新个体中是否有适应值更好的个体。如果当适应值在一段时间内(实施例中本系统为在100次迭代)最优个体没有发生变化，就说明找到了最优个体，发送信号通知总控模块停机。

STOP：停止状态，完成本系统停止过程中的相关操作。主要操作就是系统将最优个体及其适应值输出，即将个体与适应值置于指定位置(实施例中将个体存放在寄存器19、20、21、22、23，适应值存放在寄存器12中)，然后由软件层面读取打印。最后再将整个设备恢复到IDLE状态，片上内存重置。

整个系统的工作流程为：系统复位或者上电后进入IDLE状态，系统在START信号为0的时候则在IDLE状态保持等待。当系统得到START＝1后，转入INIT初始化状态；INIT状态工作未完成时，INIT_DONE一直等于0，并且在保持在INIT状态继续工作。当初始化工作完成后发出INIT_DONE＝1信号，系统转入CROSS状态；在杂交操作未完成之前，CROSS_DONE一直保持为0，并且在保持在CROSS状态继续工作。当交叉操作完成后发出CROSS_DONE＝1信号，系统转入MUT状态；在变异操作未完成之前，MUT_DONE一直保持为0，并且在保持在MUT状态继续工作。当变异操作完成后发出MUT_DONE＝1信号，系统转入EVALUE状态；评价操作完成后进行停止状态判断，如果满足停止条件，则发出STOP＝1信号，系统转入STOP状态，否则发出STOP＝0信号并转入CROSS状态，继续进行循环操作；系统完成STOP状态要做的工作后无条件转入IDLE状态。

关于软硬件通信协议由图3可知：硬件发出Request为高(1)的信号并阻塞等待软件处理完成，软件得到硬件发出Request信号为高后才开始进行相关的软件处理工作，软件处理完成后将处理done置为高(1)并且开始阻塞等待；硬件得到软件发来的信号为高(1)的done信号之后，进行相应的硬件处理，硬件处理完成后再将Request信号置为低(0)并且阻塞等待。软件得到硬件发出信号为低(0)的Request信号后将done信号置低(0)；硬件得到done信号为低(0)说明本次软硬件通信结束，然后硬件便可以进行后续工作。这种操作避免了由于硬件速度较快，导致的在软件信号在完成之后在拉低信号的过程中，硬件再次请求操作所带来的错误数据；或者软件多次响应硬件请求信号等误操作。保证了系统的稳定性和健壮性。

发明实施例选取了0-1背包问题这一典型的组合优化问题分别从三个方面做了对比实验，在实验过程中，三种方式都采用了同样的演化策略，实验结果如下表

从表中数据可以知道该发明运行速度明显优于纯软件运行的速度并且可以获得和软件一样的最优值甚至更好。另外本发明还可以应用于二进制问题，函数优化问题等，充分体现了纯硬件实现所不具备的通用性。

以上所述仅为本发明中的一个实施例，并不用于限制本发明。凡在本发明的精神与原则之内，所做的任何修改，改进等，均应包含在本发明的保护范围之内。