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

doi:10.3724/SP.J.1087.2012.01041

计算机应用 ›› 2012, Vol. 32 ›› Issue (04): 1041-1044.DOI: 10.3724/SP.J.1087.2012.01041

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

李宁¹,刘建芹²,贺毅朝¹

1. 石家庄经济学院信息工程学院，石家庄 050031
2. 石家庄信息工程职业学院国际教育部,石家庄 050035

收稿日期:2011-10-18 修回日期:2011-12-05 发布日期:2012-04-20 出版日期:2012-04-01
通讯作者: 李宁
作者简介:李宁(1977-)，女，河北石家庄人，讲师，硕士，主要研究方向：人工智能；刘建芹(1966-)，女，河北灵寿人，副教授，硕士，主要研究方向：智能算法；贺毅朝(1969-)，男，河北晋州人，教授，CCF会员，主要研究方向：智能计算、算法理论、计算机密码学。
基金资助:
河北省高等学校科学技术研究项目

Solving combinational optimization problems based on harmony search algorithm

LI Ning¹,LIU Jian-qin²,HE Yi-chao¹

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

Received:2011-10-18 Revised:2011-12-05 Online:2012-04-20 Published:2012-04-01
Contact: LI Ning

摘要/Abstract

摘要： 为了能够应用和声搜索算法（HSA）求解组合优化问题，基于HAS的三种操作的离散化实现提出了一种二进制和声搜索算法(BHSA)，并将BHSA用于求解著名的k-可满足性(k-SAT)问题和0-1背包问题，通过与粒子群优化（BPSO）和遗传算法（GA）的实例计算对比验证了新算法的可行性与有效性。

关键词: 进化算法, 二进制和声搜索, 组合优化, k-SAT问题, 0-1背包问题

Abstract: 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)

李宁刘建芹贺毅朝. 基于和声搜索算法求解组合优化问题[J]. 计算机应用, 2012, 32(04): 1041-1044.

LI Ning LIU Jian-qin HE Yi-chao. Solving combinational optimization problems based on harmony search algorithm[J]. Journal of Computer Applications, 2012, 32(04): 1041-1044.

参考文献

［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.

[1]	赵秋云, 魏乐, 舒红平. 面向制造任务的云制造虚拟车间构造方法[J]. 计算机应用, 2021, 41(7): 2003-2011.
[2]	王宇, 刘燕丽, 陈劭武. 基于顶点冲突学习的最大公共子图算法[J]. 计算机应用, 2021, 41(6): 1756-1760.
[3]	王泽昆, 贺毅朝, 李焕哲, 张发展. 基于新颖S型转换函数的二进制粒子群优化算法求解具有单连续变量的背包问题[J]. 计算机应用, 2021, 41(2): 461-469.
[4]	陈桢, 钟一文, 林娟. 求解0-1背包问题的混合贪婪遗传算法[J]. 计算机应用, 2021, 41(1): 87-94.
[5]	严华健, 张国富, 苏兆品, 刘扬. 救灾物资高维多目标自适应分配问题建模与求解[J]. 计算机应用, 2020, 40(8): 2410-2419.
[6]	李章洪, 梁晓磊, 田梦丹, 周文峰. 求解排列组合问题的解空间动态缩减策略[J]. 计算机应用, 2020, 40(7): 2016-2020.
[7]	杨云亭, 王鹏. 求解旅行商问题的多尺度量子自由粒子优化算法[J]. 计算机应用, 2020, 40(5): 1278-1283.
[8]	杨艳, 刘生建, 周永权. 贪心二进制狮群优化算法求解多维背包问题[J]. 计算机应用, 2020, 40(5): 1291-1294.
[9]	赵志学, 李夏苗, 周鲜成. 考虑拥堵区域的多车型绿色车辆路径问题优化[J]. 计算机应用, 2020, 40(3): 883-890.
[10]	张鑫, 邹德旋, 沈鑫. 含交叉项的混合二范数粒子群优化算法[J]. 计算机应用, 2018, 38(8): 2148-2156.
[11]	刘宝, 董明刚, 敬超. 改进的排序变异多目标差分进化算法[J]. 计算机应用, 2018, 38(8): 2157-2163.
[12]	袁亦川, 杨洲, 罗廷兴, 秦进. 求解动态优化问题的多种群竞争差分进化算法[J]. 计算机应用, 2018, 38(5): 1254-1260.
[13]	郭后钱, 王微微, 尚颖, 赵瑞莲. 基于动态集合进化算法的弱变异测试用例集生成[J]. 计算机应用, 2017, 37(9): 2659-2664.
[14]	熊瑞琦, 马昌喜. 多配送中心危险货物配送路径鲁棒优化[J]. 计算机应用, 2017, 37(5): 1485-1490.
[15]	郭羽含, 张美琪, 周楠. 基于偏好矩阵遗传算法求解长期车辆合乘问题[J]. 计算机应用, 2017, 37(2): 602-607.

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

Solving combinational optimization problems based on harmony search algorithm

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics