人工智能：智能优化算法
**
人工智能：智能优化算法优化问题是指在满足一定条件下，在众多方案或参数值中寻找最优方案或参数值，以使得某个或多个功能指标达到最优，或使系统的某些性能指标达到最大值或最小值。优化问题广泛地存在于信号处理、图像处理、生产调度、任务分配、模式识别、自动控制和机械设计等众多领域。优化方法是一种以数学为基础，用于求解各种优化问题的应用技术。各种优化方法在上述领域得到了广泛应用，并且已经产生了巨大的经济效益和社会效益。实践证明，通过优化方法，能够提高系统效率，降低能耗，合理地利用资源，并且随着处理对象规模的增加，这种效果也会更加明显。在电子、通信、计算机、自动化、机器人、经济学和管理学等众多学科中，不断地出现了许多复杂的组合优化问题。面对这些大型的优化问题，传统的优化方法（如牛顿法、单纯形法等）需要遍历整个搜索空间，无法在短时间内完成搜索，且容易产生搜索的“组合爆炸”。例如，许多工程优化问题，往往需要在复杂而庞大的搜索空间中寻找最优解或者准最优解。鉴于实际工程问题的复杂性、非线性、约束性以及建模困难等诸多特点，寻求高效的优化算法已成为相关学科的主要研究内容之一。受到人类智能、生物群体社会性或自然现象规律的启发，人们发明了很多智能优化算法来解决上述复杂优化问题，主要包括：模仿自然界生物进化机制的遗传算法；通过群体内个体间的合作与竞争来优化搜索的差分进化算法；模拟生物免疫系统学习和认知功能的免疫算法；模拟蚂蚁集体寻径行为的蚁群算法；模拟鸟群和鱼群群体行为的粒子群算法；源于固体物质退火过程的模拟退火算法；模拟人类智力记忆过程的禁忌搜索算法；模拟动物神经网络行为特征的神经网络算法；等等。这些算法有个共同点，即都是通过模拟或揭示某些自然界的现象和过程或生物群体的智能行为而得到发展；在优化领域称它们为智能优化算法，它们具有简单、通用、便于并行处理等特点。**
1进化类算法****自然界的生物体在遗传、选择和变异等一系列作用下，优胜劣汰，不断地由低级向高级进化和发展，人们将这种“适者生存”的进化规律的实质加以模式化而构成一种优化算法，即进化计算。进化计算是一系列的搜索技术，包括遗传算法、进化规划、进化策略等，它们在函数优化、模式识别、机器学习、神经网络训练、智能控制等众多领域都有着广泛的应用。其中，遗传算法是进化计算中具有普遍影响的模拟进化优化算法。为了求解切比雪夫多项式问题，RainerStorn和KennethPrice根据这种进化思想提出了差分进化算法。它是一种采用实数编码、在连续空间中进行随机搜索、基于群体迭代的新兴进化算法，具有结构简单、性能高效的特点。而免疫算法是模仿生物免疫机制，结合基因的进化机理，人工地构造出的一种新型智能搜索算法。该算法具有一般免疫系统的特征，它采用群体搜索策略，通过迭代计算，最终以较大的概率得到问题的最优解，相当于属于进化算法的变种算法。
1.1遗传算法遗传算法（GeneticAlgorithm，GA）是模拟生物在自然环境中的遗传和进化过程而形成的自适应全局优化搜索算法。它最早由美国的J.H.Holland教授提出，起源于20世纪60年代对自然和人工自适应系统的研究；70年代，K.A.DeJong基于遗传算法的思想，在计算机上进行了大量的纯数值函数优化计算试验；80年代，遗传算法由D.J.Goldberg在一系列研究工作的基础上归纳总结而成。遗传算法是通过模仿自然界生物进化机制而发展起来的随机全局搜索和优化方法。它借鉴了达尔文的进化论和孟德尔的遗传学说，本质上是一种并行、高效、全局搜索的方法，它能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。遗传算法操作：使用“适者生存”的原则，在潜在的解决方案种群中逐次产生一个近似最优的方案。在每一代中，根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比原个体更能适应环境。
1.2差分进化算法差分进化算法（DifferentialEvolution，DE）是一种新兴的进化计算技术。它由Storn等人于1995年提出，其最初的设想是用于解决切比雪夫多项式问题，后来发现差分进化算法也是解决复杂优化问题的有效技术。差分进化算法是基于群体智能理论的优化算法，是通过群体内个体间的合作与竞争产生的智能优化搜索。但相比于进化计算，差分进化算法保留了基于种群的全局搜索策略，采用实数编码、基于差分的简单变异操作和“一对一”的竞争生存策略，降低了进化计算的复杂性。同时，差分进化算法特有的记忆能力使它可以动态跟踪当前的搜索情况，以调整其搜索策略，它具有较强的全局收敛能力和稳健性，且不需要借助问题的特征信息，适用于求解一些利用常规的数学规划方法很难求解甚至无法求解的复杂优化问题。
1.3免疫算法最早的免疫系统模型是由Jerne于1973年提出的，他基于Burnet的克隆选择学说，开创了独特型网络理论，给出了免疫系统的数学框架，并采用微分方程建模来仿真淋巴细胞的动态变化。Farmal等人于1986年基于免疫网络学说理论构造出免疫系统的动态模型，展示了免疫系统与其他人工智能方法相结合的可能性，开创了免疫系统研究的先河。免疫算法（ImmuneAlgorithm，IA）是模仿生物免疫机制，结合基因的进化机理，人工构造出的一种新型智能搜索算法。免疫算法具有一般免疫系统的特征，采用群体搜索策略，通过迭代计算，最终以较大的概率得到问题的最优解。相比较于其他算法，免疫算法利用自身产生多样性和维持机制，保证了种群的多样性，克服了一般寻优过程中（特别是多峰值的寻优过程中）不可避免的“早熟”问题，可求得全局最优解。免疫算法具有自适应性、随机性、并行性、全局收敛性、种群多样性等优点。**
2群智能算法**群智能指的是“无智能的主体通过合作表现出智能行为的特性”，是一种基于生物群体行为规律的计算技术。它受社会昆虫（如蚂蚁、蜜蜂）和群居脊椎动物（如鸟群、鱼群和兽群）的启发，用来解决分布式问题。它在没有集中控制并且不提供全局模型的前提下，为寻找复杂的分布式问题的解决方案提供了一种新的思路。群智能方法易于实现，其算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法只需要目标函数的输出值，而不需要其梯度信息。已完成的群智能理论和应用方法研究证明：群智能方法是一种能够有效解决大多数全局优化问题的新方法。近年来群智能理论研究领域出现众多算法，如：蚁群算法、粒子群算法、鱼群算法、蜂群算法、猫群算法、狼群算法、鸡群算法、鸟群算、文化算法、杂草算法、蝙蝠算法、布谷鸟算法、果蝇算法、蛙跳算法、细菌觅食算法、萤火虫算法和烟花算法，等等。其中蚁群算法和粒子群算法是最主要的两种群智能算法。群智能理论研究领域有两种主要的算法：蚁群算法和粒子群算法。前者是对蚂蚁群体食物采集过程的模拟，已成功应用于许多离散优化问题；后者起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化算法。
2.1蚁群算法蚁群算法（AntColonyOptimization，ACO）是由意大利学者M.Dorigo、V.Maniezzo和A.Colorni等人于20世纪90年代初期通过模拟自然界中蚂蚁集体寻径行为而提出的一种基于种群的启发式随机搜索算法，是群智能理论研究领域的一种主要算法。蚂蚁有能力在没有任何提示的情形下找到从巢穴到食物源的最短路径，并且能随环境的变化，自适应地搜索新的路径。其根本原因是蚂蚁在寻找食物时，能在其走过的路径上释放一种特殊的分泌物——信息素。随着时间的推移，该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上信息素的强度成正比。当一条路径上通过的蚂蚁越来越多时，其留下的信息素也越来越多，后来的蚂蚁选择该路径的概率也就越高，从而更增加了该路径上的信息素强度。而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。通过这种正反馈机制，蚂蚁最终可以发现最短路径。蚁群算法具有分布式计算、无中心控制和分布式个体之间间接通信等特征，易于与其他优化算法相结合。它通过简单个体之间的协作，表现出了求解复杂问题的能力，已经广泛应用于优化问题的求解。
2.2粒子群算法粒子群算法（ParticleSwarmOptimization，PSO）是Kennedy和Eberhart受人工生命研究结果的启发，通过模拟鸟群觅食过程中的迁徙和群聚行为而提出的一种基于群体智能的全局随机搜索算法；1995年IEEE国际神经网络学术会议上发表了题为“ParticleSwarmOptimization”的论文，标志着粒子群算法的诞生。粒子群算法一经提出，由于它算法简单，容易实现，立刻引起了进化计算领域学者们的广泛关注，成为一个研究热点。粒子群算法与其他进化算法一样，也是基于“种群”和“进化”的概念，通过个体间的协作与竞争，实现复杂空间最优解的搜索。同时，它又不像其他进化算法那样对个体进行交叉、变异、选择等进化算子操作，而是将群体中的个体看成是在D维搜索空间中没有质量和体积的粒子，每个粒子以一定的速度在解空间运动，并向自身历史最佳位置pbestpbest和邻域历史最佳位置gbestgbest聚集，实现对候选解的进化。粒子群算法因具有很好的生物社会背景而易于理解，由于参数少而容易实现，对非线性、多峰问题均具有较强的全局搜索能力，在科学研究与工程实践中得到了广泛关注。**
3模拟退火算法**模拟退火算法（SimulatedAnnealing，SA）的思想最早由Metropolis等人于1953年提出。Kirkpatrick于1983年第一次使用模拟退火算法求解组合最优化问题。模拟退火算法是一种基于MonteCarlo迭代求解策略的随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。其目的在于：为具有NP（Non-deterministicPolynomial）复杂性的问题提供有效的近似求解算法，它克服了传统算法优化过程容易陷入局部极值的缺陷和对初值的依赖性。模拟退火算法是一种通用的优化算法，是局部搜索算法的扩展。它与局部搜索算法的不同之处，是以一定的概率选择邻域中目标值大的状态。从理论上来说，它是一种全局最优算法。模拟退火算法具有十分强大的全局搜索性能，这是因为它采用了许多独特的方法和技术：基本不用搜索空间的知识或者其他的辅助信息，而只是定义邻域结构，在邻域结构内选取相邻解，再利用目标函数进行评估；采用概率的变迁来指导它的搜索方向，它所采用的概率仅仅是作为一种工具来引导其搜索过程朝着更优化解的区域移动。因此，虽然看起来它是一种盲目的搜索方法，但实际上有着明确的搜索方向。
**
4禁忌搜索算法**搜索是人工智能的一个基本问题，一个问题的求解过程就是搜索。人工智能在各应用领域中，被广泛地使用。现在，搜索技术渗透在各种人工智能系统中，可以说没有哪一种人工智能的应用不用搜索技术。禁忌搜索算法（TabuSearchorTabooSearch，TS）的思想最早由美国工程院院士Glover教授在1986年提出，并在1989年和1990年对该方法做出了进一步的定义和发展。在自然计算的研究领域中，禁忌搜索算法以其灵活的存储结构和相应的禁忌准则来避免迂回搜索，在智能算法中独树一帜，成为一个研究热点，受到了国内外学者的广泛关注。禁忌搜索算法是对局部邻域搜索的一种扩展，是一种全局逐步寻优算法，是对人类智力过程的一种模拟。它通过禁忌准则来避免重复搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效搜索，以最终实现全局优化。
**
5神经网络算法**人工神经网络（ArtificialNeuralNetwork，ANN）简称为神经网络或称为连接模型。早在1943年，心理学家McCulloch和数学家Pitts合作提出了形式神经元的数学模型，从此开创了神经科学理论研究的时代；1957年Rosenblatt提出的感知器模型，由阈值性神经元组成，试图模拟动物和人脑的感知和学习能力；1982年H.Hofield提出了具有联想记忆功能的Hopfield神经网络，引入了能量函数的原理，给出了网络的稳定性判据，这一成果标志着神经网络的研究取得了突破性的进展。神经网络具有一些显著的特点：具有非线性映射能力；不需要精确的数学模型；擅长从输入输出数据中学习有用知识；容易实现并行计算；由大量的简单计算单元组成，易于用软硬件实现；等等。因为神经网络是一种模仿生物神经系统的新的信息处理模型，并具有独特的结构，所以人们期望它能够解决一些用传统方法难以解决甚至无法解决的问题。迄今为止，已经出现了许多神经网络模型及相应的学习算法。其中Rumelhart和McClelland于1985年提出的BP网络的误差反向后传（BackPropagation，BP）学习算法是一种最常用的神经网络算法。
**
参考文献**《智能优化算法及其MATLAB实例（第2版）》，包子阳，电子工业出版社。
人工智能前沿：组合优化问题的机器学习求解
2）启发式算法，包括近似算法、贪婪算法等，这类算法优点是存在最差解的质量保证，缺点是求解时间比较长，并且这类近似算法很难构造；
3）元启发式算法，如遗传算法、蚁群算法、模拟退火算法等，这类算法优点是比较容易实现，求解时间也不会太长，很快得到一个可行解，缺点在于该类算法对参数比较敏感，不同的实例都需要重新调整参数；
4)机器学习方法，包括监督学习、强化学习以及图神经网络等，该类方法优点是能从同分布的数据中学习到通用的规律，能快速求解同一类问题。
总之，前三类算法可以看成是人类学习如何去设计算法，该类算法规模适中、模型相对稳定、能求解一些经典问题同时也存在理论保证，而最后一类方法是通过机器学习方法去学习如何设计组合优化算法，该类算法能求解超大规模问题，是实时变化的，能处理复杂系统，唯一的缺点是该类算法是一种弱最优性。除了上述四类优化算法以外，也存在一些组合优化的求解器，包括商用求解器，Gurobi、CPLEX等以及开源求解器，SCIP以及LP_Solve等。
目前机器学习组合优化是人工智能的前沿方向，可以通过使用不同的机器学习方法来解决不同的组合优化问题，如图优化以及离散优化等。
图1组合优化与机器学习
目前组合优化问题的机器学习求解范式可以分为两类：
1）基于端到端求解，输入是问题的实例输出是问题的结果，使用自回归或者非自回归的方法学习一些启发式的策略；
2）局部改进求解，包括改进精确算法或者启发式算法等，将这些算法中比较耗时的模块转换成一个学习问题，从而加快求解的速度，如对于分支定界算法，可以将传统的使用强连通量进行分支转换成一个二分类的学习问题。
什么是组合优化|集智百科
什么是组合优化|集智百科
二、图上的组合优化问题求解
图上的组合优化问题是组合优化问题中很重要的部分，很多图上的组合优化问题都是NPC问题，只要证明任意一个NPC问题存在精确的多项式算法，那么所有的NP问题就都解决了，那么P=NP。
什么是P问题、NP问题和NPC问题？
什么是P问题、NP问题和NPC问题？
图上的组合优化问题的一般性求解框架具体分为两个阶段：第一个阶段进行图的表示学习，学习节点或边的表示向量；第二个阶段基于表示向量求解组合优化问题，可以使用非自回归方法结合启发式搜索规则，或者基于强化学习的自回归进行优化求解。下面分别具体介绍这两类方法。
图2组合优化问题的一般性求解框架
1.非自回归方法
CombinatorialOptimizationwithGraphConvolutionalNetworksandGuidedTreeSearch
https://arxiv.org/abs/1810.10659
CombinatorialOptimizationwithGraphConvolutionalNetworksandGuidedTreeSearch
https://arxiv.org/abs/1810.10659
该论文尝试解决最小支配集、最小节点覆盖以及最大割这样的NPC问题，使用监督学习算法结合树搜索以及图论技巧来学习。具体来说，模型输入一个图，然后对图进行约简，将约简后的等价图输入GCN中学习每个节点选中与否的概率，然后结合树搜索算法以及图论的局部搜索算法选择最优的结果，输出图中的每个节点是否被选中。损失函数是一个交叉熵损失，表示第i个训练图的第j个节点的标签，表示GCN输出的第j个节点选中与否的概率。为了解决组合优化解不唯一的情况，作者使用hindsightloss优化GCN输出多个loss的最小值。其中通过后面的实验发现图论技巧对于性能的提升占了很大比重，去掉局部搜索的技巧，预测的性能显著降低。但是该类算法的缺点在于泛化效果比较差，除非加很多领域的专业技巧才能提高性能。
图3基于图卷积网络和引导树搜索的组合优化算法流程图
2.自回归方法
第二类为自回归算法，其框架主要就是结合图表示学习和强化学习来优化目标。下面主要介绍三个工作，S2V-DQN(NIPS2017)、FINDER(NMI2020)以及DIRAC(NC2023)。
S2V-DQN
KhalilE,DaiH,ZhangY,etal.Learningcombinatorialoptimizationalgorithmsovergraphs[J].Advancesinneuralinformationprocessingsystems,2017,30.
KhalilE,DaiH,ZhangY,etal.Learningcombinatorialoptimizationalgorithmsovergraphs[J].Advancesinneuralinformationprocessingsystems,2017,30.
该工作是机器学习组合优化领域的里程碑式工作，引领并启发了该领域后续许多的研究。该方法的整体框架是输入一个图，然后使用多层的GraphEmbedding方法得到每个节点的表示向量，然后通过Q-Learning算法为每个节点算一个Q-value作为节点选择的长期收益，收益最大的节点被选中，然后重复GraphEmbedding和Q-Learning直到满足终止条件。其中这里的GraphEmbedding使用Struct2Vector算法。
算法训练过程主要包括四个部分：1）生成训练图数据；2）探索和利用选择节点；3）更新节点的状态；4）构建损失函数优化模型参数。该方法在最小节点覆盖、最大割以及旅行商问题中进行了实验。在最小节点覆盖实验中，相比CPLEX求解器得到的最优解，该方法的性能几乎接近最优解，同时该方法也具有很好的泛化性，在小规模图中进行训练，然后可以用来在大图中进行测试。在最大割问题中，相比于基准算法来说也是更优的。在TSP问题中,对于大图的优化性能稍微逊色些。
图4S2V-DQN算法流程图
通过可视化的方式对算法进行可解释分析，发现相比其他算法，如每步选择节点度最大的节点，该算法每次都倾向于选择那些能覆盖更多节点，同时避免破坏连通性的节点，从长远看，需要的节点更少，这也正是强化学习的优势，可以启发我们选择更加高效的贪婪算法。该算法提供了一个统一框架，适用多种图上的组合优化问题。
FINDER
FanC,ZengL,SunY,etal.Findingkeyplayersincomplexnetworksthroughdeepreinforcementlearning[J].Naturemachineintelligence,2020,2(6):317-324.
论文解读：用强化学习寻找关键节点——复杂网络研究新范式
FanC,ZengL,SunY,etal.Findingkeyplayersincomplexnetworksthroughdeepreinforcementlearning[J].Naturemachineintelligence,2020,2(6):317-324.
论文解读：用强化学习寻找关键节点——复杂网络研究新范式
虽然S2V-DQN方法已经具有很好的优化效果，但是在更大规模上的泛化能力还有待提高。因此，范长俊等人提出一种通用且可扩展的深度学习求解框架，适用于不同的瓦解场景，同时继续提升了模型的泛化能力，使得模型能在上千万节点规模的网络中都能有很好的性能。该工作尝试在网络瓦解问题上面实验，希望找到能使网络瓦解的最少节点集合。其中衡量模型的好坏可以使用ANC曲线下的面积来表示，纵轴表示复杂网路功能，横轴表示移除节点的比例。复杂网络功能又可以使用结构性功能指标（包括最大连通片规模等）和非结构性功能指标（如军事中的体系预警规模等）来衡量。
FINDER算法的框架同样采取了类似S2V-DQN这种结合图表示学习和强化学习的算法框架，但是存在一些不同，区别如下所示:
主要区别S2V-DQNFINDER节点表示Struct2VecGraphSAGE状态表示简单的节点嵌入之和表示状态引入虚拟节点表示状态动作值函数Q计算状态和动作向量的拼接状态和动作向量的交叉积训练损失函数贝尔曼损失贝尔曼损失加上图重构损失测试策略一步测试选择一个节点一步测试选择一批节点对于实验部分，作者使用两种连通性的计算方法（CN，ND）以及三种节点赋权方式（无权、度权以及随机权），共六种实验场景。在六种不同的网络瓦解场景中效果平均提升28.7%。此外，该方法具有很好的泛化能力，可以使用小规模模拟图上训练的模型来测试大规模真实的网络，这说明模型学到了网络瓦解的内在的策略。同时FINDER的计算效率也提升超过两个数量级，FINDER算法自己发现了更快瓦解复杂网络的策略。在加权网络中，FINDER优先选择cost-effective的节点，即代价不那么大，却能达到相同的瓦解效果。
DIRAC
FanC,ShenM,NussinovZ,etal.Searchingforspinglassgroundstatesthroughdeepreinforcementlearning[J].NatureCommunications,2023,14(1):725.
论文解读：Nat.Commun.前沿：深度强化学习搜索自旋玻璃基态
FanC,ShenM,NussinovZ,etal.Searchingforspinglassgroundstatesthroughdeepreinforcementlearning[J].NatureCommunications,2023,14(1):725.
论文解读：Nat.Commun.前沿：深度强化学习搜索自旋玻璃基态
该工作尝试提出一种强化学习方法（DIRAC）来解决自旋玻璃的基态求解问题，确定最优的节点状态使得目标函数值最低，其中目标函数为表示节点i的状态，每条边的权重，直线表示正权边，折线表示负权边，边的宽度与
呈正比，蓝色阴影部分表示边的能量
。
该方法同样基于图表示学习与强化学习框架，其中每个部分都有小的改动以适用自旋玻璃的基态求解问题。其中，基态求解问题受边权的影响很大，边权直接影响最终基态的分布，所以这里采用两阶段的嵌入方式，首先基于两端节点的嵌入向量更新边的嵌入向量，然后再基于相邻的边的表示更新节点的表示，这种方式能更好地捕捉边的特征与权重。
此外，最关键的是添加了规范变换的技巧（Gaugetransformation）。引入变换在于，传统的强化学习工作流程存在缺点，只能从某个状态出发，逐步增加元素（动作选择）构建解集，直到满足终止条件，每个节点选择且只能选择一次，但是，这种方式最大的问题在于动作不可重复选择，即只能产生单个“最佳猜测”。然而，组合优化问题巨大的探索空间要求智能体能够重复多次“试错探索”以避免陷入局部最优，该工作提出的规范变换能够将任意状态转化为指定的状态，从而适合智能体的重复探索。规范变换带来如下好处：1）允许模型在一次探索（DIRAC1）结束后接着继续探索（DIRACm）；2）允许模型从多个不同初态出发，从而取得更优的结果；3）允许模型和任意启发式算法结合，从而进一步提高启发式算法的结果；对性能的提升作用很大。
图5自旋玻璃的基态示意图
实验结果上，在大尺寸系统中（基态未知），DIRAC相比目前最先进的退火算法，可以取得更低的能量。在小尺寸系统中（基态已知），DIRAC均能求出全局最优解。此外，通过模型的可解释分析发现，该模型是通过牺牲短期收益，获取长远收益，这也是强化学习的优势所在。
该问题是揭开自旋玻璃奇怪而复杂行为的关键，有助于解决许多组合优化难题，有助于神经网络优化工具的开发。该算法具有以下优点：1）精度高，中等尺寸的系统可以达到全局最优解，且适用于三维及以上的高维系统；2）可扩展性强，最大系统尺寸达到三维的L=20，这是目前研究最大的系统；3）可以和任意退火算法等启发式算法结合，并进一步提高这些算法的表现。
总之自回归方法中基于图表示学习加上强化学习是目前一种主流的研究范式，优点在于模型泛化性能好、模型效果好且具有一定的可解释性。但是存在模型设计、学习难以及实现困难等缺点。因此，作者也正在开发一种基于图表示学习和深度强化学习的图上组合优化问题求解工具（OptiGNN）来降低我们的学习门槛。
三、研究进展
1.如何与精确算法结合？
SolvingMixedIntegerProgramsUsingNeuralNetworks
https://arxiv.org/abs/2012.13349
SolvingMixedIntegerProgramsUsingNeuralNetworks
https://arxiv.org/abs/2012.13349
对于求解混合整数规划问题（MIP），最常见的精确算法就是分支定界算法，然而对于具体如何分支计算是很复杂的，传统的方法都是把它松弛到线性规划，然后用线性规划求边界，再选择相应的值。然而这样的方法计算量就非常大。现在可以使用机器学习方法把分支问题看成是一个二分类问题。如DeepMind提出用神经网络求解混合整数规划，包括NeuralDiving以及NeuralBranching两个部分，NeuralDiving训练一个深度神经网络来产生MIP问题部分整数变量的赋值，剩余未赋值的变量定义了一个更小的“子MIP”，这个子问题使用现成的MIP求解器（如SCIP）来求解，进而产生一个高质量的联合变量赋值；NeuralBranching训练一个深度神经网络，在经典求解器进行分支定界的过程中，针对给定节点模仿专家的分支变量选择策略进行分支变量的选择。
具体来说，可以将MIP建模为一个二部图，决策变量和约束看成图中的两类节点，其中变量前的系数和约束作为节点和边的特征。然后使用图神经网络生成部分解，具体来说可以将构建的二部图输入图卷积神经网络得到每个节点的表示向量，接着经过MLP输出各个变量为某个值的概率。此外，在分支定界过程中，为了提高决策质量，使用模仿学习，来学习strongbranching的专家经验。模型在速度和精度均取得出色的表现。
图6神经MIP求解器算法流程图
2.如何与启发式算法结合？
Mills,KyleandRonagh,PooyaandTamblyn,Isaac.FindingthegroundstateofspinHamiltonianswithreinforcementlearning.NatureMachineIntelligence,2020.
Mills,KyleandRonagh,PooyaandTamblyn,Isaac.FindingthegroundstateofspinHamiltonianswithreinforcementlearning.NatureMachineIntelligence,2020.
该工作尝试结合启发式算法解决自旋玻璃的基态求解问题，我们知道对于模拟退火方法，有个关键问题就是温度如何下降，为了克服这个问题，该方法利用强化学习学习模拟退火算法的最佳退火策略，然后使用最佳退火策略来求解自旋玻璃的基态。然而，该方法的实验结果并没有那么好。
图7基于强化学习寻找自旋哈密顿量的基态算法流程图
3.如何提高在大规模实例的泛化表现？
GeneralizeaSmallPre-trainedModeltoArbitrarilyLargeTSPInstances
https://ojs.aaai.org/index.php/AAAI/article/view/16916
GeneralizeaSmallPre-trainedModeltoArbitrarilyLargeTSPInstances
https://ojs.aaai.org/index.php/AAAI/article/view/16916
对于如何提高大模型实例的泛化能力，下面讲解两个工作：
第一个工作使用监督学习解决经典的TSP问题，文章提出的是一种混合算法，级联了SL和RL模块。SL模块运用预训练的模型与三种图技巧（包括图采样、图转换、图合并）为任意规模的TSP构建热力图。热力图刻画了节点之间每条边属于该TSP最优环游的概率。随后，热力图将作为RL模块的重要输入。RL算法将进一步使用蒙特卡洛搜索寻找最优解，输出TSP的最优环游。该工作具有很好的泛化能力具体体现在如下操作，训练一个小规模网络的预训练模型，对于任意大规模的图输入都可以通过对图进行采样构建子图，然后分别通过学习好的预训练模型，最后将子图合并成原始的大图，解决了训练和测试图的尺寸不一致的情况。但是该方法应用也有限，该方法无法与强化学习方法进行结合。
图8解决TSP算法的流程图
第二个工作是前文提到的FINDER算法框架。在FINDER方法中，作者也尝试使用配置模型来提高模型的泛化能力，即定制匹配目标网络的训练数据，可以根据目标网络的度分布采样构建一个小规模图，然后在这些生成的图上训练模型。实验发现该方法能提升一些性能但是提升不是很大，同时针对特定的网络都要重新训练增加了模型计算量。
总之，这两个工作一定程度上提升了大模型的泛化能力，但是也带来了计算量的增加等问题，需要进一步的完善。
4.如何处理复杂的约束？
DC3:Alearningmethodforoptimizationwithhardconstraints
https://arxiv.org/abs/2104.12225
DC3:Alearningmethodforoptimizationwithhardconstraints
https://arxiv.org/abs/2104.12225
DC3这个工作尝试解决带有复杂约束的优化问题，这里的变量都是连续的，同时存在等式约束以及不等式约束。具体来说，如果决策变量有N个，同时存在M个等式约束，那么一开始我们使用神经网络先求得N-M个符合要求的解，然后使用等式约束求出其余的变量值，同时使用不等式约束来修正得到的解，最后计算损失函数反向更新参数来优化模型，其中损失函数具体包括三部分：目标函数、不等式约束以及等式约束损失。该方法的优点在于计算时间非常快，缺点在于目前的约束还是停留在线性约束上面，如何拓展到非线性约束也是一大挑战。
图9DC3框架示意图
5.如何与成熟的求解器结合？
对于与成熟的求解器结合结合解决组合优化问题也是一大研究热点，下面具体介绍两个工作：
DifferentiationofBlackboxCombinatorialSolvers
https://openreview.net/forum?id=BkevoJSYPB
DifferentiationofBlackboxCombinatorialSolvers
https://openreview.net/forum?id=BkevoJSYPB
BlackBox这个工作尝试将组合优化求解器变成深度学习模型中的可微构建块。具体来说，由于一个输入如图像等经过神经网络会得到连续的表征，然而求解器需要离散的输入。因此，该工作的重点是考虑如何将连续的表征转换成求解器的输入，反向梯度更新时又能将求解器的离散输出转换为神经网络的连续输入，训练一个端到端的框架。该工作的优点在于如果需要求出图片中两个点之间的距离，只需要输入一张图片，不需要对图像进行栅格化等额外操作，模型直接输出两个点之间的最短路径。
图10黑盒组合求解器算法流程图
Networkplanningwithdeepreinforcementlearning
https://dl.acm.org/doi/10.1145/3452296.3472902
Networkplanningwithdeepreinforcementlearning
https://dl.acm.org/doi/10.1145/3452296.3472902
该工作提出一个两阶段的优化方法尝试结合深度强化学习与精确求解器（NeuroPlan）来解决一个资源调度问题。为了克服精确求解器无法求解大规模的优化问题的困难，作者将优化过程分为两个阶段：第一个阶段使用强化学习方法学习一个离最优解较近的结果，缩小搜索空间的范围；第二阶段使用精确求解器求得最优解。在小规模优化任务中，对比只使用强化学习的方法，该方法能有更好的优化效果，同时能媲美精确求解器方法。此外，在大规模优化任务中，该方法同样能取得了最好的优化效果，然而对于精确求解器来说，超出了其求解规模导致无法计算。
图11NeuroPlan的两阶段混合方法示意图
6.如何处理更自然的原始输入？
在与成熟的求解器结合的工作中，可以处理图像输入，那么随着ChatGPT的出现，其能够理解自然语言的问题需求，使得以后根据问题理解直接自动建模并调用求解器求解成为了可能。
扫码阅读并收藏完整斑图路径：
斑图链接：https://pattern.swarma.org/article/240
讲者介绍
范长俊：国防科技大学系统工程学院副教授。研究方向包括图深度学习、组合优化、强化学习及其在智能决策、复杂系统和指挥控制中的应用。以第一作者或通讯作者在NatureMachineIntelligence、NatureCommunications、AAAI等顶级期刊和会议发表论文多篇。
图神经网络与组合优化读书会启动
现实世界中大量问题的解决依赖于算法的设计与求解。传统算法由人类专家设计，而随着人工智能技术不断发展，算法自动学习算法的案例日益增多，如以神经网络为代表的的人工智能算法，这是算法神经化求解的缘由。在算法神经化求解方向上，图神经网络是一个强有力的工具，能够充分利用图结构的特性，实现对高复杂度算法的高效近似求解。基于图神经网络的复杂系统优化与控制将会是大模型热潮之后新的未来方向。
为了探讨图神经网络在算法神经化求解的发展与现实应用，集智俱乐部联合国防科技大学系统工程学院副教授范长俊、中国人民大学高瓴人工智能学院助理教授黄文炳，共同发起「图神经网络与组合优化」读书会。读书会将聚焦于图神经网络与算法神经化求解的相关领域，包括神经算法推理、组合优化问题求解、几何图神经网络，以及算法神经化求解在AIforScience中的应用等方面，希望为参与者提供一个学术交流平台，激发参与者的学术兴趣，进一步推动相关领域的研究和应用发展。读书会从2023年6月14日开始，每周三晚19:00-21:00举行，持续时间预计8周。欢迎感兴趣的朋友报名参与！
详情请见：
加速经典算法效率，突破现实技术瓶颈：图神经网络与组合优化读书会启动
大模型热潮之后的未来新方向：图神经网络与组合优化|文献汇总
1.解码薛定谔的猫：量子物理和人工智能的新颖交叉
2.人工智能的黎明：从信息动力学的角度看ChatGPT
3.智能是什么？范畴论为通用人工智能提供普适框架
4.《张江·复杂科学前沿27讲》完整上线！
5.成为集智VIP，解锁全站课程／读书会
6.加入集智，一起复杂！
点击“阅读原文”，观看读书会回放返回搜狐，查看更多
人工智能的本质是最优化过程
模型三要素为了将事物和问题转化为最优化问题数学模型我们需要考虑三个要素：因素变量、约束条件和目标函数。我们根据事物和问题先找到影响模型的所有因素变量，然后再根据目的建立一个目标函数用来衡量系统的效果，最后还要找到客观的限制条件并作为模型的约束。
公式如上公式，实际问题的因素变量其实可以看成是一个n维向量，向量的每个元素都是实数。f0(x)是我们构建的目标函数，我们的目标就是最小化该函数（最大化的情况其实也可以转化为最小化的情况）。fi(x)和hj(x)作为约束函数，分不等式约束和等式约束两类，约束函数用来限制可能空间，如果不存在约束则不需要约束函数。
目标函数人工智能的最优化最优化与人工智能有什么关系呢？可以这样说：人工智能在本质上也是一个最优化过程，对于我们要实现的智能，也是通过学习以求得最优解。这是一个总的大框架，人工智能的问题到最后几乎都是回到最优解问题。
不管是传统的机器学习还是大热的深度学习，亦或是大有潜力的强化学习，它们的基础核心思想都可以提升到最优化问题。
最优化有约束最优化前面提到过，最优化问题可能存在约束也可能不存在约束，而且有约束的情况比无约束的情况更加复杂。约束又可以分为不等式约束和等式约束两类，约束的作用就是将最优解的可能空间限制在某些区域。
纵使有了约束情况更加复杂，但我们还是有数学工具可以解决的。对于等式约束的情况，可以引入拉格朗日乘子来解决，可以将原来的目标函数和约束函数一起转化为拉格朗日函数。拉格朗日函数与原来的目标函数拥有共同的最优解，所以只要求解拉格朗日函数的最优解即可。对于不等式约束的情况，处理的方法也类似，只是需要额外满足KKT条件。
以下图为例，假设一共有四个约束条件，它们共同的限制区域为四条不同颜色限定的一个区域。假如上半部分为问题最优解的所有可能空间，而经过约束条件限制后则在区域中。
有约束无约束最优化无约束的情况一般采用梯度下降法来寻找最优解，所谓梯度是一个向量，梯度的方向就是函数在某点增长最快的方向，梯度的模为方向导数的最大值。而梯度下降的方向就是梯度的反方向，简单地看，梯度下降就好比站在一座山的某个位置上，往周围各个方向跨出相同步幅的一步，能够最快下降的方向。
无约束此外，采用梯度下降法寻找最优解时有可能会找到局部最优解，一旦陷入局部最优后则可能无法跳出来继续寻找全局最优。所以局部最优问题也需要考虑，工程上存在专门的方法用于防止掉进局部最优解。但有时局部最优解和全局最优解差别可能不会很大，而寻找全局最优将会花费很高的代价，此时可以不必关注是否为全局最优。
局部最优人工智能的主要处理流程
MongoDB用户管理操作隔壁de老樊:文章不错，nice
scrapy爬虫爬取完整小说shiyi123_:为什么我的只能爬取第一章的调试发现不能自动点击下一章循环求大佬分析
代理服务器搭建wuyuer1027:新的云都有限制了不行了，6核以上才能绑定3个公网10个要tmd48核
代理服务器搭建为谁攀登:我能用啊，你自己水平不行怪谁？？？
scrapy爬虫爬取完整小说Rookie23:如果我从第一页开始爬取，那么下一章的标签不是a[3]