计算机工程与应用 ›› 2018, Vol. 54 ›› Issue (22): 28-34.DOI: 10.3778/j.issn.1002-8331.1710-0079

• 理论与研发 • 上一篇    下一篇

求解无容量设施选址问题的混合蝙蝠算法

刘春苗,张惠珍   

  1. 上海理工大学 管理学院,上海 200093
  • 出版日期:2018-11-15 发布日期:2018-11-13

Hybrid bat algorithm for un-capacitated facility location problem

LIU Chunmiao, ZHANG Huizhen   

  1. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, China
  • Online:2018-11-15 Published:2018-11-13

摘要: 无容量设施选址(Un-capacitated Facility Location,UFL)问题是可以运用于不同领域的经典优化难题。蝙蝠算法(Bat Algorithm,BA)是一种新的群智能优化算法,目前还未被应用到无容量设施选址问题的求解中。针对蝙蝠算法易陷入局部最优、收敛精度低、后期收敛速度慢的缺点,并结合无容量设施选址问题的具体特征,将三种局部搜索策略、和声搜索机制与基本蝙蝠算法相结合,使用一种新的随机游走法则公式改善蝙蝠的搜索能力,设计了求解无容量设施选址问题的混合蝙蝠算法。通过实例测试将混合蝙蝠算法与其他算法进行比较,验证了该算法求解无容量设施选址问题的有效性与可行性。

关键词: 无容量设施选址问题, 蝙蝠算法, 局部搜索, 和声搜索, 游走法则

Abstract: The Un-capacitated Facility Location(UFL) problem is a classical combinatorial optimization hard problem and has been applied in various fields. Bat Algorithm(BA) is a new intelligent optimization algorithm, which has not yet been applied to un-capacitated facility location problem. Based on the mathematical model and specific features of the un-capacitated facility location problem, combined with three local search strategies and harmony search mechanism, a new search equation is proposed in the best solution of current iteration, a Hybrid Bat Algorithm(HBA) is designed for solving it. Furthermore, the numerical experiment is implemented by using HBA to solve a testing example, and its solution is compared with the one obtained with the state-of-the-art algorithm. The results show that HBA can effectively and feasibly solve UFL problem.

Key words: un-capacitated facility location problem, bat algorithm, local search, harmony search, migration rule