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

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

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

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

3、y,k.SAT)和背包问题()，通过对大规模k.SAT实例和实例的计算对比表明：BHSA是一种比二进制粒子群优化(BinaryBPSO,基于和声搜索算法求解组合优化问题　　0引言　　　　　　当前，演化计算领域新算法不断涌现，继遗传算法(GeneticAlgorithm,GA)［1］、蚁群优化(AntColonyOptimization,ACO)［2］、粒子群优化(ParticleSwarmOptimization,PSO)［3］和差分演化(DifferentialEvolution,D

4、E)［4］之后，又先后出现了混合蛙跳算法(ShuffledAlgorithm,SFLA)［5,6］、萤火虫算法(FireflyAlgorithm,FA)［7］与和声搜索算法(HarmonySearchAlgorithm,HSA)［8］等多种新型进化算法。其中，HSA是由Geem等［8］于2001年提出的一种新型进化算法，已被应用于求解数值优化问题、流水线调度问题和结构工程优化问题［8-13］。为了能够应用HSA求解具有二进制编码的组合最优化问题，本文提出了一种二进制和声搜索算法(Binar

5、yHarmonySearchAlgorithm,BHSA)，并利用BHSA分别求解著名的k.可满足性问题(k.SATisfiability,k.SAT)和背包问题()，通过对大规模k.SAT实例和实例的计算对比表明：BHSA是一种比二进制粒子群优化(BinaryBPSO,BPSO)和GA更适宜用来求解具有二进制编码组合最优化问题的新算法。　　1二进制和声搜索算法　　和声搜索算法(HSA)［8］是借鉴乐师们凭借记忆通过反复调整各乐器的音调而最终达到一个美妙的和声状态的思想实现进化的

6、。在HSA中，各乐器的和声对应于解向量Xi=(xi1,xi2,…,xin)，评价结果对应于目标函数f(Xi)，和声记忆库(HarmonyMemory,HM)对应于种群Pop={X1,X2,…,Xm}，而乐曲的创作过程即为种群的进化过程。在基本HSA中，算法首先随机产生HM，然后通过对HM的记忆思考、对音调的定调修正以及随机选择音调三种操作来产生候选解，并将候选解与HM中的最差解比较，淘汰其中的差者以更新HM；反复以上过程，达到和声的最优状态为止。　　为了将和声搜索算法用于求解

7、组合优化问题，下面基于对HSA的记忆思考、定调修正和随机选取三种进化操作的离散化处理，提出一种二进制编码和声搜索算法(BHSA)。　　　　　　设maxf(X)为最大组合优化问题，其中X=(x1,x2,…,xn)∈{0,1}n为问题的解向量，对应于各乐器的和声的高与低，即xi=1时表示乐器i的和声应该为高音，否则为低音。相应地，目标函数f(X)对应于和声状态的评价。此外，HMCR∈(0,1)称为和声库的思考概率(HarmonyMemoryConsideringRate,HMCR)，

8、PAR∈(0,1)称为定调微调概率(PitchAdjustingRate,PAR)，本文中HMCR的取值为,PAR的取值为。又设W=(w1,w2,…,wn)，B=(b1,b2,…,bn)∈{0,1}n分别表示当前最差个体和最好个体，MaxT为迭代次数，则BHSA算法伪代码描述如下：　　　　基于BHSA求解组合优化问题　　2．1基于BHSA求解SAT问题可满足性问题(SatisfiabilityProblem,SAT)是计算科学中