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

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

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

1 引言

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

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

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

2 基本饑餓游戲搜索算法

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

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

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

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

1)靠近食物

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

(1)

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

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

(2)

(3)

(4)

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

2)饑餓角色

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

(5)

(6)

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

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

hungry(i)的公式如下

(7)

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

H的公式如下:

(8)

(9)

其中r6是[0,1]之間的隨機數(shù),F(i)代表每個個體的適應(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)解作為新一代個體進(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策略擴大全局搜索,有效解決了免疫遺傳算法局部搜索能力弱、易早熟收斂的問題。

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分布的兩個邊界特例分布,三者的函數(shù)分布如圖2所示。

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

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

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

(12)

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

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

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

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

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

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

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

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

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

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

步驟8:計算位置控制公式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ù)設(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)一步驗證EtHGS算法的優(yōu)化效果和穩(wěn)定性優(yōu)于其它算法,本文對18個不同特點的測試函數(shù)進(jìn)行函數(shù)優(yōu)化對比測試,其中f1f5是單峰函數(shù),用以評估算法的尋優(yōu)精度和收斂速度;f6～f18是多峰函數(shù),對算法的全局探索能力有更好的檢驗?zāi)芰Αy試函數(shù)及其具體信息如表2所示。

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

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

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

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

f1～f5為單模態(tài)函數(shù),一般用于檢測算法的開發(fā)能力。根據(jù)實驗結(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)了多個拐點,證明改進(jìn)后的EtHGS算法容易跳出局部最優(yōu)值,能更好地進(jìn)行全局最優(yōu)。

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

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

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

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

5 結(jié)語

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

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