融合細(xì)菌覓食趨化算子的生物地理學(xué)優(yōu)化算法

張新明, 康 強(qiáng), 涂 強(qiáng), 程金鳳

(1. 河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院 河南 新鄉(xiāng) 453007; 2.河南省高校計(jì)算智能與數(shù)據(jù)挖掘工程技術(shù)研究中心 河南 新鄉(xiāng) 453007)

?

融合細(xì)菌覓食趨化算子的生物地理學(xué)優(yōu)化算法

張新明1，2, 康 強(qiáng)1, 涂 強(qiáng)1, 程金鳳1

(1. 河南師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院 河南 新鄉(xiāng) 453007; 2.河南省高校計(jì)算智能與數(shù)據(jù)挖掘工程技術(shù)研究中心 河南 新鄉(xiāng) 453007)

針對高維多閾值彩色圖像分割中由于維數(shù)高帶來閾值搜索困難等問題，提出了一種融合細(xì)菌覓食算法(BFO)趨化算子的混合生物地理學(xué)算法(hybrid biogeography-based optimization, HBBO)．首先構(gòu)建一種嵌入變異操作的遷移算子，去掉BBO算法原有的變異算子;其次將細(xì)菌覓食算法中具有較強(qiáng)局部搜索能力的趨化算子的趨化步長固化為1，將此趨化算子與改進(jìn)的遷移算子融合，并將精英保留策略換成貪婪選擇算子，形成混合BBO算法;最后將HBBO算法應(yīng)用到高維Tsallis熵多閾值彩色圖像分割中．實(shí)驗(yàn)結(jié)果表明，與目前的MABC、IDPSO、MBFO和BBO-M算法相比，HBBO算法在高維多閾值圖像分割中有更好的優(yōu)化性能、更快的運(yùn)行速度和更強(qiáng)的穩(wěn)定性．

智能優(yōu)化算法； 生物地理學(xué)優(yōu)化算法； 彩色圖像分割； 多閾值分割； Tsallis熵

0 引言

智能優(yōu)化算法通過模擬某些自然現(xiàn)象或過程以解決科學(xué)及工程中遇到的優(yōu)化問題，已成為科學(xué)與工程領(lǐng)域的研究熱點(diǎn)[1-2]．近年來涌現(xiàn)出了許多智能優(yōu)化算法，如粒子群優(yōu)化算法[3]、人工蜂群算法[4]、布谷鳥算法[5]等．這些算法能夠高效地求解傳統(tǒng)優(yōu)化算法難以解決的復(fù)雜問題，且易于實(shí)現(xiàn)，因而得到廣泛的應(yīng)用．然而，沒有一種優(yōu)化方法能夠?qū)λ袉栴}都有效，每種方法有其相應(yīng)的優(yōu)勢和劣勢[6]．特別是對于一些不確定和非線性復(fù)雜系統(tǒng)問題的求解，單一模式優(yōu)化方法難以獲得最優(yōu)解或滿意解．混合算法利用各智能優(yōu)化算法內(nèi)部獨(dú)特的優(yōu)點(diǎn)和機(jī)制相互補(bǔ)充，通過算法間交叉和融合，構(gòu)造出混合智能系統(tǒng)，以便產(chǎn)生更好的優(yōu)化性能和求解效率．

生物地理學(xué)優(yōu)化算法(biogeography-based optimization, BBO)是基于生物地理學(xué)理論提出的一種新穎的群體智能進(jìn)化算法[5]，該算法因具有較強(qiáng)的全局搜索能力和穩(wěn)定性，受到業(yè)內(nèi)眾多研究者的青睞．文獻(xiàn)[6]提出一種基于高斯變異的生物地理學(xué)優(yōu)化模型，提高了算法的優(yōu)化精度；文獻(xiàn)[7]提出了一種混合遷移算子，并將其應(yīng)用于約束優(yōu)化問題；文獻(xiàn)[8]提出了一種融合了DE算法的DE/BBO，有效地結(jié)合DE的探索能力與BBO的開采能力，提高了算法的搜索性能．

閾值分割是常用的圖像分割方法之一，其性能穩(wěn)定且易于實(shí)現(xiàn)，通常分為單閾值法和多閾值法兩類．閾值分割的關(guān)鍵在于選取合適的閾值，常用的閾值分割法有最大類間方差法[9]、最小交叉熵法[10]和最大Tsallis熵法[11-12]等．對于多閾值分割常采用智能優(yōu)化算法進(jìn)行閾值選擇以降低其計(jì)算復(fù)雜度．然而，一般的優(yōu)化方法在處理低維多閾值分割問題時(shí)可以找到最佳閾值向量，而面對高維問題時(shí)就很難找到合適的閾值組合，從而圖像分割效果不佳且目前研究甚少；另外，彩色圖像分割需要對諸如R、G、B三種顏色分量尋找最優(yōu)閾值向量，其計(jì)算復(fù)雜度高．面對維數(shù)高和多分量的彩色圖像帶來的分割難度，需要引入運(yùn)行速度快、優(yōu)化性能好的優(yōu)化算法進(jìn)行閾值選?。壳癇BO及其改進(jìn)算法在高維多閾值搜索時(shí)，依然存在著搜索性能不理想、實(shí)時(shí)性差等問題．

本文針對高維Tsallis熵多閾值彩色圖像分割，提出一種融合細(xì)菌覓食算法(BFO)趨化算子的混合生物地理學(xué)優(yōu)化算法(hybrid BBO, HBBO)．新算法首先構(gòu)建一種融合變異操作的遷移算子，然后與局部搜索能力強(qiáng)的BFO趨化算子融合，去掉標(biāo)準(zhǔn)BBO算法的隨機(jī)變異算子，省去設(shè)置變異參數(shù)和計(jì)算變異概率等步驟，又將精英保留策略換成了貪婪選擇法，進(jìn)一步簡化算法流程，降低計(jì)算復(fù)雜度，提高算法性能，最終得到一種適用于高維多閾值彩色圖像分割的高效、快速的閾值搜索算法．

1 標(biāo)準(zhǔn)BBO算法

在標(biāo)準(zhǔn)BBO 算法[5]中，棲息地相當(dāng)于候選解個(gè)體，每個(gè)棲息地的適宜度指數(shù)向量(suitability index variables，SIVs)相當(dāng)于解個(gè)體中的特征向量，向量中的每一維相當(dāng)于一個(gè)特征值，描述棲息地的適宜度指數(shù)(habitat suitability index，HSI)用來衡量個(gè)體解的優(yōu)劣．棲息地Hi的遷入率λi和遷出率μi的計(jì)算公式為：

λi=I(1-Si/Smax),

(1)

μi=E(Si/Smax),

(2)

其中:I，E分別為最大遷入率和最大遷出率；Si為棲息地Hi當(dāng)前的物種數(shù)量，Smax為最大物種數(shù)量．

遷移算子通過分享HSI較高棲息地的特征值來改變HSI較低棲息地的相應(yīng)特征值．遷移操作為：

(3)

其中:Hi是遷入棲息地，He是遷出棲息地．遷移算子的偽代碼如算法1所示,N表示棲息地的數(shù)量，rand表示均勻分布在(0,1)之間的隨機(jī)實(shí)數(shù)．

算法1 遷移算子 fori=1toNdo 根據(jù)λi選擇棲息地Hi ifrand<λi then fore=1toNdo 根據(jù)μe選擇棲息地He 對Hi執(zhí)行式(3) endfor endif endfor

標(biāo)準(zhǔn)BBO算法的變異算子通過模擬棲息地環(huán)境突變造成的物種數(shù)量的變化，來提高算法的探索能力．棲息地Hi的變異概率mi與其物種數(shù)量概率Pi成反比：

(4)

其中:mmax表示最大變異概率；Pmax= max(Pi)，棲息地的物種數(shù)量概率Pi定義為：

(5)

變異算子的偽代碼如算法2所示．

算法2 變異算子 fori=1toNdo 通過概率Pi計(jì)算mi，根據(jù)mi選擇Hi(VSIV) ifrand

標(biāo)準(zhǔn)BBO算法的主要流程為：第1步定義相關(guān)參數(shù)，隨機(jī)初始化種群，并計(jì)算種群的HSI和按照HSI降序排序；第2步保留精英解，計(jì)算每個(gè)棲息地的物種數(shù)量，根據(jù)物種數(shù)量計(jì)算每個(gè)棲息地的遷入率、遷出率和變異率；第3步依據(jù)遷入率和遷出率執(zhí)行算法1的遷移算子；第4步依據(jù)變異率執(zhí)行算法2的變異算子；第5步計(jì)算種群的HSI并排序，執(zhí)行精英策略替換掉最差的解，并再次排序；第6步判斷是否達(dá)到迭代停止條件，如果達(dá)到則輸出結(jié)果，若未達(dá)到則返回至第2步．

2 混合BBO算法

2.1 改進(jìn)的遷移算子

標(biāo)準(zhǔn)BBO算法有著良好的全局搜索能力和穩(wěn)定性，但是基于候選解的特征值進(jìn)行直接替換的遷移算子容易使算法陷入局部最優(yōu)，出現(xiàn)早熟現(xiàn)象；基于隨機(jī)突變的變異算子有可能破壞較好的解，影響了優(yōu)化的性能并導(dǎo)致收斂速度減慢；基于精英保留策略的種群更新每次迭代中都要排序兩次，增加了算法的計(jì)算復(fù)雜度．為了克服以上缺點(diǎn)，本文提出的混合算法去掉了標(biāo)準(zhǔn)BBO算法中原有的隨機(jī)變異算子，構(gòu)造一種融合了變異操作的新穎遷移算子．

首先，根據(jù)棲息地的遷出率使用輪賭選擇法選出待遷出的棲息地．對選中進(jìn)行遷移操作的特征值添加擾動(dòng)，使其值在小范圍內(nèi)上下浮動(dòng)，表示為：

Hk(SIVj)←HSI(SIVj)+α*sign(1-2*rand),

(6)

α=round(rand1/2),

(7)

其中:Hk是準(zhǔn)備遷入的棲息地;HSI是準(zhǔn)備遷出的棲息地;α是調(diào)整種群擾動(dòng)幾率的控制參數(shù);round()是四舍五入取整函數(shù);sign()是符號函數(shù)，可得到-1、0或者1這3種結(jié)果來實(shí)現(xiàn)特征值是否浮動(dòng)或以最小灰度級值上下浮動(dòng)，提高搜索精度和收斂速度．由式(7)可知，α的值取1的概率要大于取0的概率，從而使式(6)中變異擾動(dòng)的概率增大．其次，給候選解中沒有選中進(jìn)行遷移操作的特征值添加一個(gè)差分變異擾動(dòng)因子，表示為：

Hk(SSIVj)←round(Hk(SIVj)+rand*(Hrn1(SSIVj)-Hrn2(SSIVj))),

(8)

其中:Hk(SIVj)表示該候選解中未進(jìn)行遷移操作的特征值；Hrn1和Hrn2是隨機(jī)選擇的兩個(gè)候選解，滿足rn1,rn2,k∈[1,N]，且rn1≠rn2≠k，N為種群數(shù)量．從式(8)可以看出，沒有遷移的特征值采用差分變異算子進(jìn)行調(diào)整，其縮放因子采用rand函數(shù)來控制變異的程度，避免調(diào)整參數(shù)，提高可操作性，增加種群的多樣性，提高算法的全局搜索能力．改進(jìn)的遷移算子偽代碼如算法3所示．

算法3 改進(jìn)的遷移算子 fork=1toNdo 根據(jù)λk選擇棲息地Hk forj=1toddo ifrand<λkthen 根據(jù)輪賭選擇法選擇遷出的棲息地HSI 根據(jù)式(7)計(jì)算α值，并執(zhí)行式(6) else 對Hk執(zhí)行式(8) endif endfor endfor

以上融合了變異操作的遷移算子同時(shí)又具備良好的開采能力和探索能力，簡化了算法的優(yōu)化過程，并且省去了變異率參數(shù)的設(shè)置及計(jì)算過程，大幅度降低了算法的計(jì)算復(fù)雜度．

BFO算法模擬了大腸桿菌在人體腸道內(nèi)尋找食物的3種基本行為，即趨化、復(fù)制和驅(qū)散，細(xì)菌通過這3種行為達(dá)到游向營養(yǎng)豐富區(qū)域的目的．趨化指細(xì)菌朝著營養(yǎng)豐富區(qū)域聚集，模擬了大腸桿菌在尋找食物過程中的兩種基本運(yùn)動(dòng)：翻轉(zhuǎn)和游動(dòng)．翻轉(zhuǎn)指細(xì)菌任意找一個(gè)新的運(yùn)動(dòng)方向并前進(jìn)單位步長；游動(dòng)指當(dāng)細(xì)菌翻轉(zhuǎn)后，若當(dāng)前位置的函數(shù)適應(yīng)度值fnew較之前的fold更優(yōu)，則沿該方向繼續(xù)前進(jìn)若干步長，直至它的營養(yǎng)分布函數(shù)值不再改善或達(dá)到預(yù)定的游動(dòng)步數(shù)Ns為止，趨化步數(shù)設(shè)置為Nc．然而，由于優(yōu)化問題的多樣性，趨化步長參數(shù)設(shè)置很不方便，為避免設(shè)置步長參數(shù)，本文將趨化步長固化為1．BFO算法中的趨化行為不僅大幅度提高了算法的局部搜索能力，使其具有較高的搜索精度，其偽代碼如算法4所示．

算法4 BFO算法趨化算子 fori=1toNcdo fork=1toNdo 細(xì)菌向隨機(jī)方向翻轉(zhuǎn)并延該方向游動(dòng)1步長 iffnew>foldthen forj=1toNsdo iffnew>foldthen 繼續(xù)沿該方向游動(dòng)1步長 endif endfor endif endfor endfor

2.3 混合BBO算法

混合BBO算法(HBBO)將改進(jìn)的遷移算子和BFO算法趨化算子進(jìn)行融合，并將趨化步長固化為1，為了進(jìn)一步降低計(jì)算復(fù)雜度，HBBO算法去掉了標(biāo)準(zhǔn)BBO算法中原有的變異算子，省去設(shè)置變異參數(shù)和計(jì)算變異概率等步驟，將計(jì)算遷入率和遷出率的步驟放到種群迭代循環(huán)之前，如此只需計(jì)算一次遷入率和遷出率.由于算法是應(yīng)用到圖像多閾值分割中，在適應(yīng)度的值保證為有效值的情況下，可以將遷入率和遷出率的計(jì)算放到循環(huán)之外，避免了重復(fù)計(jì)算，節(jié)省了時(shí)間．另外，HBBO算法將標(biāo)準(zhǔn)BBO算法中的精英策略改為貪婪選擇方案，將經(jīng)過改進(jìn)遷移算子產(chǎn)生的新一代解集與上一代解集進(jìn)行比較，采用優(yōu)勝劣汰原則保留較優(yōu)的候選解，減少了精英參數(shù)設(shè)置的同時(shí)又減少了一次排序過程，提高了運(yùn)算效率．HBBO算法設(shè)置最大迭代次數(shù)Maxgen判斷是否達(dá)到算法停止條件，其偽代碼如算法5所示．

算法5 混合的HBBO算法 參數(shù)初始化，隨機(jī)生成種群 個(gè)體適應(yīng)度評價(jià)，并按適應(yīng)度值排序 根據(jù)式(1)和式(2)計(jì)算每個(gè)個(gè)體遷入率和遷出率 forg=1toMaxgendo 根據(jù)算法3對種群執(zhí)行改進(jìn)的遷移算子 對種群進(jìn)行越界約束，并評價(jià)個(gè)體適應(yīng)度 按貪婪選擇法更新種群 根據(jù)算法4對新種群執(zhí)行BFO的趨化算子 按適應(yīng)度值排序 endfor 輸出最優(yōu)解

3 基于混合BBO算法的多閾值彩色圖像分割

3.1 Tsallis熵法多閾值選擇

Tsallis熵閾值法是常用的圖像分割方法[11-12]，文獻(xiàn)[13]指出總Tsallis熵的非廣延性使得基于該方法的單閾值分割效果良好，但面對多閾值分割問題時(shí)，其可操作性較差，計(jì)算復(fù)雜度高．文獻(xiàn)[12]通過定理證明和推導(dǎo)將基于Tsallis熵的分割方法推廣至多閾值分割問題中．描述為：

設(shè)d個(gè)閾值[t1,t2,…,td],將一維直方圖分成d+1個(gè)區(qū)域，則總的Tsallis 熵為：

(9)

1.2.7.4 規(guī)范醫(yī)療廢物處置 （1）將ICU內(nèi)負(fù)壓傳輸通道進(jìn)行全面整修，對通道進(jìn)行分類，設(shè)置MDRO專用傳遞通道；（2）規(guī)范MDRO感染醫(yī)療廢物標(biāo)識；（3）規(guī)范醫(yī)療廢物處置流程。

選取的最佳閾值向量應(yīng)滿足：

[t1,t2,…,td]*=arg max(T[t1,t2,…,td])．

(10)

3.2 基于HBBO算法的多閾值彩色圖像分割

假設(shè)對一副圖像進(jìn)行d閾值分割，解向量為x=[x1,x2,…,xd]，其取值均為正整數(shù)并且滿足0

Step 1：讀取圖片，對R顏色分量分割．初始化算法參數(shù)，設(shè)最大迭代次數(shù)為Maxgen，種群數(shù)量為N，閾值個(gè)數(shù)為d；

Step 2：初始化隨機(jī)種群X，并保證X是一個(gè)N行d列正整數(shù)矩陣，按列由小到大排列；每行代表一個(gè)棲息地，每列都是一個(gè)維度，用式(9)評價(jià)X中每個(gè)棲息地Xi的HSI，(i=1,2,…,N)，按照HSI的值對Xi進(jìn)行降序排列；

Step 3：執(zhí)行式(1)和式(2)，計(jì)算遷入率和遷出率；

Step 4：依據(jù)算法3執(zhí)行改進(jìn)的遷移算子，生成新一代解集；

Step 5：執(zhí)行貪婪選擇算子，保留新一代解集和上一代解集中較優(yōu)的N個(gè)候選解；

Step 6：對保留下來的解執(zhí)行算法4的趨化算子，再根據(jù)HSI值的降序排序；

Step 7：若沒有達(dá)到停止準(zhǔn)則，轉(zhuǎn)到Step 4；

Step 8：采用以上步驟完成彩色圖像另外G和B兩個(gè)顏色分量的閾值選擇；

Step 9：用求得的最優(yōu)閾值向量對彩色圖像進(jìn)行分割，輸出分割結(jié)果．

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

4.1 實(shí)驗(yàn)描述及參數(shù)設(shè)置

為了檢驗(yàn)HBBO算法在高維Tsallis熵多閾值彩色圖像分割中的優(yōu)化性能，本文對大量的圖片進(jìn)行多閾值分割實(shí)驗(yàn)，并將實(shí)驗(yàn)結(jié)果與MABC(modified artificial bee colony)[15]、BBO-M (biogeography-based optimization-mutation)[16]、IDPSO(improved particle swarm optimization)[17]和MBFO (modified bacterial foraging optimization)[18]在高維Tsallis熵多閾值彩色分割中的優(yōu)化結(jié)果進(jìn)行比較．篇幅所限，本文僅使用157055.jpg和145086.jpg兩幅圖片作為示例說明，其原圖像分別如圖1a和圖2a所示，其3個(gè)分量的直方圖分別見圖1b～圖1d和圖2b～圖2d.其中，橫坐標(biāo)表示灰度級，其取值范圍一般在0～255之間，縱坐標(biāo)表示圖像中具有某種灰度級別的像素個(gè)數(shù).兩幅圖片來自Berkeley數(shù)據(jù)庫(http://www.eecs.berkeley.edu/Research/Projects/CS/vision/grouping/index2.html)．所有實(shí)驗(yàn)均在操作系統(tǒng)為Windows 7、CPU主頻為3.10 GHz和內(nèi)存為4 GB的PC上進(jìn)行的，編程語言采用的是MATLAB R2014a．為了滿足不同閾值選擇的需要，設(shè)置最大迭代次數(shù)(Maxgen)隨著圖像分割閾值數(shù)的增加而增加，以便達(dá)到自適應(yīng)調(diào)整Maxgen的目的，其表示為Maxgen=2d2+20(d-1)+12，其中:d為設(shè)置的閾值數(shù)．種群數(shù)量參數(shù)設(shè)置N=30，Tsallis熵的參數(shù)q=0.8．由于HBBO每次迭代每個(gè)種群對目標(biāo)函數(shù)評價(jià)次數(shù)比其他對比算法多，為凸顯HBBO算法性能，保證HBBO算法的評價(jià)次數(shù)近似等于或小于其他4種算法，將HBBO的迭代次數(shù)及種群數(shù)量分別設(shè)置為：Maxgen/Nc和N/2．HBBO算法其他參數(shù)設(shè)置為：最大遷入率I=1，最大遷出率E=1，最大趨化步驟Nc=4，最大游動(dòng)步數(shù)Ns=3．MBFO的參數(shù)依據(jù)效果最佳原則設(shè)置：種群數(shù)量為N，最大趨化步驟Nc=10，最大游動(dòng)步數(shù)Ns=4，復(fù)制次數(shù)Nre=1，驅(qū)散次數(shù)Ned=Maxgen/Nc，細(xì)菌淘汰比率Sr=0.5，驅(qū)散概率Ped=0.3，最大步長Stepmax=4，最小步長Stepmin=0.1．MABC算法、IDPSO算法和BBO-M算法的種群數(shù)量都為N，其他參數(shù)設(shè)置見其相應(yīng)的參考文獻(xiàn)．

圖1 157055原圖像和其直方圖Fig.1 157055 original image and its histograms

圖2 145086原圖像和其直方圖Fig.2 145086 original image and its histograms

4.2 實(shí)驗(yàn)結(jié)果及分析

本實(shí)驗(yàn)首先驗(yàn)證傳統(tǒng)的優(yōu)化算法對于低維多閾值搜索同樣有效；其次考察HBBO算法在高維多閾值彩色圖像分割中搜索性能情況．實(shí)驗(yàn)先對5種算法在4閾值的低維情況下進(jìn)行閾值向量的優(yōu)化搜索，并取其中157055的G顏色分量結(jié)果和145086的B顏色分量結(jié)果進(jìn)行對比說明；再在8閾值和9閾值的高維搜索情況下進(jìn)行討論，并將實(shí)驗(yàn)結(jié)果進(jìn)行對比．目前對于彩色圖像分割，并沒有一個(gè)公認(rèn)的已確定的最優(yōu)閾值組合作為參考標(biāo)準(zhǔn).為數(shù)據(jù)可靠性起見，實(shí)驗(yàn)將5種算法分別獨(dú)立運(yùn)行30次，選其中所得最大的(最優(yōu)的)Tsallis熵值(Vopt)和其對應(yīng)的最優(yōu)閾值(optimal thresholds)組合作為參考標(biāo)準(zhǔn)，如表1所示(d為閾值數(shù)，c表示彩色圖像分量)．

表2列出了5種算法對157055圖像的G顏色分量和145086圖像的B顏色分量在低維4閾值搜索的結(jié)果. 可以看出，在低維多閾值的圖像分割中，5種算法幾乎沒有差別，無論在最大值(max)還是最小值(min)上都搜索到了最優(yōu)的閾值組合，且成功率達(dá)到100%．其實(shí)驗(yàn)數(shù)據(jù)證明，本文提出的HBBO與其他智能優(yōu)化算法BBO-M、IDPSO、MBFO和MABC對于低維多閾值圖像分割都能找到最優(yōu)閾值向量，相比之下無明顯的差別，即5種算法在低維閾值搜索中都是有效的．

表1 兩幅圖像的最優(yōu)Tsallis熵值和其對應(yīng)的最優(yōu)閾值組合
Tab.1 Optimal Tsallis entropy values and their optimal thresholds of the two images

IcdOptimalthresholdsVopt55R861，82，103，124，146，172，197，222283．5503959，80，101，122，143，164，184，205，225432．6283G478，119，159，20641．2001863，88，112，135，158，181，204，227290．3642960，79，99，120，140，160，183，205，227442．3108B823，56，86，113，140，166，193，221362．7357923，50，72，94，117，141，166，193，221567．736786R829，58，89，118，147，177，203，230339．6304927，49，74，99，125，151，178，204，230539．3213G828，52，77，105，133，161，189，220383．5673926，50，76，102，127，153，177，202，226608．0518B433，77，123，17041．7037829，54，77，100，124，149，173，197300．9091922，41，63，85，107，130，153，175，198460．3912

表2 5種優(yōu)化算法對兩幅圖像低維4閾值搜索結(jié)果對比
Tab.2 Comparison among 5 optimization algorithms on two images 4-threshold segmentation

IcmethodstdmeanmaxminNS55GBBO?M2．8908e-1441．200141．200141．200130IDPSO2．8908e-1441．200141．200141．200130MABC2．8908e-1441．200141．200141．200130MBFO2．8908e-1441．200141．200141．200130HBBO2．8908e-1441．200141．200141．20013086BBBO?M041．703741．703741．703730IDPSO041．703741．703741．703730MABC041．703741．703741．703730MBFO041．703741．703741．703730HBBO041．703741．703741．703730

表3列出了5種算法對兩幅圖像R、G、B三種顏色分量的高維8閾值和9閾值搜索結(jié)果．首先對157055圖像的分割結(jié)果分析，從最大值(max)一欄可以看出，對于3種顏色分量，不論8閾值還是9閾值，BBO-M、MABC、MBFO和HBBO都能搜索到最優(yōu)Tsallis熵值，而IDPSO在9閾值的R顏色分量和9閾值的B顏色分量上沒有搜索到最優(yōu)Tsallis熵值，表明了HBBO的尋優(yōu)能力要優(yōu)于IDPSO．最小值(min)一欄的數(shù)據(jù)表明，不管哪一分量，無論是9閾值還是8閾值，HBBO的最小值都優(yōu)于其他4種算法．隨著閾值數(shù)量的增加，雖然5種算法的性能都有所下降，但從成功數(shù)(NS)一欄表明，HBBO的成功數(shù)遠(yuǎn)高于其他4種算法，尤其是在除8閾值的R顏色分量和9閾值的B顏色分量外都獲得了30次成功，成功率達(dá)100%，在8閾值的R顏色分量和9閾值的B顏色分量上成功率也達(dá)到了85%以上，總體來看，成功率次優(yōu)的是BBO-M，其他算法的成功率都較低．從平均值(mean)一欄可以看出，對于3種顏色分量，不論8閾值還是9閾值，HBBO的平均值都是最好的，再次證明了HBBO具有優(yōu)秀的搜索能力．每一行最大值與最小值的差及標(biāo)準(zhǔn)差(Std)一欄的數(shù)據(jù)表明了5種算法的穩(wěn)定性，而這些結(jié)果中HBBO總是最小，尤其是在9閾值的R和G顏色分量及8閾值的B顏色分量上，HBBO算法優(yōu)勢明顯，精度分別達(dá)到1e-13和1e-14級別，而其他算法最多只達(dá)到1e-2級別，證明了HBBO算法在5種算法中穩(wěn)定性最強(qiáng)．其次對145086圖像的分割結(jié)果進(jìn)行分析，5種算法在R、G、B三種顏色分量的8閾值和9閾值搜索結(jié)果得到與157055圖像分割類似的結(jié)論．

表3 5種優(yōu)化算法對兩幅圖像高維8閾值和9閾值分割搜索結(jié)果對比
Tab.3 Result comparison among 5 optimization algorithms on 2 images 8-threshold and 9-threshold segmentation

cdMethod157055stdmeanmaxminNS145086stdmeanmaxminNSR8BBO?M3．3589e-01283．1670283．5503282．5737102．2726e-00339．0292339．6304330．65069IDPSO3．3901e-01283．1804283．5503282．736631．6180e-00339．2568339．6304330．70921MABC1．4871e-01283．4682283．5503282．873083．6660e-02339．6093339．6304339．527817MBFO3．2074e-01283．2504283．5503282．761323．9601e-02339．5973339．6304339．45704HBBO4．5946e-03283．5485283．5503283．5370261．5199e-04339．6304339．6304339．6298289BBO?M2．4370e-00431．8134432．6283422．847923．6039e-00538．2842539．3213524．894211IDPSO1．5816e-01432．4122432．5587431．658801．0506e-01539．0842539．3051538．83810MABC8．9835e-02432．5359432．6283432．3357105．9203e-02539．2761539．3213539．022211MBFO1．7662e-00432．1558432．6283422．863023．6161e-01539．0939539．3213537．42593HBBO2．3126e-13432．6283432．6283432．6283302．3126e-13539．3213539．3213539．321330G8BBO?M9．9787e-02290．2874290．3642289．9970162．1919e-00382．5570383．5673377．43325IDPSO3．5801e-02290．2615290．3642290．209012．6013e-00382．0693383．5673377．39732MABC6．6530e-02290．1640290．3642290．1479195．6064e-02383．5290383．5673383．359618MBFO3．3228e-01290．2370290．3642288．5085102．1485e-00382．5614383．5673377．40505HBBO0290．3642290．3642290．3642301．1563e-13383．5673383．5673383．5673309BBO?M1．0817e-00441．8680442．3108437．4613131．0846e-00607．4000608．0518602．673714IDPSO8．7729e-02442．1896442．3108441．991731．7763e-01607．6833607．9363607．09200MABC7．4317e-02442．2705442．3108442．044882．4304e-01607．9758608．0518606．897622MBFO9．1453e-02442．2532442．3108441．911762．8284e-01607．8447608．0518606．73324HBBO2．8908e-13442．3108442．3108442．3108301．1563e-13608．0518608．0518608．051830B8BBO?M3．3085e-02362．7211362．7357362．5915241．7837e-00300．3505300．9091291．21834IDPSO4．4679e-02362．6294362．7357362．522612．8435e-02300．8316300．9091300．77661MABC4．0858e-02362．6964362．7357362．5970141．0624e-01300．8329300．9091300．44159MBFO2．1940e-01362．6234362．7357361．7318101．6355e-01300．8025300．9091300．00933HBBO5．7815e-14362．7357362．7357362．7357300300．9091300．9091300．9091309BBO?M1．6007e-00566．3507567．7367561．000882．2391e-00458．6741460．3912453．44173IDPSO1．9026e-00566．0269567．6574560．766902．4417e-00458．4496460．3912454．08951MABC5．0697e-01567．5067567．7367565．180261．0336e-00459．9525460．3912454．83631MBFO1．7945e-00565．8549567．7367560．959211．8660e-00459．0596460．3802452．56170HBBO1．5583e-02567．7327567．7367567．6631282．5070e-02460．3822460．3912460．276625

表4列出了5種算法在兩幅圖像R、G、B3個(gè)顏色分量上的運(yùn)行時(shí)間對比，可以看出HBBO算法總是快于其他4種算法．從平均時(shí)間一欄看出，除HBBO算法外，運(yùn)行速度最快的是MABC算法．

分析上述5種算法的計(jì)算復(fù)雜度，首先從5種算法計(jì)算Tsallis熵目標(biāo)函數(shù)的總評價(jià)次數(shù)(function evaluations, FEs)分析，根據(jù)4.1節(jié)參數(shù)設(shè)置可知，BBO-M、IDPSO和MABC算法在兩幅圖像3種顏色分量上的FEs都約等于10 050次(9閾值分割)和8 430次(8閾值分割)，而MBFO和HBBO算法則通過30次獨(dú)立運(yùn)行實(shí)驗(yàn)實(shí)測平均FEs．

MBFO算法雖然包括5層循環(huán)，但本文設(shè)置參數(shù)既保證其目標(biāo)函數(shù)評價(jià)次數(shù)大致相同，又使優(yōu)化效果最好，在一般情況下MBFO算法的FEs一定大于BBO-M、IDPSO和MABC的FEs，實(shí)測FEs的結(jié)果也驗(yàn)證這種情況．HBBO的改進(jìn)遷移算子的執(zhí)行次數(shù)N/2，其混合的BFO的趨化算子則是在趨化步數(shù)循環(huán)過程中對種群中每個(gè)個(gè)體進(jìn)行游動(dòng)步數(shù)循環(huán)判斷，根據(jù)趨化算子本身的性質(zhì)，并不是每次趨化都一定達(dá)到游動(dòng)的步數(shù)，故趨化算子最大執(zhí)行次數(shù)為Nc*N*Ns/2，最小執(zhí)行次數(shù)為Nc*N/2，HBBO算法的FEs最少．

表4 5種優(yōu)化算法運(yùn)行時(shí)間對比Tab.4 Runnng time comparison among 5 optimization algorithm s

圖3 多閾值分割結(jié)果Fig.3 Multi-threshold segmentation results

綜上所述，HBBO算法達(dá)到了搜索能力強(qiáng)、優(yōu)化精度高、運(yùn)行速度快的目的；在面對高維Tsallis熵多閾值彩色圖像分割問題時(shí)，能夠快速找到最佳閾值向量，圖像分割效果優(yōu)良，說明本文提出的HBBO算法是可行的．

5 結(jié)束語

本文提出一種融合細(xì)菌覓食趨化算子的混合BBO算法，將變異操作融合到遷移算子中，構(gòu)造出改進(jìn)的遷移算子，去掉BBO原有的隨機(jī)變異算子，簡化算法流程的同時(shí)增強(qiáng)了算法全局和局部搜索能力；將原有的精英保留策略改為貪婪選擇方案，進(jìn)一步降低算法的計(jì)算復(fù)雜度；將BFO算法中局部搜索能力強(qiáng)的趨化算子與改進(jìn)的遷移算子融合，進(jìn)一步提高局部搜索能力．將HBBO算法應(yīng)用于高維Tsallis熵多閾值彩色圖像分割，實(shí)驗(yàn)結(jié)果表明，HBBO算法閾值搜索速度快，穩(wěn)定性好，優(yōu)化性能佳，適用于彩色圖像的高維多閾值搜索，也可以推廣到其他優(yōu)化問題中，其在工程領(lǐng)域上也有著良好的應(yīng)用前景．

[1] 田晉躍，王晨陽，李得志．基于遺傳算法的某工程車輛起步特性研究[J]．鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2016，48(2)：121-126．

[2] 張正文，譚文龍，潘甲，等．狼群搜索算法在光伏陣列MPPT中的應(yīng)用[J] ．河南科技大學(xué)學(xué)報(bào)(自然科學(xué)版)，2015，36(5)：57-61．

[3] LIU Y，MU C H，KOU W D，et al．Modified particle swarm optimization-based multilevel thresholding for image segmentation[J]．Soft computing，2015，19(5)：1311-1327．

[4] 張新明，魏峰，牛麗萍，等．混合排名映射概率和混沌搜索的ABC算法[J]．計(jì)算機(jī)科學(xué)，2014，41(2)：102-106．

[5] 儲澤楠，王慶喜．Job-shop調(diào)度問題的離散布谷鳥搜索算法求解[J]．信陽師范學(xué)院學(xué)報(bào)(自然科學(xué)版)，2015，28(3)：442-445．[6] WOLPERT D H，MACREADY W G．No free lunch theorems for optimization[J]．IEEE transactions on evolutionary computation，1997，1(1)：67-82．

[7] SIMON D．Biogeography-based optimization[J]．IEEE transaction on evolutionary computation, 2008，12 (6)：702-713．

[8] 陳基漓．基于高斯變異的生物地理學(xué)優(yōu)化模型[J]．計(jì)算機(jī)仿真，2013，30(7)：292-295．

[9] MA H P，SIMON D．Blended biogeography-based optimization for constrained optimization[J]．Engineering applications of artificial intelligence，2011，24(3)：517-525．

[10] GONG W Y，CAI Z H，LING C X．DE/BBO: a hybrid differential evolution with biogeography-based optimization for global numerical optimization[J]．Soft computing，2011，15(4)：645-665．

[11] 張新明, 孫印杰, 鄭延斌. 二維直方圖準(zhǔn)分的Otsu圖像分割及其快速實(shí)現(xiàn)[J]. 電子學(xué)報(bào), 2011, 39(8): 1778-1784．

[12] CHEN X W，KAR S，RALESCU D A．Cross-entropy measure of uncertain variables[J]．Information sciences，2012，201：53-60．[13] 張新明，張貝，涂強(qiáng)．廣義概率Tsallis的快速多閾值圖像分割[J]．?dāng)?shù)據(jù)采集與處理，2016，31(3)：502-512．

[14] PASSINO K M．Biomimicry of bacterial foraging for distributed optimization and control[J]．Control systems，2002，22(3)：52-67．

[15] BHANDARI A K，KUMAR A，SINGH G K．Modified artificial bee colony based computationally efficient multilevel thresholding for satellite image segmentation using Kapur’s, Otsu and Tsallis functions[J]．Expert systems with application，2015，42(3)：1573-1601．

[16] NIU Q，ZHANG L，LI K．A biogeography-based optimization algorithm with mutation strategies for model parameter estimation of solar and fuel cells[J]．Energy conversion and management，2014，86：1173-1185．

[17] CAO H，KWONG S，YANG J J，et al． Particle swarm optimization based on intermediate disturbance strategy algorithm and its application in multi-threshold image segmentation[J]．Information sciences，2013，250(11)：82-112．

[18] SATHYA P D，KAYALVIZHI R． Modified bacterial foraging algorithm based multilevel thresholding for image segmentation[J]．Engineering application of artificial intelligence，2011，24(4)：595-615．

(責(zé)任編輯：王浩毅)

Hybrid BBO Algorithm Based on Chemotaxis Operator of Bacterial Foraging Algorithm

ZHANG Xinming1,2， KANG Qiang1， TU Qiang1, CHENG Jinfeng1

(1.CollegeofComputerandInformationEngineering,HenanNormalUniversity,Xinxiang453007,China; 2.EngineeringTechnologyResearchCenterforComputingIntelligence&DataMiningof
HenanProvince,Xinxiang453007,China)

A hybrid biogeography-based optimization (HBBO) algorithm based on chemotaxis operator of bacterial foraging algorithm (BFO) was proposed for solving problems in high dimensional multi-level color image thresholding. Firstly, some mutation operations were blended into the original migration operator to get a new migration operator. Secondly, a one-step length chemotaxis operator from BFO was combined with the new migration operator. In addition, a greedy selection method was used to substitute the original elitist selection approach to form a hybrid BBO. Finally, the HBBO algorithm was applied to high dimensional Tsallis entropy multilevel color image thresholding. Experimental results of image segmentation showed that the HBBO obtained more significant optimization performance, faster running speed and stronger stability compared with MABC, IDPSO, MBFO and BBO-M.

intelligent optimization algorithm; biogeography-based optimization algorithm; color image segmentation; multilevel-thresholding segmentation; Tsallis entropy

2016-07-11

河南省重點(diǎn)科技攻關(guān)項(xiàng)目(132102110209)；河南省基礎(chǔ)與前沿技術(shù)研究計(jì)劃項(xiàng)目(142300410295).

張新明(1963—)，男，湖北孝感人，教授，主要從事智能優(yōu)化算法、數(shù)字圖像處理及模式識別研究，E-mail: xinmingzhang@126.com; 通訊作者： 康強(qiáng)(1989—)，男，河南鄭州人，碩士研究生，主要從事智能優(yōu)化算法及數(shù)字圖像處理研究，E-mail: kq890112@qq.com.

張新明，康強(qiáng)，涂強(qiáng)，等．融合細(xì)菌覓食趨化算子的生物地理學(xué)優(yōu)化算法[J] ．鄭州大學(xué)學(xué)報(bào)(理學(xué)版)，2016，48(4)：44-53．

TP18; TP391.41

A

1671-6841(2016)04-0044-10

10.13705/j.issn.1671-6841.2016660