徐亦鳳,劉 升,張偉康,劉宇凇

(上海工程技術(shù)大學(xué)管理學(xué)院,上海 201620)

1 引言

在社會(huì)科學(xué)、工程和經(jīng)濟(jì)等領(lǐng)域中存在著各種各樣的優(yōu)化問題,然而,在以往的基于群體的優(yōu)化方法中存在著一些缺點(diǎn)和問題。近年來,國內(nèi)外學(xué)者提出了一些基于動(dòng)物特征的優(yōu)化方法如灰狼優(yōu)化算法[1]、鯨魚優(yōu)化算法[2]和飛蛾撲火算法[3],甚至一種基于正弦余弦函數(shù)模型的正弦余弦算法[4]。這些優(yōu)化算法具有參數(shù)少,優(yōu)化原理簡單,操作易實(shí)現(xiàn)等特點(diǎn),然而,它們的數(shù)學(xué)模型存在結(jié)構(gòu)相似、性能平庸、驗(yàn)證方法有缺陷以及算法組件略有修改等問題。例如,非常流行的灰狼優(yōu)化算法由于其初始化生成的種群方法的隨機(jī)性無法保證良好的種群多樣性。鯨魚優(yōu)化算法和飛蛾撲火方法的環(huán)繞包圍機(jī)制與灰狼優(yōu)化算法相同,只是搜索范圍略有不同,這些算法實(shí)際上沒有本質(zhì)不同只是改變了探索方法。

饑餓游戲搜索算法(Hunger Games Search)[5]是楊玉濤和陳慧玲這兩位學(xué)者提出的一種根據(jù)群居動(dòng)物的共同特征及其食物搜索而設(shè)計(jì)的元啟發(fā)式優(yōu)化算法,與其它群智能算法相比,HGS算法不僅考慮了動(dòng)物群體的行為特征還考慮了生理特征,遵循幾乎所有動(dòng)物都使用的計(jì)算邏輯規(guī)則和游戲,這些競爭活動(dòng)和游戲通常通過確保更高的生存和食物獲取機(jī)會(huì)來適應(yīng)進(jìn)化。該算法具有結(jié)構(gòu)簡單、需要調(diào)節(jié)的參數(shù)少和魯棒性強(qiáng)等特點(diǎn),因此在對優(yōu)化問題的求解精度和收斂速度上具有良好的表現(xiàn)。Hoang Nguyen和Xuan-Nam Bui[6]將饑餓游戲搜索算法和人工神經(jīng)網(wǎng)絡(luò)相結(jié)合提出了HGS-ANN模型,用于預(yù)測礦山爆破誘發(fā)的地面震動(dòng)強(qiáng)度,有助于減輕礦山爆破作業(yè)的不利影響;Fahim Samuel Raafat等人[7]利用HGS算法來獲取質(zhì)子交換膜燃料電池模型參數(shù)的最佳值,正面影響燃料電池的運(yùn)行與控制,且由于基本的饑餓游戲搜索算法提出的時(shí)間較短,現(xiàn)有的論文并沒有對基本的饑餓游戲搜索算法進(jìn)行改進(jìn),需對其進(jìn)行進(jìn)一步改進(jìn)與完善以適用于更多優(yōu)化問題。

盡管已經(jīng)提出了許多元啟發(fā)式優(yōu)化算法,但是根據(jù)沒有免費(fèi)的午餐定理,本文提出精英反向?qū)W習(xí)t分布饑餓游戲搜索算法,該算法在初始化隨機(jī)種群時(shí)引入精英反向解有效增加種群多樣性和質(zhì)量,并且在全局探索過程中引入t分布自適應(yīng)策略將高斯變異和柯西變異相結(jié)合,使得算法在迭代過程中具有良好的全局探索性。

2 基本饑餓游戲搜索算法

動(dòng)物根據(jù)一些計(jì)算規(guī)則和它們與環(huán)境的相互作用來構(gòu)成它們的感覺信息,這些規(guī)則成為它們決策和選擇的基礎(chǔ),也成為它們認(rèn)知結(jié)構(gòu)進(jìn)化的依據(jù)。饑餓是動(dòng)物生活中行為、決定和行動(dòng)的最重要的動(dòng)機(jī)和原因之一。盡管各種各樣的刺激和相互競爭的需求總是影響動(dòng)物的生活質(zhì)量,但當(dāng)它們面臨熱量不足時(shí),它們會(huì)探求食物來源。為了解決這種體內(nèi)平衡失調(diào),它們必須定期尋找食物,并以在探索性、防御性和競爭性活動(dòng)之間切換的形式來靠近食物,這表明它們的進(jìn)食策略極其流暢。

行為選擇和活動(dòng)選擇在動(dòng)物王國是普遍的,它是自然界中以目標(biāo)為導(dǎo)向的行為的基本法則。各種因素或因素間的組合會(huì)影響物種的行為,觀察到的行為取決于其所在地區(qū)現(xiàn)有的動(dòng)機(jī)狀態(tài)和刺激的出現(xiàn)。神經(jīng)學(xué)家認(rèn)為對任何動(dòng)物來說,饑餓是其活動(dòng)、學(xué)習(xí)和尋找食物的強(qiáng)大動(dòng)力,是將生活條件改變?yōu)楦€(wěn)定狀態(tài)的力量。

社交生活促使動(dòng)物避開捕食者,尋找食物來源,因?yàn)樗鼈冊谧匀粎f(xié)作中工作,這增加了它們的生存機(jī)會(huì),這是進(jìn)化的本質(zhì)。健康的動(dòng)物可以更好地找到食物來源,它們比弱小的動(dòng)物有更大的生存機(jī)會(huì),這種現(xiàn)象可以被稱為自然界的饑餓游戲。無論是捕食者還是被捕食者,任何錯(cuò)誤的決定都可能改變游戲的結(jié)果,導(dǎo)致一個(gè)個(gè)體的死亡,甚至整個(gè)物種的滅絕。動(dòng)物的日常行為很大程度上受到一些動(dòng)機(jī)情況的影響,例如饑餓和被獵人殺死的緊張感。饑餓是長時(shí)間“不吃東西”的一個(gè)特征,饑餓感越強(qiáng)烈,對食物的渴望就越強(qiáng)烈,機(jī)體就越積極地在短時(shí)間內(nèi)尋找食物,以免為時(shí)已晚并導(dǎo)致饑餓或死亡。因此,當(dāng)食物來源有限時(shí),饑餓的動(dòng)物之間會(huì)有一個(gè)尋找食物來源并贏得生存機(jī)會(huì)的邏輯博弈。因此,饑餓游戲是一種基于物種的邏輯博弈。

饑餓游戲搜索機(jī)制分為靠近食物和饑餓角色兩部分。

1)靠近食物

群居動(dòng)物在覓食過程中經(jīng)常相互合作,但不排除少數(shù)個(gè)體不參與合作的可能性。為了用數(shù)學(xué)公式表示動(dòng)物靠近食物的行為,該過程的位置更新公式如下:

(1)

表1 各算法實(shí)驗(yàn)參數(shù)設(shè)置

E=sech(|F(i)-BF|)

(2)

(3)

(4)

其中rand是[0,1]中的隨機(jī)數(shù)。

2)饑餓角色

在這一部分中,個(gè)體在搜索中的饑餓特征通過一個(gè)提出的模型進(jìn)行數(shù)學(xué)模擬。

(5)

(6)

其中b=1,x1=-π+(1-τ)·2π

x2=-π+τ·2π代表個(gè)體的饑餓程度,N代表個(gè)體的數(shù)量,SHungry是所有個(gè)體饑餓程度的總和,r3、r4和r5是[0,1]之間的隨機(jī)數(shù)。

hungry(i)的公式如下

(7)

其中AllFitness(i)代表當(dāng)前迭代位置的適應(yīng)度值。

H的公式如下:

(8)

(9)

其中r6是[0,1]之間的隨機(jī)數(shù),F(i)代表每個(gè)個(gè)體的適應(yīng)度值,BF是在當(dāng)前迭代過程中獲得的最佳適應(yīng)度,WF是在當(dāng)前迭代過程中獲得的最差適應(yīng)度,UB和LB代表搜索空間中的上限和下限。

綜上所述,基本饑餓游戲搜索算法的流程圖如圖1所示。

圖1 HGS算法流程圖

3 精英反向?qū)W習(xí)t分布饑餓游戲搜索算法

3.1 精英反向?qū)W習(xí)策略

Tizhoosh[8]于2005年提出了一種反向解比當(dāng)前解更接近于全局最優(yōu)解的一種策略——精英反向?qū)W習(xí)策略,其主要原理是對問題的可行解求其反向解,并對原始解和反向解進(jìn)行排序,從中選出較優(yōu)解作為新一代個(gè)體進(jìn)行下一次迭代。該策略可以增加種群多樣性以及避免早熟現(xiàn)象。

(10)

(11)

精英反向?qū)W習(xí)(Elite Opposition-Based Learning,EOBL)是通過當(dāng)前問題的可行解構(gòu)造其反向解以此來自增加種群多樣性,該策略已成功應(yīng)用于多種算法的改進(jìn),如郭雨鑫、劉升[9]等人將EOBL策略引入黏菌算法的改進(jìn),提高了黏菌種群的多樣性和種群質(zhì)量。劉琨[10]等人將EOBL策略與縱橫交叉策略來改進(jìn)鯨魚優(yōu)化算法,提高算法跳出局部最優(yōu)的能力。韓江、閔杰[11]在煙花爆炸式免疫遺傳算法的基礎(chǔ)上引入EOBL策略擴(kuò)大全局搜索,有效解決了免疫遺傳算法局部搜索能力弱、易早熟收斂的問題。

3.2 自適應(yīng)t分布變異

t分布含參數(shù)自由度n,其曲線形態(tài)與自由度n的大小有關(guān),n值越大,曲線越陡峭,曲線中間越高、雙側(cè)尾部態(tài)勢越低,t(n→∞)→N(0,1),t(n=1)=c(0,1),其中N(0,1)為高斯分布,c(0,1)為柯西分布,即標(biāo)準(zhǔn)高斯分布和柯西分布是t分布的兩個(gè)邊界特例分布,三者的函數(shù)分布如圖2所示。

圖2 部分測試函數(shù)收斂曲線圖

圖2 t分布、高斯分布和柯西分布函數(shù)分布圖

對于饑餓角色的位置狀態(tài)xi=(xi1,xi2,…,xin)定義見下式

(12)

自適應(yīng)t分布變異使用算法的迭代次數(shù)作為t分布的自由度參數(shù),在算法運(yùn)行初期,迭代次數(shù)較少,t分布變異近似于柯西分布變異,提高了算法的全局探索能力;在算法運(yùn)行后期,t分布變異近似于高斯分布變異,提高算法的局部開發(fā)能力;在算法運(yùn)行中期,t分布變異介于柯西變異和高斯變異之間,此時(shí)t分布變異算子結(jié)合了柯西變異算子和高斯變異算子的優(yōu)勢,即同時(shí)提高了算法的局部開發(fā)與全局探索的能力。

3.3 精英反向?qū)W習(xí)t分布饑餓游戲搜索算法

針對基本的饑餓游戲搜索算法存在尋優(yōu)精度低、收斂速度慢、易陷入局部最優(yōu)等缺點(diǎn),本文提出了一種基于精英反向?qū)W習(xí)t分布的饑餓游戲搜索算法(EtHGS)。本文使用精英反向?qū)W習(xí)策略來提高種群多樣性,采用群體選擇機(jī)制,將當(dāng)前饑餓角色群體與其反向群體按照適應(yīng)度值排序,從中選出最優(yōu)個(gè)體作為下一代饑餓角色個(gè)體來提高種群質(zhì)量。另外,本文引入自適應(yīng)t分布策略,在饑餓角色的個(gè)體中加入t分布型隨機(jī)干擾項(xiàng),充分利用當(dāng)前種群的信息干擾,使個(gè)體跳出局部最優(yōu),收斂于全局最優(yōu),并且提高了收斂速度。

EtHGS具體執(zhí)行步驟如下:

步驟1:設(shè)置相關(guān)參數(shù);

步驟2:種群初始化,主要包括初始化種群個(gè)體數(shù)N、候選解維度d、最大迭代次數(shù)tmax;所有個(gè)體饑餓程度的總和SHungry;

步驟3:根據(jù)目標(biāo)函數(shù)計(jì)算每一個(gè)饑餓角色的適應(yīng)度值;

步驟5:根據(jù)αj=min(Xi,j),βj=max(Xi,j)計(jì)算個(gè)體的當(dāng)前搜索邊界;

步驟6:對種群中的每個(gè)個(gè)體根據(jù)式(10)生成精英反向解并添加到反向種群OP中;

步驟7:從當(dāng)前種群和反向種群中選取適應(yīng)度值較好的S個(gè)優(yōu)良個(gè)體作為下一代種群;

步驟8:計(jì)算位置控制公式E;

步驟9:如果rand

步驟10:如果rand>p,直接利用式(2)來更新解,并對解做越界處理;

步驟11:判斷迭代次數(shù)是否達(dá)到最大;若是,結(jié)束算法并輸出最優(yōu)解;反之,轉(zhuǎn)向步驟9。

4 仿真與結(jié)果分析

4.1 仿真環(huán)境

本次仿真測試環(huán)境為:操作系統(tǒng)版本為Win10、64位操作系統(tǒng),處理器為Intel(R) Core(TM) i5-10210U CPU 1.60GHz 2.11 GHz,內(nèi)存16.0GB,主頻2.11GHz,仿真軟件為Matlab2020b。

4.2 實(shí)驗(yàn)參數(shù)設(shè)置

本文選取饑餓游戲搜索算法(HGS)、哈里斯鷹算法[12](HHO)、黏菌算法[13](SMA)、精英反向黃金正弦鯨魚算法[14](EGoldenSWOA)以及本文提出的精英反向?qū)W習(xí)t分布饑餓游戲搜索算法對比(EtHGS),所有算法種群規(guī)模設(shè)置為30,迭代次數(shù)設(shè)置為500,共有參數(shù)保持一致。各算法的參數(shù)設(shè)置如表1所示。

4.3 測試函數(shù)

為了進(jìn)一步驗(yàn)證EtHGS算法的優(yōu)化效果和穩(wěn)定性優(yōu)于其它算法,本文對18個(gè)不同特點(diǎn)的測試函數(shù)進(jìn)行函數(shù)優(yōu)化對比測試,其中f1f5是單峰函數(shù),用以評(píng)估算法的尋優(yōu)精度和收斂速度;f6～f18是多峰函數(shù),對算法的全局探索能力有更好的檢驗(yàn)?zāi)芰Αy試函數(shù)及其具體信息如表2所示。

表2 本文選用的18個(gè)測試函數(shù)

4.4 與其它智能算法的對比分析

為驗(yàn)證EtHGS算法改進(jìn)的合理性和有效性,本文對算法的性能在18個(gè)測試函數(shù)上進(jìn)行了驗(yàn)證,為了避免實(shí)驗(yàn)偶然性帶來的結(jié)果偏差,算法在各基準(zhǔn)函數(shù)上獨(dú)立運(yùn)行30次。表3列出了餓游戲搜索算法(HGS)、哈里斯鷹算法(HHO)、黏菌算法(SMA)、精英反向黃金正弦算法(EGoldenSWOA)以及精英反向?qū)W習(xí)t分布饑餓游戲搜索算法(EtHGS)在多個(gè)標(biāo)準(zhǔn)函數(shù)上經(jīng)過30次獨(dú)立運(yùn)行后得到的實(shí)驗(yàn)結(jié)果。

表3 測試函數(shù)實(shí)驗(yàn)結(jié)果

f1～f5為單模態(tài)函數(shù),一般用于檢測算法的開發(fā)能力。根據(jù)實(shí)驗(yàn)結(jié)果可知,對于f1、f3,EtHGS、HGS、SMA以及EGoldenSWOA尋優(yōu)效果可以達(dá)到最優(yōu)值,HHO的尋優(yōu)效果最差;對于f2、f4,EtHGS以及HGS的尋優(yōu)效果最佳,SMA也表現(xiàn)良好,EGoldenSWOA較差,HHO表現(xiàn)最差;對于f5,EGoldenSWOA尋優(yōu)效果最好,EtHGS次之,HGS尋優(yōu)效果一般,HHO較差,SMA最差;對于f6、f7、f8、f10、f12～f15,所測試的5種算法尋優(yōu)效果均能達(dá)到最優(yōu)值;對于f9,EGoldenSWOA尋優(yōu)效果最好,EtHGS次之,HGS尋優(yōu)效果一般,HHO較差,SMA最差;對于f11,EtHGS以及HGS的尋優(yōu)效果最佳,EGoldenSWOA次之,HHO較差,SMA最差;對于f16～f18,EtHGS的尋優(yōu)效果最佳,其平均值最接近測試函數(shù)最優(yōu)值,標(biāo)準(zhǔn)差最小。綜上所述,對于所選的測試函數(shù),EtHGS算法明顯好于一些新穎的算法。

為了直觀展示EtHGS算法的尋優(yōu)速度與性能,本文給出了部分基準(zhǔn)函數(shù)的收斂曲線,如圖2所示。

由圖2的收斂曲線可以直觀的看出改進(jìn)EtHGS算法的收斂精度優(yōu)于HGS、HHO、SMA和EGoldenSWOA,在收斂速度上也相對快于其它四種算法。函數(shù)f1～f5屬于單模態(tài)函數(shù),常常用來測試算法的開發(fā)能力,由f1～f4的收斂曲線圖可知,改進(jìn)后EtHGS算法的收斂速度有明顯的提升,對于f1、f3,EtHGS算法在350次迭代后可以達(dá)到最優(yōu)值,明顯快于其它算法。另外,觀察f7、f8、f13和f15的收斂曲線圖可知,雖然改進(jìn)后的算法尋優(yōu)精度提高相對較小,但根據(jù)收斂曲線圖可知,改進(jìn)的算法能更快找到最優(yōu)值,并且改進(jìn)的算法在f8上出現(xiàn)了多個(gè)拐點(diǎn),證明改進(jìn)后的EtHGS算法容易跳出局部最優(yōu)值,能更好地進(jìn)行全局最優(yōu)。

4.5 求解高維函數(shù)的實(shí)驗(yàn)分析

根據(jù)上述實(shí)驗(yàn)結(jié)果可知,論文改進(jìn)的EtHGS算法對于低維函數(shù)得到了較好的尋優(yōu)結(jié)果。但是一般的改進(jìn)策略在較為復(fù)雜的現(xiàn)實(shí)問題上容易陷入“維數(shù)災(zāi)難”,為了更好地測試EtHGS算法的高維適應(yīng)性,論文對EtHGS算法進(jìn)行了高維函數(shù)測試實(shí)驗(yàn),使得HGS算法、EtHGS算法、SMA算法、HHO算法在100維、200維、500維的測試函數(shù)上分別獨(dú)立運(yùn)行30次,其它參數(shù)設(shè)置同4.1節(jié)。

由表4的結(jié)果可知,EtHGS算法在各個(gè)維度上的四項(xiàng)指標(biāo)均優(yōu)于原始HGS算法、HHO算法以及SMA算法。EtHGS算法在3種高維狀態(tài)下屢次收斂至f1～f4的理論最優(yōu)值,例如,對于f1函數(shù),EtHGS算法與其它三種算法比較最高提升了115個(gè)數(shù)量級(jí),說明EtHGS算法提高了求解精度和魯棒性。對于f5函數(shù),EtHGS算法與其它三種算法在最優(yōu)值的收斂表現(xiàn)不相上下;對于f9函數(shù),EtHGS算法與其它三種算法相比平均高出1～5個(gè)數(shù)量級(jí)。綜上所述,采用精英反向?qū)W習(xí)策略以及t分布型隨機(jī)干擾項(xiàng)使得改進(jìn)后的EtHGS算法可以充分搜索解空間,保留更多的優(yōu)良個(gè)體,為算法奠定高質(zhì)量迭代基礎(chǔ),并且很好的提高了精度和收斂速度這兩方面。

表4 高維函數(shù)求解結(jié)果

5 結(jié)語

饑餓游戲搜索算法是近年來提出的一種新型尋優(yōu)性能良好的啟發(fā)式算法,本文針對原始饑餓游戲搜索算法收斂精度不高、易陷入局部最優(yōu)等缺陷提出了精英反向?qū)W習(xí)t分布饑餓游戲搜索算法。本文利用精英反向?qū)W習(xí)策略改善了種群初始化,接著引入自適應(yīng)t分布策略,在饑餓角色的個(gè)體中加入t分布型隨機(jī)干擾項(xiàng),使個(gè)體跳出局部最優(yōu),收斂于全局最優(yōu),并且提高了收斂速度,最終優(yōu)化了整個(gè)算法的尋優(yōu)性能。本文通過單模態(tài)、多模態(tài)和高維多個(gè)測試函數(shù)來驗(yàn)證改進(jìn)后算法的性能,研究結(jié)果表明結(jié)合兩種改進(jìn)策略較好地提升了原始饑餓游戲搜索算法的全局尋優(yōu)性能、收斂精度和速度以及算法魯棒性。

已有文獻(xiàn)表明群智能算法經(jīng)常被應(yīng)用于多個(gè)金融領(lǐng)域,例如金融信用風(fēng)險(xiǎn)評(píng)價(jià)、經(jīng)濟(jì)調(diào)度、證券市場分析、金融風(fēng)險(xiǎn)預(yù)警和產(chǎn)銷不平衡等領(lǐng)域。柳宗偉等[15]提出以GIS (地理信息系統(tǒng))為可視化分析平臺(tái)、以神經(jīng)網(wǎng)絡(luò)和遺傳算法為分析模型的綜合選址方法;孫藝等[16]在一種非線性金融風(fēng)險(xiǎn)模型中引入改進(jìn)后的粒子群算法選擇最優(yōu)控制參數(shù),最大程度降低金融系統(tǒng)的總風(fēng)險(xiǎn)值。今后研究方向主要是拓展EtHGS算法優(yōu)化神經(jīng)網(wǎng)絡(luò)參數(shù)在量化投資方面的應(yīng)用。