《计算机应用研究》|Application Research of Computers

求解0-1背包问题的混合蝙蝠算法

Hybrid bat algorithm for solving 0-1 knapsack problem

免费全文下载 (已被下载 次)  
获取PDF全文
作者 万晓琼,张惠珍
机构 上海理工大学 管理学院,上海 200093
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2019)09-004-2579-05
DOI 10.19734/j.issn.1001-3695.2018.01.0137
摘要 针对基本蝙蝠算法易陷入局部最优、收敛速度慢等缺点,对其进行优化研究。基于0-1背包问题的具体特征,在基本蝙蝠算法原有概念和框架的基础上,引入遗传算法中的交叉机制以及反置算子建立全新的位置转移方式和局部搜索规则;加入贪心策略进行解的可行化和充分利用,增强局部搜索能力,加快算法收敛速度,构建全新的混合蝙蝠算法。将混合蝙蝠算法应用于两组0-1背包算例,仿真实验结果优于自适应元胞粒子群算法、基本蝙蝠算法和贪心二进制蝙蝠算法。结果验证了该混合算法求解0-1背包问题的可行性和有效性。
关键词 0-1背包问题; 蝙蝠算法; 遗传算法; 反置算子; 贪心策略
基金项目 国家自然科学基金资助项目(71401106)
国家教育部人文社科规划基金资助项目(16YJA630037)
本文URL http://www.arocmag.com/article/01-2019-09-004.html
英文标题 Hybrid bat algorithm for solving 0-1 knapsack problem
作者英文名 Wan Xiaoqiong, Zhang Huizhen
机构英文名 School of Management,University of Shanghai for Science & Technology,Shanghai 200093,China
英文摘要 In order to overcome the shortcomings of the basic bat algorithm, such as easy to fall into local optimum and slow convergence speed, the optimization study was carried out. This paper proposed a new hybrid bat algorithm based on the original features, framework of the basic bat algorithm and specific characteristics of the 0-1 knapsack problem. The hybrid algorithm introduced the crossover mechanism of the genetic algorithm and the inverse operator to construct a brand-new location transfer method and local search rule. The greedy strategy was added to make the solution feasible and fully utilized, enhancing the local search ability and speeding up the convergence. This hybrid bat algorithm was applied to two sets of 0-1 knapsack cases. The simulation results exceeded adaptive cellular particle swarm optimization, basic bat algorithm and greedy binary bat algorithm. The results verify the feasibility and effectiveness of the hybrid algorithm in solving 0-1 knapsack problem.
英文关键词 0-1 knapsack problem; bat algorithm; genetic algorithm; inverse operator; greedy strategy
参考文献 查看稿件参考文献
 
收稿日期 2018/1/27
修回日期 2018/4/12
页码 2579-2583
中图分类号 TP301.6
文献标志码 A