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

摘要

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

主权项

一种软硬件协同遗传算法实现系统，其特征在于：基于FPGA平台实现以下各部分，(1)在硬件层面，建立硬件遗传算法IP核，(2)在软件层面建立软件协同系统，用于计算适应值与随机数并向硬件遗传算法IP核提供，(3)建立硬件遗传算法IP核与软件协同系统之间信息交互的协议，使硬件层面与软件层面之间的信息交互达到同步状态；存入存储种群的片上内存，相应适应值也存入存储适应值的片上内存；所述软件协同系统包括以下模块，适应值计算模块，该模块根据实际问题提供相应的适应值函数，通过适应值函数实现个体适应值的计算，该模块的输入为个体，输出为计算得到的适应值；随机数模块，该模块根据硬件需求产生一个随机数，该模块的输入为硬件层面中初始化模块、交叉选择模块或变异选择模块发来的请求信号，输出为一定数量的随机数；所述硬件遗传算法IP核包括以下模块，总控模块，该模块提供各个模块之间调用的控制信号，从而控制整个遗传算法的流程以及数据的流向，协调各个模块在总控模块的控制信号下工作；初始化模块，该模块随机地产生演化所需的初始种群，为遗传算法提供初始种群，包括产生种群大小个二进制编码形式的个体，并且计算相应的适应值，所有个体存入存储种群的片上内存，相应适应值存入存储适应值的片上内存；交叉选择模块，该模块实现精英选择和交叉操作的相结合，即由随机数模块提供的随机数选择两个个体作为父代个体，确定交叉点位置，进行单点交叉操作产生两个新个体，然后根据适应值计算模块提供的适应值，从新个体和父代个体中选择两个适应值最高的个体替换父代并存入存储种群的片上内存，相应适应值也存入存储适应值的片上内存；变异选择模块，该模块实现精英选择和变异操作的相结合，即由随机数模块提供的随机数选择一个个体作为父代个体，确定变异点位置，进行单点变异操作产生一个新个体，然后根据适应值计算模块提供的适应值，从新个体和父代个体中选择一个适应值最高的个体替换父代；评价模块，该模块寻找出新一代种群中具有最优适应值的个体，将具有最优适应值的个体更新到存储种群的片上内存上；并判断是否已达终止条件，若满足终止条件则停止遗传算法；片上内存模块，该模块组织两个片上内存，分别用于存储种群和适应值；个体控制模块，该模块是一个四选一模块，用于判断初始化模块、交叉选择模块、变异选择模块和评价模块中是哪个模块要从存储种群的片上内存中进行个体读取和存储；适应值控制模块，该模块是一个四选一模块，用于判断初始化模块、交叉选择模块、变异选择模块和评价模块中是哪个模块要从存储适应值的片上内存中进行适应值读取和存储；所述初始化模块、交叉选择模块、变异选择模块、评价模块均是通过适应值控制模块与个体控制模块来对片上内存进行访问；所述总控模块由一个状态机构成，状态分别为IDLE、INIT、CROSS、MUT、VALUE和STOP，IDLE表示空闲状态，系统复位后进入该状态；空闲状态由硬件层面的总控模块进行控制处理，系统在时钟上升沿时检查是否有外部运行信号，在系统获得高电平信号之后开始运行，否则一直循环等待，开始运行之后即转入INIT状态；INIT表示初始化状态，完成本系统的初始化工作，初始化工作具体包含了生成种群，评价种群个体的适应值；首先由总控模块发送信号至软件层面，即将寄存器0的INIT标记位置为1；软件层面当检测到INIT标记位为1时，则开始使用随机数模块开始产生种群大小个的随机数，并且将结果送到软件层面的适应值计算模块进行评价计算；待评价结束之后，适应值计算模块将个体及其适应值放在指定位置，然后将寄存器0中的INIT_DONE标记位置为1，即发送完成信号通知总控模块；总控模块在收到完成信号之后，再发送信号通知初始化模块去指定寄存器读取个体与适应值并且将个体与适应值存储在片上内存中，所有个体存入存储种群的片上内存，相应适应值存入存储适应值的片上内存；当初始化模块完成种群大小个个体的初始化工作之后，初始化模块发送初始化结束信号给总控模块进入CROSS状态；CROSS表示交叉状态，完成本系统中的交叉选择操作，具体为总控模块发送信号调用交叉选择模块开始工作。并且在该状态进行等待。待收到交叉选择模块的完成信号之后，进入MUT状态；MUT表示变异状态，完成本系统中的变异选择操作，具体为总控模块发送信号调用变异选择模块开始工作，并且在该状态进行等待，待收到变异选择模块的完成信号之后，进入VALUE状态；VALUE表示评估状态，完成本系统中的评估和停机判断工作，评价模块判断从杂交和变异种获得的新个体中是否有适应值更好的个体，如果当适应值在一段时间内最优个体没有发生变化，就说明找到了最优个体，发送信号通知总控模块停机；STOP表示停止状态，完成本系统停止过程中的相关操作，系统将最优个体及其适应值输出，即将个体与适应值置于指定位置，然后由软件层面读取打印，最后再将整个设备恢复到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状态。