基于遺傳算法的圖像匹配

《基于遺傳算法的圖像匹配》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、基于遺傳算法的圖像匹配遺傳算法理論和特點(diǎn)1、GA的基本原理遺傳算法首先采用某種編碼方式將解空間映射到編碼空間,每個(gè)編碼對應(yīng)問題的一個(gè)解,稱為個(gè)體或染色體,再隨機(jī)確定起始的一群個(gè)體,稱為種群。在后續(xù)迭代中,按照適者生存原理,根據(jù)適應(yīng)度大小挑選個(gè)體,并借助各種遺傳算子對個(gè)體進(jìn)行交叉和變異,生成代表新的解集的種群,該種群比前代更適應(yīng)環(huán)境,如此進(jìn)化下去直到滿足優(yōu)化準(zhǔn)則。此時(shí)末代個(gè)體,經(jīng)過解碼,可作為問題近似最優(yōu)解。2、GA的理論基礎(chǔ)(1)模式定理定義1:出現(xiàn)在模式H中的0或1的數(shù)目稱為模式H的階,記作O(H)。如:O(10**1)=

2、3。定義2:模式H中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離稱為模式H的定義距,記作δ(H)。如:δ(10**1)=4。模式定理:具有低階、短定義距和平均適應(yīng)度高于種群平均適應(yīng)度的模式在后代中呈指數(shù)增長。(2)積木塊假設(shè)積木塊假設(shè):遺傳算法通過短定義距、低階和高平均適應(yīng)度的模式(積木塊),在遺傳操作下相互結(jié)合,最終接近全局最優(yōu)解。模式定理保證了遺傳算法找到全局最優(yōu)解的可能性存在,而積木塊假設(shè)指出了在遺傳操作下能生成全局最優(yōu)解。兩者構(gòu)成了分析遺傳算法進(jìn)化行為的基本理論。遺傳算法的特點(diǎn)與傳統(tǒng)的方法相比，遺傳算法以其簡單、魯棒性

3、強(qiáng)、不需很多先驗(yàn)知識等特點(diǎn)，使它能適應(yīng)于不同的環(huán)境、問題，并且在大多數(shù)情況下都能得到最優(yōu)解。遺傳算法具有很強(qiáng)的魯棒性，這是因?yàn)楸绕鹌胀ǖ膬?yōu)化搜索方法，它采用了許多獨(dú)特的方法和技術(shù)，歸納起來，主要有以下幾個(gè)方面:(1)遺傳算法的處理對象不是參數(shù)本身，而是對參數(shù)集進(jìn)行了編碼的個(gè)體，遺傳算法將待優(yōu)化問題的原始參數(shù)集編碼成有限字符集上的有限長字符串，然后以一種通用的方式去找出各編碼的類似處。這樣做的好處是大大減少了約束條件的限制，如連續(xù)性、可導(dǎo)性、單峰性等。因此，遺傳算法是一種框架算法，最適合于解決那些很難用表達(dá)式表達(dá)出來的問題。(

4、2)遺傳算法是同時(shí)處理群體中的多個(gè)個(gè)體，即多點(diǎn)搜索，在很多優(yōu)化算法中，算法總是按照某種轉(zhuǎn)移準(zhǔn)則從參數(shù)空間中的一個(gè)單點(diǎn)移至下一個(gè)單點(diǎn)，這樣做很容易在多峰的搜索空間中找到一個(gè)非全局最高的峰值，即局部最優(yōu)值。而遺傳算法是從很多點(diǎn)的集合開始同時(shí)搜索的，從而減少了陷于局部最優(yōu)解的風(fēng)險(xiǎn)。(3)遺傳算法僅用適應(yīng)度函數(shù)來指導(dǎo)搜索，以往很多的搜索方法都需要輔助信息才能正常工作。如梯度法需要有關(guān)導(dǎo)數(shù)的信息才能爬上當(dāng)前的峰值點(diǎn)，這就要求目標(biāo)函數(shù)可導(dǎo)。而遺傳算法則不需要類似的輔助信息，為了有效地搜索越來越好的編碼結(jié)構(gòu)，它僅需要與該編碼串有關(guān)的適應(yīng)度

5、函數(shù)即可。在適應(yīng)度值的指導(dǎo)下，個(gè)體隨著進(jìn)化代數(shù)的增大而不斷進(jìn)化，每一代的結(jié)果都優(yōu)異于上一代，如此逐代進(jìn)化，直到得出最優(yōu)化結(jié)果或符合要求的結(jié)果。整個(gè)算法具有自適應(yīng)環(huán)境的能力。(4)遺傳算法采用了概率轉(zhuǎn)移準(zhǔn)則而不是確定性規(guī)則，與很多方法不同，遺傳算法在搜索過程中以概率轉(zhuǎn)移準(zhǔn)則來指導(dǎo)它的搜索過程朝著更優(yōu)化的解區(qū)域移動,但使用概率并不是說遺傳算法只是簡單的隨機(jī)搜索。遺傳算法用隨機(jī)選擇作為工具去指導(dǎo)搜索向著搜索空間中可能的更好的區(qū)域進(jìn)行。遺傳算法適于解決維數(shù)很高、總體很大的復(fù)雜的非線性問題，如機(jī)器學(xué)習(xí)。遺傳算法具有以下優(yōu)點(diǎn):(1)應(yīng)用

6、的廣泛性:易于寫出通用算法，求解不同優(yōu)化問題。(2)非線性性:其他多數(shù)算法都需與可導(dǎo)、線性、凸性等性質(zhì)相聯(lián)系，遺傳算法只需適應(yīng)度函數(shù)為非負(fù)，可用于具有高度非線性的問題尋優(yōu)。(3)易于修改性:遺傳算法只需少量改變算法，即可適用于不同問題。(4)易于并行實(shí)現(xiàn)。標(biāo)準(zhǔn)遺傳算法的基本流程標(biāo)準(zhǔn)遺傳求解問題的基本流程如下:1.確定染色體、種群和適應(yīng)度函數(shù)。將問題的解編碼成染色體串，如二進(jìn)制碼串，若干個(gè)可能解構(gòu)成一組種群，適應(yīng)度函數(shù)體現(xiàn)了在問題求解過程中染色體求解問題的能力。2.基因初始化，即對種群中染色體的各基因(二進(jìn)制子串)設(shè)定初值。3

7、.將種群的各染色體置于問題的環(huán)境中遺傳進(jìn)化。（1）進(jìn)化：根據(jù)適應(yīng)度函數(shù)，計(jì)算每個(gè)染色體的適應(yīng)度。（2）選擇:選擇有較大適應(yīng)值的染色體進(jìn)行復(fù)制，替代適應(yīng)值小的染色體。（3）交換和變異:其目的在于產(chǎn)生有可能更適應(yīng)環(huán)境的新染色體。4.重復(fù)3直至滿足終止條件。這樣一代代不斷進(jìn)化，最終將收斂到一個(gè)最適應(yīng)環(huán)境的個(gè)體上，即問題的最優(yōu)解。圖1描述了標(biāo)準(zhǔn)遺傳算法的流程，從圖中可以看出GA是一種群體型操作，該操作主要以群體中的所有個(gè)體為對象。選擇、交叉、變異是GA的3個(gè)主要操作算子，它們構(gòu)成了所謂的遺傳操作。圖1標(biāo)準(zhǔn)遺傳算法流程圖產(chǎn)生初始種群計(jì)

8、算適應(yīng)度是否滿足終止條件輸出最優(yōu)個(gè)體YES選擇交叉變異NO標(biāo)準(zhǔn)遺傳算法的基本要素GA具有五個(gè)基本要素:參數(shù)編碼、初始群體的設(shè)定、適應(yīng)度函數(shù)的設(shè)計(jì)、遺傳操作設(shè)計(jì)和控制參數(shù)設(shè)定。它們是設(shè)計(jì)GA時(shí)的核心內(nèi)容。1、參數(shù)編碼編碼機(jī)制是遺傳算法的基礎(chǔ)。在進(jìn)行參數(shù)編碼設(shè)計(jì)時(shí)一般都以DeJong的編碼原理