• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      基于進(jìn)化規(guī)劃算法的圖像聚類研究

      2013-11-01 03:41:34王兆珍劉旭鵬楊淑瑩
      關(guān)鍵詞:適應(yīng)度算子變異

      王兆珍,劉旭鵬,楊淑瑩

      (1.天津現(xiàn)代職業(yè)技術(shù)學(xué)院電子工程系,天津 300350;2.天津理工大學(xué)智能計(jì)算及軟件新技術(shù)重點(diǎn)實(shí)驗(yàn)室,天津 300384)

      圖像聚類是指將圖像中若干樣品分成不同類,并將相同形狀的物體歸為一類的算法[1],它在模式識(shí)別領(lǐng)域中占有重要地位,主要用于數(shù)據(jù)壓縮、數(shù)據(jù)挖掘和圖像檢索等.圖像聚類涉及特征提取和識(shí)別算法,它們直接影響聚類速度和識(shí)別精度.在圖像聚類識(shí)別方法當(dāng)中,常用的有遺傳算法、k-means算法和粒子群算法等.其中遺傳算法[2-3]在局部搜索過(guò)程中表現(xiàn)能力差,搜索速度相對(duì)較慢,容易出現(xiàn)早熟現(xiàn)象;k-means算法[4]對(duì)初始值的聚類中心較為敏感,容易陷入局部最優(yōu);粒子群優(yōu)化算法[5]是一種基于群體的智能算法,但是后期具有收斂慢、搜索精度低和容易陷入局部極小等缺點(diǎn).在圖像聚類過(guò)程中,上述算法都不可避免地出現(xiàn)重復(fù)搜索的現(xiàn)象,如果樣品的數(shù)目過(guò)多,則上述算法進(jìn)行搜索的時(shí)間消耗將更為突出[6].

      進(jìn)化規(guī)劃(evolutionary programming,EP)是為了求解預(yù)測(cè)問(wèn)題而提出的一種有限機(jī)進(jìn)化模型,是一種通過(guò)模擬自然進(jìn)化過(guò)程得到的一種隨機(jī)搜索方法,屬于進(jìn)化計(jì)算的分支.該算法在變異運(yùn)算中引入正態(tài)分布技術(shù),從而使進(jìn)化規(guī)劃成為一種優(yōu)化搜索算法,可作為進(jìn)化計(jì)算的一個(gè)分支在實(shí)際領(lǐng)域中得到廣泛應(yīng)用.進(jìn)化規(guī)劃可應(yīng)用于求解組合優(yōu)化問(wèn)題和復(fù)雜的非線性優(yōu)化問(wèn)題,它只要求所求問(wèn)題是可計(jì)算的,且使用范圍較廣,目前已應(yīng)用于人工智能和機(jī)器人智能控制等諸多領(lǐng)域[9-10].與遺傳算法相比,在模擬生物進(jìn)化的過(guò)程中,進(jìn)化規(guī)劃主要著眼于物種的進(jìn)化過(guò)程,不使用個(gè)體交叉算子和重組算子來(lái)操作[11].進(jìn)化規(guī)劃中的選擇算子著重于群體中各個(gè)體之間的競(jìng)爭(zhēng)選擇,但是當(dāng)競(jìng)爭(zhēng)個(gè)體數(shù)目較大時(shí),也就類似于進(jìn)化策略中的選擇過(guò)程.進(jìn)化規(guī)劃直接把問(wèn)題的可行解作為個(gè)體的編碼,無(wú)需再對(duì)個(gè)體進(jìn)行編碼處理,也無(wú)需考慮隨機(jī)擾動(dòng)因素對(duì)個(gè)體的影響,更便于應(yīng)用.本研究將進(jìn)化規(guī)劃優(yōu)化算法應(yīng)用于圖像聚類問(wèn)題,并通過(guò)仿真實(shí)驗(yàn)檢驗(yàn)算法的性能.

      1 進(jìn)化規(guī)劃基本原理

      進(jìn)化規(guī)劃的基本原理為:

      (1)種群初始化(隨機(jī)分布個(gè)體).

      (2)變異(更新個(gè)體).進(jìn)化規(guī)劃中不使用平均變異方法,而使用高斯變異算子,以實(shí)現(xiàn)種群內(nèi)個(gè)體的變異,保持種群中豐富的多樣性.高斯變異算子可以根據(jù)個(gè)體適應(yīng)度獲得高斯變異的標(biāo)準(zhǔn)差,對(duì)于適應(yīng)度低的個(gè)體,其變異范圍大,高斯變異算子可擴(kuò)大搜索的范圍;對(duì)于適應(yīng)度高的個(gè)體,其變異范圍小.高斯變異算子可以在當(dāng)前位置局部小范圍的搜索,以實(shí)現(xiàn)變異操作.

      (3)適應(yīng)度計(jì)算(評(píng)價(jià)個(gè)體).

      (4)選擇(群體更新).在選擇操作上,進(jìn)化規(guī)劃算法采用父代與子代一同競(jìng)爭(zhēng)的方式,利用錦標(biāo)賽選擇算子,最終選擇適應(yīng)度較高的個(gè)體.

      雖然進(jìn)化規(guī)劃算法同樣是對(duì)生物進(jìn)化過(guò)程進(jìn)行模擬,且具有進(jìn)化計(jì)算的一般流程,但進(jìn)化規(guī)劃算法具有其自身特點(diǎn).與其他進(jìn)化計(jì)算相比[12],進(jìn)化規(guī)劃算法不使用遺傳算法的交叉,也不使用進(jìn)化策略算法的基因重組算子,而使用變異算子操作來(lái)體現(xiàn)個(gè)體之間相互作用[13].

      2 聚類算法的實(shí)現(xiàn)

      基于進(jìn)化規(guī)劃算法的聚類算法實(shí)現(xiàn)步驟如下:

      (1)設(shè)置相關(guān)參數(shù):初始化初始種群中的個(gè)體數(shù)Sizepop、最大迭代次數(shù)Itermax、聚類中心數(shù)目Numcenter以及進(jìn)行錦標(biāo)賽競(jìng)爭(zhēng)時(shí)用于比較的個(gè)體數(shù)q.

      (2)獲得所有待聚類樣品個(gè)數(shù)和特征.

      (3)群體初始化,即隨機(jī)分配每個(gè)個(gè)體基因位的值.

      (4)計(jì)算每個(gè)個(gè)體的適應(yīng)度值fitness.

      (5)通過(guò)高斯變異算子,生成Sizepop個(gè)新個(gè)體:對(duì)所有個(gè)體循環(huán)每個(gè)基因位,對(duì)該位基因運(yùn)用變異算子操作,按照高斯變異產(chǎn)生1個(gè)1~-Numcenter之間的數(shù)賦值給該位,生成子代群體.

      (6)計(jì)算新生成的Sizepop個(gè)子代個(gè)體適應(yīng)度值.

      (7)令父代與子代個(gè)體(共2×Sizepop個(gè))組成新群體totalpop,對(duì)新群體進(jìn)行選擇算子操作:隨機(jī)從totalpop中選擇q個(gè)個(gè)體,循環(huán)每個(gè)體,讓每個(gè)個(gè)體與這q個(gè)個(gè)體逐個(gè)進(jìn)行適應(yīng)度值的比較,以q個(gè)個(gè)體中適應(yīng)度值高于當(dāng)前個(gè)體適應(yīng)度值的個(gè)體個(gè)數(shù)作為當(dāng)前個(gè)體的得分,最終選擇評(píng)分最高的Sizepop個(gè)個(gè)體,作為下一代父代.

      (8)記錄種群中的最優(yōu)解:若新生成的子代群體中,最優(yōu)個(gè)體適應(yīng)度值低于全體種群的最優(yōu)個(gè)體的適應(yīng)度值(相互之間距離越近,適應(yīng)度值越小),則用當(dāng)前最好的個(gè)體替換總的最好的個(gè)體.

      (9)判斷是否滿足停止條件,即判斷是否達(dá)到總的迭代次數(shù).如果是,則輸出最優(yōu)解,即輸出各個(gè)樣品的類別號(hào),并退出;反之,則跳轉(zhuǎn)到步驟(4)繼續(xù)迭代.

      3 基于差分進(jìn)化算法的圖像聚類設(shè)計(jì)

      3.1 特征提取

      為更好地實(shí)現(xiàn)待測(cè)圖像有效聚類,首先須對(duì)每個(gè)待測(cè)圖像提取特征參數(shù)[14].本研究特征參數(shù)的提取方法為:在每個(gè)數(shù)字的外邊緣劃定1個(gè)矩形框,將矩形框的長(zhǎng)和寬進(jìn)行N×M分割,分割后的每個(gè)數(shù)字稱為N×M模板[7];然后計(jì)算每個(gè)小方格的黑像素個(gè)數(shù)在本方格內(nèi)的比例,以此作為樣品特征值.以圖1為例.

      將樣品分割成7×5個(gè)小方格,在每1小方格中統(tǒng)計(jì)黑像素所占方格總面積的比例,即得特征值,根據(jù)實(shí)際問(wèn)題的需要可適當(dāng)修改N和M的值,其值越大,樣品特征越多,聚類精度越高,算法收斂時(shí)間則會(huì)相應(yīng)延長(zhǎng);其值越小,算法收斂速度加快,但聚類精度會(huì)有所下降.

      3.2 解的編碼

      在進(jìn)化規(guī)劃中,采用符號(hào)編碼,位串長(zhǎng)度為L(zhǎng),搜索空間為1個(gè)L維空間,與其相對(duì)應(yīng),搜索點(diǎn)為1個(gè)L維向量.算法中,組成進(jìn)化群體的每個(gè)染色體X可直接用這個(gè)L維向量表示.

      圖2為待聚類樣品圖.

      圖2中每個(gè)個(gè)體均包含1種分類方案.L取12位,基因代表樣品所屬的類號(hào)(1~4),基因位的序號(hào)代表樣品的編號(hào),基因位的序號(hào)是固定的,即某個(gè)樣品在染色體中的位置是固定的,而每個(gè)樣品所屬的類別在隨時(shí)變化.若基因位為n,則其對(duì)應(yīng)第n個(gè)樣品,而第n個(gè)基因位所指向的基因值代表第n個(gè)樣品的歸屬類號(hào).

      每個(gè)解包含1種分類方案,某個(gè)個(gè)體的初始染色體編碼為(1,3,4,1,2,4,2,3,1,3,2,1),其含義為:第1、4、9和12個(gè)樣品被分到第1類;第5、7和11個(gè)樣品被分到第2類;第2、8和10個(gè)樣品被分到第3類;第3、6個(gè)樣品屬于第4類,此時(shí)還處于假設(shè)分類情況,不是最優(yōu)解,如表1所示.

      表1 初始染色體編碼Tab.1 Code of initial chromosome

      3.3 設(shè)置適應(yīng)度函數(shù)

      適應(yīng)度函數(shù)代表每個(gè)個(gè)體優(yōu)劣的程度,對(duì)初始群體中的每個(gè)染色體計(jì)算其適應(yīng)度值fitnessm_pop(i),其實(shí)現(xiàn)步驟如下:

      (1)通過(guò)人工干預(yù)獲得聚類類別總數(shù)Numcenter.

      (2)找出染色體中相同類別號(hào)的樣品,X(i)表示第i個(gè)類的樣品.

      (3)統(tǒng)計(jì)每個(gè)類的樣品個(gè)數(shù)n,ni為第i個(gè)類別的個(gè)數(shù),樣品總數(shù)為

      (5)同一類內(nèi)計(jì)算每個(gè)樣品到相應(yīng)的聚類中心的距離,并將其累加求和

      (6)將不同類的Di求和,賦值給

      將fitnessm_pop(i)作為最適應(yīng)度函數(shù),其值越小,說(shuō)明這種分類方法的誤差越小,即其適應(yīng)度值越小.

      3.4 變異算子

      變異操作是進(jìn)化規(guī)劃算法中最重要的操作,也是唯一的搜索方法,這是進(jìn)化規(guī)劃的獨(dú)特之處.在標(biāo)準(zhǔn)的進(jìn)化規(guī)劃中,變異操作應(yīng)使用高斯變異(Gauss mutation)算子[8].變異過(guò)程中,計(jì)算每個(gè)個(gè)體適應(yīng)度函數(shù)值線性變換的平方根,從而獲得該個(gè)體變異的標(biāo)準(zhǔn)差si,將每個(gè)分量加上1個(gè)服從正態(tài)分布的隨機(jī)數(shù).

      設(shè)X為染色體個(gè)體解的目標(biāo)變量,s為高斯變異的標(biāo)準(zhǔn)差.每部分都有L個(gè)分量,即染色體的L個(gè)基因位.染色體由目標(biāo)變量X和標(biāo)準(zhǔn)差s兩部分組成,即(X,s)=[(x1,x2,…,xL),s].

      個(gè)體變異的形式為 X(t+1)=X(t)+N(0,s).X和標(biāo)準(zhǔn)差s之間的關(guān)系是

      式(1)和式(2)中:F(X(t))是當(dāng)前個(gè)體的適應(yīng)度值,越靠近目標(biāo)解個(gè)體的適應(yīng)度值越小;N(0,s)是概率密度為的高斯隨機(jī)變量;b和g是待定參數(shù),一般將b和g的值設(shè)為1和0;目標(biāo)變量X的每個(gè)分量通過(guò)式(1)可以達(dá)到不同的變異效果.

      3.5 選擇算子

      在進(jìn)化規(guī)劃中,選擇機(jī)制的作用是根據(jù)適應(yīng)度函數(shù)值從父代和子代集合的2×Sizepop個(gè)個(gè)體中選擇Sizepop個(gè)較好的個(gè)體組成下一代種群,其形式化表示為:s:I2×Sizepop→ISizepop.選擇操作按照一種隨機(jī)競(jìng)爭(zhēng)的方式進(jìn)行,進(jìn)化規(guī)劃中選擇算子主要通過(guò)概率選擇、錦標(biāo)賽選擇和精英選擇3種方式選取,其中錦標(biāo)賽選擇方法是進(jìn)化規(guī)劃中較為常用的方法.錦標(biāo)賽選擇操作的具體過(guò)程為:

      (1)將由Sizepop個(gè)父代個(gè)體組成的種群P(t)和由種群P(t)經(jīng)過(guò)1次變異運(yùn)算后產(chǎn)生的由Sizepop個(gè)子代個(gè)體組成的種群P′(t)合并在一起,組成1個(gè)共含有2×Sizepop個(gè)個(gè)體的集合P(t)∪P′(t),記為I;

      (2)每個(gè)個(gè)體xi∈I,從I中隨機(jī)選擇q個(gè)個(gè)體,并將q個(gè)個(gè)體的適應(yīng)度函數(shù)值Fj(j∈(1,2,…,q))與xi的適應(yīng)度函數(shù)值進(jìn)行比較,計(jì)算出q個(gè)個(gè)體中適應(yīng)度函數(shù)值比xi適應(yīng)度差的個(gè)體的數(shù)目wi,并把wi作為 xi的得分,其中 wi∈(0,1,…,q).

      (3)在所有2×Sizepop個(gè)個(gè)體都經(jīng)過(guò)比較后,按每個(gè)個(gè)體的得分wi進(jìn)行排序,選擇Sizepop個(gè)具有最高得分的個(gè)體作為下一代種群.

      算法中,q≥1為選擇算法的參數(shù),為使錦標(biāo)賽選擇算子發(fā)揮更好的作用,需要設(shè)定適當(dāng)?shù)挠糜诒容^的個(gè)體數(shù)q.q的取值較大時(shí),偏向確定性選擇,當(dāng)q=2×Sizepop時(shí),則從2×Sizepop個(gè)個(gè)體中將適應(yīng)度值較高的Sizepop個(gè)個(gè)體選出,容易帶來(lái)早熟等弊端;相反,q的取值較小時(shí),偏向于隨機(jī)性選擇,適應(yīng)度的控制能力下降,導(dǎo)致大量低適應(yīng)度的個(gè)體被選出,造成種群退化.因此,為了既能夠保持種群的先進(jìn)性,又避免確定性選擇帶來(lái)的早熟弊端,需要依據(jù)具體問(wèn)題,合適地選取q值.

      進(jìn)化過(guò)程中,每代種群中相對(duì)較好的個(gè)體被賦予了較大的得分,能夠被保留到下一代的群體中.

      4 實(shí)驗(yàn)結(jié)果

      在MATLAB 2008環(huán)境下,編程實(shí)現(xiàn)了基于進(jìn)化規(guī)劃的手寫(xiě)數(shù)字的聚類問(wèn)題,并在Inter(R)Core(TM)i5 CPU處理器的計(jì)算機(jī)上對(duì)圖2所示的待聚類圖像進(jìn)行相應(yīng)的聚類實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖3所示.由圖3可以看出,進(jìn)化規(guī)劃算法可以很好地實(shí)現(xiàn)不同手寫(xiě)數(shù)字的聚類,取得了較好的實(shí)現(xiàn)效果.

      進(jìn)化規(guī)劃算法找到的最優(yōu)解編碼如表2所示.通過(guò)樣品值與基因值比較對(duì)照可以發(fā)現(xiàn),相同的手寫(xiě)數(shù)字被歸為一類,分到相同的類號(hào),而且全部正確.實(shí)驗(yàn)結(jié)果表明:進(jìn)化規(guī)劃算法可以有效實(shí)現(xiàn)不同圖像的聚類.

      表2 進(jìn)化規(guī)劃算法獲得的最優(yōu)解編碼Tab.2 Optimal solution achieved by evolutionary programm ing

      5 結(jié)論

      本研究分析了進(jìn)化規(guī)劃算法的原理和仿生機(jī)制,并將其應(yīng)用于圖像聚類問(wèn)題的求解,仿真實(shí)驗(yàn)結(jié)果表明,基于進(jìn)化規(guī)劃算法的圖像聚類方法具有良好的可行性與準(zhǔn)確性.

      [1]楊淑瑩.圖像模式識(shí)別—VC++技術(shù)實(shí)現(xiàn)[M].北京∶清華大學(xué)出版社,北京交通大學(xué)出版社,2005.

      [2]張講社,徐宗本,梁怡.整體退火遺傳算法及其收斂充要條件[J].中國(guó)科學(xué):E 輯,1997,27(2):154—164.

      [3]張忠華,楊淑瑩.基于遺傳算法的圖像聚類設(shè)計(jì)[J].測(cè)控技術(shù),2010,29(2):4—46.

      [4]郭慶銳,許建龍,孫樹(shù)森,等.基于顏色重心和k-means的彩色圖像聚類分割算法[J].浙江理工大學(xué)學(xué)報(bào),2010,27(4):580—584.

      [5]宋潔,董永峰,侯向丹,等.改進(jìn)的粒子群優(yōu)化算法[J].河北工業(yè)大學(xué)學(xué)報(bào),2008,37(4):55—59.

      [6]謝金星.進(jìn)化計(jì)算簡(jiǎn)要綜述[J].控制與決策,1997,12(1):1—7.

      [7]LEECY,YAOX.Evolutionary programmingusingmutationsbased on the levy probability distribution[J].Transactions on Evolutionary Computation.2004,8(2):1—13.

      [8]IWAMATSU M.Generalized evolutionary programming with Levytypemutation[J].Computer Physics Communications,2002,147(8):729—732.

      [9]商允偉,裘隸皇.一種求解數(shù)值優(yōu)化問(wèn)題的快速進(jìn)化規(guī)劃算法[J].系統(tǒng)仿真學(xué)報(bào),2004,16(6):1190—1192.

      [10]王麗萍,董江輝.帶有一種新的算子的進(jìn)化規(guī)劃算法的收斂性分析[J].科學(xué)技術(shù)與工程,2009,9(6):1428—1431.

      [11]高永超,李歧強(qiáng).退火進(jìn)化規(guī)劃算法及其收斂性[J].系統(tǒng)仿真學(xué)報(bào),2006,18(3):577—580.

      [12]王向軍,嵇斗,張民.一種多群競(jìng)爭(zhēng)進(jìn)化規(guī)劃算法[J].電子學(xué)報(bào),2004,32(11):1824—1828.

      [13]高瑋.遺傳算法與進(jìn)化規(guī)劃的比較研究[J].通訊和計(jì)算機(jī),2005,2(8):10—15.

      [14]楊淑瑩.模式識(shí)別與智能計(jì)算-Matlab技術(shù)實(shí)現(xiàn)[M].北京∶電子工業(yè)出版社,2011∶34—36.

      猜你喜歡
      適應(yīng)度算子變異
      改進(jìn)的自適應(yīng)復(fù)制、交叉和突變遺傳算法
      擬微分算子在Hp(ω)上的有界性
      變異危機(jī)
      變異
      各向異性次Laplace算子和擬p-次Laplace算子的Picone恒等式及其應(yīng)用
      一類Markov模算子半群與相應(yīng)的算子值Dirichlet型刻畫(huà)
      Roper-Suffridge延拓算子與Loewner鏈
      基于空調(diào)導(dǎo)風(fēng)板成型工藝的Kriging模型適應(yīng)度研究
      變異的蚊子
      少數(shù)民族大學(xué)生文化適應(yīng)度調(diào)查
      高台县| 双城市| 泰和县| 镇坪县| 申扎县| 开化县| 林西县| 射洪县| 澳门| 楚雄市| 油尖旺区| 开化县| 安塞县| 天等县| 昔阳县| 崇信县| 昌邑市| 宜章县| 乳山市| 绥化市| 独山县| 全椒县| 阿鲁科尔沁旗| 南靖县| 钟祥市| 天峻县| 广饶县| 安多县| 通辽市| 晋州市| 兴山县| 宁海县| 翁源县| 视频| 陵川县| 二连浩特市| 尼玛县| 汉沽区| 宝山区| 扶绥县| 会宁县|