智能優化算法之海豚回聲定位(Dolphin echolocation,DE)

一種新的優化方法：海豚回聲定位

海豚回聲定位算法（Dolphin echolocation,DE）由伊朗人A. Kaveh和N. Farhoudi于2013年提出，是一種新型的元啟發式優化算法，其模拟了海豚在捕食過程中利用回聲定位的政策。

回聲定位

海豚可以發出滴答滴答的聲音，這些滴答聲的頻率遠遠高于交流信号的頻率。當聲音撞擊到物體，聲波的部分能量會反射回海豚身上，海豚接收到回聲後會發出另一種滴答聲，海豚會根據滴答聲與回聲之間的時間間隔評估出與物體的距離，還會根據頭部兩側接收到的不同強度的信号進行方向判斷，通過不斷地發出滴答聲和接受回聲，海豚可以跟蹤并鎖定目标。當海豚接近感興趣的目标時，還會提高滴答的速率。

盡管蝙蝠也是利用回聲定位，但是它們卻與海豚的聲納系統不同。蝙蝠聲納系統的範圍較小，一般3到4米左右，而海豚能探測到的目标範圍從幾十米到一百多米不等。聲波在空氣中的傳播速度大約是水傳播速度的五分之一，是以蝙蝠在聲納傳播過程中的資訊傳遞速度要比海豚短得多。這些在環境和獵物方面的不同就需要不同類型的聲納系統，進而很難直接比較出孰好孰壞。

對于優化問題，海豚利用回聲定位的原理捕食獵物的過程類似于尋找問題的最優解。初始時，海豚對整個空間進行搜尋以尋找獵物，随着越來越接近目标，海豚就會縮小搜尋範圍，并增加滴答聲以專注于某一位置。

該算法通過限制與目标距離成比例的探索來模拟回聲定位，分為兩個階段：第一階段，算法探索整個空間以進行去全局搜尋，因而可以搜尋未曾探索過的區域，主要是通過随機探索位置來實作；第二階段，算法将圍繞前一階段中獲得的較優結果附近進行開發利用。

使用海豚回聲定位算法時，使用者可以根據預定義的曲線改變階段1與階段2産生解的比率。在使用者定義的這條曲線上應該保證優化收斂，算法然後設定參數以便遵循這條曲線。與其他方法相比，該方法與最優解出現的可能性相關，換句話說，對于每個變量，在可行域内都有不同的可選值，在每個循環中，算法根據使用者确定的收斂曲線，定義了選擇到目前為止實作的最優值的可能性，利用這條曲線，使算法的收斂性得到控制，進而降低對參數的依賴性。

回聲定位算法

在開始優化之前，需要對搜尋空間按以下規則進行排序：

搜尋空間排序：對于每個變量，對搜尋空間的可選值按升序或降序排序，如果可選值包含多個特征，則按最重要的進行排序。對于變量 j j j，所有的可選值構成了長度為 L A j LA_j LAj​的向量 A j A_j Aj​，将這些向量作為列就得到了矩陣 A l t e r n a t i v e s M A × N V Alternatives_{MA\times NV} AlternativesMA×NV​，其中 M V MV MV為 m a x ( L A j ) j = 1 : N V max(LA_{j})_{j=1:NV} max(LAj​)j=1:NV​， N V NV NV為變量個數。

優化過程中收斂因子應根據曲線進行改變，曲線定義如下：

P P ( L o o p i ) = P P 1 + ( 1 − P P 1 ) L o o p i Power  − 1 ( LoopsNumber ) Power − 1 (1) P P\left(L o o p_{i}\right)=P P_{1}+\left(1-P P_{1}\right) \frac{L o o p_{i}^{\text {Power }}-1}{(\text {LoopsNumber})^{\text {Power}}-1}\tag{1} PP(Loopi​)=PP1​+(1−PP1​)(LoopsNumber)Power−1LoopiPower ​−1​(1)

其中 P P PP PP為預定義的機率， P P 1 PP_1 PP1​為第一次循環時的收斂因子，在第一次循環中随機選擇解。 L o o p i Loop_i Loopi​為目前循環數， P o w e r Power Power為曲線度。

循環數：算法達到收斂點的循環數，這個參數應該根據計算量由使用者選擇。

算法的流程圖如下圖所示，以下面的優化問題為例，說明海豚回聲定位的主要步驟。

min ⁡ ( h = ∑ i = 1 N x i 2 ) , x i ∈ Z , − 20 ⩽ x i ⩽ 20 (2) \min \left(h=\sum_{i=1}^{N} x_{i}^{2}\right), \quad x_{i} \in Z,-20 \leqslant x_{i} \leqslant 20\tag{2} min(h=i=1∑N​xi2​),xi​∈Z,−20⩽xi​⩽20(2)

其中 N = 4 N=4 N=4。

在算法優化之前，首先根據等式(1)選擇曲線，其中 P o w e r = 1 Power=1 Power=1，循環數Loops number=8，以及 P P 1 0.1 PP_10.1 PP1​0.1，則由

P P = 0.1 + 0.9 ( Loop i − 1 7 ) = 0.1 + 0.9 ( Loop i − 1 ) (3) P P=0.1+0.9\left(\frac{\text {Loop}_{i}-1}{7}\right)=0.1+0.9\left(\text {Loop}_{i}-1\right)\tag{3} PP=0.1+0.9(7Loopi​−1​)=0.1+0.9(Loopi​−1)(3)

1. 随機初始化 N L NL NL個海豚位置。

這一步主要包括建立 L N V × N V L_{NV\times NV} LNV×NV​，其中 N L NL NL為位置個數， N V NV NV為變量個數（每個位置的次元）。對于該執行個體，考慮 N L = 30 NL=30 NL=30， N V = 4 NV=4 NV=4，每個次元取值均在[-20,20]之間，第 i i i位置的解可能為 L i = 10 , 4 , − 7 , 18 L_i={10,4,-7,18} Li​=10,4,−7,18。

1. 根據等式（1）（對于該例子就是等式（3））計算循環的 P P PP PP。
2. 計算每個位置的适應度值。

在該例中，式（2）定義了目标函數，如對于位置 L i L_i Li​， h = ( − 10 ) 2 + 4 2 + ( − 7 ) 2 + 1 8 2 = 489 h=(-10)^2+4^2+(-7)^2+18^2=489 h=(−10)2+42+(−7)2+182=489。在海豚回聲定位算法中，适應度值用于計算機率，較優的适應度值應該具有更高的機率，是以對于對于最小化問題則适應度應該為目标值的相反數，即 F i t n e s s = 1 / h Fitness=1/h Fitness=1/h。為了避免除以0，通常使用 F i t n e s s = 1 / ( h + 1 ) Fitness=1/(h+1) Fitness=1/(h+1)，在該例中， F i t n e s s ( L i ) = 1 / ( 489 + 1 ) = 0.00204 Fitness(L_i)=1/(489+1)=0.00204 Fitness(Li​)=1/(489+1)=0.00204。

1. 根據如下的海豚規則計算累積适應度值：

(a)

for i i i=1 to 可選值個數

 for j j j=1 to 變量個數

  找到Alternatives中第 j j j列的位置 L ( i , j ) L(i,j) L(i,j)，命名為 A A A

  for k k k= − R e -R_e −Re​ to R e R_e Re​

    A F ( A + k ) j = 1 R e ∗ ( R e − ∣ k ∣ )  Fitness  ( i ) + A F ( A + k ) j ( 4 ) A F_{(A+k) j}=\frac{1}{R_{e}} *\left(R_{e}-|k|\right) \text { Fitness }(i)+A F_{(A+k) j}(4) AF(A+k)j​=Re​1​∗(Re​−∣k∣) Fitness (i)+AF(A+k)j​(4)

  end

 end

end

其中 A F ( A + k ) j A F_{(A+k) j} AF(A+k)j​是為第 j j j個變量選擇的第 ( A + k ) (A+k) (A+k)個可選值的累積适應度值（可選值的編号等于Alternatives矩陣的排序）， R e R_e Re​為有效半徑，在該半徑内A的鄰域的累積适應度都會受到A的适應度值的影響，該半徑建議不超過搜尋空間的1/4。

對于靠近邊緣的可選值（ A + k A+k A+k無效， A + k < 0 A+k<0 A+k<0或 A + k > L A j A+k>LA_j A+k>LAj​）， A F AF AF将使用反射特征進行計算，這種情況下，如果可選值與邊緣的距離小于 R e R_e Re​，那麼在邊緣上放置一面鏡子時，在上述可選值的鏡像位置上存在相同的可選值。

(b)為了在搜尋空間中更均勻地分布分布這種可能性，對所有的序列均加上一個很小的數 A F = A F + ε A F=A F+\varepsilon AF=AF+ε，其中 ε \varepsilon ε應該按照适應度值定義的方式選擇，最好小于适應度值所能取得的最小值。

©找到目前循環中的最優位置，并記為最優位置“The best location”，找出配置設定給最優位置中各個變量的可選值，設定它們的 A F AF AF為0，即：

for j = 1 j=1 j=1 to 變量個數

 for i i i=1 to 可選值個數

  if i i i=The best location( j j j)

    A F i j = 0 AF_{ij}=0 AFij​=0

  end

 end

end

對于上述優化問題，首先根據等式(2)計算累積适應度值，前面提到過，可選值應該按照升序進行排列，則可選矩陣為：

 Alternatives  = [ − 20 − 20 − 20 − 20 − 19 − 19 − 19 − 19 ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ ⋅ 19 19 19 19 20 20 20 20 ] (5) \text { Alternatives }=\left[\begin{array}{cccc} -20 & -20 & -20 & -20 \\ -19 & -19 & -19 & -19 \\ \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ \cdot & \cdot & \cdot & \cdot \\ 19 & 19 & 19 & 19 \\ 20 & 20 & 20 & 20 \end{array}\right]\tag{5}  Alternatives =⎣⎢⎢⎢⎢⎢⎢⎢⎢⎡​−20−19⋅⋅⋅1920​−20−19⋅⋅⋅1920​−20−19⋅⋅⋅1920​−20−19⋅⋅⋅1920​⎦⎥⎥⎥⎥⎥⎥⎥⎥⎤​(5)

對于采樣位置 L i L_i Li​,考慮 R e = 10 R_e=10 Re​=10，則等式(4)變為：

for i = L i i=L_i i=Li​

 for j j j=1 to 4

  找到Alternatives中第 j j j列的位置 L ( i , j ) L(i,j) L(i,j)，命名為 A A A

  for k k k= − 10 -10 −10 to 10 10 10

    A F ( A + k ) j = 1 10 ∗ ( 10 − ∣ k ∣ )  Fitness  ( i ) + A F ( A + k ) j ( 6 ) A F_{(A+k) j}=\frac{1}{10} *\left(10-|k|\right) \text { Fitness }(i)+A F_{(A+k) j}(6) AF(A+k)j​=101​∗(10−∣k∣) Fitness (i)+AF(A+k)j​(6)

  end

 end

end

其中式(5)也可表示為：

for j = 1 , 2 , 3 , 4 j={1,2,3,4} j=1,2,3,4

  L ( i , j ) = − 10 , 4 , − 7 , 18 L(i,j)={-10,4,-7,18} L(i,j)=−10,4,−7,18,那麼 A = 11 , 25 , 14 , 39 A={11,25,14,39} A=11,25,14,39，-10在可選值矩陣的第一列中排在第11位，以此類推就可以得到 A A A。

 for k k k=-10 to 10

   A F ( 11 + k ) 1 = 1 10 ∗ ( 10 − ∣ k ∣ )  Fitness  ( i ) + A F ( 11 + k ) 1 ( 7 ) A F_{(11+k) 1}=\frac{1}{10} *\left(10-|k|\right) \text { Fitness }(i)+A F_{(11+k) 1}(7) AF(11+k)1​=101​∗(10−∣k∣) Fitness (i)+AF(11+k)1​(7)

   A F ( 25 + k ) 2 = 1 10 ∗ ( 10 − ∣ k ∣ )  Fitness  ( i ) + A F ( 25 + k ) 2 A F_{(25+k) 2}=\frac{1}{10} *\left(10-|k|\right) \text { Fitness }(i)+A F_{(25+k) 2} AF(25+k)2​=101​∗(10−∣k∣) Fitness (i)+AF(25+k)2​

   A F ( 14 + k ) 3 = 1 10 ∗ ( 10 − ∣ k ∣ )  Fitness  ( i ) + A F ( 14 + k ) 3 A F_{(14+k) 3}=\frac{1}{10} *\left(10-|k|\right) \text { Fitness }(i)+A F_{(14+k) 3} AF(14+k)3​=101​∗(10−∣k∣) Fitness (i)+AF(14+k)3​

   A F ( 39 + k ) 4 = 1 10 ∗ ( 10 − ∣ k ∣ )  Fitness  ( i ) + A F ( 39 + k ) 4 A F_{(39+k) 4}=\frac{1}{10} *\left(10-|k|\right) \text { Fitness }(i)+A F_{(39+k) 4} AF(39+k)4​=101​∗(10−∣k∣) Fitness (i)+AF(39+k)4​

 end

end

ϵ = 1 / ( 4 ∗ 2 0 2 ) \epsilon=1/(4*20^2) ϵ=1/(4∗202)，那麼 A F = A F + 0.000625 AF=AF+0.000625 AF=AF+0.000625。

在式(7)的這些等式中，對于第2個變量 j = 2 j=2 j=2，在計算累積适應度時，應該将搜尋空間分為兩個區域：受影響區域(有效半徑内)和不受影響區域。設定 R e = 10 R_e=10 Re​=10，由于第2個變量選擇的可選值為4，那麼與4的距離大于10( x < 6 x<6 x<6或 x > 10 x>10 x>10)的區域不會受到影響。同時在受影響的區域内，由該樣本位置産生的累積适應度線性變化，其最大值出現在x=4處，則有：

A F = A F + 0.000625 AF=AF+0.000625 AF=AF+0.000625

對所有随機選擇的解進行以上操作，就得到了第一次循環的最終累積适應度。

1. 對于變量 j ( j = 1 t o N V ) j_{(j=1 to NV)} j(j=1toNV)​，根據以下關系計算選擇可選值 i ( i = 1 t o A L j ) i_{(i=1toAL_j)} i(i=1toALj​)​的機率：

   P i j = A F i j ∑ i = 1 L A j A F i j (8) P_{i j}=\frac{A F_{i j}}{\sum_{i=1}^{L A j} A F_{i j}}\tag{8} Pij​=∑i=1LAj​AFij​AFij​​(8)

根據配置設定給每個可選值的機率，計算下一步的位置。

在該例中，對于變量 j ( j = 1 t o 4 ) j_{(j=1 to 4)} j(j=1to4)​,計算可選值 i ( i = 1 t o 40 ) i_{(i=1to40)} i(i=1to40)​的機率：

P i j = A F i j ∑ k = 1 40 A F k j (9) P_{i j}=\frac{A F_{i j}}{\sum_{k=1}^{40} A F_{k j}}\tag{9} Pij​=∑k=140​AFkj​AFij​​(9)

1. 為最優位置的所有變量選擇的所有可選值配置設定機率 P P PP PP,根據下面的公式，把其餘的機率配置設定給其他可選值：

for j = 1 j=1 j=1 to 變量個數

 for i = 1 i=1 i=1 to 可選值個數

  if i = 1 i=1 i=1 The best location( j j j)

    P i j = P P P_{ij}=PP Pij​=PP (10)

  else

    P i j = ( 1 − P P ) P i j P_{ij}=(1-PP)P_{ij} Pij​=(1−PP)Pij​ (11)

  end

 end

end

第一次循環的最優位置為 X 1 = − 11 , X 2 = 3 , X 3 = X 4 = 4 X1=-11,X2=3,X3=X4=4 X1=−11,X2=3,X3=X4=4，根據等式(3)，第一次循環的 P P = 10 % PP=10\% PP=10%,即在最優位置上的所有變量的機率為 10 % 10\% 10%,而将剩餘的 90 % 90\% 90%配置設定給其他可選值。

P i j = ( 1 − 0.1 ) P i j = 0.9 P i j (12) P_{i j}=(1-0.1) P_{i j}=0.9 P_{i j}\tag{12} Pij​=(1−0.1)Pij​=0.9Pij​(12)