量子近似优化算法在数字分区问题中的应用

量子近似优化算法(QAOA)是一种近似求解组合优化问题的方法,它通过反复调整电路参数,以获取问题哈密顿量的最大期望值为目的来解决问题,在组合优化问题领域具有广阔的应用前景。将QAOA应用于数字分区问题(二分区问题),通过将问题函数转换成对应的哈密顿量,构造了量子线路,采用线性近似约束优化(COBYLA)方法对电路参数进行了优化,并使用IBMQ模拟平台进行了模拟实验。研究发现量子近似优化算法在数字分区问题中有着良好的性能表现,可在多项式时间内给出问题的解,并且降低了问题的时间复杂度。

基于Contig的单面基因组框架填充2-近似算法

随着基因测序技术的持续发展,基因组框架填充问题受到广泛关注。该文针对基于contig的单面含重复基因的基因组框架填充问题开展研究。通过设计有效的近似算法,完成根据参照基因组,将缺失基因填充至基因测序获得的不完整框架中,提高基因组框架的完整性。前期研究的基因组框架填充问题,缺失基因可以插入到不完整序列的任意两个基因之间,而基于片段重叠群(contig)的基因组框架填充,缺失基因的插入位置被限制在两个contig之间,更具一般性,该问题已被证明是NP完全问题。现有的近似算法中,2-近似算法处理的实例具有特殊性,2.57-近似算法针对一般实例,但近似性能比不够理想。该文以缺失基因、基因位点和断点三者之间的对应关系为基础,采用贪婪策略和最大匹配相结合的方式避免在填充过程中出现冗余公共邻接,并通过生成新的contig增加外邻接的数量,将针对一般实例的算法近似性能比提高到2,完成了基于Python的可视化程序开发,进一步验证了算法的有效性。

近似图引导的演化贝叶斯网络结构学习算法

贝叶斯网络结构学习是贝叶斯网络推理及应用的基础.搜索高质量的节点序是贝叶斯网络结构学习的一类重要方法.针对在节点序空间中,搜索高质量节点序存在的难以高效、准确评估解的问题,本文提出了一种近似图引导的演化贝叶斯网络结构学习算法.首先,该算法利用互信息构建无向近似图;其次,该算法通过结合节点序和无向近似图构造有向图结构,将其贝叶斯信息准则评分作为节点序的适应度来高效评估节点序,并在演化优化的框架下,使用提出的基于Kendall Tau Distance的交叉算子和基于逆度的变异算子搜索最优节点序;最后,将搜索到的最优节点序输入K2算法得到其对应的贝叶斯网络结构.在4种不同规模网络上的实验结果表明,该算法在收敛时间和准确度之间取得了较好的平衡,其评分相较于对比算法中的次优解分别提升了10.91%、12.28%、53.96%、10.87%.

结合Benders分解和列生成的发热门诊排班数学建模和优化算法

发热门诊是抗击疫情最前线,发热门诊中的医生排班对于系统运行效率和医疗服务质量都非常重要,需要科学的排班优化算法。针对发热门诊医生排班调度问题,首先采用逐点稳态流近似方法对系统建模,定量评估系统中等待服务的患者数目,基于此建立了考虑患者排队队长限制的医生排班数学优化模型。进一步,为求解该模型设计了结合Benders分解与列生成的高效算法,对此复杂优化问题加以高效求解。最后,利用上海大型医院发热门诊的实际数据加以数值实验分析,验证了所提出算法的排班结果,显示了其在控制患者队长和医生总工作时间上具有优势。数值结果进一步验证所提出方法能适应疫情严重情况下的医生排班优化要求。研究得到的模型和算法对完善疫情中发热门诊的运作管理具有实际意义。

量子近似优化算法在精确覆盖问题中的应用

精确覆盖问题属于组合优化中的NP完全问题,使用经典算法难以在多项式时间范围内求解。为解决该问题,在开源量子计算框架qiskit上,提出基于量子近似优化算法(QAOA)的量子线路求解方案,并采用基于单纯形法的线性近似约束优化(COBYLA)算法对量子逻辑门中的参数进行优化。首先,通过精确覆盖问题的数学模型建立经典伊辛模型;其次,利用量子理论中的旋转变量对经典伊辛模型进行量子化,再用泡利旋转算子代替旋转变量,得到量子伊辛模型和问题哈密顿量,提高QAOA寻找最优的速度;最后,以混合哈密顿量为生成元的酉变换和问题哈密顿量为生成元的酉变换乘积的累积,得到问题哈密顿量期望的表达式,并由此设计生成量子线路。另外,通过经典处理器对两个酉变换中的参数进行优化,调整问题哈密顿量的期望值,从而提高求解的概率。该线路在IBM的开源量子计算框架qiskit上进行仿真实验,实验结果表明,所提方案能够在多项式时间内以95.6%的概率获得问题的解,验证了所提量子线路能够以较高的概率求得精确覆盖问题的解。

基于Benders分解算法的反恐应急设施选址-定容-分配问题

反恐应急设施的合理布局和资源配置可缩短救援到达时间并提高应急效率。对已有反恐应急设施选址研究拓展,进一步考虑设施容量有限的情形,并将袭击前后关于应急设施的选址、定容和救援物资分配问题进行集成考虑。将该问题构造为三层规划模型,上中下各层规划分别对应袭击前的选址定容问题、袭击时的袭击点选择问题和袭击后的救援物资分配问题。利用下层规划的对偶变换转化为双层规划,并设计Benders分解算法求解。最后,结合南疆交通网络进行仿真分析,验证了模型和算法的有效性。

基于近似算法的分布参数对机电系统动态响应的频时域研究

文章针对具有机械部分分布参数的机电系统进行了频时域实验研究。文章强调了考虑参数分布的重要性,并分析了影响其分布特性的重要元素。在验证阶段开发了实验装置,并采用StrimServer和CANMonitor程序用于数据采集和分析;同时开发了控制系统,描述了最简单校正装置的创建过程,突出了用于开发控制程序的编程环境,并提供了一组编程控制器的程序。在频域实验中,在模拟机电系统行为的条件下,展示了合成控制系统的有效性。通过与理论计算的比较发现,其与实际值最大相对误差不超过10%,证实了理论计算的可靠性。在时域分析中,通过CANMonitor程序绘制电流图,发现在共振频率下电流幅值增加到1.83倍,这与在谐振频率处应有的情况相符。期望本文能对理解和设计具有分布参数的机电系统带来启发。

基于Benders算法下考虑企业所有权分配的供应链跨国布局研究

随着经济全球化,供应链跨国布局成为研究热点之一。本文在构建供应链跨国布局基本模型的基础上,通过引入跨国生产转移成本,将供应链企业所有权分配参数有机嵌入到基本模型中,从而考虑了国内销售合资/独资和海外销售合资/独资,这两种情况下供应链跨国布局模型,并结合模型的实际,设计出基于Benders算法及其相应步骤。最后,通过实例分析发现,所有权分配在供应链跨国布局中,对所选择的供应商数量影响不大,但对所选择的生产商数量以及供应商跨国布局范围有着明显的影响和差异,另外,还发现在税收、汇率以及所有权分配三个主要因素之中,所有权分配对供应链跨国布局所获得的利润影响最显著。

Benders算法在发电机无功储备管理中的应用

电力系统的电压稳定性与系统中的无功储备密切相关。首先,建立了考虑N-1预想故障静态安全约束的发电机无功储备管理模型,并利用Benders算法将该模型分解为一个与正常运行方式相关的主问题和一系列与预想故障相关的子问题:主问题处理正常运行方式下的相关约束以及子问题所返回的Benders割约束,子问题处理一系列的预想故障及静态安全约束。其次,为提高Benders分解算法的求解效率,进一步提出了一种结合连续潮流方法的并行求解策略,减少了所需求解子问题的个数,仅返回一个Benders割至主问题。以IEEE 39节点系统作为算例,仿真结果验证了本文所提模型的正确性及求解策略的有效性。

优先级k-中心问题的FPT近似算法

优先级k-中心问题是聚类领域中1个经典的NP-难问题。给定度量空间中的1个集合X和参数k∈N+,其中,集合X中每个点v都被赋予1个优先级参数r(v)∈R+,求解1个大小为k的子集S■X,考虑集合X中任意数据点到集合S的距离与r(v)之间比值,找到最大比值,目标是最小化该比值。对于优先级k-中心问题,目前最好的结近似算法是多项式时间内的2-近似算法,该问题不存在1个(2-ε)-近似算法,(其中,ε为用于控制算法近似比的参数)。本文研究优先级k-中心问题的固定参数可解(fixed-parameter tractability,FPT)时间内的近似算法。基于k-中心问题的贪心策略,提出新的中心点选取方法。研究结果表明:该方法通过贪心策略选取一定规模的候选中心点集,利用加倍度量维度的性质去限制该集合的大小,实现了FPT时间内的(1+ε)-近似算法,降低了目前该问题的近似比。

基于Benders分解优化算法的区域能源供给服务网络系统规划方法研究

能源互联网是实现我国能源革命目标的关键手段之一,然而其多能互补的特点增加了能源供应的复杂性,从而影响到区域范围内系统能源供应的协调有序。为探索这一问题的解决方法,针对小范围内的能源供给服务网络的系统规划问题开展了研究,建立了以总成本函数为目标函数、考虑多能互补的系统负荷约束、系统安全性约束函数为主要约束的区域能源供给服务网络优化模型,运用Benders算法将问题分解为主问题和子问题并对模型进行求解。以华北某市郊区的区域能源规划为案例进行能源供给服务网络的规划,并与传统规划模式进行对比分析。结论表明,由于考虑了热电负荷之间的耦合关系,并在需求约束中引入了电转热替代环节,使得所提出的模型能够在系统的规划和运行阶段都选择更优的策略,从而在经济性上相较于传统工业规划方法具有更强的竞争力。

经典Benders分解算法解析

随着计算机技术的飞速发展,对于大规模非线性运算问题的计算方法的研究也越来越受到人们的关注。本文介绍了一种经典的Benders分解算法,该算法常用于求解像最小整数非线性规划和随机规划问题之类的计算难题。

经典Benders分解算法解析

随着计算机技术的飞速发展，对于大规模非线性运算问题的计算方法的研究也越来越受到人们的关注。本文介绍了一种经典的Benders分解算法，该算法常用于求解像最小整数非线性规划和随机规划问题之类的计算难题。

静态安全约束下基于Benders分解算法的可用传输容量计算

在电力市场环境下,可用传输容量(ATC)是反映输电线路可用于交易的剩余容量的重要指标。文中以最优潮流为基础,采用Benders分解方法将考虑静态安全约束的ATC计算问题分解为一个基态主问题和一系列与各预想事故有关的子问题。主问题用来处理基态潮流和相应约束以及由子问题所返回的Benders割(cut)约束,而各子问题用来处理各预想事故和形成相应的静态安全约束。文章给出了相 应的数学模型,并提出了两种改进的求解策略。4节点和IEEE30节点系统的计算结果表明了该方法和求解策略的有效性。

量子近似优化算法在投资组合优化中的应用

讨论了量子近似优化算法(QAOA)在投资组合优化问题上的应用,而后者在离散的约束条件下是NP难的;介绍了QAOA的基本框架以及相应的投资组合优化问题的建模;阐述了数个可用于解决投资组合优化问题的QAOA方法。通过数值模拟及假设检验比较这些方法与经典方法的表现,各量子算法在平均近似比上相较经典方法均有7%以上的提升。

量子近似优化算法在最大独立集中的应用

最大独立集问题是著名的NP问题,并且在许多场景中都有应用。传统的精确算法解决最大独立集问题需要指数级的时间复杂度。为更高效地解决最大独立集问题,提出了一种基于量子近似优化算法的量子线路解决方案。该方案由最大独立集的数学模型,推导出最大独立集问题的哈密顿量表达式;设计了基于量子近似优化算法的量子线路,采用COBYLA经典优化算法对参数量子门中的参数进行优化,并使用IBM提供的量子开发框架Qiskit进行仿真实验。仿真结果表明,使用量子近似优化算法可以在多项式时间内以高概率获得最大独立集问题的解,实现了指数加速。量子近似优化算法对解决最大独立集问题有一定的可行性和有效性。

平方度量的设施租赁问题的近似算法

作为设施租赁问题的推广,首次提出平方度量的设施租赁问题,平方度量侧重于突出距离对连接费用的影响,具有广泛的实际应用背景。在平方度量的设施租赁问题中,每个时间段都有顾客到达,每个到达的顾客都需要被连接到某个其到达时正在租赁的设施上。租赁设施产生租赁费用,连接顾客到设施产生连接费用,连接费用是顾客与设施之间距离的平方,通常假设距离是度量的。目标是租赁一些设施,连接每个顾客,使得租赁费用与连接费用之和最小。基于原始对偶技巧,给出平方度量的设施租赁问题的9-近似算法。

基于Benders分解的鲁棒最短路算法

为了研究路段行程时间不确定条件下的最短路问题,采用区间数据表示路段行程时间,介绍了鲁棒偏差和鲁棒成本的概念,并据此给出鲁棒最短路的定义,运用鲁棒优化中的min-max准则构建了鲁棒最短路问题的混合整数规划模型。通过固定路径决策变量将鲁棒最短路问题分解为子问题和主问题,同时结合对偶理论给出子问题的对偶模型。在此基础上设计出鲁棒最短路问题的Benders分解算法,采用AMPL编程实现算法并调用CPLEX进行求解。并在一个仿真网络中对本研究方法进行了验证分析。研究结果表明,相较于传统最短路Dijkstra算法,本研究方法求得的鲁棒最短路在不确定网络中具有更强的可靠性,设计的算法迭代效率较高,能迅速缩小迭代范围并找到最优解。

基于变可信度近似模型的BGA焊点可靠性预测与优化方法

焊点可靠性预测研究多采用有限元仿真与单一精度近似模型相结合的模式,存在仿真时间长、效率低、准确性差等问题,为此,提出了一种基于变可信度近似模型的球栅阵列(ball grid array,BGA)焊点可靠性预测与优化方法.首先,对不同网格细化方案进行收敛性验证,分别设计高/低精度样本点进行有限元仿真;其次,基于CoKriging模型融合高/低精度仿真数据进行焊点可靠性预测;最后,将预测结果与单一精度近似模型进行对比分析,并采用遗传算法优化模型获得对应结构参数.结果表明,在更少的仿真成本下,变可信度模型的预测效果更好,在同等预测精度下,变可信度模型高精度样本点数量仅为单一精度模型的1/4,相比高精度神经网络预测模型,在寻优过程中收敛更快.

基于改进近似共轭梯度追踪的轴承故障诊断方法

在确保机械系统的可靠性和功能性、生产效率和安全性方面,滚动轴承的状态监测和故障诊断极其重要。然而,故障特征通常总是被背景噪音和其他不稳定的干扰成分所掩盖,这使得这项工作变得非常困难。为了更好地提取轴承故障特征,提出了结合改进的正余弦优化算法(improved sine cosine algorithm, ISCA)的弱选择近似共轭梯度追踪(weak selection approximate conjugate gradient pursuit, WACGP)算法。将惯性权重和非线性参数更新策略引入正余弦优化算法(sine cosine algorithm, SCA)中,提高了信号稀疏表示的效率和精度,以便用字典原子最大限度地逼近原始信号,并且将弱选择策略引入近似共轭梯度追踪(approximate conjugate gradient pursuit, ACGP)中,提高了提取轴承故障特征的速度和能力。通过对轴承的故障仿真信号和实际轴承内、外圈和滚动体振动信号的分析,验证了该方法的有效性。详细说明了与基于正余弦优化的梯度追踪算法的比较,突出了所提出的方法的优点。