基于遺傳模擬退火算法的邊緣檢測研究

韓 兵,朱成杰

(安徽理工大學 電氣與信息工程學院,安徽 淮南 232001)

0 引言

1 遺傳算法和模擬退火算法

1.1 遺傳算法

遺傳算法(GA)通過種群進化尋找最優解,是一個模擬進化論和遺傳學原理的計算模型。 根據適者生存的生物進化原理,該算法引入參數優化產生的編碼,以群體中適應度函數選擇個體,并通過遺傳復制、交叉和變異等操作挑選個體,從而過濾較差個體,形成新的群體。 而后在經過一次次的重復操作后,提高種群中的適應度值,最后當符合約束條件,這種一次次的迭代就能夠終止[8]。 其基本步驟如下。

(1)初始化每個個體并隨機獲得在范圍內的每個染色體的每個基因值。

(2)根據適應度值函數計算種群中每個個體的適應值。

(3)選擇:篩選群體中的個體,挑選合適的個體繼承給下一代群體。

(4)交叉:交叉操作是指通過某種形式相互交換兩對染色體的局部基因而形成新的個體。

(5)變異:對群體進行變異操作。 即使某些個體的基因座的基因值發生變動。

(6)若算法滿足終止條件,則終止;不然,就到轉第二步。

程序的停止條件:如果種群中的個體符合預設的適應度,或程序不再繼續迭代執行算法,或種群已經達到最優,那么算法終止。

本部分主要對R&D投入與產出所選用的變量作穩健性檢驗，以支撐研究結果的可靠性和穩健性。考慮到企業R&D投入有較強的可逆性，管理層能夠比較容易地操縱當期的R&D研發投入，造成研究結果的失衡。因此，筆者嘗試采用企業技術人員數量作為替代指標來進一步分析。因為技術人員數量是企業R&D研發投入與科技專利產出的另一重要因素，且核心技術人員的離職容易造成核心技術的泄露，所以技術人員的聘任是比較穩定，是不易操控的R&D研發投入產出指標。為此，本文手工搜集了2010—2014年財務報告中的技術人員數量，數據來源于巨潮網，并構建如下模型進行考察:

1.2 模擬退火算法

模擬退火算法是一種來源于固體退火原理的概率算法,其中退火的過程有加熱、等溫和冷卻3 個過程。當物體處于加熱狀態,則物體內能增加,且物體內的粒子做快速不規則移動,在物體處于冷卻狀態,則物體內能減少,物體內的粒子做規則移動,當物體處于室溫時,能量是最小的,粒子實際上是最穩定的[9]。 該算法的過程為:初始化溫度T0、初始解V0和降溫方式;從當前解S0隨機跳變生成一個新解S1;計算舊解和新解之間的變化ΔT;依據接受Metropolis 規則,確定是否可以取新的解,若ΔT ＜0 則接受S1作為新的當前解S0,不然就以概率exp(- ΔT/T) 取S1作為新的當前解S0;如果確定取新解,則替換當前解,完成新解生成對應的當前解的變換部分,并修改目標函數的值;最終算法在溫度趨向于最低臨界值時趨向于全局最優解。

因為算法在取新解時,即使得到的是差解,也有一定的概率接受該解,防止陷入局部最優,假定冷卻過程足夠慢,就能得到多數較好解,但弊端是收斂速度慢。

2 遺傳模擬退火算法的圖像邊緣檢測方法

具體算法步驟如下。

(1)染色體編碼。 要初始化種群,首先要完成染色體編碼,而傳統的染色體編碼方式為編碼和解碼兩步,本文采用一種新的編碼方法,該方法可省去解碼,即種群中的每一個體配置結構集中的某一個邊沿配置結構,對于一個為M×N大小的數字圖像,每個染色體用M×N的二維矩陣表示,如此就可以將染色體與邊緣配置結構對應起來,進而省略了解碼,直接進行適應度的計算。

(2)種群S0初始化。 初始化的種群可隨機生成,可保障種群的多樣性,而根據數字圖像的大小不同,種群規模的取值不同,例如對于256×256 大小的圖像,取種群規模為512,512×512 大小的圖像,取1024 規模的種群。

(3)通過選擇、交叉、變異操作優化種群個體的染色體。 選擇操作是為了保留適合度高的個體,將適應度低的個體舍去,保障種群向高適應度進化,而常用的選擇方法包括輪盤賭法、隨機遍歷抽樣法、錦標賽選擇法等。 本文采用輪盤賭法使種群向高適應度發展。

交叉操作就是將優良個體的染色體片段遺傳給后代,同時交叉算子具備全局搜索的功能。 本文使用簡單交叉,即在單個編碼字符串上定義一個隨機節點,然后在此時將兩個配體的局部染色體相互替換。

變異操作是指變換個體序列中基因座的基因值。雖然變異防止了種群單一化的長處,讓種群適應度提高,但變異概率要適當選擇,本文在邊緣檢測實驗中采用0.01～0.05 的變異概率。

(4)模擬退火操作。 將通過遺傳過程后的種群S1中的個體代入模擬退火操作中,使其經過Metropolis 準則的調整組成新的種群,即將經選擇交叉變異的種群由狀態函數跳變產生新種群S2,由Metropolis 準則進行判別操作,若(FS1-FS2)＜0(F 為種群適應度),則接受種群S2為當前解,不然,就以exp(-ΔF/t) 的概率接受S2。

(5)判別SA 抽樣能否抵達穩定,如果不,則回到第四步;如果穩定,則往下進行退溫過程。

(6)將模擬退火產生的新群體S2與之前產生的新群體S1放在一起,依照適應度進行排序,且將適應度較好的若干個體作為下一代的種群。

(7)判別程序是否抵達終止條件,如果不符合停止條件,則轉第三步;如果符合終止條件,就令當前解為最終解。

3 仿真結果與分析

本文運用MATLAB 2018a 平臺進行編程,本次仿真分別選用Canny 算子、Sobel 算子和遺傳模擬退火算法進行對比實驗。 實驗結果如圖1—2 所示。

圖1 不同算法的邊緣檢測對比組1

圖2 不同算法的邊緣檢測對比組2

從兩組圖像的對比仿真結果可以看到,本文算法的邊緣檢測是最清晰的,從肉眼可以看出,它的噪聲最小,丟失的信息量最小,該算法更好地分析出了圖像的邊緣特征,體現特征區域與背景的邊緣劃分,圖像的細節得到更多的體現,在對比算法中,Sobel 算子對邊緣的位置判別稍差;Canny 算法檢測出的圖像有些邊沿細節有一定檢測失真。 但遺傳模擬退火算法則不同,在遺傳算法中結合模擬退火的過程能夠保證種群的多樣性,防止種群收斂于局部最優,使邊緣特征提取更加具有準確性。

4 結語

邊緣檢測是圖像特征提取的基礎,但許多邊緣檢測算法都有一定弊端。 針對一些弊端,提出了結合遺傳算法全局優化和模擬算法局部優化能力的邊緣檢測算法。 通過本次仿真實驗對該算法的對比檢測,表明相較于某些檢測算法,本文利用模擬退火對遺傳算法的“早熟”問題進行了很好的優化,從而防止了算法陷入局部尋化。 提高了實驗結果精度和連續性,在實踐運用過程中有很好的使用前景。 本文雖然使遺傳算法對檢測邊緣有了一定的優化,但不論是遺傳算法還是其他算法在邊緣檢測中都還有進一步研究和應用的可能。