| 求解广义分配问题的拉格朗日蝙蝠算法 |
| |
| 引用本文： | 万晓琼,张惠珍,赵玉苹.求解广义分配问题的拉格朗日蝙蝠算法[J].上海理工大学学报,2019,41(2):167-173. |
| |
| 作者姓名： | 万晓琼 张惠珍 赵玉苹 |
| |
| 作者单位： | 上海理工大学 管理学院, 上海 200093,上海理工大学 管理学院, 上海 200093,国网上海市电力公司 物资公司, 上海 200235 |
| |
| 基金项目： | 国家自然科学基金资助项目（71401106）；教育部人文社科规划基金资助项目（16YJA630037） |
| |
| 摘 要： | 基于广义分配问题(GAP)自身的特点,将拉格朗日松弛算法(LR)和蝙蝠算法(BA)相结合,提出了一种高效的拉格朗日蝙蝠算法(LR-DBA)。首先,基于GAP的数学模型,在BA算法的基本框架上,重新定义了蝙蝠速度、位置以及局部更新公式,得出全新的求解GAP的离散蝙蝠算法(DBA)。其次,将其与LR相结合,设计出求解GAP的LR-DBA算法。最后,经过大量算例测试表明,对比DBA算法,LR-DBA混合算法在求解GAP时具有明显优势。
|
| 关 键 词： | 广义分配问题 蝙蝠算法 拉格朗日松弛算法 |
| 收稿时间： | 2018/1/24 0:00:00 |
Lagrangian Bat Algorithm for Solving Generalized Assignment Problems |
| |
| WAN Xiaoqiong,ZHANG Huizhen and ZHAO Yuping.Lagrangian Bat Algorithm for Solving Generalized Assignment Problems[J].Journal of University of Shanghai For Science and Technology,2019,41(2):167-173. |
| |
| Authors: | WAN Xiaoqiong ZHANG Huizhen and ZHAO Yuping |
| |
| Institution: | Business School, University of Shanghai for Science and Technology, Shanghai 200093, China,Business School, University of Shanghai for Science and Technology, Shanghai 200093, China and Procurement Company, State Grid Shanghai, Shanghai 200235, China |
| |
| Abstract: | Generalized assignment problem (GAP) is a classic combinatorial optimization problem that has been proved to be NP-hard problem. For solving the GAP problem, combining the bat algorithm (BA) with the Lagrangian relaxation algorithm (LR), an efficient Lagrangian bat algorithm (LR-DBA) was proposed based on the characteristics of the GAP problem. The DBA takes BA as the basic framework and redefines the formulas of velocity, position and local updating. It was then combined with the LR algorithm to form the LR-DBA hybrid algorithm. A large number of examples show that compared with the DBA algorithm, the LR-DBA algorithm has obvious advantages in solving the GAP problem. |
| |
| Keywords: | generalized assignment problem bat algorithm Lagrangian relaxation algorithm |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《上海理工大学学报》浏览原始摘要信息 |
| 点击此处可从《上海理工大学学报》下载免费的PDF全文 |
|
