改進的和聲搜索算法求解多目標優化問題?

谷培義 高 尚

（江蘇科技大學計算機學院 鎮江 212000）

1 引言

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

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

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

2 基本和聲搜索算法

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

音樂演奏是一個尋找優質的和聲的過程，調整演奏出在美學評價中的最佳狀態［12］。對比之下，優化算法也是根據目標函數求解出最符合目標函數預期值即最優解的過程。對應的目標函數值則是由相關變量值的解組成的集合求解得到。如音樂演奏中的優質和聲，是參與演奏的各個樂器的聲音集合。

在HS算法中，主要有四個變量參數：和聲庫大小（HMS），和聲記憶庫保留概率（HMCR），擾動概率（PAR）以及音調微調幅度（BW）［13］。

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

圖1 HS算法的流程圖

3 多目標優化問題及評價標準

3.1 多目標優化問題基本概念

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

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

文獻［14］提出了關于多目標優化的一些基本概念。

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

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

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

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

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

3.2 多目標優化問題評價標準

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

1）收斂性指標：

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

2）多樣性指標

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

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

4.1 參數自適應

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

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

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

4.2 Pareto非支配排序

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

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

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

4.3 GHS算法步驟

Step1：算法參數：N（解集大小），T（最大迭代次數）。

Step2：在定義域范圍內先隨機產生一個解集P0。

Step3；在P0基礎上利用自適應和聲搜索算法產生一個新的解集Q0，P0和Q0的解集大小都為N。

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

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

Step6：若t≥T則終止搜索；否則轉入Step3。

5 實驗測評

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

表1 基于?的統計結果比較

表2 基于Δ的統計結果比較

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

圖2 ZDT1測試函數算法對比圖

圖3 ZDT2測試函數算法對比圖

圖4 ZDT3測試函數算法對比圖

圖5 ZDT6測試函數算法對比圖

6 結語

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