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

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协调控制程序的运行。