全局共享因子的和聲搜索算法

劉立群，火久元，王聯(lián)國(guó)

(1.甘肅農(nóng)業(yè)大學(xué)信息科學(xué)技術(shù)學(xué)院，蘭州 730070;2.蘭州交通大學(xué) 信息中心，蘭州 730070)

和聲搜索(harmony search，HS)算法［1-4］是通過(guò)類比音樂(lè)和最優(yōu)化問(wèn)題相似性提出的啟發(fā)式智能迭代算法。HS算法是對(duì)音樂(lè)演奏中樂(lè)師憑借記憶通過(guò)反復(fù)調(diào)整樂(lè)隊(duì)中各樂(lè)器音調(diào)，最終達(dá)到一個(gè)美妙和聲狀態(tài)過(guò)程的模擬。研究表明:HS算法是單個(gè)體迭代算法，具有迭代速度緩慢、易陷入局部最優(yōu)以及求解質(zhì)量不高等缺陷［2-4］。本文針對(duì)HS算法音調(diào)微調(diào)機(jī)制中存在隨機(jī)性更新的缺陷，將全局共享因子［5］的思想引入HS算法，提出一種全局共享因子的和聲搜索算法(harmony search algorithm with global sharing factor，GSFHS)。測(cè)試函數(shù)對(duì)比實(shí)驗(yàn)表明，GSF-HS算法有效改善了HS算法的優(yōu)化性能。

1 和聲搜索算法思想

隨機(jī)產(chǎn)生HMS個(gè)初始解(和聲)放入和聲記憶庫(kù)(harmony memory，HM)內(nèi)，HMS為和聲記憶庫(kù)的大小，HMCR為和聲記憶庫(kù)取值概率，PAR為音調(diào)微調(diào)概率，BW為音調(diào)微調(diào)帶寬，Tmax為算法創(chuàng)作的次數(shù)，且r1，r2，r∈[0，1]。假設(shè)問(wèn)題是求最小值，其表達(dá)形式為:

隨機(jī)生成 HMS個(gè)和聲x1，x2…，xHMS放入和聲記憶庫(kù)，形式如下:

按以下規(guī)則生成一個(gè)新的和聲x'i=(x'1，x'2，…，x'N)。

新和聲的每一個(gè)音調(diào)x'i(i=1，2，…，N)通過(guò)學(xué)習(xí)和聲記憶庫(kù)產(chǎn)生。

如果 r1＜HCMR，則

通過(guò)式(3)產(chǎn)生的新和聲音調(diào)x'i還需進(jìn)行音調(diào)微調(diào)。

如果 r2＜PAR，則

如果r1≥HCMR，則隨機(jī)選擇音調(diào)產(chǎn)生新和聲x'i，即

對(duì)和聲記憶庫(kù)按以下更新策略進(jìn)行更新。

上述過(guò)程不斷重復(fù)，直至創(chuàng)作(迭代)次數(shù)達(dá)到Tmax為止。

2 全局共享因子的和聲搜索算法

2.1 全局共享因子思想

HS算法音調(diào)微調(diào)機(jī)制利用隨機(jī)數(shù) r∈[0 ，1]產(chǎn)生新和聲。由于這種方式具有隨機(jī)性，因此對(duì)單峰值和多峰值函數(shù)尋優(yōu)問(wèn)題，HS算法易出現(xiàn)收斂速度慢、精度低等問(wèn)題。

文獻(xiàn)［5］在共享因子［6］基礎(chǔ)上提出全局共享因子的概念。全局共享因子αG是僅隨迭代次數(shù)非線性動(dòng)態(tài)變化的共享因子［5］。由于αG是由較小的初值迅速增大到一個(gè)穩(wěn)態(tài)值，故可以抑制隨機(jī)性音調(diào)微調(diào)的隨機(jī)性。

本文將HS算法中創(chuàng)作次數(shù)t∈[1，Tmax]應(yīng)用到全局共享因子中，其表達(dá)式為

根據(jù)全局共享因子理論，在HS算法初期，初始和聲隨機(jī)分布在搜索空間內(nèi)，為避免和聲音調(diào)更新步長(zhǎng)過(guò)大跳過(guò)最優(yōu)個(gè)體，應(yīng)通過(guò)較小的全局共享因子減弱音調(diào)微調(diào)帶寬對(duì)最差和聲的音調(diào)微調(diào)能力。當(dāng)?shù)螖?shù)達(dá)到一定程度時(shí)，最差和聲與通過(guò)學(xué)習(xí)和聲記憶庫(kù)產(chǎn)生的和聲的差異如果過(guò)小則會(huì)出現(xiàn)搜索停滯現(xiàn)象，此時(shí)應(yīng)通過(guò)迅速增大到一定值后的全局共享因子增強(qiáng)音調(diào)微調(diào)能力，實(shí)現(xiàn)全局收斂。

2.2 全局共享因子的和聲搜索算法

本文將上述全局共享因子αG引入到HS算法中，提出一種全局共享因子的和聲搜索算法(harmony search algorithm with global sharing factor，GSF-HS)。

GSF-HS算法是在HS算法基礎(chǔ)上對(duì)其音調(diào)微調(diào)機(jī)制中的隨機(jī)性更新進(jìn)行改進(jìn)，即GSF-HS算法中音調(diào)微調(diào)機(jī)制按式(9)進(jìn)行計(jì)算，其中全局共享因子αG按式(7)、(8)計(jì)算。

GSF-HS算法步驟如下:

步驟1 隨機(jī)生成HMS個(gè)初始和聲 x1，x2，…，xHMS，第i個(gè)和聲記為xi=(x1，x2，…，xN)，其中N為和聲音調(diào)個(gè)數(shù)。

步驟2 初始化和聲記憶庫(kù)取值概率HMCR、音調(diào)微調(diào)概率PAR、音調(diào)微調(diào)帶寬BW和算法創(chuàng)作次數(shù)Tmax。

步驟3 選取目標(biāo)函數(shù)f(xi)，按式(2)初始化和聲記憶庫(kù)HM。

步驟4 按式(7)、(8)計(jì)算全局共享因子αG。

步驟5 隨機(jī)生成 r1，r2，r∈[0，1]，如果 r1＜HCMR，則新和聲音調(diào)x'i按式(3)計(jì)算，且若r2＜PAR，則計(jì)算出的新和聲音調(diào)x'i再按(9)式計(jì)算;如果r1≥HCMR，則按式(5)計(jì)算新和聲。按式(6)對(duì)和聲記憶庫(kù)進(jìn)行更新，如此反復(fù)迭代直至Tmax為止，輸出最優(yōu)和聲。

2.3 算法流程

GSF-HS算法流程見(jiàn)圖1。

圖1 GSF-HS算法流程

3 對(duì)比實(shí)驗(yàn)及結(jié)果分析

實(shí)驗(yàn)采用 Rastrigrin、Griewank、Ackley和Rosenbrock［7-8］4個(gè)測(cè)試函數(shù)作為HS算法的目標(biāo)函數(shù)，分別對(duì)HS及GSF-HS算法進(jìn)行極小值尋優(yōu)性能測(cè)試。其中:Rastrigrin、Griewank、Ackley函數(shù)為多峰值函數(shù)，Rosenbrock函數(shù)為單峰值函數(shù)，4個(gè)函數(shù)的極小值均為0［7-8］。

實(shí)驗(yàn)參數(shù)設(shè)置如下:和聲記憶庫(kù)大小HMS=200，HMCR=0.9，PAR=0.3，BW=0.01，Tmax=30 000。實(shí)驗(yàn)所用計(jì)算機(jī)處理器為Intel Core2，主頻為2.0 GHz，內(nèi)存為2.0 GB，測(cè)試平臺(tái)為VC++6.0。最終測(cè)試結(jié)果采用獨(dú)立運(yùn)行30次后的平均值。

算法性能評(píng)價(jià)采用如下方法:①固定迭代次數(shù)，評(píng)價(jià)算法收斂精度和速度;② 固定收斂精度，評(píng)價(jià)算法達(dá)到該精度所需的迭代次數(shù)。

3.1 固定迭代次數(shù)的收斂精度和速度分析

固定迭代次數(shù)下，各算法收斂結(jié)果如表1所示。4個(gè)測(cè)試函數(shù)在固定迭代次數(shù)條件下的函數(shù)平均最優(yōu)值迭代曲線如圖2～5所示。

對(duì)多峰值 Rastrigrin和 Ackley函數(shù)，表1表明:GSF-HS算法平均最優(yōu)值結(jié)果均優(yōu)于HS算法，且GSF-HS算法標(biāo)準(zhǔn)差較HS算法更具優(yōu)勢(shì)，改進(jìn)算法對(duì)這2個(gè)函數(shù)的收斂精度改善較為明顯。圖2的Rastrigrin函數(shù)和圖4的Ackley函數(shù)迭代曲線表明:GSF-HS算法收斂速度均優(yōu)于HS算法。

對(duì)多峰值 Griewank函數(shù)，表1表明:雖然GSF-HS算法平均最優(yōu)值結(jié)果遠(yuǎn)優(yōu)于HS算法，但其標(biāo)準(zhǔn)差較HS算法高，改進(jìn)算法對(duì)Griewank函數(shù)的收斂精度沒(méi)有明顯改善。圖3的Griewank函數(shù)迭代曲線顯示:在迭代次數(shù)少于10 000時(shí)，GSFHS算法的收斂速度優(yōu)于HS算法，但在之后的迭代中，GSF-HS算法收斂速度并無(wú)太大改進(jìn)。

對(duì)單峰值Rosenbrock函數(shù)，表1表明:GSF-HS算法平均最優(yōu)值結(jié)果遠(yuǎn)優(yōu)于HS算法，且GSF-HS算法標(biāo)準(zhǔn)差為0，明顯優(yōu)于HS算法，改進(jìn)算法對(duì)單峰值函數(shù)的收斂精度改善較為明顯。圖5的Rosenbrock函數(shù)迭代曲線顯示:在迭代次數(shù)超過(guò)20 000之后，GSF-HS算法的收斂速度較HS算法有較大提升。

圖2 Rastrigrin函數(shù)平均最優(yōu)值迭代曲線

圖3 Griewank函數(shù)平均最優(yōu)值迭代曲線

圖4 Ackley函數(shù)平均最優(yōu)值迭代曲線

圖5 Rosenbrock函數(shù)平均最優(yōu)值迭代曲線

3.2 固定收斂精度下的迭代次數(shù)分析

4個(gè)測(cè)試函數(shù)的目標(biāo)精度和各函數(shù)達(dá)到目標(biāo)精度時(shí)的平均迭代次數(shù)見(jiàn)表2［7-8］。實(shí)驗(yàn)結(jié)果表明:GSF-HS算法達(dá)到目標(biāo)精度的次數(shù)明顯少于HS算法。由此可知，GSF-HS算法收斂精度、速度均優(yōu)于HS算法。

表1 固定迭代次數(shù)結(jié)果比較

表2 固定收斂精度結(jié)果比較

4 結(jié)束語(yǔ)

本文提出一種全局共享因子的和聲搜索算法，將全局共享因子思想和HS算法創(chuàng)作次數(shù)相結(jié)合，并將其應(yīng)用到HS算法的音調(diào)微調(diào)機(jī)制中以改進(jìn)HS算法音調(diào)微調(diào)機(jī)制隨機(jī)性更新的缺陷。4個(gè)測(cè)試函數(shù)的對(duì)比實(shí)驗(yàn)結(jié)果表明:GSF-HS算法收斂精度、速度均優(yōu)于HS算法，有效改善了HS算法的優(yōu)化性能。

［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).一種新的智能優(yōu)化及其改進(jìn)研究［J］.小型微型計(jì)算機(jī)系統(tǒng)，2010，31(5):955-958.

［3］雍龍泉.和聲搜索算法研究進(jìn)展［J］.計(jì)算機(jī)系統(tǒng)應(yīng)用，2011，20(7):244-248.

［4］韓紅燕，潘全科，梁靜.改進(jìn)的和聲搜索算法在函數(shù)優(yōu)化中的應(yīng)用［J］.計(jì)算機(jī)工程，2010，36(13):245-247.

［5］劉立群，王聯(lián)國(guó)，韓俊英，等.基于全局共享因子的混合蛙跳算法［J］.計(jì)算機(jī)工程，2013，39(10):162-166.

［6］王輝.一種帶共享因子的人工蜂群算法［J］.計(jì)算機(jī)工程，2011，37(22):139-142.

［7］王凌.智能優(yōu)化算法及其應(yīng)用［M］.北京:清華大學(xué)出版社，2001:2-6.

［8］Andrice P，Engelbrecht.Fundamentals of Computational Swarm Intelligence［M］.譚營(yíng)，譯.北京:清華大學(xué)出版社，2009:10-15.