求解广义分配问题的拉格朗日蝙蝠算法

摘要

基于广义分配问题（GAP）自身的特点，将拉格朗日松弛算法（LR）和蝙蝠算法（BA）相结合，提出了一种高效的拉格朗日蝙蝠算法（LR-DBA）。首先，基于GAP的数学模型，在BA算法的基本框架上，重新定义了蝙蝠速度、位置以及局部更新公式，得出全新的求解GAP的离散蝙蝠算法（DBA）。其次，将其与LR相结合，设计出求解GAP的LR-DBA算法。最后，经过大量算例测试表明，对比DBA算法，LR-DBA混合算法在求解GAP时具有明显优势。%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.