李 薇, 胡曉輝, 王鴻闖
(蘭州交通大學 電子與信息工程學院,甘肅 蘭州 730070)
生物地理學優化(biogeography-based optimization,BBO)算法是Simon D提出的一種新興的智能優化算法[1,2]。由于其獨特的遷移機制以及強大的信息共享能力,使得BBO算法得到了廣泛的應用。如李靜文等人[3]利用BBO算法對最優潮流問題進行優化;陳珍等人[4]將BBO算法應用到電力系統的經濟調度問題。在標準的BBO算法中,遷移算子只選取了已存在個體的特征,使得信息的使用效率很低,導致收斂速度較慢。
模糊C均值(fuzzy C-means,FCM)算法是1974年由Dunn J C提出并由Bezdek加以推廣的[5]。算法的關鍵是如何選取合適的初始值以獲得最佳分割效果。但標準的模糊聚類是一種局部搜索算法,若初始值選取不當很容易陷入局部最優[6]??赏ㄟ^引入智能算法對FCM的初值選取優化,如張紅旗等人結合遺傳算法和FCM進行草莓圖像的分割研究[7]。
本文針對FCM算法進行圖像分割時容易陷入局部最優的問題,引入BBO優化算法尋求全局最優聚類中心,并對算法的遷移和變異算子進行改進,提高算法效率,使算法能夠快速收斂到全局最優解,提高尋求聚類中心的效率和準確性。
在生物地理學優化算法中,每個個體稱為一個棲息地,其中每個棲息地通過棲息地的適宜度指數(habitat suitability index,HSI)評判該棲息地的好壞。
生物地理學優化算法包括遷移和變異2個主要的操作。
遷入率λ和遷出率μ影響棲息地物種的遷移,與物種數量息息相關,設當前物種的遷入率λ和遷出率μ函數為λi和μi,則有
λi=I(1-Si/Smax),μi=E(Si/Smax)
(1)
式中I為最大遷入率,E為最大的遷出率,Si為當前種群數量,Smax為最大種群數量。
棲息地發生突然變異的概率與該棲息地的生物物種數量成反比,物種數量為i的棲息地發生變異的概率mi為
(2)
式中Ps為物種數量為S的概率,mmax為給定的最大變異概率。
本文增加選擇算子,不僅加快了收斂速度,而且對于后續的遷移和變異有一定程度的幫助。算法1為選擇算子的偽代碼,NP為保留優秀解的個數,HSIj為舊解的適宜度指數,HSIx為新解的適宜度指數的值。
算法1選擇算子
fori=1 toNP
ifHSIj(i) 用新解替換舊解 end if else 保留舊解 end for 標準的遷移操作是在已有的棲息地的物種之間進行遷移,對于全局的搜索能力較差,且對于標準BBO算法的遷移操作來說,某個遷出率較高的棲息地中的遷出對于遷入率較高的棲息地并不一定完全最優。 為了提高其的全局搜索能力并且使得遷移更加的有效,本文在BBO算法選擇操作的基礎上,利用保留的優秀解對遷移操作進行。其中優化公式為 Hi←He+R(-1,1)×(Hr-He) (3) 式中Hi為選定的進行遷入的棲息地,He為選定的進行遷出的棲息地,Hr為選擇的優秀解,R(-1,1)為[-1,1]之間的隨機數。遷移策略的偽代碼如算法2,其中N為棲息地的數量,D為單個棲息地中的特征數量,rand(0,1)為(0,1)之間的隨機數。 算法2改進的遷移算子 fori=1 toN forj=1 toD 根據遷入率λi選擇待遷入的棲息地Hi if rand(0,1)<λi 選擇需要改變的特征Hi(i,j) 根據遷出率μi選擇需要遷出的棲息地He if rand(0,1)<μi end if end if end for end for 在BBO算法中,標準的變異操作使用隨機生成的特征值代替選中棲息地原有的特征值,具有一定的盲目性,可能導致BBO的收斂速度變慢。為此,本文提出了一種通過優秀解與所選棲息地的特征值進行二進制計算從而得到較優的變異特征值的方法,對于變異產生的盲目性進行一定程度的降低,并且在收斂速度上有一定程度的提高。具體為 Hi←Hr1+Fi?(Hr2⊕Hr) (4) 式中 “⊕”為異或操作,“?”為與操作,Hr1和Hr2為隨機產生的2個不同的特征值,Hr為使用選擇操作保留的最優個體;Fi為二進制變異尺度因子,是隨機產生的二進制位串。變異策略的偽代碼如算法3所示。 算法3變異算子 fori=1 toN 選擇出待變異的棲息地Hi 根據Pi計算出mi,然后用mi選擇特征Hi(i,j) if rand(0,1) 由式(4)的特征值代替Hi(i,j) end if end for 本文將改進的BBO算法引入到FCM聚類中心的選取,提高聚類中心的準確性和后續的圖像分割效率,為了驗證本文提出方法的有效性,選取了2個典型圖像(baboon和Lena)進行實驗,同時進行基于遺傳算法[8,9]以及標準BBO算法的FCM圖像分割實驗作為對比。 實驗1分割baboon圖像,設置C=3,結果如圖1。 圖1 baboon圖像分割對比 實驗2分割Lena圖像,設置C=2,結果如圖2。 圖2 Lena圖像分割對比 圖像分割的結果通過劃分熵和劃分系數評價,劃分系數Vpc,劃分熵Vpe均是基于隸屬度的聚類有效性函數指標,若Vpc的值越趨近于1,則聚類的程度越強。Vpe越趨近于0,聚類結構越明顯,如表1所示。 表1 實驗圖像的有效性指標 從分割效果以及分割時間都可以看出,本文方法優于其他2種方法看,基于標準BBO算法的FCM圖像分割法在遷移操作時有可能沒有改變被遷入棲息地的適宜度指數,且在變異操作時缺少具體的變異方向。在基于遺傳算法的FCM圖像分割法中,遺傳算法中的交叉操作無法根據適應值的不同情況來改變交叉基因的比例,更加重要的是交叉操作的片段來自同一個體,很容易導致陷入局部最優[10,11]。 基于以上分析可以得出結論,基于改進的BBO優化算法的FCM圖像分割方法能快速有效地分割復雜圖像。 本文提出了基于改進的BBO優化算法的FCM圖像分割方法,目的在于降低圖像分割的效率和改善分割效果。實驗結果顯示本文提出的分割方法行之有效。2.2 改進的遷移操作
2.3 二進制變異操作
3 實驗與結果分析
4 結 論