智能優化算法：堆優化算法
文章目錄
- 智能優化算法：堆優化算法
-
- 1.算法原理
- 2.算法結果
- 3.參考文獻
- 4.Matlab代碼
摘要：堆優化算法(Heap-based optimizer，HBO)是 Askari 等人在 2020 年提出的一種新型智能優化算法。它利用堆結構模拟了公司的層級結構，采用了堆的概念形成個體之間的互動，并且建構了三種構造新解的數學模型。具有收斂速度快，精度高的特點。
1.算法原理
HBO 模拟公司層次結建構立的樹狀結構，目前它選擇的是三元堆或者說是一個三叉樹，具體詳見圖 1。企業等級制度的最終目标是以最好的方式完成與業務相關的任務，主要包括三個數學模型:下屬與直接上司的互動、與同僚的互動和個體的自我貢獻。
圖1.三元堆
圖1中 X 1 X_1 X1所在的層次為最高層第一層，僅有一個個體(其适應度值最高，為最優個體)，； X 2 ∼ X 4 X_2\sim X_4 X2∼X4所在的層次為第二層，3 個個體(它們的适應度值低于第一層個體的适應度值，以下類似)； X 5 ∼ X 13 X_5\sim X_{13} X5∼X13 所在的層次為第三層，9 個個體；如此，第四層應該有 27 個體；所有這些個體組成一個群體，其種群大小為 40。其中，第一層至第三層在本文中稱為高層，第四層為低層(其中個體的适應度值低于高層個體的适應度值)。從 X 2 X_2 X2開始所有的個體都是通過直接上司和同僚的引導進行更新。以 X 8 X_8 X8 為例，由于堆獨特的結構，與 X 8 X_8 X8 在同一層次的個體均為其同僚，為 X 5 X 13 X_5 ~X_{13} X5 X13 ，且隻有一個直接上司 X 3 X_3 X3 。然而對于最高上司 X 1 X_1 X1 ，它所在的層是最高層，沒有直接上司，并且該層隻有 X 1 X_1 X1 一個個體，也不存在同僚。
與直接上司互動的數學模型可以描述為:
X i j ( t + 1 ) = B j + γ λ ∣ B j − X i j ( t ) ∣ (1) X_i^j(t+1)=B^j+\gamma \lambda |B^j-X_i^j(t)|\tag{1} Xij(t+1)=Bj+γλ∣Bj−Xij(t)∣(1)
γ = ∣ 2 − 4 ∗ m o d ( t , 25 ) / 25 ∣ (2) \gamma=|2-4*mod(t,25)/25| \tag{2} γ=∣2−4∗mod(t,25)/25∣(2)
λ = 2 r − 1 (3) \lambda = 2r-1 \tag{3} λ=2r−1(3)
其中， t t t 是目前疊代次數， T T T 是最大疊代次數， j j j 是一個解向量的第 j j j 個分量， B B B 是目前個體的直接上司。 r r r 是均勻分布在[0,1]中的随機數。在疊代過程中， γ γ γ 是一個三角波，它的值在 1 的左右波動，從 2 到 0，或從 0 到 2。
在堆中，位于同一層的個體都是其同僚，每個個體 X i X_i Xi根據其随機選擇的同僚$ S_r$ 更新其位置，其數學模型見式(4)。
X i j ( t + 1 ) = { S r j + γ λ ∣ S r j − X i j ( t ) ∣ , f ( S r ) < f ( X i ( t ) ) X i j + γ λ ∣ S r j − X i j ( t ) ∣ , e l s e (4) X_i^j(t+1)=\begin{cases} S_r^j+\gamma \lambda|S_r^j-X_i^j(t)|,f(S_r)<f(X_i(t))\\ X_i^j+\gamma \lambda|S_r^j-X_i^j(t)|,else \end{cases}\tag{4} Xij(t+1)={Srj+γλ∣Srj−Xij(t)∣,f(Sr)<f(Xi(t))Xij+γλ∣Srj−Xij(t)∣,else(4)
其中， f f f 是個體的目标函數。對于最小極值問題，若 f ( S r ) < f ( X i ) f (S_r)<f(X_i) f(Sr)<f(Xi)，個體可以探索 S r S_r Sr 周圍的區域；若 f ( S r ) ≥ f ( X i ) f (S_r )≥ f (X_i ) f(Sr)≥f(Xi)，個體可以探索 X i X_i Xi 周圍的區域，以保證搜尋向好的方向發展。
在個體的自我貢獻的模型中，個體在前一次疊代中的一些位置資訊會一直保留到下一次疊代。即個體 X i X_i Xi 在下一次疊代中不會改變其第 j j j個分量的值。
X i j ( t + 1 ) = X i j ( t ) (5) X_i^j(t+1)=X_i^j(t)\tag{5} Xij(t+1)=Xij(t)(5)
在 HBO 中， p 1 p_1 p1 ， p 2 p_2 p2 和 p 3 p_3 p3決定了個體将會在這三個數學模型中選擇哪個模型進行更新。選擇機率的計算方法如下:
p 1 = 1 − t / T (6) p_1=1-t/T \tag{6} p1=1−t/T(6)
p 2 = p 1 + ( 1 − p 1 ) / 2 (7) p_2=p_1+(1-p_1)/2 \tag{7} p2=p1+(1−p1)/2(7)
HBO 通過 p 1 p_1 p1 選擇自我貢獻模型更新個體，通過 p 2 p_2 p2 選擇與直接上司互動的數學模型更新個體，通過 p 3 p_3 p3 選擇與同僚互動的數學模型更新個體，其中 p 3 = 1 p_3 =1 p3=1
算法 1: 堆優化算法
Step1: 設定參數并随機初始化種群
Step2: 評估種群中個體的适應度值，擷取全局最優解
Step3: 建構堆
Step4: for t=1 to T do
Step5: for i= N to 2 do
Step6: for j=1 to D do
Step7: p=rand
Step8: if p≤p 1
Step9: 通過公式（5）更新個體位置
Step10: else if p > p 1 & p ≤ p 2
Step11: 通過公式（1）更新個體位置
Step12: else
Step13: if p > p 2 & p ≤ p 3
Step14: 通過公式（4）更新個體位置
Step15: end if
Step16: end if
Step17: end for
Step18: 邊界控制，計算個體的适應度值
Step19: 貪心選擇更新種群
Step20: 更新堆，更新全局最優解
Step21: end for
Step22: end for
Step23: 輸出全局最優解
2.算法結果
3.參考文獻
[1]Qamar Askari,Mehreen Saeed,Irfan Younas. Heap-based optimizer inspired by corporate rank hierarchy for global optimization[J]. Expert Systems With Applications,2020,161:
[1]張新明,溫少晨,劉尚旺.差分擾動的堆優化算法[J/OL].計算機應用:1-9[2021-12-11].http://kns.cnki.net/kcms/detail/51.1307.TP.20211014.1631.021.html.