奖励收集斯坦利最小树的混合拉格朗日与分散搜索算法

Hybrid Lagrange and scatter-search algorithm for prize-collecting Steiner tree problem

针对PCSTP问题,提出了HLGSS混合算法.通过拉格朗日松弛策略,将PCSTP问题转化为简单的CMST问题;然后由Volume算法求解PCSTP的拉格朗日对偶问题并获得其下界.用SS算法优化原问题的可行解,利用求解拉格朗日对偶问题过程中获得的原始-对偶信息来指导SS算法的搜索.仿真结果表明,HLGSS比SS降低了算法的搜索空间,加速了算法的收敛性.

The HLGSS is proposed for the PCSTP. The problem is transformed into an easier tractable CMST problem by using the method of Lagrange relaxation. A lower bound is obtained by solving the Lagrange dual problem and using the Volume algorithm. Then, the SS algorithm is used to optimize the feasible solutions of the PCSTP. The primal-dual information produced during solving the Lagrange-dual problem is exploited to guard the SS algorithm in the underlying procedure. The simulation results show that the proposed algorithm intensifies the search in the most promising regions of the solution space and thus speeds up the search time comparing with the SS algorithm.