期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息
共找到1篇文章
< 1 >
每页显示 20 50 100
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
显示方式：
求解增量二分图优化问题的动态规划驱动的局部搜索算法 被引量：2
1
作者 彭博 卢晨贝 +3 位作者 赵岳虎 苏宙行 廖毅 吕志鹏 《中国科学：信息科学》 CSCD 北大核心 2021年第4期582-601,共20页
增量二分图优化问题(dynamic bipartite drawing problem,DBDP)是一个具有NP难度的组合优化问题,该问题在实际生产生活中有着广泛的应用.本文提出了一种新的动态规划驱动的局部搜索(DP-LS)算法来求解该问题.不同于文献中求解该问题和该... 增量二分图优化问题(dynamic bipartite drawing problem,DBDP)是一个具有NP难度的组合优化问题,该问题在实际生产生活中有着广泛的应用.本文提出了一种新的动态规划驱动的局部搜索(DP-LS)算法来求解该问题.不同于文献中求解该问题和该类问题的所有启发式算法的邻域搜索方式(即每次邻域操作只对一个或两个节点进行插入或交换动作),本文提出的动态规划驱动的局部搜索算法能从邻域结构中挑选出并执行多个独立的邻域动作,大大提高了邻域搜索的效率.DP-LS算法从一个随机初始解出发,迭代地利用基于动态规划的局部搜索算法来寻找局部最优解,同时结合扰动机制跳出局部极值陷阱实现全局搜索.本文提出的增量评估方法能够快速评估基于插入和交换的邻域动作,可以大大提高算法的搜索效率.本文针对1120个公共算例进行了计算实验并同文献中已有算法(包括通用求解器Gurobi)进行对比,表明了所提出的动态规划驱动的局部搜索算法在解的优度和计算效率两方面的有效性.此外,通过对比实验表明了DP-LS算法中动态规划机制的有效性(提升近十倍的搜索效率).值得注意的是,本文提出的基于动态规划的局部搜索算法不仅能够用于求解DBDP问题,也能作为一种通用的启发式算法来求解其他组合优化问题,尤其是排序类优化问题. 展开更多
关键词 增量二分图优化问题 动态规划 局部搜索 增量评估机制
原文传递
已选择0条
导出题录 引用分析
参考文献
引证文献
 统计分析
检索结果
已选文献
上一页 1 下一页 到第 页
使用帮助 返回顶部