摘  要： 在自适应遗传算法的基础上，提出了一种基于模板匹配的测量固态流体速度的方法。基于基本遗传算法的模板匹配快速、简单且鲁棒性好[6]，但准确度不够，因此采用改进的自适应遗传算法。实验证明，基于自适应遗传算法的模板匹配高效准确，能够满足所采取的嵌入式实验平台关于实时性、准确性的基本要求。
关键词：自适应遗传算法；模板匹配；嵌入式

    遗传算法是模仿自然界生物进化机制发展起来的随机全局搜索和优化方法，它借鉴了达尔文的进化论和孟德斯鸠的遗传学说,具有简单、快速及鲁棒性好等特点,在函数优化、组合优化、生产调度、自动控制、机器人学、图像处理和遗传编程等领域得到广泛应用[1]。本文利用它在图像匹配方面的应用，来实现已知时间差之间固态流体图像中的图像模板匹配，从而实现对固态流体的测速。针对简单遗传算法容易产生“早熟”现象、局部寻优能力较差和收敛速度慢等缺点，本文将自适应遗传算法引入模板匹配其中，从而实现快速准确的模板匹配,满足了固态流体流速检测关于实时性准确性的要求。
1自适应遗传算法的原理和流程
1.1基本遗传算法
    基本遗传算法的原理和步骤如下。先将解空间中的解数据通过编码(encode)操作，完成表现型到基因型的映射。然后以随机的方式产生一个初始化群体（population），对其中的个体进行适应度的评价检测，再经过选择（selection）、交叉（crossover）和变异（mutation）操作产生下一代的群体。对新一代群体重复上述适应度评价、选择、交叉和变异操作，直到达到预先设定的进化代数[2]。在最后一代中选出最大适应度的个体，对其进行解码（decode）之后得到最优解。
    基本遗传算法存在以下不足：在基本遗传算法(SGA)参数中， 交叉率(PC)和变异率(Pm)直接影响算法的收敛速度。交叉率的大小决定新个体产生速度的快慢,交叉率越大,旧个体的模式越容易被破坏,新个体产生的速度就越快。过高的交叉率可能使较优良的个体的模式遭到破坏,过小的交叉率又会延缓新个体的产生,导致算法早熟,停滞不前。变异率是决定算法跳出局部最优解的一个关键因素,变异率过小，不易生成新的模式结构;而变异率过大，会使SGA成为纯粹的随机搜索算法。基本遗传算法采用固定的交叉率和变异率，不能使适应度高的个体有较小的PC和Pm以保留其优良基因，也不能使低劣个体(适应度低的个体)有较小的PC和Pm以加快其进化速度。SGA的这一缺陷导致在处理优化问题时收敛速度慢，也容易产生“早熟”现象,陷入局部最优解[2]。


2 自适应遗传算法在模板匹配中的实现
2.1 编码
    如果是一幅N×M的图像，模板的大小为K×K，那么可以将模板中心像素点在匹配图中的坐标位置(i,j)作为编码的原始数据，可以采取22 bit二进制编码，把解空间的数据表示成一个个的二进制串。由于像素点在内存中的存储位置是从左到右从下到上，本文把N×M图像的最左下角点编码为二进制22 bit全0，最右上角点编码为二进制22 bit全1。
2.2 初始化群体
    随机产生N个初始化串结构数据，每个串结构数据称为一个个体，组成最原始的群体，以便后面迭代使用。本文采取30个初始个体，进化代数为100代。

2.4 选择
    采用经典的轮盘赌的选择方法，每个个体进入下一代的概率等于它的适应度值和整个群体中每个个体适应度值和的比例。也就是说适应度越高，被选中的可能性越大，进入下一代的可能性就越大[1]。
2.5 PC和Pm的调整
    如式(1)和式(2)所示，分别设置k1、k2、k3、k4为0.3、0.25、0.02、0.01。
2.6 交叉
    交叉是指对群体中随机两两配对的个体进行部分基因交换的过程，本文采用单点交叉的方式，对交叉个体交叉点后面的二进制位进行互换。例如：两个个体的基因二进制码分别为0000101011100000100011和0000001111000001001100，交叉点位置为5，交叉之后就会变成0000101111100000001100和0000001011100001100
011[5]。
2.7 变异
    变异是以较小的概率对个体编码串中的某些位进行变换，具体到二进制编码中就是将“1”变成“0”或是将“0”变成“1”。变异的概率由Pm决定，不宜取太高。
2.8 解码
     当满足迭代次数之后，在最后一代的群体中选取适应度最高的解即为最优解，将其二进制码进行解码之后就得到模板的位置了。
3 固态流体测速的实现
    本文的最终目标是为了测量图2中矿料的流速。

    从图3可以看出，这是一个连续匹配的过程，其中有两个问题必须注意：一是模板位置的选择，显然必须选接近矿料槽的中间位置，这样矿料比较稳定，不易向两边垮散；二是两幅图像间截取的时间延时，延时时间大小为两幅图像获取时间的间隔减去之间算法消耗的时间, 因此时间不宜过短，过短算法完不成，但也不能太长，太长匹配区域很有可能变形。经过多次实验，在算法中选择的匹配区域为(150，90)、(180，90)、(150，120)和(180，120)4个点组成的四边形, 原始图像大小为320×240，延长时间为0.06 s。
4 试验结果
    本文在VC++6.0软件环境下进行试验，首先对普通全局搜索模板进行匹配、简单遗传算法模板匹配以及自适应遗传算法模板匹配进行了比较,对同一匹配点使用三种方法分别试验50次，结果如表1所示。

    本文以自适应遗传算法的模板匹配为理论基础，提出了一种对固态流体的测速方法。该方法高效准确，能够满足实际需要。当然，本文提出的方法还有很多方面的不足，比如自适应遗传算法的改进，以及具体实施过程中的防抖、光线等问题，有待进一步改进。
参考文献
[1] 王小平，曹立明．遗传算法——理论应用于软件实现[M]．西安：西安交通大学出版社，2002．
[2] 英杰，张善文． Matlab遗传算法工具箱及应用[M]．西安：西安电子科技大学出版社，2005．
[3] 郑军，诸静．基于自适应的遗传算法的图像匹配[J]．浙江大学学报，2003，37(6)：689-692．
[4] 巨永锋， 蔺广逢， 蔡占华． 基于遗传算法的图像识别技术[J]．长安大学学报(自然科学版)，2004，24(6)：98-101．
[5] MALLEY M E． A methodology for simulating the joint strike fighter’s prognostics and health management symem[D]．PhD．Department of the Air Force Air University，2001．