曾 冰， 王夢(mèng)雨， 高 亮， 董昊臻

(華中科技大學(xué) 機(jī)械科學(xué)與工程學(xué)院，湖北 武漢 430074)

0 引言

當(dāng)前，群體智能優(yōu)化算法在工程優(yōu)化問(wèn)題中的應(yīng)用日益廣泛，特別是針對(duì)NP-hard問(wèn)題，比如車間調(diào)度問(wèn)題[1-2]、WSNs分簇問(wèn)題[3-4]以及多處理器調(diào)度問(wèn)題[5]等.這些工程優(yōu)化問(wèn)題通常是多峰優(yōu)化問(wèn)題，即它們的目標(biāo)函數(shù)通常會(huì)有多個(gè)全局最優(yōu)解.如果運(yùn)用逐點(diǎn)式的傳統(tǒng)數(shù)值優(yōu)化方法來(lái)求解這些問(wèn)題，需要重復(fù)計(jì)算多次，再?gòu)倪@些解中選出最優(yōu)的解，但并不能保證該解是全局最優(yōu)解[6].群體智能優(yōu)化算法通過(guò)個(gè)體之間的合作與競(jìng)爭(zhēng)來(lái)引導(dǎo)種群的迭代，從而向更優(yōu)的解收斂；并且它們的迭代規(guī)則不依賴于函數(shù)的導(dǎo)數(shù)或梯度等信息，易于使用.因此，越來(lái)越多的群體智能優(yōu)化算法被人們用來(lái)解決實(shí)際工程優(yōu)化問(wèn)題.

受鯨魚(yú)群利用超聲波通信進(jìn)行捕食等行為的啟發(fā)，華中科技大學(xué)的曾冰和高亮于2017年提出了一種新型群體智能優(yōu)化算法——鯨魚(yú)群算法[7](whale swarm algorithm，WSA)，在函數(shù)優(yōu)化問(wèn)題的求解中取得了顯著效果.

1 鯨魚(yú)群算法的原理

鯨魚(yú)群算法是一種基于群體智能的元啟發(fā)式算法.類似于粒子群算法，鯨魚(yú)群算法首先從定義域內(nèi)隨機(jī)生成一組初始解，即隨機(jī)初始化種群各個(gè)體的位置，然后根據(jù)種群中各個(gè)體的位置和適應(yīng)度值，以某種機(jī)制產(chǎn)生新一代種群.但不同于粒子群算法通過(guò)跟蹤個(gè)體歷史最優(yōu)解和全局最優(yōu)解生成新種群的機(jī)制，鯨魚(yú)群算法模擬鯨魚(yú)群以超聲波為信息媒介進(jìn)行捕食等群體行為，將每個(gè)解類比為一條鯨魚(yú)，每條鯨魚(yú)的移動(dòng)由比它好(由適應(yīng)度值判斷)的鯨魚(yú)中離它最近的鯨魚(yú)引導(dǎo)，筆者將這種引導(dǎo)鯨魚(yú)定義為“較優(yōu)且最近”的鯨魚(yú).

2 鯨魚(yú)群算法的基本步驟

在鯨魚(yú)群算法中，每條鯨魚(yú)表示解空間中的一個(gè)候選解，解的優(yōu)劣根據(jù)由優(yōu)化目標(biāo)定義的適應(yīng)度函數(shù)判斷.WSA先對(duì)鯨魚(yú)群各個(gè)體的位置進(jìn)行隨機(jī)初始化，并在之后的迭代過(guò)程中，對(duì)種群中的每條鯨魚(yú)X，判斷其“較優(yōu)且最近”的鯨魚(yú)Y是否存在，若存在，則鯨魚(yú)X在鯨魚(yú)Y的引導(dǎo)下進(jìn)行隨機(jī)移動(dòng)，如式(1)所示；否則，鯨魚(yú)X的位置保持不變.WSA的基本流程如圖1所示.

(1)

圖1 鯨魚(yú)群算法的流程圖Fig.1 Flow chart of whale swarm algorithm

根據(jù)式(1)可知，如果一條鯨魚(yú)與它的“較優(yōu)且最近”的鯨魚(yú)之間的距離很小，該條鯨魚(yú)將會(huì)積極地朝其“較優(yōu)且最近”的鯨魚(yú)隨機(jī)移動(dòng)；否則，它將消極地朝其“較優(yōu)且最近”的鯨魚(yú)隨機(jī)移動(dòng)，如圖2所示.圖2中的目標(biāo)函數(shù)維數(shù)為2，六角星表示全局最優(yōu)解，圓圈表示鯨魚(yú)，用虛線標(biāo)記的矩形區(qū)域是當(dāng)前迭代中鯨魚(yú)的可達(dá)區(qū)域.

圖2 由“較優(yōu)且最近”的鯨魚(yú)引導(dǎo)的隨機(jī)移動(dòng)Fig.2 Random movement under the guidance of the“better and nearest” whale

3 鯨魚(yú)群算法與典型群體智能優(yōu)化算法的比較

群體智能優(yōu)化算法主要通過(guò)模擬生物的群集行為，利用種群的群體智慧進(jìn)行協(xié)同搜索.這類算法對(duì)目標(biāo)函數(shù)的性態(tài)(單調(diào)性、可導(dǎo)性、模態(tài)性等)幾乎沒(méi)有限制，使用簡(jiǎn)單高效，可廣泛地應(yīng)用于各類優(yōu)化問(wèn)題.典型的群體智能優(yōu)化算法有粒子群優(yōu)化(particle swarm optimization，PSO)算法、蟻群優(yōu)化(ant colony optimization，ACO)算法等.

受鳥(niǎo)群覓食行為的啟發(fā)，PSO采用速度-位置模型，通過(guò)動(dòng)態(tài)跟蹤個(gè)體歷史最優(yōu)解和全局最優(yōu)解在解空間內(nèi)進(jìn)行搜索.PSO主要應(yīng)用于連續(xù)優(yōu)化問(wèn)題，所需設(shè)置的參數(shù)較少，收斂速度較快，但無(wú)法直接用于求解離散優(yōu)化問(wèn)題.ACO模擬螞蟻的覓食行為，通過(guò)動(dòng)態(tài)更新各路徑上的信息素，使螞蟻在信息素的引導(dǎo)下找到最短路徑.相較于PSO，ACO適用于求解離散優(yōu)化問(wèn)題(如最短路徑問(wèn)題)，但需要調(diào)整較多的參數(shù).而WSA主要針對(duì)連續(xù)優(yōu)化問(wèn)題設(shè)計(jì)，由于其框架易于擴(kuò)充的特點(diǎn)，可通過(guò)簡(jiǎn)單的改進(jìn)應(yīng)用于離散優(yōu)化問(wèn)題.將候選解視為鯨魚(yú)，采用向“較優(yōu)且最近”的鯨魚(yú)隨機(jī)移動(dòng)的位置更新模型，在保持種群多樣性的同時(shí)進(jìn)行有效的局部搜索，有利于求解多個(gè)全局最優(yōu)解.此外WSA控制參數(shù)較少，易于使用.

WSA與近幾年提出的頭腦風(fēng)暴優(yōu)化(brain storm optimization，BSO)算法[8-9]存在諸多相似之處：兩者均充分利用種群個(gè)體的位置分布信息引導(dǎo)最優(yōu)解的搜索.其主要區(qū)別在于引導(dǎo)方式，WSA主要通過(guò)個(gè)體向“較優(yōu)且最近”的鯨魚(yú)移動(dòng)促使算法收斂至最優(yōu)解；BSO則基于問(wèn)題特征和解數(shù)據(jù)的分析，采用數(shù)據(jù)挖掘技術(shù)引導(dǎo)算法搜索最優(yōu)解.

4 鯨魚(yú)群算法的改進(jìn)

4.1 WSA迭代規(guī)則的改進(jìn)

為解決WSA中參數(shù)η設(shè)置的難題，假設(shè)超聲波的強(qiáng)度在水中不會(huì)衰減，即η=0，則ρ0·e-η·dX,Y=2.當(dāng)鯨魚(yú)X在“較優(yōu)且最近”的鯨魚(yú)Y的引導(dǎo)下隨機(jī)移動(dòng)時(shí)，若X和Y分別位于不同的全局最優(yōu)解附近，如圖3所示，X很可能離開(kāi)附近最優(yōu)解所在區(qū)域，降低了算法的局部搜索能力.因此，對(duì)WSA中鯨魚(yú)的位置更新規(guī)則進(jìn)行如下改進(jìn)：為當(dāng)前迭代的鯨魚(yú)(即正本)生成一個(gè)副本，若副本在其“較優(yōu)且最近”的鯨魚(yú)引導(dǎo)下隨機(jī)移動(dòng)到優(yōu)于正本的位置，則正本移至副本所在位置；否則正本保持原地不動(dòng).這樣圖3中的鯨魚(yú)X會(huì)以很大的概率保持原地不動(dòng)，從而引導(dǎo)其他個(gè)體向其追隨的最優(yōu)解收斂.可見(jiàn)，改進(jìn)后的位置更新規(guī)則仍然適用于η=0的情況，可以在不引入任何小生境參數(shù)的前提下，有效保證多個(gè)子種群的形成，提高算法的局部搜索能力，這非常有利于求解多個(gè)全局最優(yōu)解.

圖3 當(dāng)η=0時(shí)，由“較優(yōu)且最近”的鯨魚(yú)引導(dǎo)的隨機(jī)移動(dòng)Fig.3 Random movement under the guidance of the“better and nearest” whale when η=0

4.2 在迭代過(guò)程中識(shí)別并跳出已找到的極值點(diǎn)

為使WSA在迭代過(guò)程中有效識(shí)別并跳出已找到的極值點(diǎn)，提高算法的全局搜索能力，引入穩(wěn)定性閾值Ts和適應(yīng)度閾值Tf兩個(gè)參數(shù).穩(wěn)定性閾值Ts是一個(gè)預(yù)先定義的迭代次數(shù)，用來(lái)判斷一條鯨魚(yú)是否已經(jīng)找到所跟隨的極值點(diǎn)，達(dá)到穩(wěn)定狀態(tài).為實(shí)現(xiàn)上述判斷，每條鯨魚(yú)設(shè)置一個(gè)迭代計(jì)數(shù)器c，以記錄該鯨魚(yú)未更新位置的迭代次數(shù).適應(yīng)度閾值Tf用于識(shí)別當(dāng)前全局最優(yōu)解.在每次迭代過(guò)程中，對(duì)于種群中未更新的鯨魚(yú)X，需檢查其迭代計(jì)數(shù)器：若X未達(dá)到穩(wěn)定狀態(tài)(即X.c≠Ts)，則其迭代計(jì)數(shù)器自增1；反之，根據(jù)Tf和|fgbest-f(X)|的大小(fgbest為當(dāng)前全局最優(yōu)適應(yīng)度;f(X)為X的適應(yīng)度)，判斷是否更新當(dāng)前全局最優(yōu)解集合，接著初始化該鯨魚(yú)，從而跳出已經(jīng)找到的極值點(diǎn).基于上述對(duì)WSA的改進(jìn)方案，改進(jìn)的WSA被稱為帶迭代計(jì)數(shù)器的WSA(WSA with iterative counter，WSA-IC).

4.3 WSA-IC算法的流程

初始化鯨魚(yú)包括初始化鯨魚(yú)的位置以及將鯨魚(yú)的迭代計(jì)數(shù)器置0.

WSA-IC算法偽代碼如下.

輸入： 目標(biāo)函數(shù)，鯨魚(yú)群Ω.

輸出： 當(dāng)前全局最優(yōu)解集GloOpt.

1:開(kāi)始

2:初始化參數(shù)；

3:初始化鯨魚(yú)；

4:計(jì)算鯨魚(yú)的適應(yīng)度值；

5:while 終止條件不滿足 do

6:fori=1 to |Ω| do

7:尋找Ωi的“較優(yōu)且最近”的鯨魚(yú)Y；

8:ifY存在 then

9:生成Ωi的副本X′；

10:X′在Y的引導(dǎo)下根據(jù)公式(1)移動(dòng)；

11:計(jì)算X′的適應(yīng)度值f(X′)；

12:iff(X′)

13:Ωi=X′；

14:Ωi.c=0；

15: else

16:檢查Ωi的迭代計(jì)數(shù)器；

17:end if

18:else

19:檢查Ωi的迭代計(jì)數(shù)器；

20:end if

21:end for

22:end while

23:判斷Ω中的每條鯨魚(yú)是否是當(dāng)前全局最優(yōu)解；

24:返回GloOpt；

25:結(jié)束

4.4 WSA-IC算法復(fù)雜度及收斂性分析

4.4.1 復(fù)雜度分析

WSA-IC算法的時(shí)間復(fù)雜度分析見(jiàn)表1，種群規(guī)模和目標(biāo)函數(shù)維度分別為m、n.在復(fù)雜度最高情況下，即當(dāng)鯨魚(yú)在位置變換時(shí)沒(méi)有發(fā)現(xiàn)適應(yīng)度更優(yōu)的個(gè)體且迭代計(jì)數(shù)器達(dá)到閾值Ts，更新鯨魚(yú)個(gè)體需執(zhí)行4n+1次加法、2n次乘法和2n+m+2次比較.因此，WSA-IC算法的時(shí)間復(fù)雜度為O(n2).

4.4.2 收斂性分析

由式(1)及WSA-IC算法偽代碼可知，WSA-IC算法可寫(xiě)成如下形式：

(2)

式中:A=1-rand(0, 2)，B=rand(0, 2).

因此可通過(guò)計(jì)算求得E(A)=0，E(B)=1，D(A)=D(B)=-E(AB)=1/3.

表1 WSA-IC算法復(fù)雜度分析Tab.1 Analysis of the algorithm complexity for WSA-IC

(3)

(4)

(5)

(6)

(7)

由式(5)、(7)推出

(8)

(9)

4.5 WSA-IC算法的參數(shù)設(shè)置

WSA-IC算法包含4個(gè)參數(shù)，即超聲波源強(qiáng)度ρ0、衰減系數(shù)η、穩(wěn)定性閾值Ts以及適應(yīng)度閾值Tf.其中，ρ0和η分別被設(shè)置為2和0；Tf通常認(rèn)為與給定的適應(yīng)度誤差(即精度)相等，當(dāng)精度未給定時(shí)，可設(shè)置為1.0×10-8；基于大量實(shí)驗(yàn)結(jié)果，Ts的值一般設(shè)置為函數(shù)維度的100倍.

4.6 數(shù)值實(shí)驗(yàn)

采用如下6個(gè)多峰優(yōu)化算法作為對(duì)比算法：locally informed PSO(LIPS)[6]、fitness-euclidean distance ratio PSO(FERPSO)[10]、speciation-based DE(SDE)[11]、crowding DE(CDE)[12]、speciation-based PSO(SPSO)[13]以及WSA.所有算法都是在Microsoft Visual Studio 2015中用C++編程語(yǔ)言實(shí)現(xiàn)，在相同的環(huán)境下運(yùn)行，停止條件均為CPU計(jì)算時(shí)間.

4.6.1 測(cè)試函數(shù)

測(cè)試函數(shù)采用15個(gè)CEC2015多峰基準(zhǔn)測(cè)試函數(shù)，其基本信息如表2所示.表中n、o1、o2分別表示函數(shù)維度、全局最優(yōu)解個(gè)數(shù)、局部最優(yōu)解個(gè)數(shù).所有的測(cè)試函數(shù)都是最小化問(wèn)題，其搜索空間均為[-100, 100]n.

表2 CEC2015多峰測(cè)試函數(shù)Tab.2 CEC2015 multimodal functions for the experiment

4.6.2 參數(shù)設(shè)置

算法的主要參數(shù)設(shè)置如表3、表4所示.在表3中，m1/m2表示W(wǎng)SA-IC算法的種群大小/其他算法的種群大小，CPU計(jì)算時(shí)間以s為單位.由于WSA-IC算法在迭代過(guò)程中可以有效識(shí)別并跳出已經(jīng)找到的極值點(diǎn)，因此可以設(shè)置相對(duì)較小的種群規(guī)模，以降低算法的計(jì)算復(fù)雜度.

表3 CEC2015多峰測(cè)試函數(shù)相關(guān)參數(shù)的設(shè)置Tab.3 Setting of parameters associated with CEC2015 multimodal functions for the experiment

表4 7種算法主要參數(shù)的設(shè)置Tab.4 Setting of main parameters of seven algorithms

注：ω為慣性權(quán)重；nsize為鄰居個(gè)數(shù)；χ為收縮因子；φmax為系數(shù)；CR為交叉概率；F為縮減因子；n為種群大小；CF為擁擠因子；φ1、φ2為系數(shù).

4.6.3 評(píng)價(jià)指標(biāo)

為保證比較的公正性，每個(gè)算法在每個(gè)測(cè)試函數(shù)上獨(dú)立運(yùn)行51次，并從最優(yōu)解數(shù)量、最優(yōu)解質(zhì)量、收斂速度三方面來(lái)度量算法的性能.

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

(1)最優(yōu)解的數(shù)量.算法在最優(yōu)解數(shù)量方面的表現(xiàn)通過(guò)平均最優(yōu)解個(gè)數(shù)(average number of optima found，ANOF)衡量.算法的ANOF值及顯著性水平為0.05時(shí)的Z檢驗(yàn)結(jié)果見(jiàn)表5.表中，avg±sd表示算法取得的ANOF均值±標(biāo)準(zhǔn)差；δ表示Z檢驗(yàn)結(jié)果，且符號(hào)“+”(“-”)表示W(wǎng)SA-IC算法的結(jié)果優(yōu)于(劣于)對(duì)比算法且差異顯著，符號(hào)“=”表示W(wǎng)SA-IC算法和對(duì)比算法結(jié)果的差異不顯著.總體看來(lái)，符號(hào)“-”的數(shù)量只有1個(gè)，針對(duì)每種對(duì)比算法，符號(hào)“+”的數(shù)量占多數(shù)，意味著WSA-IC算法在最優(yōu)解數(shù)量上的表現(xiàn)遠(yuǎn)好于其他算法.

表5 7種算法在測(cè)試函數(shù)上獲得的ANOF值與Z檢驗(yàn)結(jié)果Tab.5 ANOF of seven algorithms on test functions and results of Z-test

(2)最優(yōu)解的質(zhì)量.將算法取得的最優(yōu)解適應(yīng)度值減去100與相應(yīng)函數(shù)序號(hào)的乘積，由此得到的最優(yōu)解均值(標(biāo)準(zhǔn)差)及Z檢驗(yàn)結(jié)果如表6所示，分別用avg(sd)和δ表示.顯然，符號(hào)“-”的數(shù)量遠(yuǎn)少于符號(hào)“+”和“=”的數(shù)量，說(shuō)明WSA-IC算法取得了較高的最優(yōu)解精度.

(3)收斂速度.在比較算法的求解效率時(shí)，以算法在測(cè)試函數(shù)F14上的收斂曲線為例進(jìn)行分析，如圖4所示.橫坐標(biāo)為評(píng)價(jià)次數(shù)，縱坐標(biāo)為算法多次實(shí)驗(yàn)找到的當(dāng)前全局最優(yōu)解適應(yīng)度均值.由于FERPSO和WSA的種群可能會(huì)過(guò)早收斂而停止迭代，對(duì)比算法不包括這兩個(gè)算法.從圖4可以看出，相比于其他算法，WSA-IC算法在F14上以更快的速度收斂到更優(yōu)的解.

綜上所述，WSA-IC算法能高效地搜索到更多更優(yōu)的解，這主要得益于對(duì)WSA兩方面的改進(jìn)：其一，改進(jìn)迭代規(guī)則，使WSA-IC算法在保證多個(gè)子種群形成的同時(shí)保持局部搜索能力；其二，在迭代過(guò)程中識(shí)別并跳出已經(jīng)找到的極值點(diǎn)，加速WSA-IC算法向全局最優(yōu)解收斂，盡可能地提高算法的全局搜索能力.

表6 7種算法在測(cè)試函數(shù)上獲得的最優(yōu)解質(zhì)量與Z檢驗(yàn)結(jié)果Tab.6 Quality of optima found by seven algorithms on test functions and results of Z-test

圖4 算法在函數(shù)F14上的收斂情況Fig.4 Convergence rate of algorithms on F14

(4)參數(shù)的影響.穩(wěn)定性閾值Ts是WSA-IC算法最為關(guān)鍵的參數(shù)，其值需根據(jù)優(yōu)化問(wèn)題的特點(diǎn)設(shè)定.對(duì)取不同Ts值的WSA-IC算法進(jìn)行了實(shí)驗(yàn)，結(jié)果如表7所示.由表7可知，當(dāng)Ts=100n時(shí)，WSA-IC算法在大部分測(cè)試函數(shù)上都能取得最優(yōu)的ANOF值.因此，對(duì)于幾乎所有的連續(xù)優(yōu)化問(wèn)題，Ts均可以設(shè)置為100n.

5 鯨魚(yú)群算法的應(yīng)用

目前鯨魚(yú)群算法已在某些工程優(yōu)化領(lǐng)域(如無(wú)線傳感器網(wǎng)絡(luò)能效優(yōu)化)獲得了成功的應(yīng)用.下面以煉鋼連鑄調(diào)度問(wèn)題為例介紹鯨魚(yú)群算法的具體應(yīng)用.

5.1 煉鋼連鑄調(diào)度問(wèn)題

以某鋼廠的工藝流程為例介紹煉鋼連鑄調(diào)度問(wèn)題.如圖5所示，有N個(gè)待加工澆次，各澆次包括一定數(shù)目的爐次，需按同一工藝路線(EAF-AOD-LF1-LF2-CC)進(jìn)行加工，要求在保證連鑄階段相鄰澆次預(yù)留準(zhǔn)備時(shí)間，同一澆次內(nèi)爐次連續(xù)加工的前提下，確定澆次順序、連鑄機(jī)分配和各工序的開(kāi)始時(shí)間及結(jié)束時(shí)間，以最小化最大完工時(shí)間.此外，特定工序間設(shè)置一定數(shù)量的無(wú)限緩沖區(qū)、有限緩沖區(qū)和可加工緩沖區(qū)[14].其中，無(wú)限緩沖區(qū)不限制爐次的緩存時(shí)間；有限緩沖區(qū)中爐次的緩存時(shí)間受限；可加工緩沖區(qū)既可加工爐次又可緩存爐次且緩存時(shí)間不受限.這類問(wèn)題早已獲得某些學(xué)者的關(guān)注[14-15]，但不同于已有的研究，筆者考慮連鑄階段存在2臺(tái)并行機(jī)的情況，將緩沖區(qū)視為加工時(shí)間為0的生產(chǎn)階段，則筆者所研究的煉鋼連鑄調(diào)度問(wèn)題實(shí)質(zhì)上是9階段零等待混合流水車間調(diào)度問(wèn)題.

表7 WSA-IC算法在不同的Ts取值下獲得的ANOF值Tab.7 ANOF of WSA-IC with different values of Ts

圖5 鋼鐵生產(chǎn)工藝流程圖Fig.5 Flow chart of the steel production process

5.2 基于WSA-IC的煉鋼連鑄調(diào)度算法

由于調(diào)度問(wèn)題的離散特性，WSA-IC算法不能直接用于求解煉鋼連鑄調(diào)度問(wèn)題，因此從如下4個(gè)方面對(duì)WSA-IC算法進(jìn)行了改進(jìn)：①設(shè)計(jì)了一種離散的鯨魚(yú)個(gè)體編碼與解碼方案；②采用漢明距離計(jì)算個(gè)體間的距離；③改進(jìn)了鯨魚(yú)個(gè)體的移動(dòng)規(guī)則；④設(shè)計(jì)了一種有效的自適應(yīng)鄰域搜索策略.由于該算法不需要保存在迭代過(guò)程中求得的多個(gè)當(dāng)前全局最優(yōu)解，所以該算法不需要Tf參數(shù).

基于WSA-IC的煉鋼連鑄調(diào)度算法偽代碼如下.

輸入：目標(biāo)函數(shù)，鯨魚(yú)群Ω，當(dāng)前全局最優(yōu)解GBest，當(dāng)前全局最優(yōu)解的適應(yīng)度值fgbest.

輸出：最優(yōu)解.

1:開(kāi)始

2:初始化參數(shù)；

3:初始化鯨魚(yú)；

4:計(jì)算鯨魚(yú)的適應(yīng)度值；

5:while 終止條件不滿足 do

6:fori=1 to |Ω| do

7:尋找Ωi的“較優(yōu)且最近”的鯨魚(yú)Y；

8:ifY存在 then

9:生成Ωi的副本X′；

10:X′根據(jù)個(gè)體移動(dòng)規(guī)則向Y移動(dòng)；

11:計(jì)算X′的適應(yīng)度值f(X′)；

12:iff(X′)

13:Ωi=X′；

14:Ωi.c=0；

15:else

16:ifΩi.c≠Tsthen

17:Ωi.c=Ωi.c+1；

18:else

19:重新初始化Ωi；

20:計(jì)算Ωi的適應(yīng)度值；

21:end if

22:end if

23:else

24:生成的Ωi副本X′；

25:對(duì)X′執(zhí)行自適應(yīng)鄰域搜索；

26:iff(X′)

27:Ωi=X′；

28:Ωi.c=0；

29:else

30:ifΩi.c≠Tsthen

31:Ωi.c=Ωi.c+1；

32:else

33:iff(Ωi)

34:fgbest=f(Ωi)；

35:GBest=Ωi；

36:end if

37:重新初始化Ωi；

38:計(jì)算Ωi的適應(yīng)度值；

39:end if

40: end if

41:end if

42:end for

43:end while

44:判斷最后一代種群中是否有比GBest好的鯨魚(yú)，有則替換GBest；

45:返回最優(yōu)解GBest；

46:結(jié)束

5.2.1 個(gè)體編碼與解碼

算法基于工件進(jìn)行編碼，即將澆次編號(hào)的排序作為編碼.解碼采用文獻(xiàn)[14]所提方法，根據(jù)編碼所示澆次序列，以澆次為單位安排作業(yè)計(jì)劃，其中連鑄機(jī)的分配依據(jù)最早空閑機(jī)器優(yōu)先規(guī)則.

5.2.2 個(gè)體間的距離計(jì)算

在上述離散個(gè)體編碼方案中，個(gè)體維度都相同，個(gè)體之間的距離計(jì)算與等長(zhǎng)字符串之間的距離計(jì)算非常相似，故采用漢明距離[16]計(jì)算不同鯨魚(yú)個(gè)體間的距離.假設(shè)兩條鯨魚(yú)個(gè)體X1、X2如圖6所示，X1和X2有4個(gè)元素不相同，所以，X1和X2之間的漢明距離為4.

圖6 兩條鯨魚(yú)個(gè)體示意圖
Fig.6 Sketch map of two whales

5.2.3 個(gè)體移動(dòng)規(guī)則

由于個(gè)體采用離散編碼方案，WSA算法的個(gè)體位置迭代式(1)不再適用，因此需針對(duì)煉鋼連鑄調(diào)度問(wèn)題，改進(jìn)個(gè)體移動(dòng)規(guī)則.為了保證當(dāng)前個(gè)體向它的“較優(yōu)且最近”的個(gè)體隨機(jī)移動(dòng)，引入一個(gè)新的參數(shù)——選擇概率λ.鯨魚(yú)Ωu的副本X′在它的“較優(yōu)且最近”的鯨魚(yú)Y的引導(dǎo)下，進(jìn)行如下移動(dòng)：首先比較個(gè)體X′和Y中對(duì)應(yīng)位置的元素，如果不同，則將該元素的值和位置分別存入集合A和B中；遍歷這些不同元素所在的位置，生成一個(gè)0到1之間的隨機(jī)數(shù)P，若P小于λ且Y中該位置的元素屬于集合A(存儲(chǔ)未被選擇的元素)，則將Y中該元素賦值給X′中對(duì)應(yīng)位置的元素，否則從集合A中隨機(jī)選擇一個(gè)值賦給X′中對(duì)應(yīng)位置的元素.注意到已經(jīng)賦值給X′的元素應(yīng)從集合A中移除.

5.2.4 自適應(yīng)鄰域搜索策略

為增強(qiáng)算法的局部搜索能力，當(dāng)種群中不存在當(dāng)前鯨魚(yú)個(gè)體的“較優(yōu)且最近”的鯨魚(yú)時(shí)，對(duì)當(dāng)前個(gè)體進(jìn)行結(jié)合移位算子和交換算子的自適應(yīng)鄰域搜索.自適應(yīng)鄰域搜索方法將種群不同個(gè)體與生成該個(gè)體的鄰域搜索算子關(guān)聯(lián)起來(lái).首先比較區(qū)間[0,1]內(nèi)的隨機(jī)數(shù)a和自適應(yīng)鄰域搜索概率?的大小，若a

5.3 實(shí)例仿真與分析

為驗(yàn)證本文算法的有效性，隨機(jī)生成5個(gè)不同規(guī)模的案例，選擇遺傳算法(genetic algorithm，GA)、人工蜂群算法(artificial bee colony，ABC)、傳統(tǒng)WSA算法作為比較算法.WSA-IC算法的參數(shù)設(shè)置如下：種群規(guī)模PS為50，選擇概率λ為0.5，自適應(yīng)鄰域搜索概率?為0.75，穩(wěn)定性閾值Ts為200+|Z|/2(|Z|為澆次數(shù)).所有算法以相同的迭代次數(shù)為終止條件，每組實(shí)驗(yàn)運(yùn)行10次，結(jié)果見(jiàn)表8.由表8知，對(duì)于測(cè)試的5個(gè)案例，WSA-IC算法均能找到優(yōu)于ABC、GA和WSA算法求得的解，并取得較小的標(biāo)準(zhǔn)差，且這種差異隨著案例規(guī)模的增大而增大.由此說(shuō)明，筆者提出的算法具有良好的尋優(yōu)能力和穩(wěn)定性.圖7為所示算法的收斂曲線(橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為每次迭代求得的最優(yōu)解適應(yīng)度值).從圖7可知，相較于GA、ABC和WSA算法，WSA-IC算法能更快地收斂到更優(yōu)的解.

圖7 算法調(diào)度90個(gè)澆次時(shí)的收斂情況Fig.7 Convergence rate of algorithms for the case of scheduling 90 casts

表8 WSA-IC算法與其他算法的實(shí)驗(yàn)結(jié)果Tab.8 Experimental results of WSA-IC and other algorithms

6 結(jié)束語(yǔ)

研究了一種新興的群體智能算法——鯨魚(yú)群算法(WSA).針對(duì)多峰函數(shù)優(yōu)化問(wèn)題的特點(diǎn)，提出了改進(jìn)的鯨魚(yú)群算法(WSA-IC).WSA-IC改進(jìn)了WSA的迭代規(guī)則，并引入了“穩(wěn)定性閾值”和“適應(yīng)度閾值”兩個(gè)參數(shù)，使算法能在迭代過(guò)程中有效地識(shí)別并跳出已找到的極值點(diǎn).結(jié)果表明，WSA-IC在求解多峰函數(shù)優(yōu)化問(wèn)題上有著優(yōu)異的性能，且WSA-IC的參數(shù)極易設(shè)置.此外，以煉鋼連鑄調(diào)度問(wèn)題為例，闡述了WSA在工程優(yōu)化領(lǐng)域的具體應(yīng)用，表明WSA具有較大的應(yīng)用價(jià)值.

當(dāng)前關(guān)于WSA的研究仍處于起步階段，未來(lái)可以將WSA與其他元啟發(fā)式算法相結(jié)合以提高算法的優(yōu)化性能；本文實(shí)驗(yàn)已證明WSA對(duì)多峰連續(xù)優(yōu)化問(wèn)題以及煉鋼連鑄調(diào)度問(wèn)題的適用性，未來(lái)可以研究WSA在其他實(shí)際工程優(yōu)化問(wèn)題(特別是NP-hard問(wèn)題)中的應(yīng)用.