动态调整策略改进的和声搜索算法

网络出版地址：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生，教授，博士，主要研究方向为代数系统、粗糙集理论和优化理论。