翟軍昌，秦玉平

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

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

1 引言

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

HS算法在進化后期容易盲目搜索，不能有效調(diào)整解向量的結(jié)構(gòu)。如果算法產(chǎn)生質(zhì)量較高的解向量則會引導(dǎo)算法較快地收斂，若收斂到局部最優(yōu)，則很難再跳出局部最優(yōu)解。因此，提高算法跳出局部最優(yōu)的能力受到了研究者廣泛的關(guān)注[6-13]。

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

本文提出隨機交叉全局和聲搜索（Random Crosser Global Harmony Search，RCGHS）算法。通過多策略學習隨機交叉即興創(chuàng)作產(chǎn)生新和聲，結(jié)合反向?qū)W習策略提高算法全局搜索和局部搜索的能力，克服了算法易陷入局部最優(yōu)的不足。

2 HS算法與反向?qū)W習

2.1 HS算法

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

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

2.2 反向?qū)W習

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

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

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

3 RCGHS算法

3.1 算法改進分析

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

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

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

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

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

3.2 即興創(chuàng)作

通過前面的分析，本文采用兩種學習策略隨機交叉的學習方式產(chǎn)生新和聲。將和聲記憶庫中最差和聲以及其他和聲分別向最優(yōu)和聲學習的隨機交叉動態(tài)產(chǎn)生新和聲。同時，結(jié)合隨機交叉反向?qū)W習策略擴大算法的搜索區(qū)域，提高算法搜索性能。

3.2.1 最差和聲向最優(yōu)和聲隨機學習

最差和聲向最優(yōu)和聲學習動態(tài)產(chǎn)生新和聲向量xnew的第 j( j=1,2,…,N )維分量，即

其中和分別表示最優(yōu)和聲與最差和聲向量的第 j維分量。

通過最差和聲在最優(yōu)和聲附近的對稱區(qū)間內(nèi)隨機學習，可以有效開發(fā)最優(yōu)和聲解空間附近的信息。尤其在優(yōu)化早期，不同和聲之間的差異較大。通過最優(yōu)和聲引導(dǎo)創(chuàng)作新和聲時，使當前最差和聲對最優(yōu)和聲的學習可以快速向最優(yōu)和聲聚集，提高和聲搜索算法的全局搜索性能。

3.2.2 其他和聲向最優(yōu)和聲隨機學習

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

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

3.2.3 隨機交叉

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

If rand

執(zhí)行式（4）

Else

執(zhí)行式（5）

End if

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

3.2.4 隨機交叉反向?qū)W習

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

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

3.3 更新和聲記憶庫

算法更新過程中，和聲記憶庫即興創(chuàng)作產(chǎn)生的和聲向量xnew與反向和聲向量oxnew中適應(yīng)度較優(yōu)的個體直接替換和聲記憶庫中的最差和聲。

3.4 算法操作步驟

RCGHS算法的操作步驟如下。

步驟1初始化優(yōu)化問題和算法的參數(shù)：

設(shè)置和聲記憶庫大小HMS和最大迭代次數(shù)K。

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

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

步驟3即興創(chuàng)作產(chǎn)生新和聲：

For j=1 to N%即興創(chuàng)作過程開始

If rand

執(zhí)行式（4）

Else

執(zhí)行式（5）

End if

執(zhí)行式（6）

End for

步驟4更新和聲記憶庫：

xnew與oxnew適應(yīng)度較優(yōu)的個體直接替換和聲記憶庫中的最差和聲向量。

步驟5判斷終止準則：

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

3.5 收斂性分析

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

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

在即興創(chuàng)作后期利用反向?qū)W習技術(shù)搜索反向解空間，最終將二者適應(yīng)度值較優(yōu)的和聲向量存儲于和聲記憶庫中，其本質(zhì)仍然是一種貪婪的選擇策略。因此通過兩種學習策略即興創(chuàng)作動態(tài)產(chǎn)生的新和聲，再結(jié)合反向?qū)W習策略創(chuàng)作新和聲可以保證算法的收斂性。

4 仿真實驗

4.1 仿真實驗準備

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

f1:Sphere單峰函數(shù)

其中，-100≤xi≤100，全局最優(yōu)為0。

f2:Schwefel’s problem 2.2.2單峰函數(shù)

其中，-100≤xi≤100，全局最優(yōu)為0。

f3:Rotated hyper-ellipsoid單峰函數(shù)

其中，-100≤xi≤100，全局最優(yōu)為0。

f4:Rastrigin多峰函數(shù)

其中，-100≤xi≤100，全局最優(yōu)為0。

f5:Griewank多峰函數(shù)

其中，-100≤xi≤100，全局最優(yōu)為0。

f6:Ackley多峰函數(shù)

其中，-100≤xi≤100，全局最優(yōu)為0。

4.2 仿真結(jié)果與分析

在仿真實驗中取HMS=5，每種HS算法用到的參數(shù)選擇參考文獻中最優(yōu)設(shè)置。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代表最優(yōu)值，Worst代表最差值，Mean代表平均值，Std代表方差，對6個函數(shù)的測試結(jié)果如表1和表2所示。

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

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

表1 標準函數(shù)測試結(jié)果(N=50)

表2 標準函數(shù)測試結(jié)果(N=100)

圖1 函數(shù) f1最優(yōu)值進化曲線

圖2 函數(shù) f2最優(yōu)值進化曲線

圖3 函數(shù) f3最優(yōu)值進化曲線

圖4 函數(shù) f4最優(yōu)值進化曲線

圖5 函數(shù) f5最優(yōu)值進化曲線

圖6 函數(shù) f6最優(yōu)值進化曲線

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

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

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

4.3 算法參數(shù)分析

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

5 結(jié)束語

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

[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]謝宏，向啟均，陳海濱，等.機器人逆運動學差分自適應(yīng)混沌粒子群求解[J].計算機工程與應(yīng)用，2017，53（8）：126-131.

[3]李艷娟，陳阿慧.基于禁忌搜索的人工蜂群算法[J].計算機工程與應(yīng)用，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，F(xiàn)esanghary 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.