求解增量二分图优化问题的动态规划驱动的局部搜索算法

A dynamic programming-based local search algorithm for solving the dynamic bipartite drawing problem

增量二分图优化问题(dynamic bipartite drawing problem,DBDP)是一个具有NP难度的组合优化问题,该问题在实际生产生活中有着广泛的应用.本文提出了一种新的动态规划驱动的局部搜索(DP-LS)算法来求解该问题.不同于文献中求解该问题和该类问题的所有启发式算法的邻域搜索方式(即每次邻域操作只对一个或两个节点进行插入或交换动作),本文提出的动态规划驱动的局部搜索算法能从邻域结构中挑选出并执行多个独立的邻域动作,大大提高了邻域搜索的效率.DP-LS算法从一个随机初始解出发,迭代地利用基于动态规划的局部搜索算法来寻找局部最优解,同时结合扰动机制跳出局部极值陷阱实现全局搜索.本文提出的增量评估方法能够快速评估基于插入和交换的邻域动作,可以大大提高算法的搜索效率.本文针对1120个公共算例进行了计算实验并同文献中已有算法(包括通用求解器Gurobi)进行对比,表明了所提出的动态规划驱动的局部搜索算法在解的优度和计算效率两方面的有效性.此外,通过对比实验表明了DP-LS算法中动态规划机制的有效性(提升近十倍的搜索效率).值得注意的是,本文提出的基于动态规划的局部搜索算法不仅能够用于求解DBDP问题,也能作为一种通用的启发式算法来求解其他组合优化问题,尤其是排序类优化问题.

The dynamic bipartite drawing problem is a challenging NP-hard combinatorial optimization problem with numerous applications. In this study, we propose a dynamic programming-based local search(DP-LS)algorithm for solving it. Unlike previous metaheuristics reported in the literature, which move just one vertex(or two vertices) at each neighborhood iteration, the proposed DP-LS algorithm selects and performs multiple independent neighborhood moves at the same time to enhance the search efficiency. Generally, starting from a random initial solution, DP-LS iteratively explores the search space by integrating the DP-LS to locate local optima, and then uses a perturbation procedure to escape from the local optima. In addition, the proposed incremental evaluation techniques of the insert and swap moves enhance the efficiency of the neighborhood evaluation.Extensive computational experiments on two sets of 1120 problem instances indicate that the proposed DP-LS is highly competitive with the best-performing algorithms(including the general purpose solver Gurobi) in terms of both solution quality and computational efficiency. We analyzed the dynamic programming mechanism in the proposed DP-LS algorithm to determine its effectiveness(increasing the search efficiency tens of times). Not only can the proposed DP-LS algorithm be used to solve the DBDP, it can also be used as a general methodology for solving other combinatorial optimization problems, especially permutation optimization problems.