软硬件协同的遗传算法设计与实现

聂鑫，罗剑

（1.武汉工程大学计算机科学与工程学院，武汉430205；2.武汉晴川学院计算机学院，武汉430205）

0 引言

遗传算法[1]是一种从生物界繁衍进化中学习得到的一种随机搜索算法。这种算法具有很好的鲁棒性，具有天然的内在并行性，并且算法无需丰富的先验知识。目前绝大多数遗传算法均使用纯软件实现，这类软件方式在求解实际问题时由于效率较低，运行时间较长，无法应用于实时性要求较高的场合。考虑到遗传算法中编码基本采用二进制编码，而二进制编码在硬件系统中具有操作快捷，实现简单的特点，不少学者使用纯硬件实现了遗传算法[2]。使用硬件方式[3]实现的遗传算法已经证明了具有更高的运算效率与速度。但是纯硬件的设计一旦实现，硬件结构就不能改变，所以也就只能对一个问题进行求解，缺乏了软件所具有的通用性。

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

1 软硬件协同的系统设计

1.1 硬件划分

综合软硬件各自的优点，采用软硬件协同的工作方式实现的系统[7-8]，将系统中一些底层简单而重复，特别是能够并行化的工作交由硬件完成，将具有通用性、串行的工作交由软件完成，不仅可以是系统的效率得提升，缩短了系统的开发周期，并且使得系统具有可重用性。在软硬件协同中，如何划分软硬件具体工作是一件重要的事。因为这涉及到设计的运行效率以及具体实现的功能。我们对遗传算法软硬件划分确定，硬件部分为总控模块、选择模块、编译模块、杂交模块。软件部分为随机数模块、适应值评价模块。整个系统的设计图为图1所示。

图1 系统设计图

1.2 交互协议

由于在设计平台中，CPU（PowerPC）时钟频率（300MHz）与FPGA提供的时钟频率（100MHz）不一致，并且在CPU上运行的软件程序完成所需要的时钟周期数是不确定性的。由于在本设计中存在许多软件层面与硬件层面的信息交互，为了保证信息交互的同步性，可靠性，必须设计一个通信协议来确保数据的正确性。

图2描述的为硬件端向软件端请求数据的操作。整个操作的流程如下，首先由硬件发出请求（request）信号，该信号为高信号。在软件端收到这个请求信号之后，开始进行正常的工作。此时硬件端为阻塞状态。当软件端处理完成之后，给硬件端发送完成信号（done），该信号电平同样为高。此时软件端进入阻塞状态。至此完成一次握手，这该次握手操作中确保了软件能正确地响应硬件的请求，并且能正确地通知硬件何时完成操作。在硬件端收到电平为高的done信号之后，硬件解除阻塞并且获取从软件发过来的数据，之后再发送低电平的request信号并且进入阻塞状态。此时完成了该协议的第二次握手，这次握手确保了硬件能够正确地获取所需信息并且进行标记信号的重置。在软件获得低电平的request之后，发送低电平的done信号并且解除阻塞。此时软硬件的工作基本完成，为了防止重复响应以及再次争取的响应，必须将交互信号进行重置。重置这些信号就需要该协议的第三次握手来确保双方同时重置。硬件端收到低电平的done信号之后，解除阻塞。至此，一次软硬件的信息交互结束。

图2 通信协议

在本设计中，在杂交模块，变异模块，初始化模块以及总控模块中都是用了该协议来确保软硬件双方信息交互的正确性。

2 软硬件协同的平台实现

2.1 硬件模块

如图3所示，本模块中共有6个状态：

图3 系统运行状态机

●IDLE：空闲状态，系统启动以及复位后则进入该状态。空闲状态由硬件层面的总控模块进行控制处理。模块对系统的所有控制信号进行复位操作。系统在FPGA时钟上升沿时检查是否有外部（如开关、按钮等）电平为高的运行信号（START）。在系统获得高电平启动信号之后开始进行状态的转换（以下模块转换中如无特殊说明，均是高电平有效），否则一直在IDLE状态循环等待处于空闲。系统开始运行之后即转入初始化状态（INIT）。

●INIT：初始化状态。在初始化状态中完成系统中的初始化操作。具体操作为总控模块发送启动信号通知初始化模块开始工作。之后在该状态等待初始化操作的完成。在收到初始化模块的完成信号之后，进入CROSS状态。

●CROSS：杂交状态。在杂交状态中完成系统中的杂交操作。具体操作为总控模块发送启动信号通知杂交选择模块开始工作。之后在该状态等待杂交操作的完成。在收到杂交模块的完成信号之后，进入MUT状态。

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

●VALUE：评估状态。在评估状态中完成本系统中的评估和停机判断工作。具体操作为总控模块发送启动信号通知评价模块开发工作。之后在该状态中等待评价操作完成。直到收到评价模块的完成信号之后，模块根据反馈信号的不同决定下一个状态。当STOP信号为0时，系统转入CROSS状态进行下一代遗传操作。当STOP信号为1时，系统转入STOP状态。

●STOP：停机状态。在停机状态中完成本系统停止过程中的相关操作。具体操作就是模块将算法获得的最优个体及其适应值进行输出操作，即将个体、适应值、运行代数、运行周期从模块的输出端口输出，软件层面获取输出数据之后将其反馈给用户。最后再将整个设备状态转入IDLE状态，并且重置片上内存。

2.2 软件模块

（1）随机数模块

随机数模块由软件端实现。该模块提供了遗传算法流程中初始化模块中个体生成、杂交选择模块的个体选择和杂交点选择、变异选择模块的个体选择和变异点选择。该模块采用Xilinx公司扩展的C语言实现。具体实现表现为一个函数。函数有一个控制参数。函数返回为所需求的随机数值。软硬件交互协议的部分由调用该函数的部分控制实现。函数的内部具体实现为根据控制参数来判断硬件所需的随机数的范围。函数实现为调用C语言中自带的rand（）函数，通过取模操作来选择随机数范围。虽然C语言rand函数实现同样可以使用硬件实现，但是在软件实现的rand函数的随机数种子是根据系统时间获得，而硬件实现的随机数的种子在每次产生随机数时是固定不变的。

（2）适应值评价模块

适应值评价模块由软件端实现。该模块的功能为完成遗传算法整个流程中的适应值评估工作，也就是所需要解决问题的具体描述。该模块采用Xilinx公司扩展的C语言实现。具体实现表现为一个函数。函数的参数为控制参数以及需要进行适应值评价的个体（具体表现为一个50维数组）。函数返回为该个体的适应值。软硬件交互协议的部分由调用该函数的部分控制实现。函数的内部具体实现为针对所求问题对二进制编码形式的个体进行相应的计算。由于软硬件交互时使用的是IP核内置寄存器，寄存器大小为32位。每个个体使用两个寄存器，第一个寄存器32位全部使用，第二个寄存器只使用前18位。所以从寄存器中获得个体计算适应值前，必须对寄存器中的数据进行处理。本设计中使用split函数进行该操作，输入为两个int类型，输入为50维数组。函数通过移位和与操作完成。

3 数值计算应用实例

在科学研究中，数值计算是一类经常遇到的问题，通常这类问题的复杂度较高，使用普通的算法计算时间较长。使用遗传算法解决数值问题可以起到较好的效果。但是软件实现的遗传算法执行效率低下，所以可以使用软硬件协同工作的方式在不改变算法通用性的基础上加快算法的收敛速度。

二进制问题是一类可以有效验证遗传算法功能正确性的基本问题。设计中使用的问题为计算二进制串中“1”的个数。1的个数越多，效果最优。由于初始化个体为随机初始化。所以在初始化个体中0与1的比例接近1:1，必须通过不断的杂交和变异才可以获得最优解。因为个体串长为50，所以最优解为50个1。使用软硬件协同的遗传算法解决该问题只需要改写软件端的适应值函数。无需对硬件进行修改。

二进制问题运行效果见图4所示。

图4 二进制问题运行效果图

从图4中我们可以看出算法可以正确找到最优解，运行的代数为1272，去除用于判断终止条件的500代，算法共运行700多代。整个算法运行时间为4.2秒。

因为遗传算法是一个随机搜索算法，算法的性能受初始化种群的好坏以及杂交变异的随机性影响较大。而以上实验截图均是试验中随机获取的数据，并不能代表设计的性能以及效果。

为了对软硬件协同遗传算法平台的性能进行分析。本设计还利用开发板上PowerPC实现了一种纯软件实现的遗传算法。为了验证本设计的性能，这种实现方式的遗传算法在流程和遗传算子上设计都是和本设计完全一致的。为了避免由于随机数带来的偶然性误差，本实验得到大量数据之后，再对数据平均进行数据统计。其中二进制问题的对比数据如表1所示。

表1 两种不同环境下算法运行效率对比

从表1中我们可以看到，本设计实现的算法和其他方式实现的算法都可以获得最优解，并且收敛速度基本一致。本设计相比软件实现性能却有了10倍的提高。我们可以得出结论，使用软硬件协同方式的遗传算法在保留了软件的可移植性的基础上还可以提升数倍的运行效率。

4 结语

本文介绍了算法平台设计中的软硬件划分的依据、软硬件划分的结果以及设计中模块之间的连接关系。随后对设计中的各个硬件模块的具体实现做了详细的介绍。设计了软硬件之间进行信息交互所需要的协议，最后分别介绍了将硬件化模块整合成整体遗传算法IP核、FPGA开发平台搭建、软件平台搭建、整个系统整合。该方法具有软件的通用性以及硬件的运算高效性，理论上使用到遗传算法的地方均可以使用该方法提高运行效率，尤其适合在实时性要求较高的场合（例如工业控制）应用。