硬件化演化算法在函数优化上的运用

1 引 言
    演化计算是一种借鉴生物演化和自然遗传选择的思想和原理来求解实际问题的一种极为有效的方法，它的根本思想是Darwin的进化论和Mendel的遗传学说，具有智能性、并行性和鲁棒性等特征。演化计算是一种基于种群的搜索算法，它在搜索的过程中具有将适应值好的个体保存到下一代的特点，再通过选择、交叉和变异等遗传操作来产生更适应环境的后代。演化计算提供了一种求解复杂系统优化问题的通用框架，它不需要事先描述问题的全部特点，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于众多学科，也被广泛应用与求解各种函数优化问题，但是它也具有一个突出的问题，演化速度比较慢，不大适合与实时运用的场合。
    随着微电子技术的迅速发展，大规模集成电路加工技术不断发展，可编程逻辑器件(PLD)问世，它由于具有集成度高、速度快、功耗低、价格低等优点在很多领域都日益发挥着重要的作用。而现场可编程门阵列(FPGA)是近几年加入到用户可编程电路行列的器件，它的设计为器件的选择和内连提供了更大的自由度，它的结构包括由逻辑功能块构成的陈列和连接这些逻辑功能块的可编程内部连线2个部分。FPGA可以由用户的设计而动态地改变其内部的功能结构，其设计周期短、修改、扩充、维护方便，用FPGA实现的系统成本低。升级容易，而且随着电子设计自动化技术(EDA)和VHDL，AHDL等硬件描述语言的不断完善，用户只要进行行为级、功能级的描述，则像AlteraⅡ等开发环境会自动将其生成为对最终硬件进行配置的网表文件，开发设计简单。这些特点为在硬件系统实现演化算法、提高演化算法的速度、扩大演化算法的实时应用提供了可能性。
    本文正是基于以上这些考虑，用A1tera公司的Cy—cloneⅡ型号的FPGA，并用VHDL实现了一种比较先进的演化算法，并用该硬件化演化算法求解函数优化问题。最后的实验结果表明，用这种硬件化的演化算法大大地提高了演化算法的运算速度，为演化算法在实时场合的运用提供可能性。

2 演化算法硬件化构造
    演化算法的硬件化和演化算法的软件实现存在很大的不同，演化算法的软件实现只需考虑软件的功能实现就可以，很多演化算法中的特殊的算子，复杂的算子只要在理论上可行，实现的时候基本上不会存在什么大的问题，但当硬件实现时，问题会变得比较复杂。
2．1 演化算法的软件实现思路
    演化算法的软件实现，是借助某一种高级语言，譬如：VC，Java等来实现演化算法的过程。在实现一个典型的演化算法过程中一般包括以下几个问题：编码、初始种群的生成、适应度评价函数设计和选择、交叉、变异算子的设计。
    软件实现各个部分含义为：
    (1)编码的软件实现：编码是演化算法求解问题的前提，因为演化算法一般不直接处理问题空间中的变量，而只能通过编码将问题空间转化为解空间。目前比较流行的编码技术包括：二进制编码、格雷码编码、实数编码、符号编码、排列编码、二倍体编码、DNA编码、混合编码、二维染色体编码和矩阵编码等。
    由于目前的高级语言基本上都支持所有的数据类型，包括：整型、实数型、字符型等，所以上面的各种数据类型基本上都可以实现。
    (2)初始化种群的软件实现：初始种群的生成也就是随机地产生N个个体组成1个初始种群，该种群代表一些可能解的集合。
    在软件实现时，若选择的编码方式是实数编码．一般都是用一个伪随机数发生器，在高级语言中通常就random()函数生成个体；若选择的编码方式是二进制编码，一般是按照概率生成一个个体中的每个1或是0；若是字符编码的，通常就是转化一下，通常也是将特定的字符替换成某一数字，生成该字母序列个体同样也就转化为生成该数字序列。
    (3)适应度评价函数的软件实现：适应度函数是用来进行个体评价，判断个体适应性能优劣的方法，该数值通常是作为个体选择的依据，对整个算的运行，算法的性能有重要的影响。
    在软件实现时，通常是将该函数设计成一个独立的函数或是子过程，在每个需要重新计算个体适应值的地方只要调用该函数就可以。
    (4)遗传算子的软件实现：遗传算子主要有选择、交叉和变异3大算子。
    选择算子就是按一定概率从群体中选择M对个体，作为双亲用于繁殖后代，产生的新个体加入下一代种群。选择过程体现了自然界适者生存的思想。软件实现时，一般是每次选择时都产生1个随机数，以随机数是否小于某一特定的数作为是否选择的判断条件。
    杂交算子就是对于选中的用于繁殖的每一对个体，将双亲的基因型在某个位置断开，相互交换编码。软件实现时，一般是先按照上面的选择中的方法选择2个个体，对于二进制编码的随机的在个体中选择1个或2个位置，进行交换。对于实数编码，一般是产生2个和惟一的随机数，然后将上面的2个个体按这2个随机数为比例求乘积和。
    变异算子是按一定的概率从种群中选择若干个个体。对于选中的个体，随机选择某一位进行取反操作(二进制编码)或是对个体进行微小的调整，加上或是减去某个数。软件实现时，对于二进制编码，一般先产生一个随机数，判断该随机数与某一个特定的数之间的大小，若小于该数就对个体中某一位或是几位进行取反操作；对于实数编码一般是以概率对个体进行微调。
2．2 硬件结构设计
2．2．1 从软件实现抽象硬件模块
    要实现演化算法的硬件化，必须将演化算法的各个部分都独立的在FPGA板上实现。在具体对演化算法实现模块划分的过程中必须遵循这样一个原则：“功能相近的，操作类似的部分划分在一个模块中”。因此，根据上面对演化算法软件实现的各个部分的分析可以做如下的划分：
    (1)将软件实现中初始化种群单独抽象为硬件实现时的pop_initial模块；
    (2)将软件实现中适应度评价单独抽象为硬件实现时的fitness模块；
    (3)将软件实现中选择操作单独抽象为硬件实现时的choose模块；
    (4)将软件实现中交叉、变异抽象为硬件实现时的crossover_mutation模块；
    (5)为了进行个体的读写还需要2个内存模块，分别保存个体和其适应值；
    (6)为了使这么多模块互相之间相互协作的完成任务还需要一个控制模块control模块，类似与软件实现中的CPU协调控制程序的运行。
2．2．2 硬件系统整体结构图及解释
    (1)硬件系统整体结构图
    硬件系统整体结构图如图1所示。

 (2)系统各模块功能解释如下：
    Control模块该模块好比软件实现的时候的CPU控制着整个系统的协调工作。它的主要功能是产生一些控制信号，控制各个模块的启动、停止，并为各个模块的同步提供协调信号。具体讲：它提供各个模块的时钟信号，同步各个模块；接收来自Randoml模块的2个随机地址，从RAM模块中选择个体和其对应的适应值将其传到Choose模块；接收来自Choose模块和Crossover_mutation模块的状态信号，控制其发出的对其他模块的控制信号；控制多路数据选择器、Initial模块和RAM模块的启动等。
    Initial模块该模块即是初始化模块，它内部主要是由一个随机数模块构成的，用来产生一定数量的随机数序列作为初始种群。
    Fitness模块该模块用来计算个体的适应值。一般根据软件实现中适应值函数的不同，该模块内部主要是由一些加法器、锁存器和乘法器构成(在函数优化中)。
    Choose模块该模块主要实现选择2个个体的功能。当该模块启动，并从存储模块接受2个个体和其适应值后，采用联赛竞争机制选择两者中的1个进入下一模块，如此再选择1次，选择2个要进入交叉变异模块的个体。
    交叉变异模块 该模块在启动后，接收Choose模块传来的2个个体，并按照随机数模块产生的随机数确定交叉点，进行交叉和变异。
    多路数据选择模块 对进入fitness模块的个体进行分时控制。
    Ramdoml模块该模块为选择模块选择个体和适应值提供2个随机的地址。
    Ramdom2模块该模块为交叉变异模块提供交叉和变异的概率。
    Ram模块 主要是用于保存个体和其适应值。具体实现时，我们常用了Altera公司提供的IP core生成2个双端口的ram。
    (3)系统总执行过程：系统通过Control模块中的一个始终上升沿启动，随后启动Intial模块产生初始种群，并对其产生的个体进行计数，在达到规定的种群数量后停止Intial模块，控制模块控制多路数据选择器对Intial模块选通，并让产生的初始个体进入Fitness模块计算适应值，并存入相应的RAM地址中；接着控制模块启动Choose模块，Ramdoml模块随机的产生2个地址，并选择该地址中的个体作为选择的个体，运用联赛选择选择其一，如此选择2次，产生2个用于Crossover_mutation模块的个体，Crossover_mutation模块在Ramdom2模块产生的随机数控制下对2个个体实施交叉变异，产生2个个体，控制模块选通多路数据选择模块对Crossover_mutation模块选通，使产生的新个体通过Fitness模块将个体和适应值存入RAM中相应的位置。接着长运行上述过程一直到产生规定数量的个体，控制模块结束整个系统的运行。
    (4)硬件实现：整个系统用VHDL语言编程实现上述各功能模块，在AlteraⅡ5．O环境下进行仿真。选用Al—tera公司CycloneⅡ型号的FPGA系列进行设计。Ram块用Altera IP cote中的双端口RAM。

3 实 验
    在本部分中，首先对上述提到的各个模块进行独立的仿真，然后再将其运用在一个函数的优化问题上，并与其他同问题软件实现的算法进行比较。
    (1)以下对上述提到的模块进行独立测试时候的仿真图如图2所示：

图2为初始化模块仿真波形图。从图中可以看出，当复位信号reset_initial有效以后，立即对“r1_initial信号”和“r2_initial信号”赋初值，然后在下一个时钟的上升沿(5 ns处)，初始化开始，每次产生2个个体。
    图3为Fitness模块仿真图，适应度模块是个逻辑模块，只要输入的个体发生改变，其输出也就相应改变。图3即为仿真后的波形图，此时输出信号的右侧有值。上述实现的是f(x)=一|x|的求值，这里可以看到：当ina_fitness为“000000001”(实数1)和inb_fitness为 “000000011”(实数3)时候，outa_fitness为“100000001”(实数一1)、outb_fitness为 “100000011”(实数一3)。

图4为Random模块仿真图。图4中左侧的是信号名称，中间是信号的随，右侧是信号的波形图。由图4可以看出，在复位信号reset_radom2未变高之前，输出的2个随机数的值是初始值O；当复位信号有效后，2个输出立即由O转为2个非O的输出。

(2)实验
    下面将上述各个模块合在一起，构成一个完整的系统，对以下函数进行优化，并进行一定的说明。

图6是用基于FPGA的演化算法对上述函数进行优化后得到的最优结果。从上面可以看到，由上述方法得到的最优个体是“11111010”，最差个体是“11111010”。

用VC++设计实现了上面函数的优化过程，同时软件采用的交叉和变异操作与上面提到的方法类似，算法运行参数也相同，并在同一系统环境下实现：赛扬1．7，内存256 MB。软硬件运行结果比较如表1所示。

4 结 语
    本文从演化算法的软件实现到演化算法的硬件化，详细的阐释如何用Altera公司的CycloneⅡ型号的FPGA，并用VHDL实现一种比较先进的演化算法，并用该硬件化演化算法求解一函数优化问题。演化算法的硬件化极大地提高演化算法的运行速度，为演化算法在实时场合的运用提供了一种可能性。