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

《基于和声搜索算法求解组合优化问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于和声搜索算法求解组合优化问题基于和声搜索算法求解组合优化问题　0引言　　　　　　当前，.L.演化计算领域新算法不断涌现，继遗传算法(GeicAlgorithm,GA)［1］、蚁群优化(AntColonyOptimization,ACO)［2］、粒子群优化(ParticleSOptimization,PSO)［3］和差分演化(DifferentialEvolution,DE)［4］之后，又先后出现了混合蛙跳算法(ShuffledFrog.LeapingAlgorithm,SFLA)［5,6］、萤火虫算法(FireflyAlg

2、orithm,FA)［7］与和声搜索算法(HarmonySearchAlgorithm,HSA)［8］等多种新型进化算法。其中，HSA是由Geem等［8］于2001年提出的一种新型进化算法，已被应用于求解数值优化问题、流水线调度问题和结构工程优化问题［8-13］。为了能够应用HSA求解具有二进制编码的组合最优化问题，本文提出了一种二进制和声搜索算法(BinaryHarmonySearchAlgorithm,BHSA)，并利用BHSA分别求解著名的k.可满足性问题(k.SATisfiability,k.SAT)和0.1背

3、包问题(0.1KP)，通过对大规模k.SAT实例和0.1KP实例的计算对比表明：BHSA是一种比二进制粒子群优化(BinaryBPSO,BPSO)和GA更适宜用来求解具有二进制编码组合最优化问题的新算法。　　1二进制和声搜索算法　　和声搜索算法(HSA)［8］是借鉴乐师们凭借记忆通过反复调整各乐器的音调而最终达到一个美妙的和声状态的思想实现进化的。在HSA中，各乐器的和声对应于解向量Xi=(xi1,xi2,,xin)，评价结果对应于目标函数f(Xi)，和声记忆库(HarmonyMemory,HM)对应于种群Pop

4、={X1,X2,,Xm}，而乐曲的创作过程即为种群的进化过程。在基本HSA中，算法首先随机产生HM，然后通过对HM的记忆思考、对音调的定调修正以及随机选择音调三种操作来产生候选解，并将候选解与HM中的最差解比较，淘汰其中的差者以更新HM；反复以上过程，达到和声的最优状态为止。　　为了将和声搜索算法用于求解组合优化问题，下面基于对HSA的记忆思考、定调修正和随机选取三种进化操作的离散化处理，提出一种二进制编码和声搜索算法(BHSA)。　　　　　　设maxf(X)为最大组合优化问题，其中X=(x1,x2,,xn)&is

5、in;{0,1}n为问题的解向量，对应于各乐器的和声的高与低，即xi=1时表示乐器i的和声应该为高音，否则为低音。相应地，目标函数f(X)对应于和声状态的评价。此外，HMCR∈(0,1)称为和声库的思考概率(HarmonyMemoryConsideringRate,HMCR)，PAR∈(0,1)称为定调微调概率(PitchAdjustingRate,PAR)，本文中HMCR的取值为0.9,PAR的取值为0.3。又设W=(axT为迭代次数，则BHSA算法伪代码描述如下：　　　　2基于BHSA求解组合优化问

6、题　　2．1基于BHSA求解SAT问题　　可满足性问题(SatisfiabilityProblem,SAT)是.L.计算科学中的著名NPC难题，在数理逻辑、人工智能、机器学习、VLSI集成电路设计与检测、数据库检索等方面有着重要的应用［14］。SAT问题一般描述为：给定命题变元集M={p1,p2,,pn}上的一个合取范式(ConjunctiveNormalForm,F)A，判断是否存在一个指派t∈{0,1}n，使得A是可满足的(即(A)t=1)。对于公式FA，如果其中的每个子句最多只含有k个命题变

7、元，则称为k.SAT问题。　　　　显然，利用BHSA求解k.SAT问题的关键在于如何定量描述可满足性，即如何建立适应度函数用于描述k.SAT问题是否可满足？一种可行的方法是将k.SAT问题等价转化为适于BHSA求解最优化问题。为此，下面给出一种将k.SAT问题等价转化为{0,1}n上的整型多项式函数的最大优化问题。　　　　3仿真实验分析与结论　　　　为了验证BHSA求解组合最优化问题的可行性与有效性，下面对大规模3.SAT问题实例和大规模0.1KP问题实例，分别利用BHSA、BPSO和GA进行求解对比。为了

8、比较三种算法的优劣性，它们均统一采用本文中提出的求解3.SAT问题和0.1KP问题的方法和改进措施。BHSA的种群规模设为10，BPSO和GA的种群规模均为100。所使用微机的硬件环境为Int