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

聂 鑫，殷若兰，刘海峰

(1.智能机器人湖北省重点实验室，湖北 武汉 430205；2.武汉工程大学 计算机科学与工程学院，湖北 武汉 430205；3.华为技术有限公司，广东 深圳 518000)

0 引 言

遗传算法是Holland在1975年提出的一种概率搜索算法[1]。遗传算法通过有组织地然而是随机的信息交换来重新结合那些适应性好的串。类似于生物的进化，遗传算法作用于类似于基因的二进制串上，通过寻找好的二进制串来求解问题。在每一代中，算法使用上一代适应值较好的个体通过杂交变异的方式生成一个新的种群。由于它不是直接作用于解空间，所以不受搜索空间的限制，同时也不需要丰富的先验知识，以及其内含的天然并行性。因此遗传算法作为一种有效的优化算法在多个领域得到了应用。

目前遗传算法的应用研究中存在若干问题：算法的执行效率低下、算法收敛速度慢以及算法无法找到最优解(即算法过早收敛)。对于后两个问题，不少学者通过不断的改进算法的因子以及算法的整体结构，或者是将算法与其他新算法进行融合来提高算法的收敛速度。针对算法执行效率低下的问题，现在也有不少学者试图使用硬件化的方式来实现遗传算法[2-4]，或者在大型的工作站中利用遗传算法所具有的天然并行性来解决，这些方法都取得了一定的效果。这些方法在一定程度上也代表了今后遗传算法的发展方向，同时也为遗传算法在更多领域甚至在实际场合种应用创造了条件。

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

国内外在软硬件协同处理遗传算法方面的研究还很少。考虑到纯硬件或者纯软件实现的遗传算法在各自的优点上面可以互补，通过软硬件协同工作的遗传算法同时具有硬件的高效性以及软件的通用性。这种遗传算法部署方便，开发成本低，效率高，功耗小，具有可移植性。为遗传算法在更多领域应用提供了一定的参考价值。

1 遗传算法参数设计

1.1 遗传算法操作

遗传算法通过“适者生存”这种指导思想对种群进行操作。具体就表现为遗传算法不断地通过杂交操作、变异操作以及选择操作使得适应值较坏的个体逐渐被淘汰。最后种群会逐渐地向最优解的方向收敛。下面就对文中采用的遗传算法中的一些基本操作进行介绍[9-11]。

(1)编码操作。

遗传算法不是直接作用于解空间，而是作用于一种编码方式。编码是使用遗传算法时要解决的首要问题，也是设计遗传算法时的关键步骤，因为设计遗传算子是建立在编码基础之上的。不同的编码方式所对应的遗传算子是完全不同的。遗传算法中一般使用位串编码与实数编码两种方式。众所周知在所有生物中，基因决定了一个生物的种类以及生物的形态。而这种基因就好比是一类数据的集合。使用位串编码就可以很好地模拟基因。

考虑到二进制编码在硬件系统中实现方便的特性，在本设计中使用了该编码方式。同时为了确保算法的精度，二进制串的长度i设定为50。

(2)杂交操作。

杂交操作是遗传算法中遗传操作的一部分。同生物界中一样，杂交操作可以在一定程度上保持父代个体所具有的适应值。遗传算法中的杂交操作一般有点式杂交与均匀杂交两种方式。

在本设计中，考虑到所使用的种群大小为128以及方便FPGA的实现，设计使用单点式杂交操作。

(3)变异操作。

变异操作较杂交操作相对简单。在一般的遗传算法中，变异操作是按照一定的概率n发生的。变异操作在整个遗传算法中起到辅助性搜索的作用。当变异概率n过大时，可能就会破坏种群较好的模式。当n过小时，就会使得算法产生新个体能力下降与过早成熟。当变异操作发生时，随机的在基因片段中选取一点或者多点进行编译操作。具体操作就是按位取反。

本设计中由于采用了单点式的杂交方式，并且种群并不是很大，所以这里采用的变异方式为在种群的128个个体中每次选取1个个体进行变异操作。

(4)选择策略。

在遗传算法中，选择策略也起着相当重要的作用。不同的选择策略导致了不同的选择压力。较大的选择压力使得较优的个体能在种群中获得更多的复制数目。使得种群更快收敛。而较小的选择压力则使得种群收敛速度较慢，但使得算法获得全局最优解的概率增大。

比较常见的选择有繁殖池策略、轮盘策略、精英选择策略等。繁殖池策略就是根据个体的适应值计算出其在种群中的相对适应值，根据相对适应值进行复制操作。适应值越高的个体复制的个数越多。然后在复制个体中进行遗传操作。并且使用子代完全替换父代。

在本设计中，使用μ+γ的选择策略：在父代中选择μ个产生γ个子代，然后从μ+γ个个体中选择μ个最优个体替换父代。具体操作是当子代生成进行完评价之后，每次都用子代和父代中的最好个体去替换旧个体，从而增大选择压力，使得种群更快收敛。由于本设计中变异概率较大，从而也在一定程度上缓解了种群陷入局部最优解的状况。

(5)适应值评价。

遗传算法中，适应值是评价种群个体好坏的标准，是遗传算法中收敛的驱动力。在遗传算法中，具有优秀适应值的个体将在种群中获得更多的生存机会。不同的问题有着不同形式的适应值评价函数。但是一般来说适应值评价方式有两种，一种是选取结果的最大值，另外一种则是选取结果的最小值。

在本设计中，使用选取最大值的方式。

(6)算法终止。

遗传算法的终止是通过提前设定的参数来确定的。一般使用遗传算法所解决的问题都是运算复杂度高的类型。可能只知道解的空间范围。一般来说，遗传算法的终止条件有多种。一种是无论算法是否找到最优解，当算法执行N代后则停止。使用此种方法的遗传算法运行时间比较稳定，因为它运行的代数是个确定的数字。数字N的大小在该方法中比较重要。首先，如果N较小，算法可能得不到最优解就停止。另一方面，如果N较大，虽然找到最优解的概率变大，但是如果算法在早期就达到稳定状态，那么就浪费了后续运行的时间。另外一种方法是跟踪每代运行的最优个体，如果该最优个体在N代内不发生变化，算法就会停止。数字N的大小在该方法中同样比较重要，如果N较小，可能算法只是在局部的最优解收敛，并不是全局的最优解。如果N较大，也会造成运行时间的浪费。该方法的好处是至少可以确定获得局部最优解。缺点则是算法的运行时间不确定。

在本设计中，为了保证寻找到局部最优解，采用第二种方法。

1.2 软硬件平台简介

在本设计中，使用Xilinx公司的FPGA作为开发平台。Xilinx公司FGPA芯片主要由6部分组成，即可编程输入输出单元、时钟管理、基本可编程逻辑单元、布线资源、块RAM、底层功能单元和硬核。

Virtex系列是Xilinx的高端产品，这个系列的产品一般性能好，速度快，并且板载更多硬核。Virtex-II Pro系列是在Virtex-II的基础上增强了嵌入式处理功能，内嵌了Power PC 405内核，还包括了先进的主动互联技术，以解决高性能系统所面临的挑战。Virtex-II Pro系列的主要特征如下：

(1)采用了1.5 V核电压，4输入LUT。

(2)420 MHz的始终技术，内置多达12个DCM模块。

(3)支持20多种I/O接口标准。

(4)增加多个3.125 Gb/s速率的Rocket串行收发器。

(5)内置18x18位乘法器模块。

(6)内嵌PowerPC 405硬核处理器。

本设计中使用的Virtex-II Pro系列型号为XC2VP30，因为该型号的FPGA提供了板载CPU，配合Xilinx公司的EDK工具可以很方便地进行软件开发，方便软硬件协同设计的实现。该型号的FGPA的主要性能特征如表1所示。

表1 Virtex-II Pro XC2VP30

2 软硬件协同的系统设计

2.1 硬件划分

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

图1 系统设计图

2.2 交互协议

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

(1)由于PowerPC时钟频率较快，如果软件端的请求只发送一次，而在时序控制的系统中硬件响应事件仅在时钟上升沿或者下降沿的时刻响应信号的变化，这就有可能导致硬件无法获取启动信号。

(2)同样由于PowerPC时钟频率较快，如果一直发送请求，直到硬件返回数据停止，那么就有可能使硬件响应软件多次，出现硬件无法正常工作等错误。

(3)由于FPGA处理数据较快，当硬件完成工作之后，如果在软件未就绪的情况下通知软件，就会出现信号丢失，导致整个系统出错。

(4)由于系统PowerPC时钟频率与FPGA时钟频率不一致，可能会使信号无法采集，从而使某一方面无限等待，导致系统的死机。

基于以上种种可能发生的异常，必须设计一种可靠的协议[13-14]。鉴于以上描述问题与网络通信中出现的问题有一定程度的相似性，并且网络通信中的复杂程度要远大于这里，故考虑借鉴网络通信中的可靠性传输协议，即TCP协议。TCP协议通过3次握手协议确保通信双方数据传输的可靠性。本设计借鉴3次握手的方式，设计通信协议，如图2所示。

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

图2 通信协议

2.3 通信端口设计

为了让软件与硬件能够正常通信，除了协议之外还需要有一个共同的通道。因此需要在FPGA上建立部分寄存器来模拟通信的通道。依据通信协议中所需要的状态信号以及通信数据的需要，共建立10个32位的寄存器。寄存器作用分别描述如下：

(1)寄存器0：该寄存器保存着软件端给硬件端的所有信号。信号依次如下：

Start：启动信号，通知硬件启动，该信号使用寄存器0中的第0位即 reg0[0];

Stop：停止信号，当系统有特殊需要时可能所发出的停机信号，通过该信号通知硬件停机。该信号使用寄存器0中的第1位即 reg0[1];

Cal_done：适应值评价完成信号。通过该信号来告知硬件适应值评价结束，并且已经存放在相应位置。该信号使用寄存器0中的第2位即 reg0[2];

ini_sg_done：初始化完成信号。通过该信号来告知硬件初始化工作完成。该信号使用寄存器0中的第3位即 reg0[3];

rand_done：随机数产生完成信号。通过该信号告知硬件随机数产生完成。该信号使用寄存器0中的第4位即 reg0[4]。

(2)寄存器1：该寄存器保存着硬件端给软件端的所有信号。信号依次如下：

rand_reg：随机数请求信号，该信号使用寄存器1中的第5位即 reg1[5];

cal_req：适应值评估请求信号，该信号使用寄存器1中的第3位即 reg1[3];

ini_reg：初始化请求信号，该信号使用寄存器1中的第1位即 reg1[1];

done：算法运行结束信号，该信号使用寄存器1中的第4位即 reg1[4]。

(3)寄存器2～3保存需要进行适应值计算的个体。

(4)寄存器4～5保存初始化生成的个体。

(5)寄存器6～7保存最优个体。

(6)寄存器8保存软件评价出的适应值结果。

(7)寄存器9保存由软件生成的随机数。

3 软硬件协同的平台实现

3.1 硬件模块

如图1所示，需要实现的硬件模块为总控模块、杂交模块、变异模块、评价选择模块、片上内存模块、片上内存选择读取模块、初始化模块。对平台设计中的硬件化模块进行功能仿真。仿真工具选择使用Xilinx ISE自带仿真器。

使用Xilinx ISE自带仿真器进行仿真之前，必须要建立测试硬件功能的激励文件。ISE提供了两种不同的方式。第一种是基于HDL测试代码，建立一个Verilog Test Fixture类型的文件，将这个文件与待测试文件相关联，然后根据不同的测试目的编写激励代码。这种方法工作量较大，并且修改较复杂。另外一种方式就是基于波形的测试代码，建立一个testbench波形文件，一样也将这个文件与待测模块进行关联。系统会根据模块的输入输出显示一个波形文件，用户可以通过修改这个波形文件的输入信号直观地改写测试的激励文件。最后在系统的Behavioral Simulation 状态中运行Xilinx ISE自带仿真器，就可以显示波形文件。本设计中采用第二种测试方法。

本设计硬件部分的工作流程是由总控模块来控制的。软件层面的随机数模块和适应值计算模块，硬件层面的初始化模块、交叉选择模块、变异选择模块、评价模块都与总控模块进行着信息的交互。因此总控模块是整个设计的核心部分，就好比计算机内部的CPU，控制着整个设计的流程以及数据的流向，各模块也都是在总控模块的控制信号下有序地工作。对本设计硬件部分的设计而言，整个系统的工作状态都体现在总控模块上。各个子模块通过总控模块的控制信号进行信息的交互。

该模块提供各个模块之间调用的控制信号，从而控制整个遗传算法的流程以及数据的流向，协调各个模块有序地工作。总控模块由一个大状态机构成，状态分别为IDLE、INIT、CROSS、MUT、VALUE和STOP。总控模块通过状态机的方式来控制其他模块。状态机如图3所示。

图3 系统运行状态机

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

整个系统的工作流程为：系统复位或者上电后进入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.2 软件模块

(1)随机数模块。

该模块提供了遗传算法流程中初始化模块中个体生成、杂交选择模块的个体选择和杂交点选择、变异选择模块的个体选择和变异点选择。该模块采用Xilinx公司扩展的C语言实现。具体实现表现为一个函数。函数有一个控制参数。函数返回为所需求的随机数值。软硬件交互协议的部分由调用该函数的部分控制实现。函数的内部具体实现为根据控制参数来判断硬件所需的随机数的范围。

(2)适应值评价模块。

该模块的功能为完成遗传算法整个流程中的适应值评估工作，也就是所需要解决问题的具体描述。该模块采用Xilinx公司扩展的C语言实现。具体实现表现为一个函数。函数的参数为控制参数以及需要进行适应值评价的个体(具体表现为一个50维数组)。函数返回为该个体的适应值。软硬件交互协议的部分由调用该函数的部分控制实现。函数的内部具体实现为针对所求问题对二进制编码形式的个体进行相应的计算。

3.3 硬件算法IP核建立

由于设计中所有硬件化模块之间存在种种的外在以及内在联系，本设计中将所有的硬件化模块打包生成一个硬件IP核。IP核的生成使用Xilinx公司的EDK工具提供的IPIF接口。

使用EDK工具的硬件IP核生成向导新建一个IP核，在生成过程中同时选择生成使用该IP核时所需要的寄存器，共10个32位寄存器。使用总控模块作为整个IP核的次顶层模块。在向导提供的顶层模块中将总控模块进行添加，并且将寄存器与总控模块的输入输出端口进行连接。IP核资源使用情况如图4所示。

图4 遗传算法IP核资源使用情况

从图4中可以看到，硬件IP核占用资源较少，占用整个系统资源不到18%。说明硬件部分实现体积较小并且功耗较小。IP核的使用可以极大程度地简化开发者的工作量，并且由于IP核可配置，所以为后续设计提供了可扩展空间。

3.4 FPGA工程平台搭建

使用EDK软件新建工程，在新建工程向导时选择开发板型号以及速度等信息。然后再根据本设计中的具体需求，添加PowerPC、内存、开关等基本设备。然后再往设计中添加新建的遗传算法IP核。并且将IP核的数据通讯绑定在OPB高速总线上。因为本设计中采用了更加直观的视频输出结果，所以还需要在平台中添加视频输出IP核，并加入相应的驱动程序。最后根据开发板用户使用手册将管脚进行绑定。至此硬件开发环境搭建完成。

在平台完成综合布局布线生成可下载文件之后，启动SDK工具进行软件端程序模块的搭建。在SDK工作环境下新建一个C语言环境的工程，将随机数模块、适应值评价模块以及软硬件交互协议软件部分在该工程下整合。系统所需要的内存地址数据由xparameters.h文件提供。在系统停机之后将算法停机之后的结果通过视频输出。最后编译整个工程，并且将程序代码片段及数据片段存放位置指定与片上内存，将程序使用堆栈等其他数据设置内存中存储。将SDK工程产生的ELF文件与硬件平台产生的下载文件使用系统自带工具进行联合，生成新下载文件。使用IMPACT工具将生成的文件下载到开发板中或者使用IMPACT工具新建CF卡启动引导文件完成整个设计。

4 数值计算应用实例

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

4.1 二进制问题中的应用

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

二进制问题运行效果如图5所示。

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

图5 二进制问题运行效果

4.2 背包问题中的应用

0-1背包问题是生活中比较常见的一类问题。该类问题描述为有一体积无限大的背包，但是该背包只能容纳一定重量的货物。如果你有一组货物，每种货物有着不同的重量以及价格，所求问题是如何在这些货物中选取适当的货物(货物个数没有限制)，使这个背包在指定的重量范围内，商品的价值最高。在本设计中，个体二进制串长为50。所以使用的货物总数为50个。在适应值评价时，50个货物与二进制串的二进制位相对应，如果该二进制位为“1”则该货物被选取，为“0”则不选取。最后累加选取货物的重量与价值。首选判断货物总重量，如果总重量大于设定的最大重量，就将适应值设置为-1。否则就将适应值设置为货物的总价值。

设物品的价值为P，重量为S，背包容量为C，分别有：

P={220，208，198，192，180，180，165，162，160，158，155，130，125，122，120，118，115，110，105，101，100，100，98，96，95，90，88，82，80，77，75，73，70，69，66，65，63，60，58，56，50，30，20，15，8，5，3，1，1}

S={80，82，85，70，72，70，66，50，55，25，50，55，40，48，50，32，22，60，30，32，40，48，50，32，22，60，30，32，40，38，35，32，25，28，30，22，50，30，45，30，60，50，20，65，20，25，30，10，20，25，15，10，10，4，4，2，1}

C=1 000

使用软硬件协同的遗传算法解决该问题同样只需要改写软件端的适应值函数，无需对硬件进行修改。本问题经过优化的遗传算法所能获得的最优值为3 103。而使用普通遗传算法(即本设计所采用的遗传算子)所能获得的最优解为3 031。

背包问题运行效果如图6所示。

图6 0-1背包问题运行效果

从图6中可以看出，算法获得的最优解为2 906，基本接近解3 031，运行的代数为1 722，去除用于判断终止条件的500代，算法共运行1 000多代。整个算法运行时间为11秒。

4.3 实验分析

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

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

表2 二进制问题算法运行效率对比

0-1背包问题的对比数据如表3所示。

表3 0-1背包问题算法运行效率对比

从表2中可以看到，本设计实现的算法和其他方式实现的算法都可以获得最优解，并且收敛速度基本一致。本设计相比软件实现性能却有了10倍的提高。从表3中同样可以看到，本设计实现的算法在处理0-1背包问题时同样和其他方式实现的算法可以获得近似的最优解，并且在收敛代数上也相差不多。同样可以发现，在实验二中，本设计和软件实现的遗传算法运行时间减少将近一半，已经有了近100%的提高。因此可以得出结论，使用软硬件协同方式的遗传算法在保留软件可移植性的基础上还可以大幅提升运行效率。

5 结束语

文中介绍了算法平台设计中的软硬件划分的依据、软硬件划分的结果以及设计中模块之间的连接关系。随后对设计中的各个硬件模块的具体实现做了详细的介绍。设计了软硬件之间进行信息交互所需要的协议。最后分别介绍了将硬件化模块整合成整体遗传算法IP核、FPGA开发平台搭建、软件平台搭建、整个系统整合。

该方法具有软件的通用性以及硬件的运算高效性，并且通过使用IP核节约了开发成本以及开发时间。理论上使用到遗传算法的地方均可以使用该方法提高运行效率，尤其适合在实时性要求较高的场合(例如工业控制)应用。