精英反向學習t分布饑餓游戲搜索算法

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

(上海工程技術大學管理學院,上海 201620)

1 引言

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

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

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

2 基本饑餓游戲搜索算法

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

行為選擇和活動選擇在動物王國是普遍的,它是自然界中以目標為導向的行為的基本法則。各種因素或因素間的組合會影響物種的行為,觀察到的行為取決于其所在地區現有的動機狀態和刺激的出現。神經學家認為對任何動物來說,饑餓是其活動、學習和尋找食物的強大動力,是將生活條件改變為更穩定狀態的力量。

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

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

1)靠近食物

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

(1)

表1 各算法實驗參數設置

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

(2)

(3)

(4)

其中rand是[0,1]中的隨機數。

2)饑餓角色

在這一部分中,個體在搜索中的饑餓特征通過一個提出的模型進行數學模擬。

(5)

(6)

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

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

hungry(i)的公式如下

(7)

其中AllFitness(i)代表當前迭代位置的適應度值。

H的公式如下:

(8)

(9)

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

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

圖1 HGS算法流程圖

3 精英反向學習t分布饑餓游戲搜索算法

3.1 精英反向學習策略

Tizhoosh[8]于2005年提出了一種反向解比當前解更接近于全局最優解的一種策略——精英反向學習策略,其主要原理是對問題的可行解求其反向解,并對原始解和反向解進行排序,從中選出較優解作為新一代個體進行下一次迭代。該策略可以增加種群多樣性以及避免早熟現象。

(10)

(11)

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

3.2 自適應t分布變異

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

圖2 部分測試函數收斂曲線圖

圖2 t分布、高斯分布和柯西分布函數分布圖

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

(12)

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

3.3 精英反向學習t分布饑餓游戲搜索算法

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

EtHGS具體執行步驟如下:

步驟1:設置相關參數;

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

步驟3:根據目標函數計算每一個饑餓角色的適應度值;

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

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

步驟7:從當前種群和反向種群中選取適應度值較好的S個優良個體作為下一代種群;

步驟8:計算位置控制公式E;

步驟9:如果rand

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

步驟11:判斷迭代次數是否達到最大;若是,結束算法并輸出最優解;反之,轉向步驟9。

4 仿真與結果分析

4.1 仿真環境

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

4.2 實驗參數設置

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

4.3 測試函數

為了進一步驗證EtHGS算法的優化效果和穩定性優于其它算法,本文對18個不同特點的測試函數進行函數優化對比測試,其中f1f5是單峰函數,用以評估算法的尋優精度和收斂速度;f6～f18是多峰函數,對算法的全局探索能力有更好的檢驗能力。測試函數及其具體信息如表2所示。

表2 本文選用的18個測試函數

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

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

表3 測試函數實驗結果

f1～f5為單模態函數,一般用于檢測算法的開發能力。根據實驗結果可知,對于f1、f3,EtHGS、HGS、SMA以及EGoldenSWOA尋優效果可以達到最優值,HHO的尋優效果最差;對于f2、f4,EtHGS以及HGS的尋優效果最佳,SMA也表現良好,EGoldenSWOA較差,HHO表現最差;對于f5,EGoldenSWOA尋優效果最好,EtHGS次之,HGS尋優效果一般,HHO較差,SMA最差;對于f6、f7、f8、f10、f12～f15,所測試的5種算法尋優效果均能達到最優值;對于f9,EGoldenSWOA尋優效果最好,EtHGS次之,HGS尋優效果一般,HHO較差,SMA最差;對于f11,EtHGS以及HGS的尋優效果最佳,EGoldenSWOA次之,HHO較差,SMA最差;對于f16～f18,EtHGS的尋優效果最佳,其平均值最接近測試函數最優值,標準差最小。綜上所述,對于所選的測試函數,EtHGS算法明顯好于一些新穎的算法。

為了直觀展示EtHGS算法的尋優速度與性能,本文給出了部分基準函數的收斂曲線,如圖2所示。

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

4.5 求解高維函數的實驗分析

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

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

表4 高維函數求解結果

5 結語

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

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