基于VRC的自演化系统设计与实现

李增武，姚睿

(南京航空航天大学，江苏 南京 210016)

0 引言

自演化系统能够在演化算法的控制下改变自身结构演化得到目标电路[1-2]。基于FPGA的片上可编程系统(system on a programmable chip，SOPC)设计可以对硬件资源的配置进行反复修改，在保证电路功能不变的情况下改变自身结构，实现自演化[3-5]。演化硬件(evolvable hardware，EHW)是实现自演化系统的硬件载体，VRC(vitual reconfigurable circuit)是一种实现EHW技术的虚拟电路结构。VRC结构是由设定的连线连接起来的一组规则的基本逻辑功能单元[6-8]，基本逻辑功能单元能够根据配置位串实现自身功能的改变，连线也可以根据配置位串进行控制，具有很好的灵活性和通用性。本文使用基于FPGA的SOPC设计方法实现基于VRC的自演化系统，并以演化2位乘法器电路进行了验证。

1 自演化系统的总体结构

自演化系统采用基于FPGA的SOPC设计方法实现，结构如图1所示。

自演化系统包括MicroBlaze软核微处理器、通用异步通信接口UART及自定制的可进化IP核等。MicroBlaze是系统的CPU，负责系统控制和指令的发布。UART负责FPGA和PC机的通信。在演化时系统需要对FPGA的资源进行反复修改，因此需要自定制IP核以满足该要求。

2 遗传算法

本文选取遗传算法(genetic algorithm，GA)作为系统演化算法。EA是理论基础最为完备的演化算法，在演化算法中应用较为广泛。EA基于“适者生存”的原则，在每一次迭代过程中计算种群个体的适应度值，并根据候选个体的适应度值获取该次迭代过程中的最优解。通过竞争选择机制，获取适应度值较高的个体，对这些个体的染色体进行交叉、变异操作，产生新的种群。在迭代过程中，种群的部分个体不断得到改进，越来越靠近系统需要的最优解，类似于大自然中的生物进化过程。在搜索全局最优解过程中能自动积累搜索空间的知识，并自动控制搜索过程以求得最优解[9]。

EA的具体实现过程如下：

1) 初始化种群，编码基因位串，建立算法和目标问题的关联。

2) 配置硬件电路，并计算个体的适应度值。

3) 按照竞争选择机制挑选适应度值较高的个体，根据设定变异率对基因位串进行交叉变异操作。

4) 若满足最大迭代次数或达到最大适应度值，则停止迭代操作，输出最优解，否则，转到2) 。

3 可演化IP核设计

VRC电路的结构如图2所示。图中VRC电路是由规则的基本可配置逻辑单元Cell阵列构成的。Cell作为演化的基本单位，由Slice实现，是执行运算与数据处理的基本单元，可执行与、或、非、同或、异或等操作。每个Cell有2个输入和1个输出。其中第一列Cell为输入级，其输入外接系统功能区的输入；最后一列Cell为输出级，其输出作为系统功能区的输出。其他每个Cell的输入可通过多路器在其前相邻2列Cell的输出中选择，输出可作为其后相邻2列Cell的输入。每个Cell单元的功能配置和输入选择均由其配置寄存器的值决定。VRC电路可以简化染色体编码，具有较好的适用性和可移植性。本文所设计Cell阵列为5×8阵列。每个Cell单元的输入均为16位，由高8位和低8位组成。第一列Cell单元输入的高8位是演化机制开启时的演化输入，低8位是高8位的取反。2、3、4、5列的16位输入的高8位为前一列的输出，低8位由前一列输入的高8位组成。

图2 VRC电路结构图

VRC中的可配置功能单元Cell的内部结构如图3所示。

中医制剂能力建设是中医院专科建设的重要方面，医院从战略角度，加强对制剂的研发、保护、推广使用显得尤为重要。在专科建设中，医院要主动寻求发展方向和突破点，制定有效的绩效激励机制，鼓励临床研究总结临床疗效好的治疗方法，对于医药市场供应缺失品种，有针对性的研发系列疗效好的病种处方，加强中医制剂的深入挖掘和保护，从而增强专科核心竞争力；加强中医制剂的人才队伍建设，创造良好的用人环境和氛围，充分调动临床医生、药学研究人员等开发制剂新品种的积极性，鼓励运用新剂型、新技术促进中药特色疗法的开展。

图3 Cell内部结构图

其核心是一个由4bit RAM构成的LUT查找表，此外还包括2个16选1多路器。其中LUT查找表用于实现逻辑运算功能，2个16选1多路器分别用于为2个输入选择输入信号。Cell单元逻辑功能配置和2个输入的选择均可通过配置寄存器编程配置。

单个Cell的配置共需要16位染色体，其中16选1选择器需要4位，LUT查找表的输出选择需要4位。总的配置位数=3×4=12位。图4所示为单个Cell的染色体分配图，总共12位，存放染色体寄存器中。文中使用的VRC电路包含40个Cell单元，因此一个VRC电路阵列所需的染色体配置位=40×12=480位。

图4 Cell染色体分配图

4 自演化系统的软件设计

1) 染色体的编码方式

染色体是一组配置位串，能够直接下载到FPGA中。EA能够根据配置位串的不同对可演化的电路结构进行实时调整和评估，搜索得到最优解。染色体的编码方式可分为直接编码和间接编码。直接编码是用一组二进制编码表示个体解。间接编码是将电路的配置位串表示成多级，首先把配置位串表示成高层次的表达形式，再根据设定的对应方式翻译成可直接配置到FPGA的位串。直接编码形式易于理解，更为直观，但是如果电路结构较为复杂，一组配置位串可能过长，不利于软件的开发。间接编码把配置位串分为多级编码形式，如果电路结果比较简单，则会把简单问题复杂化。本文使用的VRC电路所需的配置位串位数为480bits ，配置位串不长，因此选择直接编码方式。

2) 适应度计算

电路的适应度值计算通过软件完成。对于每种可能输入，读取硬件电路的输出结果和期望值比较，根据两者匹配的位数，决定个体适应度值fitness增加多少。这样循环操作，即可得到个体解对应的适应度值。

3) 种群初始化及个体解配置

4) 遗传算法种群产生方法

在EA的操作过程中，产生种群的方式有两种，在系统初始，通过随机函数对种群进行初始化，之后的每一代则通过竞争选择、变异的方式产生新的种群。首先采用竞争选择的方式，从父代中随机选择一定数量的个体，数量大小由设定的竞争选择规模来确定，然后选择出适应度值最大的个体，进行变异用于产生下一代种群。一共进行P(种群规模)次该操作，产生新的种群。

在竞争选择过程中，被挑选出的最大适应度值个体需要进行变异操作。变异是根据设定的变异率对个体解位串进行翻转实现的。为了保证变异的公平性，并保持种群发展的稳定性，本文采用均匀随机变异，设定的变异率较小。

5 自演化系统的板级验证及结果分析

下面以演化2位乘法器电路为例对自演化系统进行验证。实验在Xilinx Virtex-6 ML605开发板上进行。

1) 其他参数不变，种群规模N变化

保持变异率M=3/256，竞争选择规模S=20，最大适应度值MAX_FITNESS=64，为了兼顾各种情况，设定最大演化代数MAX_GEN=50 000，种群规模N的变化范围为40～150。一共进行13组实验，每组实验进行20次，最终每组所得时间为20次实验花费时间的平均值。统计N在不同值的情况下，在50 000代内可达到的最大适应度值max_fitness、对应的演化代数Gen和对应的时间t，如表1所示。达到最大适应度值所对应演化代数Gen与种群规模N的关系曲线如图5所示。

表1 M=3/256、S=20，N变化时演化情况统计

图5 找到最优解时演化代数Gen和种群规模N的变化

由表1和图5可知，种群规模N=104时，演化得到最优解的平均演化代数和平均演化时长最小，演化速度最快。由图5可知，演化速度随着N的增大呈现先增大后减小的趋势。种群规模不宜太大也不宜太小，当N<96或者>128时，演化得到最优解的速度明显变慢很多。因此N的最佳取值在96～128。

2) 其他参数不变，竞争选择规模S变化

保持种群规模N=104、变异率M=3/256、其他参数保持不变，竞争选择规模S的变化范围为1～30。共进行10组实验，每组实验进行20次，最终每组所得时间为20次实验花费时间的平均值。统计S在不同值的情况下，在50 000代内可达到的最大适应度值max_fitness、对应的演化代数Gen和对应的时间t，如表2所示。达到最大适应度值所对应演化代数Gen与竞争选择规模S的关系曲线如图6所示。

表2 N=104、S=20，M变化时演化情况统计

图6 找到最优解时演化代数Gen和竞争选择规模S的变化

由表2和图6可知，演化速度随着S的增大逐步加快，当S增大到较强程度后呈现稳定的趋势。由图6可知，演化得到最优解的速度在1～13之间近似成倍增大。但是，S并不是越大越好，当S>13以后，演化得到最优解的速度基本稳定。

6 结语

本文采用基于FPGA的SOPC设计方法设计了基于VRC的自演化系统。给出了自演化嵌入式系统的总体结构，本文中的嵌入式系统是在Virtex ML605开发套件上开发实现的，通过演化 2位乘法器电路验证了自演化系统的有效性。实验结果表明，基于VRC的自演化系统每次演化均可搜索得到目标电路，而且演化速度较快。由于能够添加自定制IP核，因此该设计方法具有很好的灵活性和通用性，具有进一步的研究价值。