摘要:为了能够应用和声搜索算法（HSA）求解组合优化问题，基于HAS的三种操作的离散化实现提出了一种二进制和声搜索算法(BHSA)，并将BHSA用于求解著名的�k�.可满足性(�k�.SAT)问题和0.1背包问题，通过与粒子群优化（BPSO）和遗传算法（GA）的实例计算对比验证了新算法的可行性与有效性。
关键词:进化算法；二进制和声搜索；组合优化；�k�.SAT问题；0.1背包问题
中图分类号: TP301.6 文献标志码:A
�
Solving combinational optimization problems based on
harmony search algorithm
LI Ning�1�*, LIU Jian.qin� 2, HE Yi.chao� 1
�(
1. School of Information Engineering, Shijiazhuang University of Economics, Shijiazhuang Hebei 050031, China�；�
2. Department of International Education, Shijiazhuang Information Engineering Vocational College, Shijiazhuang Hebei 050035, China
Abstract:
For solving combinational optimization problems, proposed a Binary Harmony Search Algorithm (BHSA) based on three discrete operators of Harmony Search Algorithm （HSA）. Then, use BHSA to solve the famous k-SAT problem and 0-1 Knapsack problem. The numeral results of BHSA, Binary Particle Swarm Optimization （BPSO） and Genetic Algorithm (GA) show that the BHSA is feasible and high efficient.
For solving combinational optimization problems, a Binary Harmony Search Algorithm (BHSA) based on three discrete operators of Harmony Search Algorithm （HSA）was proposed. Then, BHSA was used to solve the famous �k�.SAT problem and 0.1 knapsack problem. The numeral results of BHSA, Binary Particle Swarm Optimization （BPSO） and Genetic Algorithm (GA) show that the BHSA is feasible and highly efficient.
�Key words:
evolutionary algorithm; binary harmony search; combinational optimization; �k�.SAT problem; 0.1 Knapsack Problem (KP)
�
0 引言�
当前，演化计算领域新算法不断涌现，继遗传算法(Genetic Algorithm, GA)�［1］、蚁群优化(Ant Colony Optimization,ACO)�［2］、粒子群优化(Particle Swarm Optimization, PSO)�［3］和差分演化(Differential Evolution, DE)�［4］之后，又先后出现了混合蛙跳算法(Shuffled Frog.Leaping Algorithm,SFLA)�［5,6］、萤火虫算法(Firefly Algorithm, FA)�［7］与和声搜索算法(Harmony Search Algorithm, HSA)�［8］等多种新型进化算法。其中，HSA是由Geem等�［8］于2001年提出的一种新型进化算法，已被应用于求解数值优化问题、流水线调度问题和结构工程优化问题�［8-13］。为了能够应用HSA求解具有二进制编码的组合最优化问题，本文提出了一种二进制和声搜索算法(Binary Harmony Search Algorithm,BHSA)，并利用BHSA分别求解著名的�k�.可满足性问题(�k�.SATisfiability,�k�.SAT)和0.1背包问题(0.1KP)，通过对大规模�k�.SAT实例和0.1KP实例的计算对比表明：BHSA是一种比二进制粒子群优化(Binary BPSO, BPSO)和GA更适宜用来求解具有二进制编码组合最优化问题的新算法。�
1 二进制和声搜索算法�
和声搜索算法(HSA)�［8］是借鉴乐师们凭借记忆通过反复调整各乐器的音调而最终达到一个美妙的和声状态的思想实现进化的。在HSA中，各乐器的和声对应于解向量�X�i=(x�i1,x�i2,…,x�in)，评价结果对应于目标函数f(X�i)，和声记忆库�(Harmony Memory,HM)�对应于种群Pop={X�1,X�2,…, X�m}，�而乐曲的创作过程即为种群的进化过程。在基本HSA中，算法首先随机产生HM，然后通过对HM的记忆思考、对音调的定调修正以及随机选择音调三种操作来产生候选解，并将候选解与HM中的最差解比较，淘汰其中的差者以更新HM；反复以上过程，达到和声的最优状态为止。�
为了将和声搜索算法用于求解组合优化问题，下面基于对HSA的记忆思考、定调修正和随机选取三种进化操作的离散化处理，提出一种二进制编码和声搜索算法(BHSA)。�
�
设�max� f(X)为最大组合优化问题，其中X=(x�1,x�2,…,x�n)∈{0,1}�n为问题的解向量，对应于各乐器的和声的高与低，即x�i=1时表示乐器i的和声应该为高音，否则为低音。相应地，目标函数f(X) 对应于和声状态的评价。此外，HMCR∈(0,1)称为和声库的思考概率�(Harmony Memory Considering Rate, HMCR)， �PAR∈(0,1)称为定调微调概率�(Pitch Adjusting Rate, PAR)，�本文中HMCR的取值为0.9, PAR的取值为0.3。又设W=(w�1,w�2,…,w�n)，B=(b�1,b�2,…,b�n)∈{0,1}�n分别表示当前最差个体和最好个体，MaxT为迭代次数，则�BHSA�算法伪代码描述如下：
2 基于BHSA求解组合优化问题�
2．1 基于BHSA求解SAT问题�
可满足性问题(Satisfiability Problem, SAT)是计算科学中的著名NPC难题，在数理逻辑、人工智能、机器学习、VLSI集成电路设计与检测、数据库检索等方面有着重要的应用�［14］。SAT问题一般描述为：给定命题变元集�M={p�1,p�2,…,p�n}�上的一个合取范式(Conjunctive Normal Form,CNF) �A�，判断是否存在一个指派�t∈{0,1}�n，使得A是可满足的(即(A)�t=1)。�对于公式CNF �A，如果其中的每个子句最多只含有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问题的方法和改进措施。BHSA的种群规模设为10，BPSO和GA的种群规模均为100。所使用微机的硬件环境为Intel(R) Pentium(R) 4，主频2.4�GHz，1�GB内存，操作系统为Microsoft Windows XP，并利用Microsoft Visual C++ 6.0编程。�
对于3.SAT问题，采用随机产生测试实例进行计算对比，分别比较BHSA、BPSO和GA得到可满足指派所耗费的平均执行时间与可满足样例个数两个重要指标。各算法的运行时间均设定为80�s，每个测试实例的样本数为100，计算结果见表1。�
从表1中的求解结果可以看出：对于�200≤n≤600且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.
［2］
DORIGO M, CARO G. The ant colony optimization meta.heuristic［M］. London: McGraw Hill,1999:11-32.
［3］
KENNEDY J, EBERHART R C. Particle swarm optimization［C］// Proceedings of the IEEE International Conference on Neural Networks. Piscataway: IEEE Service Center,1995:1942-1948.
［4］
STORN R, PRICE K. Differential evolution―a simple and efficient heuristic for global optimization over continuous spaces［J］. Journal of Global Optimization,1997,11（4）:341-359.
［5］
EUSUFF M M, LANSEY K E. Optimization of water distribution network design using the shuffled frog.leaping algorithm［J］. Journal of Water Resources Planning and Management,2003,129(3): 210-225.
［6］
贺毅朝，曲文龙，许冀伟．一种改进的混合蛙跳算法及其收敛性分析［J］．计算机工程与应用,2011，47(22)：37-40.
［7］
YANG XIN.SHE. Firefly algorithm, stochastic test functions and design optimisation［J］. Journal International Journal of Bio.Inspired Computation, 2010,2(2):78-84.
［8］
GEEM Z W, KIM J H, LOGANATHAN G V. A new heuristic optimization algorithm: Harmony search［J］. Simulation, 2001,76(2): 60-68.
［9］
MAHDAVI M, FESANGHARY M, DAMANGIR E. An improved harmony search algorithms for solving optimization problems［J］. Applied Mathematics and Computation, 2007,188(2): 1567-1579.
［10］
LEE K S, GEEM Z W. A new meta.heuristic algorithm for continuous engineering optimization: Harmony search theory and practice［J］. Computer Methods in Applied Mechanics and Engineering, 2005, 194(36/37/38): 3902-3933.
［11］
武磊，潘全科，桑红燕，等．求解零空闲流水线调度问题的和声搜索算法［J］．计算机集成制造系统，2009，15(10)：1960-1967.
［12］
韩红燕，潘全科，梁静．改进的和声搜索算法在函数优化中的应用[J]．计算机工程，2010，36(13)：245-247.
［13］
邹德旋，高立群，吴建华，等．混合差分进化―和声搜索算法在结构工程中的应用［J］．东北大学学报：自然科学版，2010，31(6)：769-772.
［14］
张健.逻辑公式的可满足性判定――方法、工具及应用［M］．北京：科学出版社，2000.
［15］
刘建芹，贺毅朝，顾茜茜．基于离散微粒群算法求解背包问题研究［J］．计算机工程与设计，2007，28(13)：3189-3191，3204.
［16］
潘正君，康立山，陈毓屏．演化计算［M］．北京：清华大学出版社，2000.
［17］
KELLERER H, PFERSCHY U, PISINGER D. Knapsack problems［M］. Berlin: Springer, 2004.