改進的和聲搜索算法求解多目標優(yōu)化問題?

谷培義 高 尚

（江蘇科技大學(xué)計算機學(xué)院 鎮(zhèn)江 212000）

1 引言

多目標優(yōu)化是運籌學(xué)中的重要部分，同時也是科學(xué)研究和社會生活中普遍存在的一類優(yōu)化問題。在多目標優(yōu)化問題中，相同的變量因素，相同的變化，往往造成不同的目標產(chǎn)生相反的變化，使得最優(yōu)選擇的尋找變得十分困難。因此，多目標優(yōu)化問題一直是各個學(xué)科研究者的研究對象。隨著進化算法的出現(xiàn)與不斷發(fā)展，前人提出了許多優(yōu)化的多目標進化算法，如：非劣排序遺傳算法（NS?GA）［1］及其改進算法NSGA-II［2］，強度Pareto進化算法（SPEA）［3］，多目標遺傳算法（MOGA）等［4］。在多目標優(yōu)化問題的求解上這些算法在不同的方面有不同的優(yōu)勢，對于多目標優(yōu)化問題的求解具有較好的表現(xiàn)，但也存在著一定的改進空間［5］。

和聲搜索算法（Harmony Search Algorithm）在求解單目標連續(xù)問題上取得了較好的效果［6］，在某些實際問題上的應(yīng)用也取得了較好的表現(xiàn)［7］，但在解決多目標問題上，和聲搜索算法出現(xiàn)了收斂速度慢，容易陷入局部最優(yōu)解等問題［8］。

本文在和聲搜索算法的基礎(chǔ)上，通過引入自適應(yīng)操作［9］，提出了一種改進的多目標和聲搜索優(yōu)化算法，使和聲搜索算法的關(guān)鍵參數(shù)動態(tài)變化，根據(jù)迭代次數(shù)產(chǎn)生合適的參數(shù)值，從而增強了算法的全局搜索能力，增加解的多樣性；同時對解集根據(jù)Pa?reto最優(yōu)解［10］進行非支配排序，每次選取解集非支配排序中最優(yōu)部分的解進行和聲微調(diào)，以此來提高算法效率，增加算法在后期的收斂精度。最后根據(jù)仿真實驗和評價標準對改進后的算法進行評測。

2 基本和聲搜索算法

和聲搜索（Harmony Search，HS）算法［11］是一種啟發(fā)式算法，是模仿音樂家即興創(chuàng)作而產(chǎn)生的，由Geem.Z.W等在2001年提出。類似地還有其他典型的智能優(yōu)化算法，如蟻群算法對螞蟻行為特性的模擬仿真，遺傳算法對生物進化的模仿，模擬退火算法對物理退火機制的模仿等。

音樂演奏是一個尋找優(yōu)質(zhì)的和聲的過程，調(diào)整演奏出在美學(xué)評價中的最佳狀態(tài)［12］。對比之下，優(yōu)化算法也是根據(jù)目標函數(shù)求解出最符合目標函數(shù)預(yù)期值即最優(yōu)解的過程。對應(yīng)的目標函數(shù)值則是由相關(guān)變量值的解組成的集合求解得到。如音樂演奏中的優(yōu)質(zhì)和聲，是參與演奏的各個樂器的聲音集合。

在HS算法中，主要有四個變量參數(shù)：和聲庫大?。℉MS），和聲記憶庫保留概率（HMCR），擾動概率（PAR）以及音調(diào)微調(diào)幅度（BW）［13］。

基礎(chǔ)和聲搜索算法流程（見圖1）。

圖1 HS算法的流程圖

3 多目標優(yōu)化問題及評價標準

3.1 多目標優(yōu)化問題基本概念

多目標優(yōu)化問題是在各個變量因素變化范圍內(nèi)綜合考慮不同的目標，根據(jù)需求得出的最優(yōu)解集。一個具有m個目標變量、n個決策變量的多目標優(yōu)化問題，可表示為

式中：X為決策變量，X=(x1，x2，…，xn)T，n為向量X的維數(shù)；fk(X)是k個目標k=1，2，…，p，p為目標函數(shù)的個數(shù)；gi(x)是第i個不等式束；m為不等式約束數(shù)目hj(x)是j個等式約束；l為等式約束數(shù)目。

文獻［14］提出了關(guān)于多目標優(yōu)化的一些基本概念。

定義1（支配）：向量U=(u1，u2，…，uk)被向量V=(v1，v2，…，vk)支配當(dāng)且僅當(dāng)：

定義2（Pareto最優(yōu)解集）：對于任意的X∈Ω，不存在X滿足f(X)?f(X*)，則X*是Pareto最優(yōu)解。

定義3（Pareto最優(yōu)解集）對一個多目標優(yōu)化問題F(X)，它的最優(yōu)解集為

定義4（Pareto前沿）：對于一個給定的多目標優(yōu)化問題F(X)和它的Pareto最優(yōu)解集P*則它的Pareto前沿(PF*)定義為

多目標優(yōu)化問題的目標函數(shù)之間是相互影響的，通常情況下，一個變量參數(shù)的變化，可能會導(dǎo)致其中一個目標函數(shù)的結(jié)果變差，同時反而會讓另一個目標函數(shù)的結(jié)果變好。目標函數(shù)之間彼此沖突，因此，多目標優(yōu)化算法目的是最優(yōu)化求解出一系列非支配解，這些Pareto最優(yōu)解可以盡可能地協(xié)調(diào)各個目標函數(shù)結(jié)果的好與差。

3.2 多目標優(yōu)化問題評價標準

多目標優(yōu)化算法性能的主要評價指標為收斂性和多樣性。Deb等在文獻［15］中提出的收斂性指標?和多樣性指標Δ來評價

1）收斂性指標：

其中，n為所求解出的非支配解的個數(shù)，di為第i個非支配解與理論Pareto前沿的最小距離。收斂性指標數(shù)值越小，說明算法所求解越接近Pareto最優(yōu)前沿。

2）多樣性指標

其中，n為求解出的支配解個數(shù)，di為相鄰兩個個體之間的歐氏距離；dˉ為di的均值；df、dl是求解出的非支配解中的兩個邊界解與極端解的歐氏距離。Δ越小，代表算法的多樣性越好［16］。

4 改進的和聲搜索算法（GHS）

4.1 參數(shù)自適應(yīng)

傳統(tǒng)的和聲搜索算法參數(shù)微調(diào)概率（PAR）和音調(diào)微調(diào)幅度（BW）算法運行過程中是固定值，因而算法易陷入局部最優(yōu)。和聲搜索算法中也有很多改進的方法被應(yīng)用其中［17］，本文算法中PAR根據(jù)式（4）動態(tài)變化，BW根據(jù)式（5）動態(tài)變化。

式中PAR(t)是隨著迭代次數(shù)t變化的，t是當(dāng)前迭代次數(shù)，PARmax是最微調(diào)概率取值上限，PARmin是微調(diào)概率取值下限，T是總的迭代次數(shù)。

式中BW(t)是隨著迭代次數(shù)t變化的，BWmax是調(diào)整幅度取值上限［18］，BWmin是調(diào)整幅度取值下限。

4.2 Pareto非支配排序

首先解集中的每個解都與解集中其他解進行支配關(guān)系比較，是否支配其他解，記錄每個解的被支配個數(shù)k，根據(jù)k值對解集中的解進行排序。

然后，k相同的解按照相鄰的解距離大小（D）按照從大到小排序。D按照式（6）計算。目標函數(shù)的邊界值的D取無窮大。

式中D[i]表示第i個解的距離，n表示目標函數(shù)的數(shù)量，f[i]j+1表示第i個解的第j+1個目標函數(shù)的值，f[i]j-1表示第i個解的第j-1個目標函數(shù)的值。表示第j個目標函數(shù)的最小值和最大值［19］。

4.3 GHS算法步驟

Step1：算法參數(shù)：N（解集大?。琓（最大迭代次數(shù)）。

Step2：在定義域范圍內(nèi)先隨機產(chǎn)生一個解集P0。

Step3；在P0基礎(chǔ)上利用自適應(yīng)和聲搜索算法產(chǎn)生一個新的解集Q0，P0和Q0的解集大小都為N。

Step4：將Pt和Qt并入到Rt中（初始時t=0），Rt大小為2 N，對Rt進行非支配排序，得到一個按照k值大小從小到大排序的解集，得到不同等級的非支配解集。

Step5：Rt取前N個解存入Pt，形成新的解集。

Step6：若t≥T則終止搜索；否則轉(zhuǎn)入Step3。

5 實驗測評

本文的實驗選取文獻［15］中的四個目標函數(shù)ZDT1、ZDT2、ZDT3和ZDT6來分別進行測驗，并在算法收斂性和多樣性方面與NSGA-II、SPEA2［20］這兩個多目標優(yōu)化算法進行比較。參數(shù)設(shè)置：解集數(shù)量N=200，最大迭代次數(shù)T=500，PARmax=0.95，PARmin=0.5，BWmax=0.1，BWmin=0.001。實驗分別對三種算法均獨立運行20次，三種算法的結(jié)果進行相互比較。通過表1和表2對比，改進后的HS在解決多個目標優(yōu)化問題時，Pareto最優(yōu)解集的?和Δ兩個指標值，總體要優(yōu)于NSGA-II和SPEA2兩種多目標優(yōu)化算法。因此改進后的和聲搜索算法能夠更有效地求解多目標優(yōu)化問題。

表1 基于?的統(tǒng)計結(jié)果比較

表2 基于Δ的統(tǒng)計結(jié)果比較

GHS所得Pareto前沿圖與真實的Pareto前沿圖對比，如圖2～5。

圖2 ZDT1測試函數(shù)算法對比圖

圖3 ZDT2測試函數(shù)算法對比圖

圖4 ZDT3測試函數(shù)算法對比圖

圖5 ZDT6測試函數(shù)算法對比圖

6 結(jié)語

本文提出了一種改進的多目標和聲搜索算法，引入?yún)?shù)自適應(yīng)操作，使和聲搜索算法的關(guān)鍵參數(shù)動態(tài)變化，根據(jù)迭代次數(shù)產(chǎn)生合適的參數(shù)值，從而增強了算法的全局搜索能力，增加解的多樣性；同時對解集根據(jù)Pareto最優(yōu)解進行非支配排序，每次選取解集非支配排序中最優(yōu)部分的解進行和聲微調(diào)，提升了算法效率和算法在后期的收斂精度。最后通過實驗測評，測評數(shù)據(jù)表明該算法具有較好的收斂性和多樣性。