動態調整策略改進的和聲搜索算法

網絡出版地址：http://www.cnki.net/kcms/detail/23.1538.TP.20150326.1016.004.html

動態調整策略改進的和聲搜索算法

拓守恒,雍龍泉,鄧方安

(陜西理工學院 數計學院，陜西 漢中 723001)

摘要：為了得到高維復雜問題的全局高精度最優解，提出一種動態調整策略，并用該策略改進和聲搜索算法。算法選取和聲記憶庫中最差和聲向量作為優化調整目標，隨著迭代的進行，逐步降低決策變量的調整概率，該方法能夠使得算法在全局探索能力和局部高精度開發能力之間實現平衡，有效提高了新和聲更新最差和聲的成功率。通過6個高維Benchmark測試函數的仿真結果表明，提出的動態調整策略能夠有效提高和聲搜索算法求解高維復雜優化問題的能力。

關鍵詞：自適應調整策略；高維優化問題；和聲搜索算法

DOI:10.3969/j.issn.1673-4785.201402019

中圖分類號：TP391文獻標志碼：A

收稿日期：2014-02-21.網絡出版日期：2015-03-26.

基金項目：國家自然科學基金資助項目(11401357)，陜西省教育廳科研資助項目(14JK1141)；漢中市科技局科研資助項目(2013hzzx-39);陜西理工學院科研資助項目(SLGKY 13-27).

作者簡介：

中文引用格式：拓守恒,雍龍泉,鄧方安.動態調整策略改進的和聲搜索算法[J]. 智能系統學報， 2015, 10(2): 307-315.

英文引用格式：TUO Shouheng, YONG Longquan, DENG Fang’an. Dynamic adjustment strategy for improving the harmony search algorithm[J]. CAAI Transactions on Intelligent Systems, 2015, 10(2): 307-315.

Dynamic adjustment strategy for improving the harmony search algorithm

TUO Shouheng, YONG Longquan, DENG Fang’an

(School of Mathematics and Computer Science, Shaanxi University of Technology, Hanzhong 723001,China)

Abstract：A dynamic adjustment strategy is used to improve the harmony search algorithm for solving high-dimensional multimodal global optimization problems. It chooses the worst harmony vector from the harmony memory (HM) as an optimization objective vector. With the process of iteration, the adjustment probability of decision variables is reduced step by step. It can achieve the balance effectively between the global exploration powers and local exploitation competence， and can increase the success rate of evolution. Finally, the experimental results of 16 high-dimension benchmark functions demonstrated that the proposed method can enhance the performance and robustness of the harmony search algorithm obviously in solving large scale multimodal optimization problems.

Keywords：adaptive adjustment strategy; high-dimensional optimization problems; harmony search algorithm

通信作者：拓守恒.tuo_sh@126.com.

近年來，隨著社會的發展和大數據時代的到來，人們對科技產品的能耗和性能要求越來越高，使得產品的設計遇到了極大的挑戰。許多產品的設計需要考慮很多的設計要求，并要使其產品整體設計能夠達到最優,這些問題都可轉化為大規模復雜優化問題(optimization problems,OP)。對于OP問題，近年來，研究者將關注的焦點集中在模擬自然的啟發式(meta-heuristics)優化方法[1-9]等。

和聲搜索算法是Geem等[1]在2001年通過模擬音樂家創作音樂和調節和聲的過程，提出的一種新的啟發式優化算法。音樂家在音樂創作過程中，需要不斷調整各個音符，使其成為優美和聲。由于和聲算法搜索能力強，并且結構簡單，很容易在各種軟件和硬件中實現，引起很多科學研究者和工程設計人員的關注，近年來，已經廣泛應用于實踐中，例如，管網優化設計[10]、結構優化設計[11]、交通運輸路徑優化[12]、電力系統經濟負荷分配問題[13]和PID控制器優化[14]等領域。然而，研究發現，在有限的時間內，和聲搜索算法具有很強的全局探索能力，但是，在實數優化問題中，求解精度較低[15-17]。為此，很多改進的和聲搜索算法被提出，潘全科等[15]采用動態子種群策略提出了局部最好和聲搜索算法，利用自適應動態策略提出一種全局最優和聲搜索算法[16]。M. Mahdavi 等設計出一種參數動態調整策略，有效改進了HS算法的性能(IHS)[18]；M.G.H.Omran提出全局最優和聲搜索算法(GHS)[19]； Zou[20]采用一種很簡單的差分學習策略，有效屏蔽了參數HMCR (harmony memory considering rate )和 PAR(pitch-adjusting rate)，降低了算法的復雜性[21-22]。P.Yadav 給出一種智能調整和聲搜索算法(ITHS)[17]; S.Das通過理論分析與證明，給出了一種新的和聲步長(pitch bandwidth，BW)調整算法(EHS)[23]；本文作者在文獻[24]和[25]中分別提出了“混沌和聲搜索算法”與“基于教與學策略的和聲搜索算法”;另外，在一些具體應用中，對和聲搜索算法進行了有效改進[26-34]。盡管上述改進算法從某些方面對和聲搜索算法進行了改進，但并沒有從算法的運行代價考慮，比如EHS算法，雖然搜索能力有了明顯的改進，但是，由于每次迭代都需要計算和聲記憶庫(harmony memory，HM)的方差，其計算量甚至超過了和聲搜索算法本身的計算量，使得算法的運行代價是標準和聲算法HS的好幾倍。特別是在求解高維復雜優化問題時，目前的和聲算法運行速度普遍較慢。為此，本文通過引入一種動態和聲調整策略，使其能夠有效提高和聲算法的性能，并且，能使算法運行代價降低，提高其搜索速度。

1標準和聲搜索算法

考慮如下優化問題：

1.1標準和聲搜索算法

標準和聲搜索算法的基本步驟如下：

1)設置參數值(D,HMS,Tmax,HMCR,PAR,BW)。各參數含義如下：

D為問題的維數，HMS為和聲記憶庫大小，Tmax為算法迭代次數；HMCR為和聲記憶庫選擇概率，PAR為局部微調概率，BW為局部微調步長值。

2)隨機初始化和聲記憶庫HM

式中：rand是(0,1)中的隨機數。

3)利用3種和聲調節規則創作新和聲

4)更新操作

如果新和聲向量xnew優于HM中最差的和聲xworst，則用xnew將其替換，否則，轉至(3)重新產生新和聲。重復3)、4)，直到滿足終止條件。

2動態降維和聲調整策略

2.12種和聲調整策略分析與比較

目前的和聲搜索算法和一些改進算法是在整個種群的基礎上通過組合策略(規則①)產生新的候選解，這樣實現了組合算子的多樣性，因此具有較好的全局搜索性能。但是，在進化后期，即使發現了全局最優解所在的區域，由于其較低的更新成功率(更新成功率是指每次產生的新解好于和聲記憶庫中最差解的概率)，使得算法往往很難獲得高精度的最優解。

(1)

(2)

此時，假設HM的每個和聲中都僅有一個決策變量沒有達到最優。由于和聲算法中規則①的調整概率HMCR一般都大于0.9，也就是說規則①在和聲搜索算法中是非常重要的，這時，如果僅僅采用和聲搜索算法中的規則①進行優化。采用下列2種方法分別產生一個新和聲xnew，分析2種方法的更新成功率。

圖1　2種方法在維數不同時的更新成功率曲線圖 Fig.1　The update-success rate curve of two methods on different dimensioalities

圖1可以看出，在HMS相同的情況下，隨著維數D的增加，方法1的成功率急劇下降，而方法2下降幅度很小。在問題的維數較低時，方法1的更新成功率高于方法2，但當維數D>40時，方法2的更新成功率高于方法1。

由上例可知，對于一個高維優化問題，利用方法1難以驅動算法獲得高精度的最優解。如果借鑒方法2的思想進行優化，就有可能取得較好的優化效果。因此，本文提出一種基于動態減少調整維數的和聲優化策略。該策略首先選取和聲記憶庫中最差和聲向量作為優化目標，然后，通過對最差和聲向量的不斷調整，使其達到最優解。在優化剛開始時，對最差和聲向量進行較多維數的擾動，使得算法具有較強的空間探索能力，隨著優化的進行，逐步降低擾動概率，僅僅在較少維上進行優化調整，使得優化調整具有更高的成功率，從而獲得高精度的全局最優解。

2.2基于動態降維調整的和聲搜索算法

本文提出的基于動態降維調整策略的和聲搜索算法流程請見圖2。本文算法中，調整概率TP=TPmax-(TPmax-TPmin)·(t/Tmax)2隨著迭代次數的增加逐步減小(如圖3)，其中，TPmax和TPmin分別為最大調整概率值和最小調整概率值。

在算法優化開始時，以較大的擾動調整概率TPmax進行優化，隨著優化進行，調整概率TP逐漸減小，開始進行局部微調。但是，為了防止優化調整概率太小，可能導致所有維都得不到調整，因此，需要從1～D中隨機選取一維J=ceil(rand×D) ，使其必須得到調整，避免了算法“空轉”。這樣調整的好處是，迭代初期，需要較強的全局擾動能力，此時，可以在優化目標向量xnew上加大擾動力度，增強種群多樣性，使其具有較強的全局探索能力，隨著優化的進行，到了后期，多數個體可能已經聚集在了全局最優解附近，此時，開始加強局部最優解的探索，為了保證較高的更新成功率，對優化目標向量xnew，選擇較少的維數進行優化調整，從而，增強算法的求解精度。

圖2　基于動態降維調整的和聲搜索算法流程圖 Fig.2　The flow chart of HS algorithm based on dynamic dimensionality reduction strategy

圖3　調整概率TP變化曲線 Fig.3　Adjustment curve of TP

3仿真實驗

為了評估本文算法提出的動態降維調整策略的性能，選取了6個復雜的Benchmark測試函數進行仿真測試[35-38](見表1)，16個函數除了F7和F8是單峰函數之外，其余函數都是復雜的高維多峰值函數。

分別將HS、IHS、ITHS、EHS和GHS利用本文算法思想進行改進，將其改進后分別稱為HS2，IHS2，ITHS2，EHS2和GHS2，并將其與改進前的算法進行比較。檢驗改進后的算法是否比改進前的算法能夠獲得更高精度的解，同時，檢驗其運行成本(運行時間)是否降低。

3.1實驗環境和算法參數設置

本文實驗采用戴爾工作站T7500 Inter(R) Xeon(R) CPU E560@ 2.1GHz, 8.0GB內存，Windows Server2003 Server操作系統，所有測試程序采用Matlab R2009a編寫。10種算法參數設置如表2。

表1　6個Benchmark函數(F1～ F6)

表2　參數設置

表3　在D=500時， 5種和聲算法及其利用本文算法改進的5種和聲算法對6個測試函數的運行結果比較

3.2實驗結果與分析

為了保證算法測試的公平性，改進前的算法和改進后的算法取相同的初始和聲記憶庫HM，每個算法中隨機數設置rand(′twister′,5489)，每個算法程序獨立運行20次，記錄每次運行的過程，統計出20次運行的最優目標函數適應值的平均值Mean，最優值Best, 20次最優解的標準差(Std)和平均運行時間(run time)。設置維數D=500，運行結果見表3。 表中將HS、IHS、ITHS、EHS和GHS 分別與HS2、IHS2、ITHS2、EHS2和GHS2進行比較，較好結果的用粗體標出。

從表3可看出，對于高維多峰值優化函數(例如，F3: Levy, F5: Rastrigin, F6:Schwefel2.26)，本文算法相比改進前的算法，更具有優勢，算法的運行代價(運行時間)也相對較少。說明本文算法在求解高維多極值復雜優化問題時具有更好的性能優勢。

3.3算法更新成功率分析

(a)算法HS與HS 2成功率比較

(b)算法IHS與IHS 2成功率比較

(c)算法EHS與EHS 2成功率比較

(d)算法ITHS與ITHS 2成功率比較 圖4　 函數Rastrigin在D=1000時，改進前與改進后的算法成功率比較 Fig.4　Successrate comparison between ITHS and improved ITHS on D=1000

由圖4可以看出，本文策略改進后的算法成功率都明顯高于改進前的算法，并且，改進后的算法成功率曲線成凹形曲線變化。這是由于初始時，種群是隨機產生，個體的適應值較差，容易探索到比當前更好的解。隨著迭代的進行，成功率逐漸降低。對改進前的算法來說，由于一個新解完全是靠組合算子和微調策略產生，成功率會越來越低(根據第3節的分析)，而本文采用動態降維調整策略逐步減小最差解xworst中決策變量的調整概率，從而增加了更新成功率。從圖4中可以看出，在后期，算法的成功率不降反升，證明了本文改進策略的有效性。這是由于在后期，只對最差解向量xworst中很少的幾個決策變量進行調整，獲得成功的機會遠高于在所有維上的更新調整。

3.4算法種群多樣性分析

種群的多樣性是指種群中個體間的差異性，個體差異越大，種群多樣性越高，反之，差異性越小，種群多樣性越低。本文采用如下公式計算種群的多樣性。

對于群智能優化算法來說，種群的多樣性直接決定算法的搜索能力，當具有較高的種群多樣性時，算法的全局探索能力較強，適合探索新的搜索區域，但是，如果一直保持較高的種群多樣性，種群很難向全局最優解靠近，往往難以獲得高精度的全局最優解。所以，在搜索初期，需要種群具有較高的種群多樣性，后期，為了獲得高精度的全局最優解，種群需要向最優解聚集，多樣性逐步降低。

和聲搜索算法具有較強的全局探索能力，但求解精度較低[19-20],主要是因為在進化后期，算法的局部求解能力較差。本文通過對多峰值函數Schwefel2.26進行測試(設置函數的維數D=1000)，比較改進后的與改進前算法中種群多樣性的變化(如圖5)。

(a)算法HS與HS2的種群多樣性比較

(b)算法IHS與IHS 2的種群多樣性比較

(c)算法ITHS與ITHS2的種群多樣性比較

(d)算法GHS與GHS 2的種群多樣性比較 圖5　 函數Schwefel2.26的多樣性曲線(D=1000) Fig.5　diversity curve of function Schwefel2.26 (D=1000)

圖5可以看出，改進后算法種群多樣性變化明顯，在搜索初期，多樣性較高，有助于進行全局探索，隨著搜索的進行，當種群逐漸聚集到全局最優解附近區域時，開始進行局部高精度求解，種群的多樣性迅速降低。

4結束語

本文提出用一種新穎的維度動態調整策略改進和聲搜索算法，使其通過對和聲記憶庫中最差和聲向量進行調整，在優化初期，采用大范圍、廣維度調整策略保證了種群的多樣性，增強了算法的全局探索能力；隨著優化的進行，逐步降低調整維數，慢慢變為在部分維上進行調整，從而增強算法的局部開發能力，提高其求解精度。這樣，和聲搜索算法有效地在全局探索和局部開發之間實現了平衡. 通過對6個高維復雜多極值測試函數進行實驗，發現本文算法在求解精度和運算成本上都有了明顯改進，并且，隨著維數的增加，本文算法的優勢更加顯著，說明本文改進策略可用于大規模高維復雜問題的求解。

參考文獻:

[1]GOLDBERGDE.Geneticalgorithmsinsearchoptimizationandmachinelearning[M].Boston:Addison-Wesley, 1989：25-30.

[2]EBERHARTRC,KENNEDYJ.Anewoptimizerusingparticleswarmtheory[C]//ProceedingsoftheSixthInternationalSymposiumonMicroMachineandHumanScience.Nagoya,Japan, 1995： 23-30.

[3]STORNR,PRICEKV.MinimizingtherealfunctionsoftheICEC1996contestbydifferentialevolution[C]//ProcIEEEIntConfEvolComput.Nagoya,Japan, 1996: 842-844.

[4]DORIGOM,MANIEZZOV,COLORNIA.Theantsystem:optimizationbyacolonyofcooperatingagents[J].IEEETransSystManCybern, 1996, 26(1): 29-41.

[5]KARABOGAD,BASTURKB.Ontheperformanceofartificialbeecolony(ABC)algorithm[J].AppliedSoftComputing, 2008, 8 (1): 687-697.

[6]GEEMZW,KIMJH,LOGANATHANGV.Anewheuristicoptimizationalgorithm:harmonysearch[J].Simulation, 2001, 76: 60-70.

[7]SIMOND.Biogeography-basedoptimization[J].IEEETransactionsonEvolutionaryComputation, 2008, 12: 702-713.

[8]RAORV,SAVSANIVJ,VAKHARIADP.Teaching-learning-basedoptimization:anovelmethodforconstrainedmechanicaldesignoptimizationproblems[J].Computer-AidedDesign, 2011, 43: 303-315

[9]拓守恒,雍龍泉,鄧方安. “教與學”優化算法研究綜述[J]. 計算機應用研究, 2013(7): 1933-1938.

TUOshouheng,YONGLongquan,DENGFang′an.Surveyofteaching-learning-basedoptimizationalgorithms[J].ApplicationResearchofComputers, 2013(7): 1933-1938.

[10]GEEMZW,KIMJH,LOGANATHANGV.Harmonysearchoptimization:applicationtopipenetworkdesign[J].InternationalJournalofModelling&Simulation, 2002, 22(2): 125-133.

[11]LEEKS,GEEMZW.Anewstructuraloptimizationmethodbasedontheharmonysearchalgorithm[J].Computers&Structures, 2004, 82(9): 781-798.

[12]GEEMZW,LEEKS,PARKY.Applicationofharmonysearchtovehiclerouting[J].AmericanJournalofAppliedSciences, 2005, 2(12): 1552.

[13]VASEBIA,FESANGHARYM,BATHAEESMT.Combinedheatandpowereconomicdispatchbyharmonysearchalgorithm[J].InternationalJournalofElectricalPower&EnergySystems, 2007, 29(10): 713-719.

[14]WANGH,YUANX,WANGY,etal.Harmonysearchalgorithm-basedfuzzy-PIDcontrollerforelectronicthrottlevalve[J].NeuralComputingandApplications, 2013, 22(2): 329-336.

[15]PANQK,SUGANTHANPN,LIANGJJ,etal.Alocal-bestharmonysearchalgorithmwithdynamicsubpopulations[J].EngineeringOptimization, 2010, 42(2): 101-117.

[16]PANQK,SUGANTHANPN,TASGETIRENMF,etal.Aself-adaptiveglobalbestharmonysearchalgorithmforcontinuousoptimizationproblems[J].AppliedMathematicsandComputation, 2010, 216(3): 830-848.

[17]YADAVP,KUMARR,PANDASK,etal.Anintelligenttunedharmonysearchalgorithmforoptimization[J].InformationSciences, 2012, 196: 47-72.

[18]MAHDAVIM,FESANGHARYM,DAMANGIRE.Animprovedharmonysearchalgorithmforsolvingoptimizationproblems[J].AppliedMathematicsandComputation, 2007, 188(2): 1567-1579.

[19]OMRANMGH,MAHDAVIM.Global-bestharmonysearch[J].AppliedMathematicsandComputation, 2008, 198(2): 643-656.

[20]ZOUDexuan,GAOLiqun,WUJianhua,etal.Novelglobalharmonysearchalgorithmforunconstrainedproblems[J].Neurocomputing, 2010,73: 3308-3318.

[21]ZOUDexuan,GAOLiqun,WUJianhua,etal.Anovelglobalharmonysearchalgorithmforreliabilityproblems[J].Computers&IndustrialEngineering, 2010, 58 (2): 307-316.

[22]ZOUDexuan,GAOLiqun,LIS,etal.Solving0-1knapsackproblembyanovelglobalharmonysearchalgorithm[J].AppliedSoftComputing, 2011, 11: 1556-1564.

[23]DASS,MUKHOPADHYAYA,ROYA,etal.Exploratorypoweroftheharmonysearchalgorithm:analysisandimprovementsforglobalnumericaloptimization[J].IEEETransactionsonSystems,Man,andCybernetics,PartB:Cybernetics, 2011, 41(1): 89-106.

[24]TUOShouheng,YONGLongquan.Animprovedharmonysearchalgorithmwithchaos[J].JournalofComputationalInformationSystems， 2012， 8(10 ) : 4269-4276.

[25]TUOShouheng,YONGLongquan,ZHOUTao.Animprovedharmonysearchbasedonteaching-learningstrategyforunconstrainedoptimizationproblems[J].MathematicalProblemsinEngineering, 2013， 19： 69-76.

[26]SARVARIH,ZAMANIFARK.Improvementofharmonysearchalgorithmbyusingstatisticalanalysis[J].ArtificialIntelligenceReview, 2012, 37(3): 181-215.

[27]ASKARZADEHA,REZAZADEHA.Agrouping-basedglobalharmonysearchalgorithmformodelingofprotonexchangemembranefuelcell[J].InternationalJournalofHydrogenEnergy, 2011, 36(8): 5047-5053.

[28]GHOSHS,KUNDUD,SURESHK,etal.DesignofoptimaldigitalIIRfillersbyusingabandwidthadaptiveharmonysearchalgorithm[C]//2009WorldCongressonNature&BiologicallyInspiredComputing.Coimbatore,India, 2009: 480-485.

[29]HOANGDC,YADAVP,KUMARR,etal.Arobustharmonysearchalgorithmbasedclusteringprotocolforwirelesssensornetworks[C]//2010IEEEInternationalConferenceonCommunicationsWorkshops(ICC).[S.l.], 2010: 1-5.

[30]JABERIPOURM,KHORRAME.Solvingthesum-of-ratiosproblemsbyaharmonysearchalgorithm[J].JournalofComputationalandAppliedMathematics, 2010, 234(3): 733-742.

[31]POURSHAM,KHOSHNOUDIANF,MOGHADAMAS.Harmonysearchbasedalgorithmsfortheoptimumcostdesignofreinforcedconcretecantileverretainingwalls[J].InternationalJournalofCivilEngineering, 2011, 9(1): 1-8.

[32]KHAZALIAH,KALANTARM.Optimalreactivepowerdispatchbasedonharmonysearchalgorithm[J].InternationalJournalofElectricalPower&EnergySystems, 2011, 33(3): 684-692.

[33]KHAZALIAH,PARIZADA,KALANTARM.Optimalvoltage/reactivecontrolbyanimproveharmonysearchalgorithm[J].IntRevElectrEng, 2010, 5: 217-224.

[34]KHORRAME,JABERIPOURM.Harmonysearchalgorithmforsolvingcombinedheatandpowereconomicdispatchproblems[J].EnergyConversionandManagement, 2011, 52(2): 1550-1554.

[35]FUKUSHIMAM.Testfunctionsforunconstrainedglobaloptimization[OL/EB].[2014-01-12].http://www-optima.amp.i.kyoto-u.ac.jp/member/student/hedar/Hedar-files/TestGO-files/Page364.htm.

[36]TANGK,YAOX,SUGANTHANPN,etal.BenchmarkfunctionsfortheCEC’2008specialsessionandcompetitiononlargescaleglobaloptimization[OL/EB].[2013-10-21].http://www.ntu.edu.sg/home/EPNSugan/, 2008.

[37]TANGK,LIX,SUGANTHANPN,etal.BenchmarkfunctionsfortheCEC’2010specialsessionandcompetitiononlargescaleglobaloptimization[R].NatureInspired

ComputationandApplicationsLaboratory,USTC,China&NanyangTechnologicalUniversity, 2009.

[38]HERRERAF,LOZANOM,MOLINAD.Testsuiteforthespecialissueofsoftcomputingonscalabilityofevolutionaryalgorithmsandothermeta-heuristicsforlargescalecontinuousoptimizationproblems[OL/EB].[2013-10-21].http://sci2s.ugr.es/eamhco/CFP.php.

拓守恒，男，1978年生，副教授，博士研究生，CCF會員，主要研究方向為智能優化算法、生物信息分析與處理，發表學術論文多篇。

雍龍泉，男，1980年生，副教授，博士，主要研究方向為優化理論與算法設計、智能優化算法等。

鄧方安，男，1963生，教授，博士，主要研究方向為代數系統、粗糙集理論和優化理論。