張嘯宇, 方忠慶, 杜 義, 孔維賓, 王玉婷, 程子耀
(鹽城工學院信息工程學院, 江蘇 鹽城 224051)
元啟發(fā)式算法是一類獨立于問題的優(yōu)化算法,能夠有效探索一個搜索空間并找到全局最優(yōu)解。這類算法主要通過模擬自然界優(yōu)勝劣汰的規(guī)律以及生物行為,實現(xiàn)種群的整體進步,最終求解最優(yōu)解。典型算法有遺傳算法(GA)[1]、差分進化算法(DE)[2]、粒子群算法(PSO)[3]、灰狼算法(GWO)[4]、鯨魚優(yōu)化算法(WOA)[5]、金豺狼優(yōu)化算法(GJO)[6]等。
按閾值對圖像分割是一種常用的圖像分割方法,目前國內(nèi)外已經(jīng)有很多學者將元啟發(fā)式算法用于圖像的閾值分割優(yōu)化中。KHAIRUZZAMAN等[7]將灰狼優(yōu)化算法應(yīng)用于圖像的多級閾值分割,取得了很好的效果。于洋等[8]為了解決紅外相機采集行人圖片時圖像分割效果問題,提出一種自適應(yīng)粒子群優(yōu)化二維OSTU的閾值分割算法,能夠快速且準確地得到最佳閾值,提高了圖像預(yù)處理的分割效果。UPADHYAY等[9]將Kapur熵作為適應(yīng)度函數(shù),并通過烏鴉搜索算法求得最大Kapur熵,達到最優(yōu)閾值。
非洲禿鷲算法(AVOA)[10]是受非洲禿鷲覓食和導航行為啟發(fā)而提出的高性能智能算法,具有求解精度高的優(yōu)點,但其全局搜索能力弱、易陷入局部。本文通過分段線性混沌映射(PWLCM)進行種群初始化,增強種群多樣性;在全局搜索階段引入β分布更好地控制種群在搜索空間上的重新劃分;提出了新的基于饑餓率的全局搜索策略,用于增強算法搜索能力。將改進算法運用在二維Otsu圖像閾值分割任務(wù)中取得了不錯的效果。
非洲禿鷲優(yōu)化算法(AVOA)是通過對非洲禿鷲的覓食行為和生活習慣進行模擬和建模而提出的。在AVOA中,非洲禿鷲的生活習慣和覓食行為主要包括以下4個階段。
初始化種群后首先計算種群的適應(yīng)度,其次選擇最優(yōu)個體為最優(yōu)禿鷲,選擇次優(yōu)個體作為次優(yōu)禿鷲。每次的最佳禿鷲會在這兩個個體中通過如下公式計算產(chǎn)生,同時在每次更新迭代后重新計算整個總體。
(1)
其中,L1和L2為搜索操作之前給定的參數(shù),其值介于0~1且兩個參數(shù)之和為1。選擇最優(yōu)解的概率pi使用如下公式的輪盤賭方式獲得,并為每組選擇最優(yōu)解。
(2)
禿鷲的饑餓率由如下公式計算得出:
(3)
(4)
其中,F表示禿鷲的饑餓率,l表示當前的迭代次數(shù),maxiterations表示最大迭代次數(shù),z為介于-1~1且每代變化的隨機數(shù),h是介于-2~2的隨機數(shù),rand1是介于0~1的隨機數(shù)。
同時,當F的絕對值大于1時,算法進入探索階段;當F的值小于或等于1時,算法進入開發(fā)階段。
AVOA的探索階段禿鷲有兩種不同的搜索策略,在兩組最佳禿鷲之一的周圍區(qū)域?qū)ふ沂澄锖透鶕?jù)其饑餓程度在環(huán)境中隨機搜索。
P(i+1)=R(i)-D(i)×F
(5)
D(i)=|X×R(i)-P(i)|
(6)
公式(5)模擬了在兩組最佳禿鷲之一的周圍區(qū)域?qū)ふ沂澄?其中P(i+1)為下一次迭代的位置,F是由公式(4)計算得出的禿鷲的饑餓率,R(i)是由公式(1)給出的最佳禿鷲,D(i)為到兩組最佳禿鷲之一的隨機距離,通過公式(6)計算得到。在公式(6)中,R(i)是由公式(1)給出的最佳禿鷲。X被用作增加隨機運動的系數(shù)向量,由X=2×rand計算得到,其中rand為介于0~1的隨機數(shù)。P(i)為當前禿鷲的位置。
P(i+1)=R(i)-F+rand2×((ub-lb)×rand3+lb)
(7)
公式(7)模擬了禿鷲根據(jù)其饑餓程度在環(huán)境中隨機搜索,其中rand2是介于0~1的隨機值,lb和ub表示變量的上界和下界,rand3是用于增加隨機性的系數(shù)。
這兩種策略會根據(jù)P1的值進行選擇,P1是介于0~1的數(shù)。設(shè)randP1為介于0~1的隨機數(shù)。如果randP1的值小于或等于P1,則使用公式(5),反之,使用公式(7)。
1.4.1 開發(fā)(第一階段)
當F的絕對值介于0.5~1時,AVOA進入開發(fā)階段的第一階段。在開發(fā)階段的第一階段,執(zhí)行緩慢圍攻和旋轉(zhuǎn)飛行兩種不同的策略。
(1)緩慢圍攻:當|F|≥0.5時,禿鷲相對能量充足。當許多禿鷲聚集在一個食物源上時,會在食物獲取上引起嚴重的沖突。身體強壯的禿鷲不喜歡分享食物,而弱小的禿鷲試圖聚集并引發(fā)小沖突以便獲取食物,如下兩個公式模擬了這兩個過程。
P(i+1)=D(i)×(F+rand4)-d(t)
(8)
d(t)=R(i)-P(i)
(9)
公式(8)中,D(i)為到兩組最佳禿鷲之一的隨機距離,通過公式(6)計算得出,rand4為介于0~1的隨機值。公式(9)中,R(i)是在當前迭代中使用公式(1)選擇的最佳禿鷲。
(2)旋轉(zhuǎn)飛行:禿鷲經(jīng)常進行旋轉(zhuǎn)飛行,可用于模擬螺旋運動。所有禿鷲與最佳和次佳禿鷲中的一只建立了一個螺旋方程,公式如下所示:
(10)
(11)
P(i+1)=R(i)-(S1+S2)
(12)
其中,rand5和rand6是介于0~1的隨機數(shù),最后通過公式(12)更新禿鷲的位置。
這兩種策略會根據(jù)P2的值進行選擇,P2是介于0~1的數(shù)。設(shè)randP2為介于0~1的隨機數(shù)。如果randP2的值小于或等于P2,則根據(jù)公式(8)實施緩慢圍攻策略,反之,使用公式(12)執(zhí)行旋轉(zhuǎn)飛行策略。
1.4.2 開發(fā)(第二階段)
當|F|<0.5時,AVOA進入開發(fā)階段的第二階段,禿鷲開始進行聚集圍攻和爭奪食物。
(1)幾種禿鷲在食物源上的聚集。
描述禿鷲這種運動的公式如下所示:
(13)
(14)
(15)
公式(13)和公式(14)中,BestVulture1(i)是當前迭代中第一組的最佳禿鷲,BestVulture2(i)是當前迭代中第二組的最佳禿鷲。用公式(15)計算得到下一代禿鷲的位置P(i+1)。
(2)對食物的激烈競爭。
當|F|<0.5時,領(lǐng)頭的禿鷲變得饑餓和虛弱,沒有足夠的能量對抗其他禿鷲。而其他禿鷲會從不同方向朝著領(lǐng)頭禿鷲的位置移動,可以使用如下公式模擬該現(xiàn)象:
P(i+1)=R(i)-|d(t)|×F×Levy(d)
(16)
其中,d(t)表示禿鷲與兩組中最佳禿鷲之間的距離,該距離通過公式(9)計算得出。萊維飛行機制用于提高公式(16)中AVOA算法的有效性,萊維飛行生成的隨機分量用以下公式計算。
(17)
其中
(18)
公式(17)、公式(18)中,α為固定值1.5。u和v服從正態(tài)分布:
(19)
第二階段的兩種策略會根據(jù)P3的值進行選擇,P3是介于0~1的數(shù)。設(shè)randP3是介于0~1的隨機數(shù),如果randP3小于或等于P3,則根據(jù)公式(15)更新位置;反之由公式(16)實施對食物的激烈競爭。
針對非洲禿鷲算法全局搜索能力不足、局部搜索策略冗余及收斂速度慢等缺點,β-PAVOA主要做了以下改進。
混沌映射是生成混沌序列的一種方法,被廣泛地應(yīng)用于各種算法中。PWLCM[11]作為混沌映射的典型代表,其數(shù)學形式簡單,具有遍歷性和隨機性。如圖1所示,PWLCM在空間中的分布非常均勻。
(a)PWLCM混沌映射圖
通過PWLCM初始化種群,可以使β-PAVOA在初始化種群時更好地搜索整個解空間。PWLCM映射的描述如公式(20)所示:
(20)
公式(20)中,PZ=0.4,如果t≥2,則z(t)值可根據(jù)公式(20)計算得到,如果t=1,則z(1)為映射的初始值,z(1)取值是介于0~1的隨機數(shù)。
將生成的值映射到解空間,如下公式所示:
P(i)=(ub-lb)×z(i)+lb
(21)
其中,P(i)是映射后的種群位置,ub和lb分別是位置的上界和下界,z(i)是由公式(20)得到介于0~1的混沌映射隨機值。
β分布[12]是指一組定義在區(qū)間[0,1]的連續(xù)概率分布。在使用元啟發(fā)式算法解決工程問題時,將β分布用于其中很有效,它可以近似模擬包括正態(tài)高斯分布在內(nèi)的幾種分布,也允許近似線性或指數(shù)遞減的分布,可以是一維的,也可以是多維。一維β分布表達式如下:
(22)
(23)
其中,通過改變參數(shù)p和q就可以得到可能的β分布的多樣性?;讦路植嫉娜衷鰪娝阉鞑呗匀绻?24)所示:
P(i+1)=(ub-lb)×betarand+lb
(24)
其中,P(i+1)為更新后的位置,betarand是p=1、q=1的情況下生成的β隨機數(shù)。
在測試過程中發(fā)現(xiàn),AVOA在探索階段的全局搜索表現(xiàn)不佳,因此提出了基于禿鷲饑餓率的改進搜索策略如公式(25)所示,用于改善這一問題。
P(i+1)=(rand-F)×X(randi(1,pop_size))
(25)
其中,P(i+1)為更新后的位置,rand為介于0~1的隨機值。X為種群的歷史最優(yōu)位置,randi(1,pop_size)為1至種群大小之間的隨機整數(shù)值。
β-PAVOA針對局部搜索策略冗余、收斂慢的缺點,對開發(fā)階段策略進行了精簡,整個開發(fā)階段只使用AVOA在開發(fā)階段的第二階段中的更新策略,rand是介于0~1的隨機數(shù)。如果rand小于0.3,則根據(jù)公式(15)更新位置;反之由公式(16)實施對食物的激烈競爭。β-PAVOA的算法流程如圖2所示。
β-PAVOA在8個基準測試函數(shù)上進行了測試,選取了非洲禿鷲算法(AVOA)、金豺狼優(yōu)化算法(GJO)、灰狼算法(GWO)、鯨魚優(yōu)化算法(WOA)和粒子群算法(PSO)作為對比算法。測試函數(shù)分為兩類:F1~F4為單峰函數(shù),F5~F8為多峰函數(shù),測試函數(shù)設(shè)置見表1,算法默認參數(shù)設(shè)置見表2。將測試結(jié)果進行秩和檢驗,確定β-PAVOA獲得結(jié)果的平均值與對比算法之間是否存在顯著差異,當ρ>0.05時,認為β-PAVOA與對比算法的尋優(yōu)性能相當。種群大小設(shè)置為50,最大迭代次數(shù)為1 000次,測試維度為30。為了減少不確定性,每個測試獨立進行30次,計算30次測試的平均數(shù)和方差。實驗是在配備32 GB RAM與i7-12700H處理器的個人計算機上進行的。
表1 測試函數(shù)設(shè)置Tab.1 Benchmark function settings
表2 算法參數(shù)設(shè)置Tab.2 Algorithm parameter settings
β-PAVOA與其他算法的測試結(jié)果見表3和表4。在F1~F8上,β-PAVOA展現(xiàn)出了極強的優(yōu)勢,從表3和表4中可以看出,相比其他算法在F3、F4、F7、F8上的測試結(jié)果,β-PAVOA有著領(lǐng)先幾個量級的精度,在F1、F2、F5、F6上的測試結(jié)果相近的情況下,其穩(wěn)定性有著明顯的優(yōu)勢。同時,從圖3和圖4中的算法收斂曲線可以明顯看出,β-PAVOA在F1~F8上的收斂精度與收斂速度均優(yōu)于其他算法。
表3 各類算法在 F1~F4上的測試結(jié)果Tab.3 Test results of various algorithms on F1~F4
表4 各類算法在F5~F8上的測試結(jié)果Tab.4 Test results of various algorithms on F5~F8
(a)F1函數(shù)的收斂對比曲線
(b)F2函數(shù)的收斂對比曲線
(c)F3函數(shù)的收斂對比曲線
(d)F4函數(shù)的收斂對比曲線圖3 不同算法的F1~F4收斂曲線對比Fig.3 Comparison of convergence curves of different algorithms on F1~F4
(a)F5函數(shù)的收斂對比曲線
(b)F6函數(shù)的收斂對比曲線
(c)F7函數(shù)的收斂對比曲線
(d)F8函數(shù)的收斂對比曲線圖4 不同算法的F5~F8收斂曲線對比Fig.4 Comparison of convergence curves of different algorithms on F5~F8
Otsu閾值分割常用于圖像二值化或閾值化[13]。圖像閾值化是將灰度圖像轉(zhuǎn)換為二值圖像的過程,其中每個像素根據(jù)特定的閾值被賦予黑色或白色值。Otsu閾值分割法簡單高效,適用于分割、目標檢測和特征提取[14]。Otsu閾值分割法在具有雙峰直方圖的圖像上效果最好,即圖像中有清晰的表示背景和前景像素強度的峰值。對于具有更復雜分布的圖像,其他閾值化方法或更高級的技術(shù)可能更合適。
Otsu閾值分割法是找到能夠使類間方差最大化的閾值,從而有效地將像素分為兩個類別:前景和背景。類間方差測量兩個類之間的擴展或可分性,并根據(jù)圖像中的像素強度和概率計算。
假設(shè)圖形大小為M×N,圖像灰度范圍為[0,L-1],ni為圖像灰度級i的像素點數(shù),則灰度級i出現(xiàn)的概率為pi=ni/(M×N)。在單閾值分割模型中,圖像被分割成兩類,其中C0類像素點灰度級為[0,T],C1類像素點灰度級為[T+1,L-1]。P0(T)、P1(T)分別為C0、C1出現(xiàn)的概率,u0(T)、u1(T)分別為C0、C1的平均灰度級,由如下公式計算得出:
(26)
(27)
(28)
(29)
(30)
(32)
(33)
(34)
(35)
(36)
(37)
圖像的類間方差用公式(36)表示,公式(37)則是最終的目標函數(shù)。
在二維Otsu模型測試中測試了β-PAVOA及對比算法的性能表現(xiàn),測試選取了2張常用測試圖片與1張內(nèi)容復雜的圖片(如圖5所示)。測試結(jié)果如圖6所示,β-PAVOA在找到最優(yōu)解時,收斂速度與穩(wěn)定性相比其他算法有明顯的優(yōu)勢,這也驗證了優(yōu)化策略的有效性。
(a)相機
(b)人像
(c)月球圖5 測試用圖Fig.5 The text pictures
(a)相機二維Otsu測試結(jié)果
(b)相機二維Otsu模型迭代曲線
(d)人像二維Otsu模型迭代曲線
(e)月球二維Otsu測試結(jié)果
(f)月球二維Otsu模型迭代曲線圖6 測試結(jié)果圖Fig.6 The test results graph
本文提出了一種基于PWLCM與β分布的非洲禿鷲算法β-PAVOA。首先,通過PWLCM擴大種群在解空間的覆蓋程度,提高尋優(yōu)能力。其次,使用基于β分布的全局增強搜索策略增強算法的全局搜索能力?;陴囸I率F的改進搜索策略進一步增強了全局搜索能力。最后,通過簡化局部搜索策略提升局部收斂速度。為了驗證β-PAVOA的有效性,通過8個基準測試函數(shù)和二維Otsu圖像閾值分割模型與非洲禿鷲算法(AVOA)、金豺狼優(yōu)化算法(GJO)、灰狼算法(GWO)、鯨魚優(yōu)化算法(WOA)和粒子群算法(PSO)進行對比實驗,采用均值、標準差與秩和檢驗方法進行評估。結(jié)果表明,β-PAVOA算法在探索能力和求解精度上都有顯著優(yōu)勢。