基于和声搜索算法求解组合优化问题

—论文发表专家—论文发表专家—-基于和声搜索算法求解组合优化问题摘要:为了能够应用和声搜索算法（hsa）求解组合优化问题，基于has的三种操作的离散化实现提出了一种二进制和声搜索算法（bhsa），并将bhsa用于求解著名的k•可满足性（k.sat）问题和0.1背包问题，通过与粒子群优化（bpso）和遗传算法（ga）的实例计算对比验证了新算法的可行性与有效性。关键词:进化算法；二进制和声搜索；组合优化；k.sat问题；0.1背包问题solvingcombinationaloptimizationproblemsbasedonharmonysearchalgorithmlining1*,liujian.qin2,heyi・chao1(1.schoolofinformationengineering,shijiazhuanguniversityofeconomics,shijiazhuanghebei050031,china2・departmentofinternationaleducation,shijiazhuanginformationengineeringvocationalcollege,shijiazhuanghebei050035,chinaabstract:—论文发表专家—E国寻朮发衣厨wwwqikanwang,neforsolvingcombinationaloptimizationproblems,proposedabinaryharmonysearchalgorithm(bhsa)basedonthreediscreteoperatorsofharmonysearchalgorithm(hsa).then,usebhsatosolvethefamousk-satproblemand0-1knapsackproblem.thenumeralresultsofbhsa,binaryparticleswarmoptimization(bpso)andgeneticalgorithm(ga)showthatthebhsaisfeasibleandhighefficient.forsolvingcombinationaloptimizationproblems,abinaryharmonysearchalgorithm(bhsa)basedonthreediscreteoperatorsofharmonysearchalgorithm(hsa)wasproposed.then,bhsawasusedtosolvethefamousk.satproblemand0.1knapsackproblem.thenumeralresultsofbhsa,binaryparticleswarmoptimization(bpso)andgeneticalgorithm(ga)showthatthebhsaisfeasibleandhighlyefficient.keywords:evolutionaryalgorithm;binaryharmonysearch;combinationaloptimization;k.satproblem;0.1knapsackproblem(kp)0引言

—论文发表专家—E国寻朮发衣厨当前，演化计算领域新算法不断涌现，继遗传算法(geneticalgorithm,ga)[1]、蚁群优化(antcolonyoptimization,aco)[2]、粒子群优化(particleswarmoptimization,pso)[3]和差分演化(differentialevolution,de)[4]之后，又先后出现了混合蛙跳算法(shuffledfrog.leapingalgorithm,sfla)[5,6]、萤火虫算法(fireflyalgorithm,fa)[7]与和声搜索算法(harmonysearchalgorithm,hsa)[8]等多种新型进化算法。其中，hsa是由geem等[8]于2001年提出的一种新型进化算法，已被应用于求解数值优化问题、流水线调度问题和结构工程优化问题[8-13]。为了能够应用hsa求解具有二进制编码的组合最优化问题，本文提出了一种二进制和声搜索算法(binaryharmonysearchalgorithm,bhsa)，并利用bhsa分别求解著名的k.可满足性问题(k.satisfiability,k.sat)和0.1背包问题(0.1kp),通过对大规模k.sat实例和0.1kp实例的计算对比表明：bhsa是一种比二进制粒子群优化(binarybpso,bpso)和ga更适宜用来求解具有二进制编码组合最优化问题的新算法。1二进制和声搜索算法和声搜索算法(hsa)[8]是借鉴乐师们凭借记忆通过反复调整各乐器的音调而最终达到一个美妙的和声状态的思想实现进化的。在hsa中，各乐器的和声对应于解向量xi=(xi1,x—论文发表专家——论文发表专家—E国学朮发丢网www.qikanwangnet—论文发表专家——论文发表专家—E国学朮发丢网www.qikanwangnet—论文发表专家—论文发表专家—'0:0E国寻朮发夷厨i2,…,xin),评价结果对应于目标函数f(xi),和声记忆库(harmonymemory,hm)对应于种群pop二{x1,x2,…，xm}，而乐曲的创作过程即为种群的进化过程。在基本hsa中，算法首先随机产生hm,然后通过对hm的记忆思考、对音调的定调修正以及随机选择音调三种操作来产生候选解，并将候选解与hm中的最差解比较，淘汰其中的差者以更新hm；反复以上过程，达到和声的最优状态为止。为了将和声搜索算法用于求解组合优化问题，下面基于对hsa的记忆思考、定调修正和随机选取三种进化操作的离散化处理，提出一种二进制编码和声搜索算法(bhsa)。设maxf(x)为最大组合优化问题，其中x=(x1,x2,…,xn)e{0,1}n为问题的解向量，对应于各乐器的和声的高与低,即xi=1时表示乐器i的和声应该为高音，否则为低音。相应地,目标函数f(x)对应于和声状态的评价。此外，hmcre(0,1)称为和声库的思考概率(harmonymemoryconsideringrate,hmcr),pare(0,1)称为定调微调概率(pitchadjustingrate,par),本文中hmcr的取值为0.9,par的取值为0・3。又设w=(w1,w2,…,wn),b=(b1,b2,…,bn)e{0,1}n分别表示当前最差个体和最好个体，maxt为迭代次数，则bhsa算法伪代码描述如下：2基于bhsa求解组合优化问题2.1基于bhsa求解sat问题可满足性问题(satisfiabilityproblem,sat)是计算科学中的著名npc难题，在数理逻辑、人工智能、机器学习、vlsi集成电路设计与检测、数据库检索等方面有着重要的应用［14］。sat问题一般描述为：给定命题变元集m={p1,p2,…,pn}上的一个合取范式(conjunctivenormalform,cnf)存在一个指派tU{0,1}n,使得a是可满足的(即(a)t=1)。对于公式cnfa,如果其中的每个子句最多只含有k个命题变元，则称为k・sat问题。显然，利用bhsa求解k.sat问题的关键在于如何定量描述可满足性，即如何建立适应度函数用于描述k.sat问题是否可满足？一种可行的方法是将k.sat问题等价转化为适于bhsa求解最优化问题。为此，下面给出一种将k.sat问题等价转化为{0，1}n上的整型多项式函数的最大优化问题。3仿真实验分析与结论为了验证bhsa求解组合最优化问题的可行性与有效性，下面对大规模3.sat问题实例和大规模0.1kp问题实例，分别利用bhsa、bpso和ga进行求解对比。为了比较三种算法的优劣性，它们均统一采用本文中提出的求解3.sat问题和0.1kp问题的方法和改进措—论文发表专家——论文发表专家—E国寻朮发丢画www.qikanwangne一论文发表专家一E国寻朮凌丢网wwwPqikanwang,net施。bhsa的种群规模设为10,bpso和ga的种群规模均为100。所使用微机的硬件环境为intel(r)pentium(r)4,主频2.4ghz,1gb内存，操作系统为microsoftwindowsxp,并利用microsoftvisualc++6.0编程。对于3.sat问题，采用随机产生测试实例进行计算对比，分别比较bhsa、bpso和ga得到可满足指派所耗费的平均执行时间与可满足样例个数两个重要指标。各算法的运行时间均设定为80s，每个测试实例的样本数为100，计算结果见表1。从表1中的求解结果可以看出：对于200WnW600且m=150的随机大规模3.sat实例，无论是算法的平均求解时间还是所得到的可满足样例个数，bhsa均远远优于bpso和ga；而且随着n值的增大，bhsa的优势也越来越明显。综上所述，无论对于3.sat问题还是0.1kp问题，bhsa的求解效果均比bpso和ga更好，由于3.sat问题和0.1kp问题是具有代表性的组合难优化问题，因此可以得出结论：bhsa是一种比bpso和ga更适用于求解具有二进制编码组合优化问题的算法。4结语为了求解具有二进制编码的组合优化问题，本文提出了一种二进制和声算法(bhsa)，通过利用bhsa分别求解大规模3.sat问题实例和0.1kp问题实例的计算结果对比表明：bhsa是一种比bpso和ga的求解性能更优的新算法。由于hsa的提出时间相对较晚，因此其应用领域还有待进一步的扩展，本文提出的bhsa为拓宽hsa的应用提供了可行的参考思路，为此，今后将进一步研究如何利用bhsa利用求解n皇后问题和二划分问题等组合难优化问题。参考文献：[1]陈国良，王熙法，庄镇泉，等.遗传算法及其应用[m].北京:人民邮电出版社，2003.dorigom,carog.theantcolonyoptimizationmeta.heuristic[m].london:mcgrawhill,1999:11-32.[3]kennedyj,eberhartrc.particleswarmoptimization[c]//proceedingsoftheieeeinternationalconferenceonneuralnetworks.piscataway:ieeeservicecenter,1995:1942-1948.stornr,pricek.differentialevolution—asimpleandefficientheuristicforglobaloptimizationovercontinuousspaces[j].journalofglobaloptimization,1997,11（4）:341-359.5]

—论文发表专家—E国寻朮发罢网www.qikanwang,neteusuffmm,lanseyke.optimizationofwaterdistributionnetworkdesignusingtheshuffledfrog.leapingalgorithm[j].journalofwaterresourcesplanningandmanagement,2003,129(3):210-225.贺毅朝，曲文龙，许冀伟．一种改进的混合蛙跳算法及其收敛性分析[j].计算机工程与应用,2011,47(22)：37-40.[7]yangxin.she.fireflyalgorithm,stochastictestfunctionsanddesignoptimisation[j].journalinternationaljournalofbio.inspiredcomputation,2010,2(2):78-84.geemzw,kimjh,loganathangv.anewheuristicoptimizationalgorithm:harmonysearch[j].simulation,2001,76(2):60-68.mahdavim,fesangharym,damangire.animprovedharmonysearchalgorithmsforsolvingoptimizationproblems[j].appliedmathematicsandcomputation,2007,188(2):1567-1579.[10]leeks,geemzw.anewmeta.heuristicalgorithmforI—I—论文发表专家—胃山国寻朮菽罢网§gwww.qikanwang,net—论文发表专家—ED国寻朮发罢网www.qikanwang,netcontinuousengineeringoptimization:harmonysearchtheoryandpractice[j].computermethodsinappliedmechanicsandengineering,2005,194(36/37/38):3902-3933.武磊，潘全科，桑红燕，等．求解零空闲流水线调度问题的和声搜索算法[j].计算机集成制造系统，2009,15(10)：1960-1967.韩红燕，潘全科，梁静．改进的和声搜索算法在函数优化中的应用[j].计算机工程，2010,36(13)：245-247.邹德旋，高立群