李松陽(yáng)，于海鵬，王 淼

(河南工程學(xué)院 軟件學(xué)院，河南 鄭州 451191)

貓群優(yōu)化(cat swarm optimization，CSO)算法是2006年Chu等[1]基于對(duì)貓群行為的觀察，為解決連續(xù)和單目標(biāo)優(yōu)化問(wèn)題，設(shè)計(jì)并提出的一種新的群體智能算法。貓群優(yōu)化算法采用迭代的方式優(yōu)化問(wèn)題，具有易實(shí)現(xiàn)、能全局搜索、收斂速度較快等優(yōu)點(diǎn)。作為新興的群體智能算法，貓群優(yōu)化算法在國(guó)外引起了眾多研究者的關(guān)注。Pyari等[2]對(duì)貓群優(yōu)化算法進(jìn)行了擴(kuò)展，提出了一種新的多目標(biāo)進(jìn)化算法。Tsai等[3]提出了一種并行貓群優(yōu)化算法，在貓群數(shù)量和迭代次數(shù)較少的條件下實(shí)現(xiàn)快速收斂，并進(jìn)一步研究了增強(qiáng)并行貓群優(yōu)化算法，比如在貓群跟蹤模式中引入田口法(Taguchi method)，提高貓群優(yōu)化算法的收斂速度和全局搜索能力[4]。Tsai等[5]結(jié)合貓群優(yōu)化算法和人工蜂群算法提出了一種混合優(yōu)化算法框架。貓群優(yōu)化算法與其他群體智能算法結(jié)合的混合優(yōu)化算法開(kāi)始發(fā)展起來(lái)。Vivek等[6]提出了一種將貓群優(yōu)化算法、粒子群優(yōu)化算法和遺傳算法結(jié)合的混合算法用于解決情感識(shí)別問(wèn)題。Nanda[7]提出了一種結(jié)合貓群優(yōu)化算法和小波神經(jīng)網(wǎng)絡(luò)(wavelet neural network)的混合算法用于預(yù)測(cè)混沌和非線(xiàn)性時(shí)間序列。Sarswat等[8]提出了一種結(jié)合貓群優(yōu)化算法、遺傳算法、模擬退火算法的混合算法用于解決社交網(wǎng)絡(luò)問(wèn)題。在貓群優(yōu)化算法提出后，眾多學(xué)者針對(duì)該算法也提出了很多改進(jìn)的方法。Sharafi等[9]提出了一種基于貓群優(yōu)化算法的二進(jìn)制離散優(yōu)化方法，大幅提高了0/1背包問(wèn)題的準(zhǔn)確率。Siqueira等[10]提出了一種基于布爾算子的二進(jìn)制貓群優(yōu)化算法 ，在髙維0/1背包問(wèn)題上具有較好的可行性。現(xiàn)實(shí)中，貓群優(yōu)化算法在背板接線(xiàn)問(wèn)題、天線(xiàn)陣綜合等方面有眾多應(yīng)用[11-12]。

在國(guó)內(nèi)，貓群優(yōu)化算法也吸引了眾多研究者。在貓群優(yōu)化算法改進(jìn)方面，楊進(jìn)等[13]在貓群的跟蹤模式中引入交換子和交換序及隨時(shí)間變化的分組率用于求解旅行商問(wèn)題。裴小兵等[14]引入了基于線(xiàn)性混合比率的貓行為模式選擇，依據(jù)迭代次數(shù)合理分配局部搜索和全局搜索的比例。陶亞楠等[15]依據(jù)當(dāng)前迭代次數(shù)和最大迭代次數(shù)的比值來(lái)調(diào)節(jié)貓群優(yōu)化算法的分組率，從而使算法自適應(yīng)性增強(qiáng)。陳超泉等[16]提出了一種具有Logistic函數(shù)特點(diǎn)分組率和慣性權(quán)重的自適應(yīng)方法，該方法對(duì)于貓群優(yōu)化算法來(lái)說(shuō)在收斂速度及求解精度方面都有一定程度的提高。

以上國(guó)內(nèi)外的研究雖然都在一定程度上實(shí)現(xiàn)了貓群優(yōu)化算法的改進(jìn)，但優(yōu)化方向主要集中在算法的分組率、慣性權(quán)重因子和變異率等關(guān)鍵參數(shù)的選擇策略上。由于貓群優(yōu)化算法在迭代時(shí)分為搜尋模式貓群和跟蹤模式貓群，故如果只對(duì)貓群優(yōu)化算法中分組率即貓群劃分策略進(jìn)行改進(jìn)，雖然能改善其性能，但兩種行為模式貓群間的交流也會(huì)影響該算法的收斂能力，并且每只貓的學(xué)習(xí)模式固定，對(duì)算法性能的提升有限[17]。

本研究提出了一種基于子群信息交互的改進(jìn)貓群優(yōu)化算法(IICSO)。該算法采用動(dòng)態(tài)分組策略調(diào)整分組率，從而實(shí)現(xiàn)搜尋模式貓群和跟蹤模式貓群的動(dòng)態(tài)調(diào)整。在迭代過(guò)程中搜尋模式貓群和跟蹤模式貓群需要交流學(xué)習(xí)，充分發(fā)揮不同貓群優(yōu)勢(shì)，使算法具有了良好的全局探索能力和較快的收斂速度。最后，通過(guò)10個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)驗(yàn)證了該算法在收斂速度和尋優(yōu)精度方面都具有顯著優(yōu)勢(shì)。

1 改進(jìn)的貓群優(yōu)化算法

1.1 原始貓群優(yōu)化算法流程

貓群優(yōu)化算法是一種模仿貓群生活習(xí)性的智能算法。貓群有跟蹤和搜尋兩種不同的行為模式。搜尋模式下的貓大部分時(shí)間在休息，同時(shí)也在觀察周?chē)h(huán)境，總是保持警覺(jué)；跟蹤模式下的貓發(fā)現(xiàn)獵物后，在追逐目標(biāo)時(shí)會(huì)快速移動(dòng)。

在貓群優(yōu)化算法中，每只貓對(duì)應(yīng)了待優(yōu)化問(wèn)題的一個(gè)解。每只貓都有自身的適應(yīng)值、標(biāo)志和位置。適應(yīng)值用來(lái)評(píng)價(jià)貓群中每只貓位置的好壞，標(biāo)志用來(lái)區(qū)分每只貓的跟蹤和搜尋行為模式。對(duì)于第i只貓來(lái)說(shuō)，其位置Pi是定義在解空間中的一個(gè)N維向量，pij表示第i只貓位置Pi的第j個(gè)維度。位置Pi的每一維(pij)有自身的速度(vij)，則vij構(gòu)成的N維向量組成了第i只貓的速度Vi：

Pi=|pij|，j=1，2，…，N，

(1)

Vi=|vij|，j=1，2，…，N。

(2)

貓群優(yōu)化算法的基本流程如圖1所示。在N維解空間中，通過(guò)隨機(jī)的方式設(shè)置每只貓的位置和速度，形成一定數(shù)量的貓群。初始化貓群的分組率等參數(shù)，計(jì)算每只貓的適應(yīng)值，并記錄最優(yōu)適應(yīng)值到pbest中。根據(jù)分組率將貓群隨機(jī)劃分為跟蹤和搜尋兩種行為模式。根據(jù)貓的標(biāo)志，對(duì)跟蹤行為模式的貓執(zhí)行跟蹤流程，對(duì)搜尋行為模式的貓執(zhí)行搜尋流程。待跟蹤流程和搜尋流程結(jié)束后，計(jì)算每只貓的適應(yīng)值，并記錄最優(yōu)適應(yīng)值到pl中。比較pbest和pl的大小，更新pbest。若滿(mǎn)足結(jié)束條件，則終止算法，否則重新分組迭代。

圖1 貓群優(yōu)化算法流程Fig.1 Cat swarm optimization algorithm flow chart

1.2 跟蹤模式流程

在跟蹤行為模式下，貓發(fā)現(xiàn)獵物后會(huì)快速移動(dòng)，向目標(biāo)靠近。跟蹤模式是對(duì)貓追蹤目標(biāo)時(shí)一系列行為的建模，每只貓會(huì)調(diào)整移動(dòng)速度從而調(diào)整位置，持續(xù)朝著目標(biāo)移動(dòng)。

跟蹤流程如下：

(1)更新處于跟蹤模式的第i只貓的速度vij：

vij=ω×vij+rand×c×(pbestj-pij)，j=1，2，…，N，

(3)

式中：pbestj為貓群中最優(yōu)適應(yīng)值貓的位置的第j維；ω為慣性權(quán)重因子；rand為均勻分布在[0,1]的隨機(jī)數(shù)；c為事先確定的0～2的常數(shù)。

(2)如果設(shè)置了貓群優(yōu)化算法貓速度區(qū)間，則檢查更新后的貓速度有沒(méi)有超出預(yù)先設(shè)定的速度范圍。

(3)更新處于跟蹤模式的第i只貓的位置pij：

pij=pij+vij，j=1，2，…，N。

(4)

1.3 搜尋模式流程

在搜尋行為模式中，貓大部分時(shí)間在休息，但也在觀察周?chē)h(huán)境，總是保持警覺(jué)。如果想移動(dòng)位置，貓?jiān)谟^察周?chē)h(huán)境后，總是小心翼翼非常緩慢地移動(dòng)到新位置。貓群搜尋模式是模擬貓四處搜索并尋找下一個(gè)位置的模型，它有3個(gè)關(guān)鍵參數(shù)，即記憶池、變異率、變化數(shù)。

記憶池：用SMP表示，定義每一只貓的搜尋記憶大小，用來(lái)存放此貓搜索過(guò)的能夠記憶的所有位置點(diǎn)。

變異率：用SRD表示，定義貓位置變化時(shí)每一維能夠變化的范圍。

變化數(shù)：用CDC表示，定義貓位置變化時(shí)可以發(fā)生變異的維度數(shù)目，該數(shù)目不能大于解空間維度N。

搜尋流程如下：

(1)處于搜尋模式的第i只貓，把該貓復(fù)制K份到SMP(K=SMP)。

(2)K份副本中，保留其中1份副本不變，其余K-1份副本根據(jù)第i只貓的CDC值，隨機(jī)選擇與CDC值數(shù)目相同的維數(shù)進(jìn)行位置變異：

pij=(1±SRD)*pij，pij∈pi。

(5)

(3)更新計(jì)算SMP中每個(gè)副本的適應(yīng)值。

(4)從K份副本中，選擇適應(yīng)值最優(yōu)的副本替換第i只貓的位置，從而實(shí)現(xiàn)貓對(duì)空間的搜索與位置更新。

1.4 分組率動(dòng)態(tài)調(diào)整策略

貓群優(yōu)化算法中分組率是十分重要的參數(shù)，是貓群中執(zhí)行跟蹤模式的貓占貓群的比例，能極大地影響算法的開(kāi)拓和搜尋能力。分組率(MR)動(dòng)態(tài)調(diào)整策略見(jiàn)公式(6)：

(6)

式中：MRmax是分組率最大值；MRmin是分組率最小值；iter表示當(dāng)前的迭代次數(shù)；MaxIt為最大迭代次數(shù)；a1和a2是調(diào)節(jié)因子，控制MR的變化速度。

圖2展示了a1和a2不同取值時(shí)MR的變化情況：在迭代前期MR變化較為平緩，有較多的貓被劃分為跟蹤行為模式，提高了全局搜索能力；在迭代中后期，MR快速降低，有較多的貓被劃分為搜尋行為模式，提升了算法的局部搜索能力。

圖2 MR變化情況Fig.2 Change of MR

1.5 子貓群信息交互策略

將整個(gè)貓群依據(jù)MR動(dòng)態(tài)劃分為兩種行為模式后，不同行為模式貓群之間的信息交互也影響著算法效果。在圖1展示的貓群優(yōu)化算法流程中，執(zhí)行搜尋模式的貓和執(zhí)行跟蹤模式的貓，它們的信息交互依賴(lài)于整個(gè)貓群最優(yōu)適應(yīng)值貓位置的更新，兩種行為模式貓群之間不存在其他交互方式。本研究采用Rao等[18]提出的教與學(xué)優(yōu)化算法強(qiáng)化兩個(gè)貓群互相交流學(xué)習(xí)。首先比較兩種行為模式貓群適應(yīng)度值大小，擁有較優(yōu)適應(yīng)度的貓群為優(yōu)秀貓群，另一個(gè)為普通貓群；然后從優(yōu)秀貓群中隨機(jī)挑選一個(gè)學(xué)習(xí)貓(Pl)，普通貓群中所有貓使用教與學(xué)優(yōu)化算法學(xué)習(xí)階段的規(guī)則向?qū)W習(xí)貓(Pl)學(xué)習(xí)，并產(chǎn)生新后代。學(xué)習(xí)方法如下：

(7)

式中：符號(hào)f(Pi)表示第i個(gè)貓的適應(yīng)值；plj表示學(xué)習(xí)貓(Pl)位置向量的第j維；pij表示第i個(gè)貓(Pi)位置的第j維；γ為學(xué)習(xí)因子，是[0,1]的隨機(jī)數(shù)。從公式(7)可以看出當(dāng)學(xué)習(xí)貓(Pl)的適應(yīng)值小于普通貓群中第i個(gè)貓的適應(yīng)值時(shí)，第i個(gè)普通貓會(huì)遠(yuǎn)離學(xué)習(xí)貓(Pl)；當(dāng)學(xué)習(xí)貓(Pl)的適應(yīng)值大于等于普通貓群中第i個(gè)貓的適應(yīng)值時(shí)，第i個(gè)普通貓會(huì)靠近學(xué)習(xí)貓(Pl)。 學(xué)習(xí)結(jié)束后采用公式(4)計(jì)算普通貓的新位置。當(dāng)新位置的適應(yīng)值優(yōu)于原位置時(shí)，普通貓移動(dòng)到新位置，否則不移動(dòng)。

1.6 改進(jìn)的貓群優(yōu)化(IICSO)算法流程

步驟1： 初始化貓群及控制參數(shù)。

步驟2： 計(jì)算貓群中每個(gè)貓的適應(yīng)值，同時(shí)更新此時(shí)的全局最優(yōu)解pbest。

步驟3： 利用公式(6)計(jì)算分組率MR。 按照MR將貓群隨機(jī)分為兩部分,一部分執(zhí)行搜尋流程， 另一部分執(zhí)行跟蹤流程。

步驟4： 執(zhí)行搜尋流程，更新搜尋行為模式貓的位置；執(zhí)行跟蹤流程，更新跟蹤行為模式貓的速度和位置。

步驟5： 兩種行為模式貓群之間交流，普通貓群向優(yōu)秀貓群中的學(xué)習(xí)貓Pl學(xué)習(xí)并產(chǎn)生后代，更新普通貓的速度，并依據(jù)公式(4)計(jì)算普通貓位置，判斷普通貓是否滿(mǎn)足移動(dòng)到新位置的條件，如滿(mǎn)足則移動(dòng)，否則不移動(dòng)。

步驟6： 計(jì)算每只貓的適應(yīng)值，并記錄最優(yōu)適應(yīng)值到pl中。 比較pbest和pl的大小，更新pbest。 若滿(mǎn)足結(jié)束條件，則終止算法，否則重復(fù)步驟3重新分組迭代。

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

2.1 算法設(shè)置

為了充分比較CSO算法、ADSCSO算法與IICSO算法的求解精度和收斂速度，對(duì)這3種算法使用10個(gè)代表廣泛的標(biāo)準(zhǔn)測(cè)試函數(shù)進(jìn)行驗(yàn)證，測(cè)試函數(shù)范圍限制和算法參數(shù)設(shè)置分別見(jiàn)表1和表2。這3種算法的機(jī)器配置為Windows 10操作系統(tǒng)，CPU為Intel(R) Core(TM) i7- 4700MQ 2.40 GHz，內(nèi)存為8.00 GB。數(shù)據(jù)分析采用MATLAB R2020b軟件。

表1 測(cè)試函數(shù)的數(shù)學(xué)描述Tab.1 Mathematical description of test function

表1(續(xù))

表2 不同算法參數(shù)設(shè)置Tab.2 Parameter settings of different algorithms

如表1所示，F(xiàn)1～F2函數(shù)屬于板狀函數(shù)(plate-shape)，除全局極小值外不存在局部極小值。F3～F6函數(shù)具有較多的局部極小值(many local minima)，使算法有陷入局部極小值的風(fēng)險(xiǎn)。F7函數(shù)是碗狀(bowl-shaped)的，除全局極小值外，還具有與解空間維數(shù)相同的局部極小值，具有連續(xù)的、凸的和單峰的特征。F8函數(shù)是山谷狀(valley-shaped)的，具有單峰，全局最小值位于一個(gè)狹窄的山谷。F9函數(shù)是單峰陡峭形態(tài)(steep drops-shaped)的，全局極小值相對(duì)于搜索空間的面積很小。F10函數(shù)具有多峰，在輸入域的拐角處有尖峰等特征。

所有算法的相關(guān)參數(shù)如表2所示。對(duì)于所有算法，群體大小設(shè)置為 100，最大迭代次數(shù)是500。 每種算法在實(shí)驗(yàn)中獨(dú)立運(yùn)行20次，統(tǒng)計(jì)每個(gè)算法的測(cè)試函數(shù)平均值、標(biāo)準(zhǔn)差和最優(yōu)值。平均值能夠體現(xiàn)出算法的收斂能力，標(biāo)準(zhǔn)差能夠體現(xiàn)出算法的穩(wěn)定性。

2.2 結(jié)果與分析

表3為CSO算法、 ADSCSO算法與IICSO算法的對(duì)比結(jié)果。其中，平均值和標(biāo)準(zhǔn)差由20次獨(dú)立運(yùn)行后獲得，黑體字表示算法獲得的值在對(duì)應(yīng)測(cè)試函數(shù)上是最好的。從表3可以看出,在板狀函數(shù)F1、F2上，IICSO算法在高維測(cè)試函數(shù)F2(解空間20維)上的性能明顯優(yōu)于其他兩種算法，但在低維測(cè)試函數(shù)F1上(解空間2維)，CSO算法更具有優(yōu)勢(shì)。在具有較多局部極小值特征的測(cè)試函數(shù)F3～F6和F10上，IICSO算法也具有明顯優(yōu)勢(shì)。在函數(shù)F3、F10上，IICSO算法的平均值、標(biāo)準(zhǔn)差和最優(yōu)值都是最好的。在函數(shù)F6上，IICSO算法的平均值是最好的，其最優(yōu)值搜索到了函數(shù)F6的理論值。在函數(shù)F4上雖然ADSCSO算法的平均值和標(biāo)準(zhǔn)差都優(yōu)于其他算法，但I(xiàn)ICSO算法的最優(yōu)值也搜索到了函數(shù)F4的理論值。在函數(shù)F5上，3種算法各有優(yōu)勢(shì)，其中CSO算法的標(biāo)準(zhǔn)差最優(yōu)，ADSCSO算法的平均值最優(yōu)，IICSO算法能夠搜索到最優(yōu)的最小值。在碗狀函數(shù)F7上， IICSO算法的平均值、標(biāo)準(zhǔn)差和最優(yōu)值都優(yōu)于其他兩種算法。在山谷狀函數(shù)F8和陡峭形態(tài)函數(shù)F9上， IICSO算法的平均值和標(biāo)準(zhǔn)差明顯比其他兩種算法更有優(yōu)勢(shì)。綜上所述，IICSO算法與其他兩種算法相比，針對(duì)不同類(lèi)型的測(cè)試函數(shù)具有更好的收斂性能和優(yōu)化精度。

表3 CSO算法、ADSCSO算法和IICSO算法對(duì)比Tab.3 Comparisons of CSO、ADSCSO and IICSO algorithm

圖3分別展示了CSO算法、ADSCSO算法和IICSO算法在10個(gè)不同測(cè)試函數(shù)下的適應(yīng)值變化情況。為了清晰地比較3種算法，除測(cè)試函數(shù)F9外，其余測(cè)試函數(shù)適應(yīng)值變化的縱軸采用對(duì)數(shù)處理后的數(shù)量級(jí)。從圖3可以看出:對(duì)于測(cè)試函數(shù) F1、F3、F8、F9、F10來(lái)說(shuō)，IICSO算法的收斂速度和收斂精度都優(yōu)于其他兩種算法;對(duì)于測(cè)試函數(shù) F6、F7來(lái)說(shuō)，雖然IICSO算法前期收斂速度相對(duì)緩慢，但在中后期收斂速度加快，并且在收斂精度上也比其他兩種算法有優(yōu)勢(shì);對(duì)于測(cè)試函數(shù)F2、F4、F5來(lái)說(shuō)，雖然IICSO算法的收斂速度不占優(yōu)勢(shì)，但在最優(yōu)值搜尋中具有一定優(yōu)勢(shì)。從圖3還可以看出，無(wú)論是針對(duì)高維還是低維搜索空間，無(wú)論是針對(duì)板狀函數(shù)還是多局部極小值、碗狀、山谷狀測(cè)試函數(shù)，IICSO算法都能在全局搜索后以較快的收斂速度尋到較優(yōu)解，優(yōu)于ADSCSO算法和CSO算法，從而驗(yàn)證了IICSO算法在收斂速度和收斂精度方面的優(yōu)勢(shì)。

圖3 適應(yīng)值變化對(duì)比Fig.3 Comparisons of fitness change

3 結(jié)語(yǔ)

針對(duì)貓群優(yōu)化算法兩種行為模式貓群間缺乏交流而影響算法收斂速度和收斂精度的問(wèn)題，本研究提出了一種基于兩種行為模式貓群之間信息交互的貓群優(yōu)化算法。該算法采用動(dòng)態(tài)分組方案調(diào)整貓群的分組率，利用教與學(xué)優(yōu)化算法的學(xué)習(xí)階段實(shí)現(xiàn)不同貓群之間的交流學(xué)習(xí)。在10個(gè)測(cè)試函數(shù)上對(duì)CSO算法、ADSCSO算法和本研究的IICSO算法進(jìn)行對(duì)比分析，發(fā)現(xiàn)兩種行為模式貓群之間的信息交互提升了算法的全局搜索能力和收斂速度。