Quafu-Qcover:Explore combinatorial optimization problems on cloud-based quantum computers

We introduce Quafu-Qcover,an open-source cloud-based software package developed for solving combinatorial optimization problems using quantum simulators and hardware backends.Quafu-Qcover provides a standardized and comprehensive workflow that utilizes the quantum approximate optimization algorithm(QAOA).It facilitates the automatic conversion of the original problem into a quadratic unconstrained binary optimization(QUBO)model and its corresponding Ising model,which can be subsequently transformed into a weight graph.The core of Qcover relies on a graph decomposition-based classical algorithm,which efficiently derives the optimal parameters for the shallow QAOA circuit.Quafu-Qcover incorporates a dedicated compiler capable of translating QAOA circuits into physical quantum circuits that can be executed on Quafu cloud quantum computers.Compared to a general-purpose compiler,our compiler demonstrates the ability to generate shorter circuit depths,while also exhibiting superior speed performance.Additionally,the Qcover compiler has the capability to dynamically create a library of qubits coupling substructures in real-time,utilizing the most recent calibration data from the superconducting quantum devices.This ensures that computational tasks can be assigned to connected physical qubits with the highest fidelity.The Quafu-Qcover allows us to retrieve quantum computing sampling results using a task ID at any time,enabling asynchronous processing.Moreover,it incorporates modules for results preprocessing and visualization,facilitating an intuitive display of solutions for combinatorial optimization problems.We hope that Quafu-Qcover can serve as an instructive illustration for how to explore application problems on the Quafu cloud quantum computers.

MODS： A Novel Metaheuristic of Deterministic Swapping for the Multi-Objective Optimization of Combinatorials Problems

This paper states a new metaheuristic based on Deterministic Finite Automata （DFA） for the multi - objective optimization of combinatorial problems. First, a new DFA named Multi - Objective Deterministic Finite Automata （MDFA） is defined. MDFA allows the representation of the feasible solutions space of combinatorial problems. Second, it is defined and implemented a metaheuritic based on MDFA theory. It is named Metaheuristic of Deterministic Swapping （MODS）. MODS is a local search strategy that works using a MDFA. Due to this, MODS never take into account unfeasible solutions. Hence, it is not necessary to verify the problem constraints for a new solution found. Lastly, MODS is tested using well know instances of the Bi-Objective Traveling Salesman Problem （TSP） from TSPLIB. Its results were compared with eight Ant Colony inspired algorithms and two Genetic algorithms taken from the specialized literature. The comparison was made using metrics such as Spacing, Generational Distance, Inverse Generational Distance and No-Dominated Generation Vectors. In every case, the MODS results on the metrics were always better and in some of those cases, the superiority was 100%.

Original optimal method to solve the all-pairs shortest path problem: Dhouib-matrix-ALL-SPP

The All-pairs shortest path problem(ALL-SPP)aims to find the shortest path joining all the vertices in a given graph.This study proposed a new optimal method,Dhouib-matrix-ALL-SPP(DM-ALL-SPP)to solve the ALL-SPP based on column-row navigation through the adjacency matrix.DM-ALL-SPP is designed to generate in a single execution the shortest path with details among all-pairs of vertices for a graph with positive and negative weighted edges.Even for graphs with a negative cycle,DM-ALL-SPP reported a negative cycle.In addition,DM-ALL-SPP continues to work for directed,undirected and mixed graphs.Furthermore,it is characterized by two phases:the first phase consists of adding by column repeated(n)iterations(where n is the number of vertices),and the second phase resides in adding by row executed in the worst case(n∗log(n))iterations.The first phase,focused on improving the elements of each column by adding their values to each row and modifying them with the smallest value.The second phase is emphasized by rows only for the elements modified in the first phase.Different instances from the literature were used to test the performance of the proposed DM-ALL-SPP method,which was developed using the Python programming language and the results were compared to those obtained by the Floyd-Warshall algorithm.

Solving Combinatorial Optimization Problems with Deep Neural Network:A Survey

Combinatorial Optimization Problems(COPs)are a class of optimization problems that are commonly encountered in industrial production and everyday life.Over the last few decades,traditional algorithms,such as exact algorithms,approximate algorithms,and heuristic algorithms,have been proposed to solve COPs.However,as COPs in the real world become more complex,traditional algorithms struggle to generate optimal solutions in a limited amount of time.Since Deep Neural Networks(DNNs)are not heavily dependent on expert knowledge and are adequately flexible for generalization to various COPs,several DNN-based algorithms have been proposed in the last ten years for solving COPs.Herein,we categorize these algorithms into four classes and provide a brief overview of their applications in real-world problems.

Application of the edge of chaos in combinatorial optimization

Many problems in science,engineering and real life are related to the combinatorial optimization.However,many combinatorial optimization problems belong to a class of the NP-hard problems,and their globally optimal solutions are usually difficult to solve.Therefore,great attention has been attracted to the algorithms of searching the globally optimal solution or near-optimal solution for the combinatorial optimization problems.As a typical combinatorial optimization problem,the traveling salesman problem(TSP)often serves as a touchstone for novel approaches.It has been found that natural systems,particularly brain nervous systems,work at the critical region between order and disorder,namely,on the edge of chaos.In this work,an algorithm for the combinatorial optimization problems is proposed based on the neural networks on the edge of chaos(ECNN).The algorithm is then applied to TSPs of 10 cities,21 cities,48 cities and 70 cities.The results show that ECNN algorithm has strong ability to drive the networks away from local minimums.Compared with the transiently chaotic neural network(TCNN),the stochastic chaotic neural network(SCNN)algorithms and other optimization algorithms,much higher rates of globally optimal solutions and near-optimal solutions are obtained with ECNN algorithm.To conclude,our algorithm provides an effective way for solving the combinatorial optimization problems.

基于D3QN的火力方案优选方法

针对在多类弹药协同攻击地面工事类目标任务中火力方案优选效率低的问题,提出一种基于双层决斗DQN(dueling double deep Q network,D3QN)的火力方案优选方法。该方法将打击过程建模为马尔科夫决策过程(Markov decision processes,MDP),设计其状态空间和动作空间,设计综合奖励函数激励火力方案生成策略优化,使智能体通过强化学习框架对策略进行自主训练。仿真实验结果表明,该方法对地面工事类目标的火力方案进行决策,相较于传统启发式智能算法能够获得较优的火力方案,其计算效率和结果的稳定性相较于传统深度强化学习算法具有更明显的优势。

多维背包问题的启发式算法研究探讨

多维背包问题是NP难组合优化问题,其模型及算法近年来在众多领域得到了广泛应用。本文主要探讨多维背包问题的启发式求解算法,通过对相关文献进行研究,阐述现有算法的优缺点,针对多维背包问题设计更高效的启发式求解算法,为其提供新的思路和参考。

基于离散粒子群算法的管道保温结构优化研究

针对目前管道保温结构优化算法不稳定、结果优化程度不高的问题,建立以经济效益为目标函数,以满足国家散热损失标准等条件为约束函数的离散型数学模型。以BPSO算法为基础改变其位置更新规则,防止种群进化失效;采用自适应权重增加粒子的全局和局部搜索能力;充分利用模拟退火算法的思想避免出现早熟现象。应用改进的算法分别对普通蒸汽管道和核电站的蒸汽管道进行系统仿真实验。结果表明,该算法能够在满足国家散热损失标准等条件下取得最优解,可以为管道保温结构提供合理的优化方案。

A unified pre-training and adaptation framework for combinatorial optimization on graphs

Combinatorial optimization(CO)on graphs is a classic topic that has been extensively studied across many scientific and industrial fields.Recently,solving CO problems on graphs through learning methods has attracted great attention.Advanced deep learning methods,e.g.,graph neural networks(GNNs),have been used to effectively assist the process of solving COs.However,current frameworks based on GNNs are mainly designed for certain CO problems,thereby failing to consider their transferable and generalizable abilities among different COs on graphs.Moreover,simply using original graphs to model COs only captures the direct correlations among objects,which does not consider the mathematical logicality and properties of COs.In this paper,we propose a unified pre-training and adaptation framework for COs on graphs with the help of the maximum satisfiability(Max-SAT)problem.We first use Max-SAT to bridge different COs on graphs since they can be converted to Max-SAT problems represented by standard formulas and clauses with logical information.Then we further design a pre-training and domain adaptation framework to extract the transferable and generalizable features so that different COs can benefit from them.In the pre-training stage,Max-SAT instances are generated to initialize the parameters of the model.In the fine-tuning stage,instances from CO and Max-SAT problems are used for adaptation so that the transferable ability can be further improved.Numerical experiments on several datasets show that features extracted by our framework exhibit superior transferability and Max-SAT can boost the ability to solve COs on graphs.

基于混合遗传搜索求解载重约束的电动车辆路径问题

载重约束的电动车辆路径问题(capacitated electric vehicle routing problem,CEVRP)是物流配送中的一种NP困难的组合优化问题,要求满足车辆的载重和电量约束条件,最小化总配送距离。提出一种混合遗传搜索算法来解决CEVRP,将其分解为两个子问题:载重约束的车辆路径问题和固定路径车辆充电问题。设计了双层染色体结构的编码方案,表示两个子问题的决策变量。采用Split操作生成满足载重约束的车辆路径,使用Relocate、2-Opt、2-Opt^(*)、SWAP和SWAP^(*)邻域搜索算子对其进行局部优化;提出一种基于回溯的充电策略,将合适的充电站编号插入车辆路径,以满足电量约束。本文算法与五种方法实验比较的结果表明,本文算法在多数CEVRP测试问题上能找到比其它方法更好的解,尤其适合于求解大规模的CEVRP。

相干伊辛计算的研究与应用进展

随着人工智能技术的快速发展,与之相关的各种行业都产生了海量的算力需求。低能耗光计算和量子计算成为未来高速、大数据量处理极具前景的方案,相干伊辛计算作为其中的典型计算技术,受到了研究领域和产业界的广泛关注,近年来取得了一系列重要的研究进展。相干伊辛计算利用光学参量振荡脉冲作为量子比特,在运行中可以搜索出伊辛模型基态时的自旋构型,从而能够提升求解组合优化问题的计算速度和正确率。通过纠错改进后的相干伊辛机可以逃离局部极小值的限制,在大规模组合优化问题上的测试结果也超越了部分经典算法,为多种组合优化问题的解决提供了新的发展方向。

增强型群论优化算法求解折扣{0-1}背包问题

群论优化算法(GTOA)是基于群论方法提出的一个离散演化算法,非常适于求解以整型向量为可行解的组合优化问题。为了进一步提高GTOA求解折扣{0-1}背包问题(D{0-1}KP)的性能,首先指出了它的随机线性组合算子(RLCO)未能充分考虑当前个体位置信息的不足,基于个体基因保留策略对其进行改进。然后,在随机反向变异算子(IRMO)中引入增强0分量变异策略,用于处理因个体0分量无法及时变异而导致的解的质量下降、种群多样性降低等问题。在改进上述两个算子的基础上,提出了增强型GTOA(EGTOA),并基于它给出求解D{0-1}KP的新方法。随后,将改进策略应用于二进制GTOA(GTOA-2),提出了增强型GTOA-2(EGTOA-2)及其求解D{0-1}KP的新方法。为了验证EGTOA和EGTOA-2的性能提高程度与优异性,分别利用它们求解四类大规模D{0-1}KP实例,通过与GTOA、GTOA-2以及求解D{0-1}KP的已有8个最先进算法的比较表明:EGTOA和EGTOA-2求得最优解的能力比GTOA和GTOA-2提高了至少1.14倍,比8个最先进算法提高了5%~60%,它们的平均性能比GTOA、GTOA-2以及8个最先进算法的性能更佳。因此,EGTOA和EGTOA-2是当前求解D{0-1}KP的最佳算法。

带冲突图的着色旅行商问题模型与算法

着色旅行商问题是多旅行商问题的一个重要变种,它被广泛地应用于带有重叠区域的多机工程系统。现有的着色旅行商问题难以有效应对带冲突的场景,这种冲突通常表现为两个城市不允许被同一旅行商访问。受带冲突图的组合优化问题的启发,提出了带冲突图的着色旅行商问题,且给出了其形式化的表达。带冲突图的着色旅行商问题是一个NP难问题,精确算法求解器CPLEX仅能在小规模问题实例上获得问题的最优解。为了求解更大规模的实例,提出了一个有效的模因算法。该模因算法采用了自适应大规模邻域搜索算子。对比模因算法和精确算法,模因算法在20个小规模实例中的9个结果更好,在18个实例上展现了其远超精确算法的求解速度。而比较模因算法和其他启发式算法,模因算法在全部14个中等规模实例上均取得了更好结果。此外,消融实验结果验证了模因算法中自适应大规模领域搜索算子的有效性。

特殊钢模铸生产中钢锭模组合优化研究

针对特殊钢的生产特点,提出求解特殊钢模铸生产过程中的钢锭模组合优化问题的方法,该方法将钢锭模组合优化问题抽象为背包问题,并使用动态规划算法和递归回溯算法进行求解,能快速计算具有最优锻造比的钢锭模组合方案,还能计算所有满足要求的钢锭模组合,同时考虑了出钢量与电炉生产能力是否匹配的问题。通过对生产实例进行试验,验证了该方法的有效性,能够在一定程度上满足特殊钢企业的实际应用需求,对实际生产具有一定的指导意义。

二维矩形Strip Packing问题的算法研究与改进

二维矩形Strip Packing问题的约束条件及目标函数与基本型二维矩形Packing问题类似,都是在有限的矩形容器中,有效地摆放各个矩形块,以最大化容器利用率为目标。为了解决这一NP-hard问题,该文在邓见凯、王磊提出的拟人型全局优化算法的基础上进行了深入的算法研究与改进。针对Strip Packing问题特点,提出了QHG(Quasi-Human Group)算法,其核心改进涵盖了多个方面,包括扩充初始点集合、删除和替换评价标准以及扩大邻域空间搜索范围。和单个局部极小值点的迭代相比,对局部极小值点集合进行迭代所生成布局优度更高,跳坑策略用于跳出局部极小值点,将搜索引向有希望的区域,优美度枚举有望进一步提高布局优度。通过这些措施,QHG算法更好地模拟人类决策过程,提高了全局搜索的效率。为评估QHG算法性能,对8组标准问题实例(C组、N组、NT组、CX组、NP组、ZDF组、2sp组、bwmv组)进行了大量实验。实验结果表明,QHG算法生成的布局优度优于当前国际文献中的几种较先进算法,展现了其在Strip Packing问题上的卓越性能。

基于量子压缩的相干光计算系统

相干光计算是一种基于量子光学的非冯诺依曼框架的专用计算方法,是有望在后摩尔时代突破计算性能与功耗瓶颈的热门计算技术。相干光计算的核心思想是根据最小增益原理,通过从振荡阈值以下逐渐增加简并光学参量振荡器中泵浦光的强度,使得振荡器中最低能量的基态模式被激发,从而完成一种类似物理退火的过程。这种退火过程可被用于求解组合优化问题,并具备计算速度快、求解质量高和功耗低等优势。相干光计算机也被称为相干伊辛机(Coherent Ising Machines),可用于交通流分配、工业资源调度、金融投资组合等问题的快速高质量求解,是量子计算硬件的重要研究方向。本文作为“先进算力技术”专题的第二篇,介绍了相干光计算和相干伊辛机的基本原理、历史发展以及实验系统。本文不仅可以作为未来计算技术领域的一般性了解,本文附录给出的PPT课件也可以作为大学物理等课程中“量子物理”相关篇章的有益补充。

精英群体引导遗传算法求解车辆路径问题

为了改善遗传算法在求解车辆路径问题时容易陷入局部最优和运算量大的问题,通过提升种群质量,形成以精英群体引导种群快速进化策略。改进传统遗传算法的交叉、变异和选择操作,以更多群体选择性提高进化效率。在6个TSPLIB标准库基准问题上和实际问题验证所提出的算法的可行性和有效性,实验结果表明:基于精英群体引导的遗传算法可有效地避免陷入局部最优解,提高了种群收敛速度,在求解的准确率、稳定性上都具有优势。

融合分解和自适应邻域的多目标离散组合优化算法

为了高效获取现实中大规模多目标优化问题解决方案,实现收敛性、多样性和均匀性的平衡逐渐发展为多目标优化的重要目标之一。针对复杂多目标离散组合优化问题,提出了融合分解和自适应邻域的多目标离散组合优化算法(MOALNS)。该算法在问题分解的基础上为各子问题的寻优进程引入大邻域搜索策略与自适应调整机制,形成一套新型的收敛指导准则突破寻优阻力,进而使各子问题在搜索多维解空间的过程中达到全局搜索与局部搜索的平衡。同时,提出为各子问题配置独立算子积分库可有效地调整各子问题的寻优方向,解决由于目标权重不同而造成的求解方向偏差问题,以此实现更为高效、稳定的多目标优化进程。数值实验表明,提出的新型多目标离散组合优化算法在多组标准测试算例与真实案例中均展现出了在收敛性、多样性、均匀性和延展性等方面的良好性能,相较于其他经典多目标优化算法而言更具优势。

机会约束的多选择背包问题的遗传算法求解

机会约束的多选择背包问题(CCMCKP)是一类具有重要应用价值的NP难组合优化问题,但目前还缺乏关于该问题求解方法的专门研究。为此,提出首个CCMCKP的求解框架,并基于该框架构建了两种求解方法:基于动态规划的RA-DP和基于遗传算法的RA-IGA。RA-DP是精确求解方法,具有最优性保证,但是在可接受的时间(1 h)内仅能求解小规模问题样例;相较而言,RA-IGA是近似求解方法,具有更好的可扩放性。仿真实验结果验证了所提求解方法的性能:在小规模问题样例上,RA-DP和RA-IGA都可以找到最优解;在中大规模问题样例上,RA-IGA表现出了比RA-DP显著更高的求解效率,它总是可以在给定时间(1 h)内快速获得可行解。在CCMCKP的后续研究中,RA-DP和RA-IGA可作为基准对比方法,而实验工作中所构建的测试样例集可作为该问题的标准测试集。

基于鲁棒性模拟的停机位分配问题的数值方法比较

为了提升机场停机坪分配的鲁棒性,针对大型国际机场航班延误常态化对机场运行稳定性的影响,构建了两种整数线性规划模型,并引入爬山算法与大邻域搜索(LNS)元启发式算法进行效能比较。同时,采用Monte Carlo方法对不同目标函数在处理航班冲突时的效果进行评估。测试结果表明LNS算法在提升大型机场停机位分配方案的鲁棒性方面表现卓越,在求解速度和方案质量上均有显著提升。特别是,当以空闲时间的平方作为目标函数时,其效果尤为突出。