组合优化问题

摘要： 近年来,深度学习为求解组合优化问题提供了新的视角。但目前已有的方法在训练时基本都存在收敛速度慢的问题,学习到的策略性能不够高。针对该问题,以经典组合优化问题中的旅行商问题(Travelling salesman problem,TSP)为例,基于Transformer的模型结构,在编码器中屏蔽已访问的城市,解码器在每一步解码时都先对整个输入节点序列重新编码,并且使用新的编码输出得到的聚合嵌入向量和上一步访问的城市对应于编码输出中的节点嵌入向量构造新的上下文向量,结合强化学习的训练方法,提出了一种新的求解旅行商问题的深度学习模型,在随机标准均匀分布数据集上较现有的主流模型有更好的表现。

摘要： 针对未设计启发式算法的组合优化问题设计统一的解决方案已成为机器学习领域的一个研究热点,目前成熟的技术主要针对静态的组合优化问题,但是对于加入动态变化的组合优化问题还没有得到充分的解决。为了解决以上问题,提出一个将多头注意力机制与分层强化学习结合来求解动态图上的旅行商问题的轻量级模型Dy4TSP。首先,用以多头注意力机制为基础的预测网络处理来自图卷积神经网络的节点表征向量输入;然后,借助分布式强化学习算法训练来快速地预估图中每个节点被输出作为最优解的可能性,使得模型在不同的可能性中全面探索问题的最优解决方案空间;最后,训练后的模型将实时地生成满足具体目标奖励函数的动作决策序列。该模型在3个组合优问题上进行了评估,实验结果表明,该模型在经典旅行商系列问题中解的质量比开源求解器LKH3高0.15~0.37个单位,明显优于带有边嵌入的图注意网络(EGATE)等最新的算法;并且在其他的动态旅行商问题中可以达到0.1~1.05的最优路径差距,结果也略胜一筹。

摘要： 本文将深度强化学习应用于二维不规则多边形的排样问题中,使用质心到轮廓距离将多边形的形状特征映射到一维向量当中,对于在随机产生的多边形中实现了1%以内的压缩损失.给定多边形零件序列,本文使用多任务的深度强化学习模型对不规则排样件的顺序以及旋转角度进行预测,得到优于标准启发式算法5%–10%的排样效果,并在足够次数的采样后得到优于优化后的遗传算法的结果,能够在最短时间内得到一个较优的初始解,具有一定的泛化能力.

摘要： 实现碳达峰、碳中和(以下简称“双碳”)目标是我国对国际社会的庄严承诺,也是推动高质量发展的内在要求。推进“双碳”目标应坚持系统观念,推动有效市场和有为政府有机结合。实现“双碳”目标对政府治理与市场机制提出了新的更高要求保障能源安全供应对政府治理与市场机制提出新的更高要求。保障我国能源安全面临多个组合优化问题,归根结底就是要在守住安全底线前提下,在绿色低碳发展与成本可负担之间建立新平衡。这需要市场机制和政府治理发挥各自优势,组合协同发力。

摘要： 蚁群算法是一种解决组合优化问题的算法,具有灵活性、稳健性等优势,而旅行商问题正是一个利用蚁群算法得以解决的经典选择优化问题。本文首先以蚁群算法为研究对象,阐述了蚁群算法的基本原理、模型的建立以及算法的实现流程,其次讨论了蚁群算法在经典的旅行商问题上的应用,最后利用Matlab软件对旅行商问题进行编程求解并对最终实验结果进行了分析。

摘要： 本文研究了具体的矩形件最优排样问题,先是讨论了几种常规的数学建模方法和求解结果,然后从最小间隙问题出发,使得排样间隙最小时达到板材的最优利用率,根据这种方法利用一定的数论思想和 Matlab软件确立并求解出利用率最高的矩形件切割方案的数学模型,从而将这种模型推广为多矩形件同时排样的复杂数学模型,最后求解了具体的两种矩形件同时排样问题中利用率更高的矩形件切割方案.

摘要： 为了高效求解具有单连续变量的背包问题(KPC),首先基于高斯误差函数提出了一个新颖S型转换函数,给出了利用该转换函数将一个实向量转换为0-1向量的新方法,由此提出了一个新的二进制粒子群优化(NBPSO)算法;然后,利用KPC的第二数学模型,并且把NBPSO与处理KPC不可行解的有效算法相结合,提出了求解KPC的一个新方法.为了检验NBPSO求解KPC的性能,利用NBPSO求解四类大规模KPC实例,并把所得计算结果与基于其他S、V型转换函数的二进制粒子群优化算法(BPSO)、具有混合编码的单种群二进制差分演化算法(S-HBDE)、具有混合编码的双种群二进制差分演化算法(B-HBDE)和二进制粒子群优化算法(BPSO)等的计算结果相比较.比较结果表明NBPSO不仅平均计算结果更优,而且稳定性更佳,说明NBPSO的性能比其他算法有显著提升.

摘要： 本文基于数学领域中最为著名的问题之一就是旅行商问题(TSP),属于典型的组合优化问题,对于大规模TSP问题在使用经典算法很难求出精确解的情况下,一般采用智能算法来获取最优解或次优解。基于Geatpy遗传算法库,本文给出了一种求解TSP问题的方法,实验结果证明该方法是有效的,具有一定的通用性,值得进一步应用推广。

摘要： 针对卫星观测任务规划问题约束复杂、求解空间大和输入任务序列长度不固定的特点,使用深度强化学习(DRL)方法对卫星观测任务规划问题进行求解.综合考虑时间窗口约束、任务间转移机动时间和卫星电量、存储约束,对卫星观测任务规划问题进行建模.基于指针网络(PN)的运行机制建立序列决策算法模型,使用Mask向量来考虑卫星观测任务规划问题中的各类约束,并通过Actor Critic强化学习算法对模型进行训练,以获得最大的收益率.借鉴多头注意力(MHA)机制的思想对PN进行改进,提出多头注意力指针网络(MHA-PN)算法.根据实验结果可以看出,MHA-PN算法显著提高了模型的训练速度和泛化性能,训练好的MHA-PN算法模型可以直接对输入序列进行端到端的推理,避免传统启发式算法迭代求解的过程,具有较高的求解效率.

摘要： 粗粒度可重构阵列(CGRA)因为其灵活性和高能效比受到广泛关注,动态发射型CGRA提供一种更为高效的实现模式,针对其编译技术的研究可以充分发挥其计算能力.动态发射型CGRA的编译问题转化为一个关于调度的组合优化问题,使用模拟退火算法实现调度空间的产生和探索.实验结果表明,相比之前的编译技术,可以获得平均19.80％的性能提高.

摘要： 蚁群算法是一种新的进化算法,其基本思想是模拟蚂蚁的合作行为.蚁群算法已成功地应用于许多优化问题,成为求解组合优化问题的新的进化算法.最新研究表明蚁群算法是一种基于群体的强鲁棒性的进化算法.但是,蚁群算法也有收敛速度慢,容易陷入局部最优的缺点.为了克服这些缺点,吸取微粒群算法的优点,提出了一种改进的蚁群算法.实验结果表明改进算法是有效的,与标准的蚁群算法相比,算法性能得到了明显改善.

摘要： 卫星数据传输调度问题指的是为了最大限度满足用户对卫星侦察信息的需要，利用某种调度规则或调度算法为卫星实施数据传输分配地面资源及可用时间。针对卫星数据传输调度问题，考虑在卫星和地面站接收设备的可见时间、卫星和地面站接收设备的匹配等约束条件下，为了降低卫星数据传输调度的算法复杂性，采用了分治法思想。以时间长度为贪婪准则运用贪婪算法有效地解决了卫星数据传输调度问题，编程实现了基本的应用模型，为进一步研究该问题，给出了一种新的思路。

摘要： 卫星数据传输调度问题指的是为了最大限度满足用户对卫星侦察信息的需要，利用某种调度规则或调度算法为卫星实施数据传输分配地面资源及可用时间。针对卫星数据传输调度问题，考虑在卫星和地面站接收设备的可见时间、卫星和地面站接收设备的匹配等约束条件下，为了降低卫星数据传输调度的算法复杂性，采用了分治法思想。以时间长度为贪婪准则运用贪婪算法有效地解决了卫星数据传输调度问题，编程实现了基本的应用模型，为进一步研究该问题，给出了一种新的思路。

摘要： 卫星数据传输调度问题指的是为了最大限度满足用户对卫星侦察信息的需要，利用某种调度规则或调度算法为卫星实施数据传输分配地面资源及可用时间。针对卫星数据传输调度问题，考虑在卫星和地面站接收设备的可见时间、卫星和地面站接收设备的匹配等约束条件下，为了降低卫星数据传输调度的算法复杂性，采用了分治法思想。以时间长度为贪婪准则运用贪婪算法有效地解决了卫星数据传输调度问题，编程实现了基本的应用模型，为进一步研究该问题，给出了一种新的思路。

摘要： 卫星数据传输调度问题指的是为了最大限度满足用户对卫星侦察信息的需要，利用某种调度规则或调度算法为卫星实施数据传输分配地面资源及可用时间。针对卫星数据传输调度问题，考虑在卫星和地面站接收设备的可见时间、卫星和地面站接收设备的匹配等约束条件下，为了降低卫星数据传输调度的算法复杂性，采用了分治法思想。以时间长度为贪婪准则运用贪婪算法有效地解决了卫星数据传输调度问题，编程实现了基本的应用模型，为进一步研究该问题，给出了一种新的思路。

摘要： 本发明提供一种能够高效地构建尖峰神经的模拟的尖峰神经装置。尖峰神经装置使用相干伊辛机，所述相干伊辛机具备：谐振器部，用于放大多个光脉冲；测定部，测定该多个光脉冲的相位和振幅并得到测定结果；以及反馈构成，基于该测定结果使用伊辛模型的耦合系数对与某光脉冲相关的相互作用进行运算并反馈，所述尖峰神经装置的特征在于，所述反馈构成对所述多个光脉冲中的规定的两个光脉冲反馈输入由彼此符号相反的两个耦合系数决定的相关关系，通过由所述测定部最终得到的两个光脉冲的值中的一方的值来模拟尖峰神经的状态。

摘要： 本发明公开了一种使用基于MapReduce的蚁群优化技术求解组合优化问题的方法，属于组合优化问题求解技术领域。本发明包括如下步骤：根据设定的mapper的数量划分指定组合优化问题的解空间；Map阶段，每个mapper独立并行地在步骤1)划分得到的子问题解空间中执行改进的蚁群算法，搜索局部最优解；Reduce阶段，reducer接受所有mapper在不同解空间搜索到的局部最优解，根据步骤1)中采用的解空间划分情况综合得到全局最优解；输出reducer当前得到的全局最优解，结束。本发明具有更好的可伸缩性，能够更好的改善求解大规模组合优化问题的效率。

摘要： 本发明提供一种可编程伊辛机及组合优化问题和密码学问题的解决方法，可编程伊辛机包括：依次环形连接的第一电光调制器、长光纤、光电探测器、编程模块及混频器；激光脉冲产生装置，连接第一电光调制器的输入；本振源，连接混频器的输入。本发明的可编程伊辛机可以实现超大规模的伊辛自旋，具有大带宽、免电磁干扰的特点，借助可编程器件，可以实现任意自旋之间的可编程连接，产生相位特定分布的二相位脉冲自旋电信号，对应可编程伊辛机的最小增益，最小增益对应组合优化问题和密码学问题的最优解。

摘要： 本说明书提供的组合优化问题的求解方法和系统，通过分支定界算法求解组合优化问题的实施例，并将求解实施例过程中的每个分支节点的约束和松弛解以及节点对应的强分支作为样本数据，来训练决策模型。所述求解方法和系统在对目标组合优化问题求解过程中，基于分支定界算法，在每个分支节点，将分支节点对应的约束和松弛解输入至训练好的决策模型中，并输出当前节点对应的强分支，从而基于决策模型来模拟分支定界过程中的分支过程，快速找到分支节点中的强分支，无需对每个分支进行求解，大大缩短计算时间，从而加快组合优化问题的求解速度。

摘要： 本发明提供一种相干伊辛机及组合优化问题的解决方法，相干伊辛机包括：脉冲激光器，产生光载波；泵浦光产生模块，产生泵浦光；信号光产生模块，产生第一信号光；第一非线性媒介，对第一信号光进行光参量放大，产生第二信号光和空闲光，空闲光的相位为泵浦光和第二信号光的相位之差；第一光耦合器，将光载波分束为第一光载波，第二光载波和第三光载波；第二光耦合器，耦合第三光载波和空闲光；存储转换模块，将第二光耦合器输出的光信号存储并转换为第一电信号；逻辑运算模块，对第一电信号进行逻辑运算，产生并输入第二电信号到信号光产生模块。通过该相干伊辛机，能够实现相干伊辛机的高相干、大规模以及可编程的有机结合。

摘要： 本发明提供一种光电振荡伊辛机及组合优化问题的解决方法，光电振荡伊辛机包括：由首尾依次连接的电光调制器，长光纤，光电探测器，可调电衰组成的闭合环路，激光器，用于产生光载波；电光调制器，用于将电路输入的第二电信号调制到光载波上，得到光信号；长光纤，用于存储光信号，以延长光环路时间；光电探测器，用于将光信号转换为电信号；可调电衰，用于对电信号进行衰减，使闭合环路处于混沌分叉状态，产生伊辛自旋信号；自旋耦合模块，用于耦合伊辛自旋信号。通过长光纤，可调电衰和自旋耦合模块等器件的共同作用，能够实现光电振荡伊辛机的大规模，相干性，可编程的有机统一。

摘要： 本发明涉及一种解决图组合优化问题的方法、装置、电子设备及存储介质。本发明所述的解决图组合优化问题的方法包括：获取真实数据对应的实例图，生成所述实例图对应的图数据结构；将所述图数据结构输入到图神经网络中进行编码处理，得到所述图数据结构的每个节点的特征向量；用所述每个节点的特征向量定义用来进行强化学习训练的Q函数，得到Q函数的参数化表示；迭代执行使用经过强化学习训练的Q函数计算各节点的Q值，根据所述各节点的Q值对所述图信息进行状态更新；直至状态更新后的图信息是否达到终止条件，输出当前图信息为最优解。本发明所述的解决图组合优化问题的方法，提高了对经验的采样率，加快了Q函数的学习。

摘要： 本发明公开了一种处理组合优化问题的电路，包括全局随机数生成模块、翻转概率计算单元、接收决策模块、自旋更新单元、ROM、第一选择器以及若干局部能量单元；局部能量单元的输出与第一选择器相连接，第一选择器的输出以及概率翻转计算单元的输出均接入接收决策模块，接收决策模块的输出分别连接至自旋更新单元和局部能量单元，全局随机数生成模块生成的随机数输出至第一选择器、ROM和自旋更新单元，自旋更新单元的输出以及ROM的输出均接入局部能量单元的输入。本发明总体上通过数模混合的方法避免了量子计算机对于极端工作环境的要求和计算过程中遇到的问题，通过模拟伊辛模型的方式给出了一种解决组合优化问题的电路，可广泛应用于电路领域。

摘要： 本发明提供一种相干伊辛机及组合优化问题的解决方法，相干伊辛机包括：线偏振光产生模块，用于产生第一线偏振光；微波信号产生模块，用于产生微波信号；分光及逻辑运算模块，用于产生反馈信号来控制偏振调制器产生单一偏振状态的光脉冲信号；偏振调制器，用于使用微波信号和反馈信号对第一线偏振光进行调制，得到第二线偏振光；波片，用于将第二线偏振光转换为振荡方向相互正交的第三线偏振光；第一光耦合器，用于将第三线偏振光进行分束，一束输入到微波信号产生模块中，另一路输入到分光及逻辑运算模块中。通过本发明的相干伊辛机可以实现高相干、可编程、大规模的统一以及解决复杂的组合优化问题。

摘要： 本发明提供了一种机组组合优化问题的快速计算方法及装置，所述方法包括：对建模时段进行时段抽稀，得到关键时段；基于所述关键时段构建非连续时段SCUC模型；根据所述非连续时段SCUC模型进行求解得到缩减时段求解结果，重新扩展至全部的连续时段后，辨识并固定无效整数变量；固定所述无效整数变量后对剩余有效整数变量构建连续时段SCUC模型；根据所述连续时段SCUC模型进行求解得到机组组合优化结果。本发明首先对时段进行抽稀，然后在此基础上进行建模并求解；在得到一个小型解后，再重新将变量扩展至全时段，在此过程中辨识并固定无效整数变量；最后再继续求解剩余未固定的变量，并得到最终解。本发明能够有效降低模型的运算量，提高机组组合求解的效率。