求解最大二等分问题的混合二进制人工蜂群算法  

A hybrid binary artificial bee colony algorithm for the max-bisection problem

作　　者：林耿[1] LIN Geng(College of Mathematics and Data Science,Minjiang University,Fuzhou 350108,China)

机构地区：[1]闽江学院数学与数据科学学院

出　　处：《浙江大学学报（理学版）》2019年第5期556-564,共9页Journal of Zhejiang University（Science Edition）

基　　金：国家自然科学基金资助项目(11301255);福建省自然科学基金资助项目(2017J01076);福建省高校新世纪优秀人才支持计划项目

摘　　要：为更好地解决最大二等分问题,提出了一种求解该问题的混合二进制人工蜂群算法。首先,针对传统人工蜂群算法不能解决离散问题的缺陷,根据最大二等分问题的特点,重新设计了蜂群的食物源更新方法,新产生的食物源既继承了先前找到的高质量解的优良结构,又具有良好的多样性。其次,采用填充函数算法对新产生的食物源进行进一步优化,有效提高了人工蜂群算法的局部搜索能力。最后,通过比较混合二进制人工蜂群算法和其他现有算法对不同规模标准测试例子的计算结果,验证了本算法的优越性。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.

关 键 词：最大二等分 填充函数 人工蜂群算法 局部搜索 

分 类 号：O224.1[理学—运筹学与控制论] TP301[理学—数学]