检索结果-内蒙古大学图书馆

工程数学学报 2007年第3期24卷 401-413页

作者：夏勇中国科学院数学与系统科学研究院计算数学所

二次指派问题是组合优化领域最大的挑战之一。下界技术在精确求解该类离散最小化问题中起关键性作用。本文中我们改进了二次指派问题的Gilmore-Lawler界并且得到了一些新的有前景的下界。我们还提出了一个实际效果很好的模糊下界,由此... 详细信息

二次指派问题是组合优化领域最大的挑战之一。下界技术在精确求解该类离散最小化问题中起关键性作用。本文中我们改进了二次指派问题的Gilmore-Lawler界并且得到了一些新的有前景的下界。我们还提出了一个实际效果很好的模糊下界,由此引入了一个公开问题:什么时候该模糊下界是真实下界。

关键词：二次指派问题下界线性规划 Lagrangian松弛 Lagrangian分解

来源：评论

学校读者我要写书评

暂无评论

二次指派问题的理论与算法

二次指派问题的理论与算法

引用

作者：夏勇中国科学院数学与系统科学研究院

学位级别：博士

二次指派问题(Quadratic Assignment Problem，简称QAP)自1957年问世以来就一直是国际研究热点之一，广为世界各地的数学家、计算机科学家、运筹学者以及工程设计师所关注。一方面是因为它的实际和理论的重要性，另一方面是由于它的计... 详细信息

二次指派问题(Quadratic Assignment Problem，简称QAP)自1957年问世以来就一直是国际研究热点之一，广为世界各地的数学家、计算机科学家、运筹学者以及工程设计师所关注。一方面是因为它的实际和理论的重要性，另一方面是由于它的计算复杂性，它是组合优化领域最困难的问题之一，不仅本身是NP-难问题，而且求一个∈近似解也是NP-难的。\n 本文在扼要综述了二次指派问题理论和算法各研究分支的结果之上分别作出了多项贡献。\n 第二章我们完善了置换方阵直接消去分解的结构分析，为后继工作提供了理论工具。我们还提出了平移消去分解。\n 第三章我们提出了二次指派问题的两个新线性化XYL1(A，B)和XYL2(A，B)，它们都是当时规模最小的线性化。然后我们基于置换方阵的直接消去分解又提出了两个新的更小规模的线性化，SL1(A，B)和SL2(A,B)，从而回答了“Kaufman-Broeckx线性化是否是二次指派问题规模最小的线性化”这个公开问题。最后，我们还提出了一种新的中等规模的线性化XL(A，B)。\n 第四章我们改进了二次指派问题的很多下界，提出了一些新颖的下界。在线性规划下界部分，松弛我们的线性化XYL2(A，B)得到线性规划下界RXYL2(A，B)，我们证明了它不弱于经典的Gilmore-Lawler下界GLB(A，B)，且在一定的假定下我们证明了RXYL2(A，B)严格大于GLB(A，B)。我们证明了判断是否GLB(A，B，C)=QAP(A，B，C)这一NP-完全问题的计算复杂度最多是O(nk+3)，k是GLB(A，B，C)的最优顶点解的个数。最后我们讨论了线性化XYL2(A，B)的Lagrangian松弛下界和Lagrangian分解下界。在特征值下界部分，我们给出了改进原始特征值下界的方法，对投影特征值下界，我们也给出了两种改进方法。此外，我们提出了一个Gilmore-Lawler类型的投影特征值下界，它不弱于投影特征值下界，而且计算简单，复杂度O(n3)。我们改善了信赖域型下界TB(A，B，C)。我们建立了基于直接消去分解的投影信赖域型下界TRB(A，B，C)，证明了它至少不比在某个二次指派问题的等价变形下的信赖域型下界弱。随后，我们对该投影信赖域型问题添加了一个凹二次约束，它来自我们对置换方阵直接消去分解的精细结构分析。我们证明了添加了这样一个凹二次约束之后的问题仍然具有强对偶性，其对偶为一半正定规划，我们同时给出了该问题的最优解形式，而且其计算复杂度只有O(n3)。原来的约束是半径为(√n-1)的(n-1)2维超球的一个子集合，我们添加的这个约束相当于从原来的那个约束集合内再挖去一个半径为(√n-2)的开球。因此我们在不改变计算量的前提下极大地改进了投影信赖域型下界。随后我们利用上一小节改进投影特征值下界的技巧进一步改进了TRB(A，B，C)。在二次规划下界部分，我们先讨论了如何改进简单的二次规划下界。我们给出了基于改进的投影特征值下界的技巧的两个凸二次规划下界，证明其中之一不比改进的投影特征值下界弱，且在一定假定下要严格强。我们提出了基于改进的投影信赖域下界TRB(A，B，C)的凸二次规划下界QTRB(A,B，C)，证明了它不比TRB(A,B，C)弱，而且在一定假定下要严格强。进一步我们基于前一节改进TRB(A,B，C)的技巧也得到了两个凸二次规划下界，并证明了一定的紧性结果。在求解这类坏条件数的凸二次规划方面，我们利用二维子空间搜索改进了传统的Frank-Wolfe算法效率，取得了良好的计算效果。最后在半正定规划下界方而，我们给出了两个新的含O(n4)变量的半正定规划下界，证明了它们不比相应的二次规划下界弱。我们首次提出了简单的只含O(n2)个变量的半正定规划，在介绍了文献最新的也是更强的含O(n2)个变量的半正定规划之后，我们给出了基于直接消去分解的相应的半正定规划下界，基于此我们还提出了一个很强的线性规划下界。最后，我们建立了一个含O(n3)个变量的半正定规划，我们证明了它不比最新文献中的O(n2)变量的半正定规划弱。我们也证明了它不比相应的二次规划下界弱。最后我们也利用直接消去分解技术给出了相应的半正定规划下界和相应的理论结果。\n 第五六七章是算法方面。我们改善了传统的割平面算法效率，讨论了还不成熟的两边夹算法。我们提出了非单调局部搜索算法。基于我们的线性化XYL1(A，B)极大地改善了启发式割平面算法的效率，给出了相应的数值结果，并进一步结合禁忌搜索提高了计算效率。我们对一般的带线性约束的非线性0-1优化问题提出了新的连续化方法，它被成功地应用到二次指派问题上，数值结果显示了我们策略的优越性，此外我们还讨论了二次指派问题的舍入技巧。对比新的连续化方法和蚂蚁

关键词：二次指派问题线性规划半正定规划特征值局部搜索超启发式算法

来源：评论

学校读者我要写书评

暂无评论

求解二次指派问题的混合演化策略(英文)

引用

华南理工大学学报（自然科学版） 2000年第1期28卷 38-41页

作者：彭宏梁文静欧永斌华南理工大学计算机工程与科学系广东广州510640

本文给出了一种求解二次指派问题的混合演化策略.该方法的主要优点是优化效果好,运算量小,通用性强.模拟计算的结果,验证了该方法的有效性,它可用于求解其它组合优化问题.

关键词：二次指派问题演化策略组合优化模拟计算

来源：评论

学校读者我要写书评

暂无评论

二次指派问题的蚁群算法研究

引用

铁道运输与经济 2005年第5期27卷 68-70页

作者：尹晓峰刘春煌铁道科学研究院电子计算技术研究所北京100081

蚁群算法是受自然界蚂蚁觅食过程中,基于信息素的最短路径搜索食物行为启发,提出的一种智能优化算法。在采用蚁群算法求解二次指派问题中,针对蚁群算法存在的过早收敛问题,使用距离及流量作为启发式信息并引入局部优化,对蚁群算法的结... 详细信息

蚁群算法是受自然界蚂蚁觅食过程中,基于信息素的最短路径搜索食物行为启发,提出的一种智能优化算法。在采用蚁群算法求解二次指派问题中,针对蚁群算法存在的过早收敛问题,使用距离及流量作为启发式信息并引入局部优化,对蚁群算法的结果加以改进,计算机仿真结果表明,蚁群算法对求解二次指派问题有较好的效果。

关键词：二次指派问题蚁群算法信息素过早收敛问题使用距离流量工作原理混合算法智能优化算法

来源：评论

学校读者我要写书评

暂无评论

Actor-critic框架下的二次指派问题求解方法

引用

中国科学院大学学报（中英文） 2024年第2期41卷 275-284页

作者：李雪源韩丛英中国科学院大学数学科学学院北京100049

二次指派问题(QAP)属于NP-hard组合优化问题,在现实生活中有着广泛应用。目前相对成熟的启发式算法通常以问题为导向来设计定制化算法,缺乏迁移泛化能力。为提供一个统一的QAP求解策略,将QAP问题的流量矩阵及距离矩阵抽象成两个无向完... 详细信息

二次指派问题(QAP)属于NP-hard组合优化问题,在现实生活中有着广泛应用。目前相对成熟的启发式算法通常以问题为导向来设计定制化算法,缺乏迁移泛化能力。为提供一个统一的QAP求解策略,将QAP问题的流量矩阵及距离矩阵抽象成两个无向完全图并构造相应的关联图,从而将设施和地点的指派任务转化为关联图上的节点选择任务,基于actor-critic框架,提出一种全新的求解算法ACQAP。首先,利用多头注意力机制构造策略网络,处理来自图卷积神经网络的节点表征向量;然后,通过actor-critic算法预测每个节点被作为最优节点输出的概率;最后,依据该概率在可行时间内输出满足目标奖励函数的动作决策序列。该算法摆脱人工设计,且适用于不同规模的输入,更加灵活可靠。实验结果表明,在QAPLIB实例上,本算法在精度媲美传统启发式算法的前提下,迁移泛化能力更强;同时相对于NGM等基于学习的算法,求解的指派费用与最优解之间的偏差最小,且在大部分实例中,偏差均小于20%。

关键词：二次指派问题图卷积神经网络深度强化学习多头注意力机制 actor-critic算法

来源：评论

学校读者我要写书评

暂无评论

求解二次指派问题的最优迭代最大最小蚂蚁算法

引用

计算机应用 2014年第1期34卷 199-203页

作者：牟廉明戴锡笠李坤贺灵悦内江师范学院数学与信息科学学院四川内江641100 四川省高等学校数值仿真重点实验室(内江师范学院) 四川内江641100

为提高二次指派问题的求解质量,设计了一个有效的最大最小蚂蚁求解算法。首先,运用最优迭代思想,让每只蚂蚁从当前最优路径中随机地选择位置及其对应的任务作为下一轮迭代的初始值,增强每轮搜索的有效性;其次,采用加入新任务后目标值的... 详细信息

为提高二次指派问题的求解质量,设计了一个有效的最大最小蚂蚁求解算法。首先,运用最优迭代思想,让每只蚂蚁从当前最优路径中随机地选择位置及其对应的任务作为下一轮迭代的初始值,增强每轮搜索的有效性;其次,采用加入新任务后目标值的增量作为启发式因子来引导状态转移,增加每步搜索的目的性;然后,应用多精英策略来进行信息素更新,增加解的多样性;并设计有效的双重变异技术来提高解的质量,提高算法的收敛速度;最后,应用QAPLIB数据集进行了大量实验,结果表明:该算法在二次指派问题的求解质量和稳定性上显著优于其他算法。

关键词：二次指派问题最优迭代最大最小蚂蚁算法双重变异启发因子

来源：评论

学校读者我要写书评

暂无评论

强化最优和最差狼的郊狼优化算法及其二次指派问题应用

引用

计算机应用 2019年第10期39卷 2985-2991页

作者：张新明王豆豆陈海燕毛文涛窦智刘尚旺河南师范大学计算机与信息工程学院河南新乡453007 湖北省肿瘤医院妇瘤科武汉430079

针对郊狼优化算法(COA)优化性能不足的问题,提出一种强化最优和最差狼的COA(BWCOA)方法。首先,对于组内最差郊狼的成长,在最优郊狼引导的基础上引入全局最优郊狼引导操作,以提高最差郊狼的社会适应能力(局部搜索能力);然后,在组内最优... 详细信息

针对郊狼优化算法(COA)优化性能不足的问题,提出一种强化最优和最差狼的COA(BWCOA)方法。首先,对于组内最差郊狼的成长,在最优郊狼引导的基础上引入全局最优郊狼引导操作,以提高最差郊狼的社会适应能力(局部搜索能力);然后,在组内最优郊狼的成长过程中嵌入一种随机扰动操作,即以郊狼之间的随机扰动促进成长,发挥组内每个郊狼的能动性,提高种群的多样性进而强化全局搜索能力;最后,组内其他郊狼的成长方式保持不变。将BWCOA运用到复杂函数优化和以医院科室布局为例的二次指派问题(QAP)中。在CEC-2014复杂函数上的实验结果表明,与COA以及其他最先进的算法相比,BWCOA获得1.63的平均均值排名和Friedman检验中1.68的秩均值,均排名第一。另外,在6组QAP上的实验结果表明,BWCOA获得了5次均值最优的结果。实验结果均表明BWCOA具有更强的竞争性。

关键词：智能优化算法郊狼优化算法全局最优二次指派问题医院科室定位

来源：评论

学校读者我要写书评

暂无评论

对具有二部图特点的二次指派问题的研究

引用

制造业自动化 2021年第2期43卷 63-70页

作者：张长泽李引珍尹胜男金启明兰州交通大学交通运输学院兰州730070

为求解具有二部图特点的二次指派问题,提出一种基于熵收敛的改进蚁群算法(EC-IACA)。首先,为提高初始种群解的质量,提出了基于假定应急物流中心的贪婪思想与设施交互次数相结合的初始化方法,并用当前最优解来设置初始值,较少搜索的盲目... 详细信息

为求解具有二部图特点的二次指派问题,提出一种基于熵收敛的改进蚁群算法(EC-IACA)。首先,为提高初始种群解的质量,提出了基于假定应急物流中心的贪婪思想与设施交互次数相结合的初始化方法,并用当前最优解来设置初始值,较少搜索的盲目性;其次,使用一种伪随机比例规则,引入先验概率来引导状态转移,用已得到的部分解和未遍历完指派集的状态对启发信息进行动态改进,以此增强算法的收敛速度;然后,应用自适应策略对信息素进行更新来避免早熟,运用2-opt邻域结构对历史最优解进行局部搜索,以此提高算法的局部搜索性能;最后,在算法后期引入信息素平滑机制来增强解的多样性,并引入信息熵来分析算法的收敛性。仿真计算实验和算法比较验证了EC-IACA的优化性能。

关键词：二次指派问题改进蚁群算法动态启发信息信息素平滑机制信息熵

来源：评论

学校读者我要写书评

暂无评论

求解二次指派问题松弛问题的Lp范数正则化算法

求解二次指派问题松弛问题的Lp范数正则化算法

引用

作者： APPIAH-KUBI FRANK KWAME 北京工业大学

学位级别：硕士

因二次指派问题是NP-难的，本文利用L0范数稀疏性及双随机矩阵的矩阵性质，提出了基于双随机矩阵集的二次指派问题松弛问题。然而，带L0离散约束的双随机锥优化问题依旧是NP-难的，仍很难直接求解。因此将双随机锥模型中L0约束惩罚到目... 详细信息

因二次指派问题是NP-难的，本文利用L0范数稀疏性及双随机矩阵的矩阵性质，提出了基于双随机矩阵集的二次指派问题松弛问题。然而，带L0离散约束的双随机锥优化问题依旧是NP-难的，仍很难直接求解。因此将双随机锥模型中L0约束惩罚到目标函数上，利用Lp范数来近似L0范数项，并设计一种求解相应的二次指派松弛问题的快速求解方法。在正则参数足够大的情况下，本研究所提出的Lp正则模型的最优解与L0松弛问题相同。本研究撷取QAPLIB数据库中的数据，采取加速的邻近梯度法对所提出的Lp正则松弛模型进行求解。数值结果表明，本文提出的Lp正则松弛模型为原二次指派问题提供了一个更接近的下界。

关键词：二次指派问题松弛问题 Lp-范数正则化置换矩阵加速邻近梯度法

来源：评论

学校读者我要写书评

暂无评论

求解二次指派及相关问题的一个新的连续化方法(英文)

求解二次指派及相关问题的一个新的连续化方法(英文)

引用

中国运筹学会第八届学术交流会

作者：夏勇中国科学院数学与系统科学研究院科学与工程计算数学所

针对带线性约束的非线性0-1规划本文提出了一种新的光滑化算法并用于求解二次指派问题。有限的数值算例表明该方法比现有的对数光滑化算法能在更短的时间内找到高质量的解。

关键词：连续化办法非线性0-1规划光滑化方法 Frank-Wolfe算法二次指派问题

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：