隨機交叉全局和聲搜索算法

翟軍昌，秦玉平

1.渤海大學 信息科學與技術學院，遼寧 錦州 121013

2.渤海大學 工學院，遼寧 錦州 121013

1 引言

受音樂創作中樂師根據經驗調音現象的啟發，Geem等人提出了一種新的啟發式優化算法和聲搜索（Harmony Search，HS）[1]。與一般啟發式優化算法[2-6]相比，HS算法種群規模小故內存開銷較小，而且每次迭代只產生一個候選和聲向量，提高了算法的靈活性。此外，HS算法不需要對求解問題進行編碼等操作。HS算法參數較少，具有非常好的優化效果，因此在工程中得到了廣泛的應用[7-8]。

HS算法在進化后期容易盲目搜索，不能有效調整解向量的結構。如果算法產生質量較高的解向量則會引導算法較快地收斂，若收斂到局部最優，則很難再跳出局部最優解。因此，提高算法跳出局部最優的能力受到了研究者廣泛的關注[6-13]。

文獻[9-10]探索了和聲記憶庫考慮概率HMCR、基音調整概率PAR和基因調整步長bw的調節對算法的影響，提出動態參數策略提高算法性能。但算法中引入了過多的靜態參數，導致算法的適用性降低。文獻[11-15]分別研究了全局最好和聲作為引導產生新和聲的策略，提高算法全局收斂性能。其中，文獻[11]在文獻[9]的基礎上研究了全局最好和聲引導產生新和聲的策略，雖然算法具有較好的全局收斂性，但算法的參數并未減少，而且新和聲的分量從最好和聲的隨機一維引導產生，在解決實際工程問題時，容易破壞解向量的結構。文獻[12]雖然提出新和聲通過最好和聲對應維的信息產生，但算法中仍然無法擺脫需要設置多個參數的困擾。文獻[13]則將HMCR、PAR和bw三個參數排除，引入了位置更新和變異操作，雖然提高了算法的收斂性和跳出局部最優的能力，但算法又引入了新參數變異概率。最近，文獻[15]在文獻[13]的研究成果基礎上，引入反向學習技術提高HS算法對解空間信息的開發能力，但算法的參數并未減少。上述研究成果雖然在一定程度上提高了算法的收斂精度和收斂速度，但仍然存在參數設置較多，收斂速度慢和陷入局部最優等問題。

本文提出隨機交叉全局和聲搜索（Random Crosser Global Harmony Search，RCGHS）算法。通過多策略學習隨機交叉即興創作產生新和聲，結合反向學習策略提高算法全局搜索和局部搜索的能力，克服了算法易陷入局部最優的不足。

2 HS算法與反向學習

2.1 HS算法

HS算法通過和聲記憶庫考慮、隨機選取和基因調整策略，對優化問題每個決策變量在一定范圍內不斷搜索和調整，從而獲得最優解。主要包括參數與和聲記憶庫初始化、即興創作、更新和判斷終止條件5個步驟。其中，即興創作可以描述為：

其中，rand表示0到1之間的隨機數。表示新生成和聲向量xnew的第 j維分量。xjL和xjU分別表示第 j維分量的下界和上界。

2.2 反向學習

反向學習[16]的原理是通過問題的可行解尋找其反向解并對二者評估，選出較優的解作為下一代個體。其中，反向點和反向學習優化的定義如下：

定義1反向點：假設x=(x1,x2,…,xD)為D維空間中的任意一點，且x1,x2,…,xD∈R，xi∈[ai,bi]。則與x對應的全局反向點定義為ox=(ox1,ox2,…,oxD)，其中

定義2反向學習優化：設x=(x1,x2,…,xD)為D維空間的一個點，其全局反向點ox=(ox1,ox2,…,oxD)，考慮最小化問題，如果 f(ox)

3 RCGHS算法

3.1 算法改進分析

HS算法通過隨機選擇和聲即興創作策略，對小規模優化問題具有較好的優化效果。如果面臨高維復雜優化問題，算法在進化后期的盲目搜索，會使和聲記憶庫的多樣性變差，導致算法陷入局部最優難以跳出。相比之下，通過當前最好和聲引導即興創作，可以提高算法的全局收斂性能和算法的效率。文獻[13]提出最差和聲與最好和聲的對稱區間內產生新和聲的策略。其中，新和聲向量xnew的第 j維分量通過下面的策略產生，即

式（2）和（3）的實質可以看成是算法進化過程中，最差和聲向最優和聲學習的一種策略。

當前最差和聲向最好和聲學習，雖然可以使其快速向最好和聲聚集，但很容易忽略其他一些有價值的和聲附近的信息。尤其在解決多個局部最優值問題時，經過一定迭代次數之后和聲集中于局部最優值附近，導致整個和聲記憶庫中的和聲陷入一個狹小的空間內，從而使算法局部最優。

從經驗學習的角度去考慮，如果只強調最差和聲向最優和聲學習，則忽略了其他和聲與最優和聲之間的經驗交互。對于算法進化而言，算法局部搜索的能力則會隨之降低。而最差和聲代表了當前和聲的適應度函數值是最差的，并不代表最差和聲所有分量的信息都是最差且沒有價值（潛力）的。對于最差和聲向量來說，可能只有部分分量的信息是較差的。如果能將最差和聲向量的某些分量借助其他和聲對應分量的信息更新，則會提高算法的進化效率。此時，如果能夠加強其他和聲的某些分量向最優和聲學習進行經驗交互，從而實現對局部信息的搜索就顯得尤為重要。

因此，通過隨機選擇其他和聲與當前最優和聲交互隨機學習，增加其他和聲與最優和聲之間彼此交互的機會，既可以提高算法局部搜索的能力，也為和聲記憶庫即興創作提供更有價值的信息，為產生高質量的和聲提供有力的保障。

3.2 即興創作

通過前面的分析，本文采用兩種學習策略隨機交叉的學習方式產生新和聲。將和聲記憶庫中最差和聲以及其他和聲分別向最優和聲學習的隨機交叉動態產生新和聲。同時，結合隨機交叉反向學習策略擴大算法的搜索區域，提高算法搜索性能。

3.2.1 最差和聲向最優和聲隨機學習

最差和聲向最優和聲學習動態產生新和聲向量xnew的第 j( j=1,2,…,N )維分量，即

其中和分別表示最優和聲與最差和聲向量的第 j維分量。

通過最差和聲在最優和聲附近的對稱區間內隨機學習，可以有效開發最優和聲解空間附近的信息。尤其在優化早期，不同和聲之間的差異較大。通過最優和聲引導創作新和聲時，使當前最差和聲對最優和聲的學習可以快速向最優和聲聚集，提高和聲搜索算法的全局搜索性能。

3.2.2 其他和聲向最優和聲隨機學習

為了增加其他和聲與最優和聲之間彼此交互，實現對其他和聲附近解空間信息有效開發，提高算法局部搜索性能。在和聲記憶庫即興創作過程中，新和聲向量某一維以一定的概率隨機選擇一個和聲xr與xbest對應的分量相互學習開發解空間信息，從而產生新和聲向量xnew的第 j維分量，即

其中，r∈{1 ,2,…,HMS} ，和分別表示xr和xbest的第j(j =1,2,…,N )維分量。通過其他和聲向最優和聲隨機交互學習進化，可以實現對其他和聲附近解空間局部信息有效開發并利用，提高算法局部搜索的性能。不僅提高了和聲記憶庫中和聲向量的質量，同時為后續即興創作產生新和聲向量提供指導作用。

3.2.3 隨機交叉

本文將兩種學習策略隨機交叉即興創作。新和聲向量xnew的第j(j =1,2,…,N )維分量按照下面的規則執行。其偽代碼為：

If rand

執行式（4）

Else

執行式（5）

End if

兩種學習策略隨機交叉使新和聲的一部分分量通過最差和聲向最優和聲學習產生，實現全局搜索。同時，新和聲的另一部分分量通過其他和聲向最優和聲學習進行經驗交互后產生，實現對局部信息的搜索。將二者隨機交叉，發揮啟發式優化算法的隨機性的特點，通過其在全局搜索與局部搜索之間隨機跳躍，避免了算法單一進行全局搜索或局部搜索的缺陷，從而實現全局搜索和局部搜索的動態平衡。此外，通過兩種不同學習策略隨機交叉動態產生新和聲的策略，既保持了當前最優和聲向量的特性，同時又繼承了最差和聲向量與其他和聲向量的某些特質。隨機交叉策略避免了最差和聲向量某些分量信息對算法即興創作的干擾，加快了算法的收斂速度，提高了算法的優化效率。

3.2.4 隨機交叉反向學習

為了擴大算法的搜索區域，采用一種隨機反向學習策略。其原理是：一方面通過兩種學習策略產生的新和聲向量xnew后，即興產生其對應的反向和聲向量oxnew；另一方面通過和聲記憶庫中最好和聲xbest反向數的鄰域值，通過每一維的迭代反向學習，產生反向和聲向量oxnew。oxnew對應的第 j維分量按照下面的規則執行，即

通過反向解的引入，對新和聲向量進行反向區域的搜索，可以擴大算法的搜索區域，增強算法的鄰域搜索和全局搜索能力。

3.3 更新和聲記憶庫

算法更新過程中，和聲記憶庫即興創作產生的和聲向量xnew與反向和聲向量oxnew中適應度較優的個體直接替換和聲記憶庫中的最差和聲。

3.4 算法操作步驟

RCGHS算法的操作步驟如下。

步驟1初始化優化問題和算法的參數：

設置和聲記憶庫大小HMS和最大迭代次數K。

步驟2初始化和聲記憶庫：

確定第 j個分量的范圍[xjL,xjU]，隨機產生HMS個和聲向量存入和聲庫中。

步驟3即興創作產生新和聲：

For j=1 to N%即興創作過程開始

If rand

執行式（4）

Else

執行式（5）

End if

執行式（6）

End for

步驟4更新和聲記憶庫：

xnew與oxnew適應度較優的個體直接替換和聲記憶庫中的最差和聲向量。

步驟5判斷終止準則：

如果當前迭代次數等于最大迭代次數K，則終止運行算法，否則重復執行步驟3和步驟4。

3.5 收斂性分析

本文RCGHS算法通過兩種不同學習策略隨機交叉動態產生新和聲。其中，第一種學習策略采用當前最差和聲向當前最優和聲學習進化，可以使當前最差和聲快速向最優和聲聚集，使新產生的和聲成為最優和聲的可能性大大提高，提高了算法的全局搜索性能。第二種學習策略，通過其他和聲向量向最優和聲學習，可以有效地對其他和聲附近局部信息的開發，避免較差分量對新和聲的干擾，提高算法局部搜索的性能。將兩種學習策略隨機交叉，使新和聲在解空間不同區域內隨機更新，可以實現算法全局搜索和局部搜索之間的平衡，提高了算法跳出局部最優的能力，使算法向全局最優收斂。

兩種學習策略中通過當前和聲記憶庫中最優和聲向量作為引導，使最差和聲與其他和聲均向最優和聲向量學習實現解空間信息的開發。動態產生的新和聲繼承了和聲之間交互學習后的經驗，而且受最優和聲的引導啟發，保證新和聲以一種單調遞增的方式去產生，其實質是一種貪婪的選擇策略使新和聲逐漸向全局最優逼近，可以保證算法的收斂性。

在即興創作后期利用反向學習技術搜索反向解空間，最終將二者適應度值較優的和聲向量存儲于和聲記憶庫中，其本質仍然是一種貪婪的選擇策略。因此通過兩種學習策略即興創作動態產生的新和聲，再結合反向學習策略創作新和聲可以保證算法的收斂性。

4 仿真實驗

4.1 仿真實驗準備

將 RCGHS與 HS 算法[1]、SGHS算法[12]、NGHS 算法[13]、IGHS 算 法[14]、GOHS 算法[15]、人工 蜂 群 ABC 算法[4]、基本粒子群PSO算法[5]和灰狼GWO算法[6]進行優化性能測試。實驗中選取優化算法6個經典標準測試函數，其中函數 f1～f3是單峰函數，函數 f4～f6是多峰函數，具體表達如下：

f1:Sphere單峰函數

其中，-100≤xi≤100，全局最優為0。

f2:Schwefel’s problem 2.2.2單峰函數

其中，-100≤xi≤100，全局最優為0。

f3:Rotated hyper-ellipsoid單峰函數

其中，-100≤xi≤100，全局最優為0。

f4:Rastrigin多峰函數

其中，-100≤xi≤100，全局最優為0。

f5:Griewank多峰函數

其中，-100≤xi≤100，全局最優為0。

f6:Ackley多峰函數

其中，-100≤xi≤100，全局最優為0。

4.2 仿真結果與分析

在仿真實驗中取HMS=5，每種HS算法用到的參數選擇參考文獻中最優設置。ABC算法種群大小取30，limit=50；PSO算法，學習因子C1和 C2均取2，種群大小取30；GWO算法，種群大小取30。

實驗中所有HS算法迭代60 000次，ABC、PSO和GWO算法分別迭代2 000次。實驗中向量空間分別取N=50和N=100，每種算法獨立運行30次，分別用Best代表最優值，Worst代表最差值，Mean代表平均值，Std代表方差，對6個函數的測試結果如表1和表2所示。

由表1和表2中對6個測試函數的優化結果來看，HS、SGHS、NGHS、ABC和PSO算法的優化效果相對較差，尤其是到了高維空間中，這幾種算法均陷入了局部最優。IGHS、GOGHS和GWO算法的優化精度則相對有所提高。相比之下，無論在低維空間還是高維空間，本文RCGHS算法的優化效果明顯優于其他幾種算法的優化結果。RCGHS算法對6個函數優化均可以搜索到最優解，而且除了函數 f6外，對其他幾個函數優化無論在低維空間還是高維空間中所得到的最差值和平均值均與最優解相同。由表1和表2的實驗結果總體來看，本文RCGHS算法在高維空間中優化精度變化相對較小，其他幾種算法的優化精度均有不同程度的下降。這說明RCGHS算法比其他幾種算法更加穩定。

在實驗中，函數 f4、f5和 f6均是多峰函數，RCGHS算法在低維空間和高維空間均可以搜索到其最優解，而且對 f4和 f5優化的最差值和均值都與最優解相同。尤其對多峰函數 f6優化很多算法都陷入了局部最優，而本文算法仍然可以搜索到最優解。這說明在解決具有多個極值問題時，RCGHS算法在當前最好和聲引導即興創作具有很強的全局搜索能力的前提下，增加其他向量向最優和聲向量學習的策略后，算法加強了對其他和聲附近信息的精細搜索，使算法的局部搜索能力得到了提高。此外，在算法進化后期，隨機交叉策略結合反向學習技術實現對反向解得搜索，使算法能迅速擺脫局部最優的困擾，提高了算法跳出局部最優的能力。

表1 標準函數測試結果(N=50)

表2 標準函數測試結果(N=100)

圖1 函數 f1最優值進化曲線

圖2 函數 f2最優值進化曲線

圖3 函數 f3最優值進化曲線

圖4 函數 f4最優值進化曲線

圖5 函數 f5最優值進化曲線

圖6 函數 f6最優值進化曲線

為了對比幾種和聲搜索算法的收斂精度和收斂速度，本文給出了幾種和聲搜索算法對函數 f1～f6在高維空間(N=100)優化，每種算法迭代60 000次時的最優值進化曲線，如圖1～6所示。

由圖1～6中6個函數的最優值進化曲線可以看出，不論是從收斂速度還是收斂精度來看，RCGHS算法的優化效果明顯優于其他幾種HS算法。

根據表1和表2中的實驗結果以及圖1～6函數的最優值進化曲線總體上說，引入新的學習策略后，RCGHS算法對于6個標準函數優化的尋優精度得到了明顯的提升，而且本文RCGHS算法的收斂速度明顯快于其他幾種改進HS算法。

4.3 算法參數分析

在上面的仿真實驗中，幾種和聲搜索算法除了和聲記憶庫大小HMS和迭代次數K兩個參數外，每種算法的其他主要參數個數分別為：HS算法3個參數(HMCR、PAR 和 bw)，SGHS算法5個參數 (HMCRm、PARm、bwmin、bwmax和 LP)，NGHS算法1個參數 (Pm)，IGHS算法2個參數(HMCR和PAR)，GOGHS算法1個參數(Pm)，RCGHS算法0個參數。根據算法的主觀參數分析可以看出本文算法的主觀參數最少，所以本文算法的實驗結果受經驗影響相對較小。

5 結束語

本文針對和聲搜索算法容易陷入局部最優的問題，提出了隨機交叉全局和聲搜索（RCGHS）算法。通過不同的學習策略的隨機交叉對解空間信息進行開發，并結合隨機反向學習策略實現算法全局搜索和局部搜索的平衡。與其他HS算相比，RCGHS算法的主觀經驗參數設置較少，算法更具有適用性。利用優化算法6個標準測試函數對RCGHS算法與目前已發表文獻中優秀的改進HS算法及ABC、PSO和GWO算法進行尋優效果比較，仿真結果表明RCGHS算法的尋優性能得到了有效的提升，驗證了算法的有效性和穩定性。

[1]Geem Z W，Kim J H，Loganathan G V.A new heuristic optimization algorithm：harmony search[J].Simulation，2001，76（2）：60-68.

[2]謝宏，向啟均，陳海濱，等.機器人逆運動學差分自適應混沌粒子群求解[J].計算機工程與應用，2017，53（8）：126-131.

[3]李艷娟，陳阿慧.基于禁忌搜索的人工蜂群算法[J].計算機工程與應用，2017，53（4）：145-151.

[4]Karaboga D.An idea based on honey bee swarm for numerical optimization，Technical Report-tr06[R].Erciyes University，Engineering Faculty，Computer Engineering Department，2005.

[5]Kennedy J，Eberhart R C.Particle swarm optimization[C]//IEEE International Conference on Neural Networks，1995：1942-1948.

[6]Mirjalili S，Mirjalili S M，Lewis A.Grey wolf optimizer[J].Advances in Engineering Software，2014，69：46-61.

[7]Molina-Moreno F，García-Segura T，Martí J V，et al.Optimization of buttressed earth-retaining walls using hybrid harmony search algorithms[J].Engineering Structures，2017，134：205-216.

[8]Al-Betar M A，Awadallah M A，Khader A T，et al.Tournament-based harmony search algorithm for non-convex economic load dispatch problem[J].Applied Soft Computing，2016，47（C）：449-459.

[9]Mahdavi M，Fesanghary M，Damangir E.An improved harmony search algorithm for solving optimization problems[J].Applied mathematics and computation，2007，188（2）：1567-1579.

[10]Chen J，Pan Q，Li J.Harmony search algorithm with dynamic control parameters[J].Applied Mathematics and Computation，2012，219（2）：592-604.

[11]Omran M G H，Mahdavi M.Global-best harmony search[J].Applied Mathematics and Computation，2008，198（2）：643-656.

[12]Pan Q K，Suganthan P N，Tasgetiren M F，et al.A selfadaptive global best harmony search algorithm for continuous optimization problems[J].Applied Mathematics and Computation，2010，216（3）：830-848.

[13]Zou D，Gao L，Wu J，et al.Novel global harmony search algorithm for unconstrained problems[J].Neurocomputing，2010，73（16）：3308-3318.

[14]Valian E，Tavakoli S，Mohanna S.An intelligent globalharmony search approach to continuous optimizationproblems[J].Applied Mathematics and Computation，2014，232：670-684.

[15]Guo Z，Wang S，Yue X，et al.Global harmony search with generalized opposition-based learning[J].Soft Computing，2017，21（8）：2129-2137.

[16]Tizhoosh H R.Opposition-based learning：A new scheme for machine intelligence[C]//International Conference on Computational Intelligence for Modelling，Control and Automation，and International Conference on Intelligent Agents，Web Technologies and Internet Commerce，2005，1：695-701.