强化学习求解组合最优化问题的研究综述

组合最优化问题(COP)的求解方法已经渗透到人工智能、运筹学等众多领域。随着数据规模的不断增大、问题更新速度的变快,运用传统方法求解COP问题在速度、精度、泛化能力等方面受到很大冲击。近年来,强化学习(RL)在无人驾驶、工业自动化等领域的广泛应用,显示出强大的决策力和学习能力,故而诸多研究者尝试使用RL求解COP问题,为求解此类问题提供了一种全新的方法。首先简要梳理常见的COP问题及其RL的基本原理;其次阐述RL求解COP问题的难点,分析RL应用于组合最优化(CO)领域的优势,对RL与COP问题结合的原理进行研究;然后总结近年来采用RL求解COP问题的理论方法和应用研究,对各类代表性研究所解决COP问题的关键要点、算法逻辑、优化效果进行对比分析,以突出RL模型的优越性,并对不同方法的局限性及其使用场景进行归纳总结;最后提出了四个RL求解COP问题的潜在研究方向。

剖分拟阵约束下求解下模函数最大值问题的一种贪婪算法

给出了求解剖分拟阵约束下,下模函数最大值问题的一种新的近似算法,这一算法是改进的贪婪算法,即将局部搜索法与贪婪算法相结合,使其整体具有更好的性能保证。同时从理论上证明了这一算法的可靠性。最后通过具体算例验证了算法的有效性。

模糊遗传算法在机器调动问题运用

单机器调度问题是研究工件在多道工序进行加工的加工活动排序的组合最优化问题．由于调度问题中绝大多数属于ＮＰ－难类问题，不存在有效的最优求解算法．针对用智能优化算法—遗传算法求解单机器调度问题中交叉率和变异率难以确定的问题，设计了一种模糊算法以便自动确定交叉率和变异率．通过数值实验，嵌入模糊规则的遗传算法比简单的遗传算法要好，说明在实际生产中，此算法具有强大的发展前途．

一种求解CVRP的动态图转换模型

带容量的车辆路径问题是组合最优化问题中的经典问题,多年以来一直被反复研究。最近,Transformer已经成为解决车辆路径问题的主流深度学习架构。然而,由于一个实例在模型不同构造步骤中会发生改变,相应的节点特征也需要更新,传统位置编码方法不适用于提取动态优化问题的位置信息。因此,现有方法在提高学习效率方面效果较差。以最小化路径长度为目标,提出一种动态图转换模型(DGTM)和动态位置编码(DPE)方法,并使用一种双重损失REINFORCE算法训练DGTM模型。此外,强化学习、图神经网络和Transformer架构相结合,提高了模型的训练效率,增强了神经网络对带约束路径问题信息的表征能力。实验结果表明,DGTM模型在此问题上的优化效果超越了目前基于深度强化学习的方法和部分传统算法,整体性能优于专业求解器的,且具有较好的泛化性能,为求解图上组合最优化问题提供了一种有效方法。

基于遗传算法的布局求解法

在分析布局问题的基础上 ,对编码方式、交叉操作等做了改进 ,提出一种基于遗传算法的布局求解方法 .计算结果表明 ,算法具有良好的全局搜索能力和较快的收敛速度 .

非可靠性测试条件下复杂系统多故障定位方法

针对复杂系统多故障并存且实际测试中存在误警和漏检等特点,提出非可靠性测试条件下多故障定位问题的解决方法。以寻找后验概率最大的故障假设为目标,引入贝叶斯理论并结合系统的检测、误警相关矩阵,将原问题转化为一个组合最优化问题。采用改进的偏转次梯度优化算法(modified reflection subgradient optimization algorithm,简称MRSOA)求解优化问题的拉格朗日对偶,获得故障定位结果。对某型雷达发射机在非可靠性测试情况下的多故障定位结果表明,该方法具有较高的定位效率和定位准确度。

遗传算法的不充分性及其改进方法

遗传算法 (GA)是基于自然淘汰的遗传机制的搜索算法 ,近年来的研究 ,验证了GA较之其它地搜索算法更能有效地处理困难地多峰函数寻优和极其复杂的机器学习 ,生产调度等组合最优化问题。但是 ,所谓的GA hardProblems、欺骗函数问题 ,难度极大的三维空间寻优问题、技能模糊控制问题等使GA受到了严峻地挑战。因此 ,研究未来的GA将如何解决上述课题有着相当重要地意义。

蚁群算法在计算机自动组卷中的应用研究

分析并研究了当前自动组卷算法的优点与不足;提出了自动组卷问题数学模型;设计了一种基于蚁群算法的计算机自动组卷方法;针对中考地理考试进行了计算机自动组卷算法模拟实验,实验表明该算法能够在多项式时间内产生一个近似最优解。

顶点覆盖约束下的同类机排序算法研究

给定m台同类机和n个工件,其中第j台机器的速度为sj,第i个工件的加工时间为pi并且在第j台机器上的负载为pi sj.构造一个顶点赋权无向图G=(V,E;w),其中图G的n个顶点代表这n个工件,顶点权重代表相应工件的加工时间.本文研究顶点覆盖约束下的同类机排序问题.该问题是两个组合最优化问题的组合问题,其目标为首先确定图G的一个顶点覆盖,即图的一个顶点子集,使得图中每一条边都至少存在一个顶点属于该子集;然后把这个子集所代表的相应工件集放到m台同类机上加工,使得最大完工时间最小.该问题是NPhard的.本文基于分层算法和LSPT算法设计一个(2+(m−1)·8m/Σ_(j=1^(m)8j))-近似算法,当所有机器的速度都相差不大时,该算法的近似效果较好.

’94MCM我校参赛队又获佳绩

’９４ＭＣＭ我校参赛队又获佳绩’９４美国大学生数学模型竞赛（ＭＣＭ）于今年２月１８日一２０日举行，我校数学系选派了两个队参加。参赛选手经过紧张的赛前Ｄｌｌ练和竞赛时顽强地拼搏，又获得了好成绩．以沙丹老师为教练，由张亮、仇磷、何红春组成的参赛队，获得了...

扫雷高手的百万大奖之梦

当你在网上通过电子商务系统把一笔巨款转入预期的账户时,你一定是心安神泰,因为你相信这种系统是安全可靠的。当你被告知,它竟是建立在一个尚未证明的数学猜想上时,你或许以为这是胡扯。然而很不幸,这是事实。这个猜想就是:P≠NP。一个猜想。

计算机通讯网络中的施泰纳树问题

经典的施泰纳（Steiner）树问题，它又被称为最小连接树问题，被定义为：在一个度量空间中，对给定的一个点集合，找出相互连接所有给定点的最短网络。这样的网络被称之为在给定集合上的施泰纳树。施泰纳树问题是最著名的组合最优化问题之一，它具有悠久的研究历史，可以认为它是费马问题的推广。