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

1/6基于和声搜索算法求解组合优化问题基于和声搜索算法求解组合优化问题0引言当前，论文联盟演化计算领域新算法不断涌现，继遗传算法GENETICALGORITHM,GA1、蚁群优化ANTCOLONYOPTIMIZATION,ACO2、粒子群优化PARTICLESWARMOPTIMIZATION,PSO3和差分演化DIFFERENTIALEVOLUTION,DE4之后，又先后出现了混合蛙跳算法SHUFFLEDALGORITHM,SFLA5,6、萤火虫算法FIREFLYALGORITHM,FA7与和声搜索算法HARMONYSEARCHALGORITHM,HSA8等多种新型进化算法。其中，HSA是由GEEM等8于2001年提出的一种新型进化算法，已被应用于求解数值优化问题、流水线调度问题和结构工程优化问题813。为了能够应用HSA求解具有二进制编码的组合最优化问题，本文提出了一种二进制和声搜索算法BINARYHARMONYSEARCHALGORITHM,BHSA，并利用BHSA分别求解著名的K可满足性问题KSATISFIABILITY,KSAT和背包问题，通过对大规模KSAT实例和实例的计算对比表明2/6BHSA是一种比二进制粒子群优化BINARYBPSO,BPSO和GA更适宜用来求解具有二进制编码组合最优化问题的新算法。1二进制和声搜索算法和声搜索算法HSA8是借鉴乐师们凭借记忆通过反复调整各乐器的音调而最终达到一个美妙的和声状态的思想实现进化的。在HSA中，各乐器的和声对应于解向量XIXI1,XI2,XIN，评价结果对应于目标函数FXI，和声记忆库HARMONYMEMORY,HM对应于种群POPX1,X2,XM，而乐曲的创作过程即为种群的进化过程。在基本HSA中，算法首先随机产生HM，然后通过对HM的记忆思考、对音调的定调修正以及随机选择音调三种操作来产生候选解，并将候选解与HM中的最差解比较，淘汰其中的差者以更新HM；反复以上过程，达到和声的最优状态为止。为了将和声搜索算法用于求解组合优化问题，下面基于对HSA的记忆思考、定调修正和随机选取三种进化操作的离散化处理，提出一种二进制编码和声搜索算法BHSA。设MAXFX为最大组合优化问题，其中3/6XX1,X2,XN0,1N为问题的解向量，对应于各乐器的和声的高与低，即XI1时表示乐器I的和声应该为高音，否则为低音。相应地，目标函数FX对应于和声状态的评价。此外，HMCR0,1称为和声库的思考概率HARMONYMEMORYCONSIDERINGRATE,HMCR，PAR0,1称为定调微调概率PITCHADJUSTINGRATE,PAR，本文中HMCR的取值为,PAR的取值为。又设WW1,W2,WN，BB1,B2,BN0,1N分别表示当前最差个体和最好个体，MAXT为迭代次数，则BHSA算法伪代码描述如下基于BHSA求解组合优化问题21基于BHSA求解SAT问题可满足性问题SATISFIABILITYPROBLEM,SAT是论文联盟计算科学中的著名NPC难题，在数理逻辑、人工智能、机器学习、VLSI集成电路设计与检测、数据库检索等方面有着重要的应用14。SAT问题一般描述为给定命题变元集MP1,P2,PN上的一个合取范式CONJUNCTIVENORMALFORM,CNFA，判断是否存在一个指派T0,1N，使得A是可满足的即AT1。对于公式CNFA，如果其中的每个子句最多只含有K4/6个命题变元，则称为KSAT问题。显然，利用BHSA求解KSAT问题的关键在于如何定量描述可满足性，即如何建立适应度函数用于描述KSAT问题是否可满足一种可行的方法是将KSAT问题等价转化为适于BHSA求解最优化问题。为此，下面给出一种将KSAT问题等价转化为0,1N上的整型多项式函数的最大优化问题。仿真实验分析与结论为了验证BHSA求解组合最优化问题的可行性与有效性，下面对大规模问题实例和大规模问题实例，分别利用BHSA、BPSO和GA进行求解对比。为了比较三种算法的优劣性，它们均统一采用本文中提出的求解问题和问题的方法和改进措施。BHSA的种群规模设为10，BPSO和GA的种群规模均为100。所使用微机的硬件环境为INTELRPENTIUMR，主频GHZ，1GB内存，操作系统为MICROSOFTWINDOWSXP，并利用MICROSOFTVISUALC0编程。对于问题，采用随机产生测试实例进行计算对比，分别比较BHSA、BPSO和GA得到可满足指派所耗费的平均5/6执行时间与可满足样例个数两个重要指标。各算法的运行时间均设定为80S，每个测试实例的样本数为100，计算结果见表1。从表1中的求解结果可以看出对于200N600且M150的随机大规模实例，无论是算法的平均求解时间还是所得到的可满足样例个数，BHSA均远远优于BPSO和GA；而且随着N值的增大，BHSA的优势也越来越明显。综上所述，无论对于问题还是问题，BHSA的求解效果均比BPSO和GA更好，由于问题和问题是具有代表性的组合难优化问题，因此可以得出结论BHSA是一种比BPSO和GA更适用于求解具有二进制编码组合优化问题的算法。结语为了求解具有二进制编码的组合优化问题，本文提出了一种二进制和声算法BHSA，通过利用BHSA分别求解大规模问题实例和问题实例的计算结果对比表明BHSA是一种比BPSO和GA的求解性能更优的新算法。由于HSA的提出时间相对较晚，因此其应用领域还有待进一步的扩展，本文提出的BHSA为拓宽HSA的应用提供了可行的参考思路，为此，今后将进一步研究如何利用BHSA利用求解N皇后问