摘  要： 在自適應遺傳算法的基礎上，提出了一種基于模板匹配的測量固態流體速度的方法。基于基本遺傳算法的模板匹配快速、簡單且魯棒性好[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．