Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2019, Vol. 46 Issue (5): 556-564    DOI: 10.3785/j.issn.1008-9497.2019.05.007
数学与计算机科学     
求解最大二等分问题的混合二进制人工蜂群算法
林耿
闽江学院 数学与数据科学学院，福建 福州 350108
A hybrid binary artificial bee colony algorithm for the max-bisection problem.
LIN Geng
College of Mathematics and Data Science, Minjiang University, Fuzhou 350108, China
 全文: PDF(577 KB)   HTML  
摘要： 为更好地解决最大二等分问题，提出了一种求解该问题的混合二进制人工蜂群算法。首先，针对传统人工蜂群算法不能解决离散问题的缺陷，根据最大二等分问题的特点，重新设计了蜂群的食物源更新方法，新产生的食物源既继承了先前找到的高质量解的优良结构，又具有良好的多样性。其次，采用填充函数算法对新产生的食物源进行进一步优化，有效提高了人工蜂群算法的局部搜索能力。最后，通过比较混合二进制人工蜂群算法和其他现有算法对不同规模标准测试例子的计算结果，验证了本算法的优越性。
关键词： 最大二等分;  填充函数;  人工蜂群算法;  局部搜索    
Abstract: To solve the max-bisection problem, a hybrid binary artificial bee colony algorithm is presented. First, to overcome the defect that artificial bee colony algorithm cannot solve discrete problem, based on the characteristics of the max-bisection problem, a new bee colony updating method is proposed. The newly generated solutions inherit the good structure of previously found good quality solutions, and have good diversity. Next, in order to improve the local search ability, the newly generated solutions are further improved by the filled function method. The proposed algorithm is compared with existing algorithms based on several different scale benchmark instances,demonstrating the effectiveness and superiority of the new algorithm in solving the max-bisection problem.
Key words: max-bisection    filled function    artificial bee colony algorithm    local search
收稿日期: 2018-04-01 出版日期: 2019-09-25
CLC:  O 224.1  
基金资助: 国家自然科学基金资助项目(11301255)；福建省自然科学基金资助项目(2017J01076)；福建省高校新世纪优秀人才支持计划项目.
作者简介: 林耿(1981—)，ORCID:http://orcid.org/0000- 0002-1643-6859 ，男，博士，教授，主要从事优化理论与算法、智能计算等研究，E-mail：lingeng413@163.com.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
林耿

引用本文:

林耿. 求解最大二等分问题的混合二进制人工蜂群算法[J]. 浙江大学学报（理学版）, 2019, 46(5): 556-564.

LIN Geng. A hybrid binary artificial bee colony algorithm for the max-bisection problem.. Journal of ZheJIang University(Science Edition), 2019, 46(5): 556-564.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2019.05.007    或    https://www.zjujournals.com/sci/CN/Y2019/V46/I5/556

1 GAREYM R, JOHNSOND S. Computers and Intractability:A Guide to the Theory of NP-Completeness[M]. New York: WH Freeman, 1979.
2 BRUNETTAL, CONFORTIM, RINALDIG. A branch-and-cut algorithm for the Equicut problem[J]. Mathematical Programming, 1997, 78(2): 243-263.DOI:10.1007/bf02614373
3 KARISCHS E, RENDLF, CLAUSENJ. Solving graph bisection problems with semidefinite programming[J]. Informs Journal on Computing, 2000, 12(3): 177-191. DOI:10.1287/ijoc.12.3.177.12637
4 YUL, LIUS Y, WANGX H. A 0.488 algorithm for max-bisection problem with nonnegative weights[J]. Chinese Journal of Engineering Mathematics, 2005, 22(6): 1137-1140.DOI:10.3969/j.issn.1005-3085.2005.06.032
5 FRIEZEA, JERRUMM. Improved approximation algorithm for max k-cut and max-bisection[J]. Algorithmica, 1997, 18(1): 67-81.
6 YEY Y. A 699-approximation algorithm for max-bisection[J]. Mathematical Programming, 2001, 90(1): 101-111.
7 HALPERINE, ZWICKU. A unified framework for obtaining improved approximation algorithm for maximum bisection problems[C]//In Proc of 8th International IPCO Conference. Utrecht:Wiley Periodicas Inc, 2001: 210-225.DOI:10.1007/3-540-45535-3_17
8 GOEMANSM X, WILLIAMSOND P. Improved approximation algorithm for max-cut and satisfiability problems using semidefinite programming[J]. Journal of the ACM, 1995, 42(6): 1115-1145.
9 ALIZADEHF. Interior point methods in semidefinite programming with applications to combinatorial optimization[J]. SIAM Journal on Optimization, 1995, 5(1): 13-51. DOI:10.1137/0805002
10 MUX W, LIUH W, LIUS Y. A feasible direction algorithm for max bisection via low-rank factorization[J]. Journal of Systems Science and Mathematical Sciences, 2007, 27(5): 780-790.DOI:10.3969/j.issn.1000-0577.2007.05.015
11 BURERS, MONTEIROR D C, ZHANGY. Rank two relaxation heuristics for max-cut and other binary quadratic progrmas[J]. SIAM Journal on Optimization, 2001, 12(2): 503-521. DOI:10.1137/s1052623400382467
12 ZHANGF, XUC X. Improvement on the rank-two relaxation algorithm for the graph max-bisection problem[J]. Chinese Journal of Engineering Mathematics, 2010, 27(4): 621-626.DOI:10.3969/j.issn.1005-3085.2010.04.007
13 LINGA F, XUC X, TANGL. A modified VNS metaheuristic for max-bisection problems[J]. Journal of Computational and Applied Mathematics, 2008, 220(1-2): 413-421. DOI:10.1016/j.cam.2007.08.018
14 XUF M, MAS X, CHENB L. A new Lagrangian net algorithm for solving max-bisection problems[J]. Journal of Computational and Applied Mathematics, 2011, 235(13): 3718-3723. DOI:10.1016/j.cam.2011.01.015
15 WUQ H， HAOJ K. Memetic search for the max-bisection problem[J]. Computers ＆ Operations Research, 2013, 40(1): 166-179.
16 LING, ZHUW X. An efficient Memetic algorithm for the max-bisection problem[J]. IEEE Transactions on Computers, 2014,63(3): 1365-1376. DOI:10.1109/tc.2013.7
17 LING, XUM Q. Discrete filled function method for max-bisection problem[J]. Computer Engineering and Applications, 2016, 52(5): 27-32. DOI:10.3778/j.issn.1002-8331.1403-0373
18 KARABOGAD. An Idea Based on Honey Bee Swarm for Number Optimization [R]. Erciyes: Erciyes University, 2005.
19 LUJ S, WENGY W, LIX L, et al. Application of hybrid artificial bee colony algorithm in mixed assembly lines sequencing[J]. Computer Integrated Manufacturing Systems, 2014, 20(1): 121-127.
20 YED Y, CHENZ J. A new approach to minimum attribute reduction based on discrete artificial bee colony[J]. Soft Computing, 2015, 19(7): 1893-1903.DOI:10.1007/s00500-014-1371-0
21 THAMMANOA, PHU-ANGA. A hybrid artificial bee colony algorithm with local search for flexible job-shop scheduling problem[J]. Procedia Computer Science, 2013,20: 96-101. DOI:10.1016/j.procs.2013.09.245
22 SINGHALP K, NARESHR, SHARMAV. A novel strategy-based hybrid binary artificial bee colony algorithm for unit commitment problem[J]. Arabian Journal for Science Engineering, 2015, 40(5): 1455-1469. DOI:10.1007/s13369-015-1610-4
23 SUNY H, DINGY Y, WUT T. Improved binary artificial bee colony algorithm for dynamic image clustering[J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2017, 37(5): 19-24.DOI:10.14132/j.cnki.1673-5439.2017.05.004
24 ZHANGX, ZHANGX. A binary artificial bee colony algorithm for constructing spanning trees in vehicular ad hoc networks[J]. Ad Hoc Networks, 2017, 58: 198-204. DOI:10.1016/j.adhoc.2016.07.001
25 PANQ K,TASGETIRENM F,SUGANTHANP N, et al. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J]. Information Sciences, 2011,181(12):2455-2468. DOI:10.1016/j.ins.2009.12.025
26 HEY C, XIEH R, WONGT L, et al. A novel binary artificial bee colony algorithm for the set-union knapsack problem[J]. Future Generation Computer Systems, 2018, 78(Part1): 77-86. DOI:10.1016/j.future.2017.05.044
[1] 林耿. 一种求解厌恶型p-中位问题的混合进化算法[J]. 浙江大学学报（理学版）, 2018, 45(1): 29-36,43.
[2] 林耿, 关健. 自适应memetic算法求解集合覆盖问题[J]. 浙江大学学报（理学版）, 2016, 43(2): 168-174.