量子视角下的智能优化算法综述

王 鹏，王 方

(1.西南民族大学计算机科学与工程学院 成都 610225；2.广东省国产服务器工程技术研究中心 广州 510535；3.中国科学院成都计算机应用研究所 成都 610041；4.中国科学院大学 北京 石景山区 100049)

量子力学诞生于20 世纪初，是在Einstein、Bohr、Schrödinger、Heisenberg 等一大批天才的物理学家的共同努力下建立起来的，这是人类历史上少有的由科学家群体共同努力建立的科学理论框架[1-2]。量子力学打破了人们从宏观世界获得的确定性世界观“常识”，为我们描述了一个被概率和不确定性统治的微观世界。物质世界的运动规律本质上是概率化的，电子双缝实验、波函数和不确定性关系等量子力学中的实验和理论都在不断地证明这一结论。量子力学揭示了物质世界本质的运动规律并被应用于各个技术领域，成为现代科学和技术的基石。同时量子力学的普遍适用性也在不断地得到证明，量子技术已成为一个国家科技实力的标志性技术，是继云计算、大数据、人工智能、区块链技术之后，我国未来的一个新的战略性新兴技术领域。

不少文章在表述量子算法时都有所混淆。算法主要概括为两种：1)采用物质的量子效应制造的量子计算机及其在上面运行的算法。这种算法主要又包括两类，一类是基于量子门的量子计算机及其算法[3-6]，另一类是基于量子退火原理的量子退火计算机及其算法[7-10]。其中量子退火计算机并不是通用量子计算机，它主要用于对优化问题的求解[11-12]。2)借鉴量子力学中的一些概念，如量子比特、量子门，将这些概念用于改进现有算法性能。这类算法还是运行在经典计算机上的，其所使用的量子特性可被认为仅仅是一种数学上的操作。本文所介绍的优化算法指的是后一种运行在经典计算机上的优化算法。

由于优化算法具有广泛的应用场景，经过长期发展，经历了百花齐放的过程。量子理论中的一些观点和方法在优化算法中也得到过成功的应用，但优化领域一直面临缺乏完备理论支持的问题，大量的优化算法模型特别是自然模型都在从各自的视角对优化算法进行解释。但由于这些自然模型往往缺乏完备的数学框架，所以一些自然模型所提出的理论框架事实上是人为“杜撰”的。量子力学是描述大自然最基础、最本质规律的一门学科，同时量子力学通过长期的发展已具备了完备的数学框架并被大量的实验所证明[13-14]，因此，将量子力学作为描述优化算法的物理模型是可行的。

量子视角下的智能优化算法研究有两个方向：

1) 将量子计算中一些概念和数学机制应用于已有的优化算法，其目的是提升现有算法的性能。如量子遗传算法(quantum-inspired genetic algorithms,QGA)利用量子位和量子叠加态对染色体进行编码，使一个染色体表示多个状态的信息的同时使用量子旋转门对种群进行更新，以当前最优个体的信息为引导进化[15]。在迭代过程中，每个量子位的叠加态将会塌缩到一个确定的状态，从而趋于稳定和达到收敛，最后实现寻优的目的。量子蚁群算法(quantum ant colony algorithm,QACA)将量子计算和蚁群算法相结合，把量子计算中的态矢量和量子旋转门引入到蚁群算法中，加速了算法的收敛速度[16]。量子人工鱼群算法(quantum artificial fish school algorithm,QAFSA)用量子计算的方法重新描述了人工鱼的行为，用量子比特对人工鱼进行编码，用量子旋转门实现人工鱼的更新操作，用量子非门进行人工鱼变异，从而实现了目标的优化求解[17]。该方向应用量子理论的目的不是为了解释智能优化算法，而只是单纯地将量子力学中的一些方法作为提升算法性能的手段。由于量子力学描述的是一个概率化的微观世界，量子机制通常都是概率化的，该方向的工作证明量子机制在智能优化算法中常常是有效的。目前在智能优化算法中使用的量子比特并不试图从量子力学的角度对智能优化算法做出解释，而仅被作为一种可以借鉴的编码机制。

2)基于智能优化算法和量子力学在概率行为上的相似性，将优化问题的目标函数视为量子系统中的约束势能，从而将优化问题转化为求量子系统的基态波函数问题。第二个方向的特点是将优化问题从模型上视为量子问题，这样量子力学的整个数学框架就能被应用于对智能优化算法的研究和分析，得到智能优化算法迭代过程中的基本动力学规律和基本操作。量子退火算法(quantum annealing algorithm,QAA)是这个研究方向的先驱，其利用Schrödinger 方程，对优化问题进行了初步的建模，提出了势能−优化问题等效的概念，量子退火算法利用量子力学的隧穿效应，在寻找全局最小值时更快地穿过局部极值点旁的势垒从而找到最优或接近最优的解[18]。多尺度量子谐振子算法(multi-scale quantum harmonic oscillator algorithm,MQHOA)也使用Schrödinger 方程[19]，将优化过程转换为在谐振子势约束下的多尺度退火过程[20]，利用多尺度的概念，实现了量子扰动的逐步减小和优化系统对基态能量的逼近。这样利用Schrödinger方程构建优化模型的方法还有量子粒子群算法(quantum-behaved particle swarm optimization,QPSO)，其利用Delta 势阱的假设，假设PSO 粒子群在虚拟的约束条件下运行，构建了其模拟量子优化系统[21-22]。

从当前研究情况来看，基于量子比特的智能优化算法研究已进行得相对充分，其主要应用场景是性能改进领域。而采用量子力学对智能优化算法进行建模，并利用量子力学的数学体系对智能优化算法进行研究目前尚处于初级阶段，是今后一个非常有前途的研究方向，将对解决智能优化算法领域当前的一些挑战具有建设性的作用。

本文结合智能优化算法的最新研究进展，对量子力学在智能优化算法中的应用进行综述。介绍了从基于量子比特的智能优化算法向智能优化算法的量子动力学发展的过程，重点对智能优化算法量子动力学当前取得的一些研究结果进行了介绍，并展望了未来的研究方向。

1 智能优化算法当前面临的挑战

优化问题是一类常见问题，在实际工程应用中有大量的问题都可被抽象为优化问题。求函数的最小值、寻找最优路线和神经网络算法中获得最优的连接权重值等，都可被视为优化问题。

以函数优化为例，从数学的角度，一维函数优化问题可以定义如下：

针对目标函数f(x)在 实数定义域 [a,b]上的优化问题，找到一个实数x0∈[a,b]，对于任意x∈[a,b]，满足f(x0)≤f(x)，则称x0为目标函数在实数定义域[a,b]的全局最优解。

以上定义是数学上对优化问题的一个确定性的定义。数学上的优化问题是要从理论上找到x0这一个确定的全局最优解。而从算法的视角来看函数优化问题则是将目标函数假设为黑盒。黑盒假设认为：目标函数的表达式f(x)是未知的，智能优化算法只能通过采样确定从目标函数定义域集合到值域集合中的每一个映射。每一次采样就是对黑盒进行的一次测量，测量的次数越多所获得的目标函数信息也越多。由于通常无法对目标函数定义域进行遍历，所以智能优化算法对目标函数f(x)全局最优解的位置的测量结果是不确定的，算法在运行过程中并不知道它是否找到了全局最优解。

回顾经典计算机上的智能优化算法的历史，其发展经历了一个黄金时期，遗传算法[23]、退火算法[24]、蚁群算法[25]和粒子群算法[26]等经典的方法都在这一时期被提出，并很快被广泛地应用于各个领域。随后，针对这些经典智能优化算法的改进研究也成为了该领域的研究热点，这使智能优化算法的性能得到了快速的提升，并开始向高维大规模问题进行挑战。受前期经典智能优化算法构造思路的启发，许多算法研究者不断地采用新的启发式模型并据此不断提出新的方法。很快智能优化算法领域变得百花齐放，每一个性能优良的新智能优化算法后面都有一批跟进的研究者，并形成一个又一个的研究团体和派别，此时智能优化算法的研究进入了鼎盛时期。

然而智能优化算法研究的隐忧却也在逐渐显现出来，总结为以下两点：

1) 大量的智能优化算法模型来自于对自然现象的模拟，在理论分析时很难为这些复杂的体系建立完备的理论模型，这阻碍了对智能优化算法的深入研究；

2) 不同的智能优化算法中存在着同质化的机制和操作。如很多算法都采用了均匀采样或正态采样，抑或是多尺度行为，但却由于算法模型的不同被割裂地解释为不同的原理。

这些问题已被一些优化领域的学者注意到了。文献[27]提出“现在优化计算领域的研究，重要的不是提出新的算法而是为优化算法建立普遍适用的规则和策略，研究优化问题和优化算法中的共性问题”。文献[28]提出“不鼓励大家再提出新的优化算法，这些新算法可能只会分散解决优化中真正具有挑战性和真正重要问题的注意力”。因此，有研究者认为当前大量的新算法是对旧算法的新伪装，并认为这一时代即将结束[29-30]。这时需要更深刻地去认识优化问题，解释智能优化算法的基本操作和核心迭代过程，避免在漫无目的的探索中去提出各种所谓的新算法，这可能是当前智能优化算法研究的一个重要方向。

2 选择量子力学

量子力学所描述的是被概率所统治的世界图像，而智能优化算法在不确定性算法的基础上大量地在使用概率化的搜索行为。这使得量子力学所描述的世界体系与智能优化系统在概率上存在着一定的相似性，这正是采用量子力学视角对智能优化算法进行研究的基础。事实上，量子力学对现代计算机技术的发展有着深刻的影响，不少计算机科学的开创者都在研究量子力学，甚至还为量子力学做出过巨大贡献。现代计算机之父von Neumann 写出了《量子力学的数学基础》[31]，1931 年Turing 认真研读了这本书。而且早在1929 年，Turing 还着迷于天文学家Eddington 所著的《物理世界的本质》[32]，Eddington 也认为“大脑也是由原子、电子组成的，量子物理或许能为人类意识、思维提供产生的机会和空间”。

1926 年Schrödinger 提出了量子力学中最为著名的方程——Schrödinger 方程：

式中，V(x) 为 势能；ψ (x,t)为波函数。1927 年，Born给出了Schrödinger 方程中波函数的概率解释[33]，他认为波函数代表了微观粒子的概率分布，而且波函数也完整地表达了一个微观粒子的运动状态。Born的解释建立了波函数与概率分布之间的关系，揭示了一个由概率行为所统治的微观世界。

量子力学在Born 的概率解释下与智能优化算法搜索过程中的随机性存在着深刻的内在联系。这一点提示我们采用量子理论的视角对优化问题和智能优化算法进行建模是一种可行的思路。随机性也是计算机智能产生的根源之一，文献[34]指出“随机性的程度决定了智能的高低”，这一论断指出了智能的本质是随机性。包括人类的智能也来自于随机性，一个充满了随机性的世界通过长期演化才出现了人类。1976 年，图灵奖获得者Rabin 认为“应该放弃的只是以完全确定的方式获得结果，这种结果可能出错，然而出错的可能性微乎其微，也就是说可以把概率算法用到这类问题中来”。Rabin 的论断可以理解为以牺牲确定性来获得较高的计算效率，他从技术层面给出了实现智能的方法就是放弃对确定性的追求。现代人工智能算法几乎无一例外的采纳了Rabin 的建议，这说明越来越多的学者认识到智能产生于随机性。而由量子力学所描述的物质世界的本质运行规律正好是概率化的，采用量子力学对智能优化算法进行研究是基于自然哲学的本质要求。2018 年11 月李国杰院士在《中国计算机学会通讯》上发表了题为《计算机科学基础理论需要重塑》的卷首语，他指出“量子力学改变了传统的逻辑定义，把概率看成了逻辑的内在组成。在计算机领域，构造一台完全公理化驱动的自动机也不现实，而对复杂环境，需要放弃严格逻辑而改用概率逻辑”。正如著名量子物理学家Feynman 所说：“自然不是经典的，如果你想模拟自然，你最好把它变成量子力学。”而且 Feynman也最早指出了量子计算机的可行性，开启了量子计算时代[35]。对于量子力学在智能优化算法中的应用不应只是停留在借鉴层面，由于优化问题和智能优化算法自身的概率特性，智能优化算法的迭代过程或可能被量子理论的基本规律所描述。

3 隐含并行性

研究量子视角下的智能优化算法，可以先从隐含并行性开始。量子力学中的概率机制所带来的不确定性正是用量子模型来描述智能优化算法的原因。隐含并行性的起源也是来自于不确定性，这或许也是智能算法所具有的解空间高速搜索能力的原因。虽然量子智能优化算法研究的是经典计算机上的智能优化算法，但由不确定性造成的隐含并行计算能力也是不应该回避的话题。

各类智能优化算法获得高效的解空间搜索能力的原因都是在某种程度上牺牲了对解的确定性的要求。如果要求以100%的概率找到最优解则只能使用强力搜索，这在大多数复杂优化问题中是不可能实现的。因此几乎所有的智能优化算法都不同程度地使用了随机数和概率策略，这些策略的引入使智能优化算法能在可以接受的时间内获得准确度可以接受的解。这种搜索速度提高的现象被称为算法的隐含并行性(implicit parallelism)。

算法的隐含并行性有别于算法的内在并行性(inherent parallelism)。内在并行性是指算法本身非常适合大规模并行，可以同时让几百甚至数千台计算机各自独立进行计算，运行过程中基本不做任何消息通信。对于隐含并行性在其他智能优化算法中的情况，目前的研究资料还极度缺乏，其实这是一个十分重要的研究课题，它涉及到了智能算法的内在核心问题，但由于本身问题的理论困难，研究一直相对缓慢。

隐含并行性的研究开始于20 世纪70 年代，目前对隐含并行性的研究多集中于遗传算法。1975年文献[36]首次提出了隐含并行性的概念，并指出隐含并行性是遗传算法能够快速有效搜索的根本原因。虽然隐含并行性是广泛存在于智能算法中的一个重要特性，但有关其他智能算法隐含并行性的研究长期以来没有得到国内外学者的重视。

根据文献[36]定义的隐含并行性，结构重组等遗传操作可以使被采样的模式数尽可能的多，这样可以带来较大的隐含并行性。遗传算法每代虽然只处理了N个个体，但隐含处理的模式数远远大于N。针对这一定义，文献[37]指出遗传算法每代虽然只显示处理N个个体串，实际隐含处理的模式数下界为，其中c1为 一个小整数，l为串长。这一下界表明模式数和N3成正比，也就是说遗传算法每代虽然只显示处理N个个体串，但是隐含处理了至少N3个模式。遗传算法这种隐含处理能力正是该算法在解空间快速搜索的原因，随后其他学者对这一结论展开了进一步研究[38-41]。遗传算法[42]在这一结论的基础上进一步证明了隐含处理的模式数的下界为紧下界。国内有关隐含并行性的研究也是针对遗传算法进行的，文献[43]进一步研究了遗传算法隐含处理的模式数，给出了对任意串长l及群体规模N，在等概率抽取每个群体的条件下，遗传算法每代所处理的模式长度不超过ls的不同模式期望数的精确表达。文献[44]给出了每代至少产生O(2N−1)数量级的新模式。

1975 年Rabin 等人提出的检测素数的不确定性方法Miller-Rabin 检测法正是一种以牺牲确定性来获得快速检测素数的方法。Miller-Rabin 检测法对待检测数n进 行k次试验所需的时间为O(log3n)，而出错的概率不超过1 /2k。目前这一素数检测方法也是检测素数最快的方法之一，其本质上也是通过牺牲确定性构造出具有隐含并行性的算法，其获得的隐含并行计算能力也是指数级的。

文献[45]从遗传算法和模拟退火算法的隐含并行性入手，利用物理学中的不确定性原理以及热力学中的熵对隐含并行性进行分析，指出算法隐含并行性的根源是不确定性和高熵态。文献[46-47]分析了隐含并行性与不确定性的关系，并从哲学角度对不确定性进行了分析。研究表明隐含并行性是智能算法中普遍存在的重要机制。隐含并行性的研究结果为智能优化算法的设计指出了一个重要的原则：牺牲算法确定性可能获得更好的计算效率。由于隐含并行性可能是指数级的，因此这种确定性的牺牲在算法实践中是可以接受的，事实上大多数的智能优化算法和智能算法都不同程度地采用了这种策略。

总之，隐含并行性作为一种反映算法内在快速搜索能力的指标一直以来未被研究者所重视。算法隐含并行性至今还没有严格的数学定义，特别是不确定性与隐含并行性之间的对应关系还未得出结论，相关研究工作主要也还是针对遗传算法在进行。近年来算法隐含并行性的研究更是处在停顿状态，几乎无法检索到相关论文，国内的研究者更是寥寥，这个非常重要的研究方向被大家所忽略了。

4 基于量子比特的智能优化算法

算法的隐含并行性要求一个算法要构造一个具有概率特性的算法结构和算法操作，量子力学所具有的天然的概率特性成为了描述和研究优化问题的一个有力的理论武器。量子力学中的粒子可以处于多种本征态的叠加态，这是量子力学所描述的一种非常奇特的现象，最有名的思想实验就是Schrödinger 的猫，量子叠加态在经典世界是非常难以理解的。量子比特是量子叠加态原理的一种特殊情况，如果一个量子系统只有两个状态，采用Dirac 算符分别用 |0〉和 |1〉来表示这两个状态，它可以用来描述一个基于二进制编码的系统。在经典计算机中一个bit 只能是0 或1，也就是说只能处于|0〉态和|1〉态。而在量子系统中一个量子比特可以处于两种状态的叠加，即：

式中，α 和 β 是分别处于两种态的概率幅，α2+β2=1。状态φ 既不是0 也不是1，而是处于0 和1 的叠加态。在对这种叠加态进行观察时会按概率坍缩到其中一个态。

量子比特这一概念是智能优化算法设计时常采用的一个机制。最早应用这一机制的是遗传算法，1996 年文献[15]提出了量子遗传算法(quantuminspired genetic algorithms,QGA)求解旅行商问题，并将这一算法称为量子启发式算法，他们借鉴了量子叠加原理构造了一个具有“多宇宙”的策略，可以认为是一个多种群的策略。

2000 年，文献[48]提出遗传量子算法，采用量子比特的概念提高对背包问题的求解能力，量子比特提高了算法的随机性，对于算法的全局搜索能力是有益的。2002 年文献[49]将算法的名称改为量子进化算法(quantum-inspired evolutionary algorithm,QEA)，完整的结果发表在TEVC 杂志上。他们的基本思路是将量子比特的概念与遗传算法的基本操作相结合，采用量子比特来改造遗传算法二进制编码机制，使遗传算法的经典二进制编码串成为量子比特串。通过量子比特改造的具有n位长度的遗传算法二进制编码可以表示为：

与经典的二进制表达相比，量子比特使二进制串的不确定性大大增加。如果采用量子比特所构成的串并对其进行多次测量，则任意一个可能解都会以一定的概率出现。如具有3 个量子比特的量子串为：

这个串是由3 个量子比特构成：

量子比特所构成的量子比特串拥有强大的表达力，它蕴含了所有解出现的概率。假设最优解为二进制串101，则其在测量过程中出现的概率为，也就是说量子比特串中以一定概率隐含最优解。量子比特串使确定性的二进制串变成了解的概率叠加，从而大大增加了算法迭代过程中解的不确定性。对于长度为n的量子比特串的任何操作等效于对 2n个不同经典比特串的操作。

量子比特在理论和实践上的成功使不少研究者进入这一领域，构造出了一批基于量子比特的量子智能优化算法。2007 年同样采用量子比特机制的量子蚁群算法被提出[16]，2010 年量子鱼群算法被提出[17]，文献[50-51]也将量子比特用于免疫克隆算法中并提出了量子免疫克隆算法。

这一类基于量子比特的算法是将量子比特的数学框架作为一种通用手段应用于已有的算法，以提高已有算法的性能，特别是全局搜索性能。由于量子比特的引入必然会增加算法迭代过程中的不确定性，从而使迭代过程不易陷入局部最优。理论上这对基础算法效果的改进是可行的，但这类研究并未从智能优化算法本身量子特性的角度来考虑，因此无法依据量子力学的知识获得智能优化算法的核心基础操作。

5 量子退火算法与优化问题的量子可描述性

采用量子比特来构造量子计算机和智能优化算法是基于对经典计算机的惯性认识，量子计算不一定要采用基于比特的逻辑运算来实现。在量子计算领域中，优化问题是被解决得最好的，这得益于优化问题可以有效的被量子模型所描述。量子退火理论及量子退火计算机的出现为这一问题提供了确切的证据。

1994 年文献[52]提出可以将优化问题的目标函数f(x)视 为量子系统中的势能V(x)(称为势能等效关系，equivalence of potential energy,EPE)，即V(x)=f(x)，从而可以通过量子退火过程或扩散蒙特卡罗方法(Diffusion Monte Carlo,DMC)来获得系统的基态[52]。如果将势能等效关系条件下量子系统的基态视为优化问题的解，则该工作从理论上证明了智能优化算法的迭代过程演化可以采用含时Schrödinger 方程来描述。并认为量子退火与经典退火的不同之处在于量子退火通过量子隧道效应在优化过程中实现跳出局部最优，并且隧道效应的大小与量子系统的质量有关，这一点指出了智能优化算法的多尺度过程。文献[52]还采用这一方法计算了 Lennard-Jones 势下的分子团簇最低能量。DMC 方法是上世纪70 年代文献[53]首次提出的一种采用随机行走(random walk)求解分子Schrödinger 方程基态波函数的方法。DMC 利用了Schrödinger 方程和扩散方程之间的同构性，模拟扩散过程推动波函数逐步向基态演化，从而实现对目标函数全局最优化解的搜索。文献[54]对扩散蒙特卡罗方法进行了非常深入细致的介绍，文献[55]针对量子退火的综述是目前国内较为完整的。

1998 年文献[56]提出可以采用位于横向磁场中的Ising 模型实现量子退火过程的方案，并对此方案进行数值仿真，证明其比经典退火过程具有更好的收敛于基态的能力。在这一模型中，横向磁场被作为与温度相似的扰动能量，推动量子系统以绝热过程的方式向基态演化。此工作的意义在于为量子退火计算机的研究提供了具体实现路径。

Ising 模型是统计物理中的一种模型，它具有表述简单、内涵丰富和应用广泛的特点，甚至在社会科学中都得到了成功的应用。将Ising 模型作为实现量子退火算法的理论方案，这意味着只要能找到可以形成Ising 模型的实际物理系统，就能按照他们的方案实现量子退火计算机。

Ising 模型由具有向上和向下两个方向的小磁针排列组合而成，向上取1，向下取−1：

在小磁针排列为 {si}时 系统的总能量为：

式中，J为能量耦合常数；〈ij〉代表对所有相邻小磁针进行求和，如si=sj总能量减小J；H为外磁场强度，磁场向上为正，向下为负，如果小磁针方向也和外场一致，总能量减少一个单位。这表明在Ising 模型中所有磁针方向一致并与外磁场方向相同时能量最低。当外界温度T越高时，就有数量越多的小磁针发生随机翻转。翻转后小磁针的排列状态为，如果此时能量则接受这次翻转；如果此时能量，则以概率接受这一翻转。在这一机制下系统会向能量较低方向演化，最终到达如下的能量分布状态，即玻尔兹曼分布：

文献[56]设计的量子退火方法采用横向磁场Γ(t)作 为能量扰动，横向磁场强度 Γ(t)随时间逐步降低，推动系统达到基态。

因此量子退火过程采用Schrödinger 方程描述为：

从智能优化算法的角度看这其实是表达一个多尺度的搜索过程，Γ (t)的值逐步减小时量子隧道效应逐步降低，搜索尺度减小。

1999 年文献[57]在《Science》上报道他们成功地采用Ising 磁体材料在横向磁场内实现了简单的量子自旋模型。这一成果为采用量子退火计算机实现对优化问题的求解找到了一个具体实现方案，并首次从实验上证明了量子退火在求解优化问题中的可行性。意大利高等国际研究院(International School for Advanced Studies,SISSA)的一个项目组也对量子退火在优化问题中的实现进行了大量的研究，证明了这一方法在实践中的可行性[58-59]。

2011 年基于量子退火原理的D-Wave 量子计算机成为了世界上第一台可以商用的量子退火计算机，D-Wave 同样采用了横向场Ising 模型，D-Wave中的量子比特不是用于量子门操作的，而是用于构造Ising 模型的[60]。D-Wave 主要的用途就是进行优化问题的求解，D-Wave 在求解优化问题时并不涉及具体的算法，而是通过退火过程由大自然给出问题的答案。

从隐含并行性的观点来看，D-Wave 获得快速求解优化问题的能力也是由于对于最终解的确定性的放松，其加速效果是针对强力搜索算法而言的。事实上大多数运行在经典计算机上的智能优化算法都能在较短的时间内获得一个组合优化问题的可行解，其采用的方法也放松了对解正确性的严格要求。量子退火计算机和经典计算机上的智能优化算法获得的快速计算能力都可以利用隐含并行性得到解释，量子退火计算机并不一定会比经典计算机上的智能优化算法快，只是两者运行的物理载体不一样。

量子退火技术在解决优化问题的理论和实践上的成功证明了优化问题具有量子可描述性，即可以采用一个量子模型对优化问题进行描述，同时智能优化算法的迭代演化过程也可以由一个量子系统的演化过程来描述。当按照量子退火算法中的势能等效关系对智能优化算法进行建模后，可以发现智能优化算法的迭代采样过程就是满足Schrödinger 方程所描述的演化过程的。

量子动力学在智能优化算法中的应用得益于量子科学领域中量子退火算法的出现。智能优化算法的研究人员在广泛借鉴量子比特这一概念时，对物理学中的量子退火方法有所忽略，而正是量子退火算法才真正的指出了智能优化算法与量子理论之间密切的联系，而不仅仅是概念的借鉴。

将量子力学引入智能优化算法更为重要的目的是希望能采用量子力学的数学框架分解出智能优化算法迭代过程的基本操作。智能优化算法的迭代过程是一个时间演化过程，因此描述智能优化算法的数学工具应该是一种动力学方程。量子退火思想的引入为建立智能优化算法的量子模型提供了契机，量子退火在处理优化问题时具有独特的优势。

量子退火的核心思想有4 点：

1) 将优化问题的目标函数视为量子系统中的粒子势能；

2) 量子系统能量最低的基态就是优化问题的解；

3) 通过逐步降低外在能量扰动使量子系统能量逐步演化到基态；

4) 优化问题的解采用概率化的波函数进行表达。

6 量子动力学理论

量子退火的思想为建立智能优化算法的量子模型提供了思路，智能优化算法有可能自身就是一个可以被量子力学所描述的过程，即可以用Schrödinger方程来完整地描述智能优化算法的时间演化过程。与量子退火理论相似，如果将优化问题的目标函数f(x)作 为量子系统中粒子的约束势能V(x)，即V(x)=f(x)，就可以得到如下的智能优化算法的Schrödinger方程：

这一思想在文献[21-22]提出的量子粒子群算法中得到了部分的采用。QPSO 算法的经典版本采用 δ势阱对应的基态波函数来构造采样函数，受粒子群算法的影响并未明确指出V(x)=f(x)的关系，算法的整体构造思路不是彻底量子化的，算法的核心迭代结构还是以粒子群算法为基础。QPSO 算法在性能上获得了成功，但在高维函数优化时容易陷入局部最优。QPSO 将采样函数与波函数对应起来的想法具有了智能优化算法量子模型的雏形。这使智能优化算法向量子理论迈进了一步，但其并未建立起智能优化算法和量子力学之间的数学物理关系，也没有意识到目标函数与势能之间的关系，这使得QPSO 算法不能真正的成为量子化的算法，更未能为智能优化算法建立量子模型。

明确将智能优化算法的目标函数视为Schrödinger 方程中势能的算法是多尺度量子谐振子算法(MQHOA)[61-64]。MQHOA 算法依据量子谐振子的波函数构造了智能优化算法，这一提法使智能优化算法向量子模型前进了一步。在该算法中还定义了波函数、零点能等量子物理中的重要概念[65]，并对多尺度过程和不确定性关系进行了研究[66]。但有意思的是从量子动力学的角度看MQHOA 算法的模型并不是完全正确的，在模型的应用上显得牵强。然而其构造出的算法结构却就是智能优化算法量子动力学所指出的基本迭代操作，而且MQHOA算法及其改进算法的性能也得到了一定程度的验证[67-72]。这些结果“意外”地证明了智能优化算法量子动力学给出的基本操作是简单而有效的，可以作为构造性能更好的算法的基础。MQHOA 算法利用了智能优化算法的Schrödinger 方程[73]，但却未能明确指出并利用Schrödinger 方程作为动力学方程来研究智能优化算法。虽然其在算法结构上基本与动力学模型给出的操作相似，但物理解释却不正确。MQHOA 算法和QPSO 算法都可以认为是量子动力学模型的萌芽。

为解决该问题，文献[74]对智能优化算法的量子基础进行了讨论，确立了势能等效、优化问题的含时Schrödinger 方程等一系列从量子视角研究智能优化算法的理论基础。为了利用经典计算机模拟智能优化算法在搜索过程中的随机马尔可夫过程，对Schrödinger 方程做Wick转动[75]，将时间转变为虚时间并令，则智能优化算法的含时Schrödinger 方程重新写为：

智能优化算法的含时Schrödinger 方程就是智能优化算法的量子动力学方程，它从量子力学的角度描述了智能优化算法的时间演化过程，智能优化算法的迭代演化过程通过Schrödinger 方程转化为波函数 ψ (x,τ)的时间演化过程。Schrödinger 方程所对应的基态波函数就是优化问题所对应的解。从理论上讲，在f(x)已知的情况下可以通过求解Schrödinger方程获得基态波函数。

该文采用扩散蒙特卡罗方法来求解基态波函数。虽然扩散方程和Schrödinger 方程在形式上是相似的，但优化问题约束条件f(x)的引入却破坏了式(12)格林函数的归一性，其格林函数为：

式中，势能项因子 exp(−τV)破坏了上式的归一性，因此需要向上述格林函数中引入一个收敛因子exp(τER)，使式(12)所描述的系统得到稳定收敛的解，改变后的格林函数是调整后的Schrödinger方程的解，其公式如下：

式中，ER是参考能量，是对当前优化系统能量的估计值；f(x)−ER是系统的势能项，反应优化问题对优化系统的影响。随着优化系统的演化，粒子的分布将不断的变化从而使参考能量ER不断逼近基态能量。式(14)即为一般意义上优化问题的含时Schrödinger 方程。

建立智能优化算法的Schrödinger 方程具有两个重要的理论意义：

1) 从物理意义上，优化问题通过Schrödinger方程被转化为求解受势能f(x)约束的量子系统的基态波函数ψ0(x)；

2) 从数学意义上，将优化问题和优化系统纳入统一的方程描述，即Schrödinger 方程这个线性偏微分动力学方程。这意味着量子力学中求解该方程的过程可以用作解释量子动力学理论下的智能优化算法的优化过程。

通过Schrödinger 方程，智能优化算法在量子视角下被转换为一个模拟的物理优化系统，该系统由量子空间中的虚拟粒子组成，优化问题的目标函数转换为加之于该系统的约束势场，而该系统的运行方式符合Schrödinger 方程的描述。

对于智能优化算法的Schrödinger 方程，可以通过Feynman 积分的方法，利用初态 ψ(x0,0)在A至B 所有路径上的积分，描述粒子从A 到B 的状态变化。Schrödinger 方程任意位置x和 时间 τ的解ψ(x,τ)可以表达如下：

式中，P(xn,xn−1)为虚拟粒子随机运动的动能相关项，描述了粒子的运动行为，与当前粒子位置xn−1和 粒子的质量m有关，其公式如下：

式(15)中，W(xn)为概率权重项，描述了粒子通过随机运动出现在xn的几率，与当前采样结果f(x)和 参考能量ER有关，其公式如下：

式(15)以积分的形式描述了在扩散过程中自由粒子运动和密度的变化，由于标准数值积分方法难以求解该积分，因此采用了扩散蒙特卡罗方法。在扩散蒙特卡罗方法中，如果函数h(x)可以分解为函数f(x)和 概率函数p(x)的乘积，则该积分可以表示为f(x)在 密度p(x)下的期望，其公式如下：

根据式(15)，采样密度函数为：

状态函数f(x1···xN)为：

因此，式(15)可以通过p(x1,···,xN)密度下的采样和权重函数W(xn)对采样结果的调整来获取：

由“扩散采样−权重调整”组成的迭代循环即为量子力学中求解Schrödinger 方程常用的扩散蒙特卡罗方法，其模拟了粒子在Schrödinger 方程下通过随机运动向基态能量演化的过程。

同时，多尺度退火过程是通过逐步降低模拟量子优化系统的动能实现的，公式如下：

式(22)中HT与粒子扩散公式(16)中的搜索尺度是正相关的。其原因是因为在优化过程中，目标函数的规模与模拟量子优化系统的规模不总是一致的，因此需要不断的改变优化系统的搜索尺度HT以匹配动能HV，这也是量子退火中减少能量扰动的原因。

智能优化算法量子动力学下的基本对应关系和操作汇总如表1。

表1 智能优化算法量子动力学下的基本对应关系和操作

特别有意思的是量子动力学模型并非想象中的那样给出一个量子化的新智能优化算法，而是得到了一些操作和基本迭代方法。其核心操作主要包括：正态采样、权重计算、多尺度过程，其他很多智能优化算法都可以视为在这一核心操作的基础上进行改进。智能优化算法的量子动力学解释了智能优化算法的量子化本质，为利用量子力学对智能优化算法进行分析提供了基础。

7 智能优化算法的核心操作

从量子动力学可以得到一些Schrödinger 方程下的智能优化算法的基本操作，这一结果提示：一些基于不同算法模型的智能优化算法都是从这些基本操作过程中衍生出来的。这一问题似乎也被不少研究者所注意到了，虽然他们可能并未从量子力学的视角去解释，但却发现智能优化算法可能存在“骨架”结构。

7.1 Kennedy 对粒子群算法基本框架的探索

粒子群算法(particle swarm optimization,PSO)是Kennedy 和Eberhart 在1995 年提出的一种群体智能优化算法[76]。Kennedy 认为这一算法的迭代过程模拟了鸟群的社会行为，这一算法的核心思想是通过个体行为和社会行为的综合来决定每一个体下一步的行为。

在PSO 算法中每次迭代都要保存个体的最好位置 pbest 和群体中的最好位置 gbest，每一个粒子的位置更新公式如下：

式中，学习因子c1和c2需 要人为确定，c1=0时粒子运动不考虑自己的个体历史信息，c2=0时粒子运动不考虑群体的历史信息。其参数值的设定带有很强的主观色彩，什么时候要考虑、考虑多少都是人为定的，这给算法性能优化造成很大的困难。同时由于这一算法最初没有采样尺度的递减策略，其性能并不是太好。直到1998 年文献[77]在PSO 算法的速度公式中引入递减的惯性权重因子w，才使PSO 算法成为一个多尺度算法，新的速度计算公式如下：

在迭代过程中通过逐步减小w的值，实现全局搜索和局部搜索的平衡。后来Clerc 又增加了控制速度的约束因子α，约束因子成为了一个不折不扣的多尺度参数[78]，也使PSO 算法成为一个多尺度搜索算法。

多尺度策略是智能优化算法量子模型中不确定性原理所预言的一种基本迭代操作[65]。如同量子理论中位置和动量不能同时被测定[64]一样，智能优化算法在同一尺度下不能同时实现良好的全局搜索和局部搜索能力。加入惯性权重后，PSO 算法成为一种多尺度群体算法。惯性权重的引入在算法上是正确的，但在模型上却显得牵强，这使得PSO 算法逐步离开了Kennedy 他们所提出的基本模型。特别是后来大量的改进算法和混合算法更是走得越来越远，PSO 也就逐渐成了一个算法名称的符号。

在PSO 算法提出近十年时，也就是2003 年左右，Kennedy 也意识到PSO 算法的参数变化太多而使算法难以理解，因此想简化PSO 算法。并且他认为PSO 算法与其他算法存在相似性，这一点与采用从量子动力学中得到智能优化算法的基本迭代操作是相似的。因此他提出了PSO 算法的骨架(bare bone)算法[79]，在这篇文章中Kennedy 采用随机正态采样取代了速度，取得了更好的性能。他认为正态采样既有很好的邻域采样能力，又能以较小的概率采到距离当前位置较远的位置。Kennedy在文中也自嘲道：“这样鸟在空间里的‘飞行’就变为‘飞溅’了。”同时他还认为PSO 算法和其他的一些进化算法有可能应该被归类到一个统一的优化种类中去。虽然他并未明确地给出统一模型，只是进行粗略的描述，但这一认识可能是对智能优化算法进行统一建模思想的雏形。Kennedy 所得到的一些结论与采用量子动力力学作为统一模型所得到的结论几乎完全吻合。就在PSO 算法的骨架提出的第二年即2004 年的CEC 会议上，Kennedy明确放弃了从鸟群模型构造的速度项，提出了一种基于正态随机采样的更为简洁的算法[80]，其采样公式如下：

对于其在算法中采用的正态随机采样在量子动力学中也曾早有预言。在扩散蒙特卡罗方法中，量子动力学方程转化为扩散方程，而扩散方程的格林函数就是正态函数，它代表了扩散过程中粒子在下一时刻到达某一位置的概率，其含义就是随机采样时的采样概率函数，从量子力学来看也就是波函数，即粒子出现在某一位置的概率。

至此Kennedy 将PSO 算法的演化过程简化为简单的正态概率采样过程，其基本结构与量子动力学给出的智能优化算法基本迭代结构已较为接近，但量子动力学给出的迭代过程则更为简单清晰。

7.2 智能优化算法的基本迭代过程

当从智能优化算法的量子动力学的角度去解释智能优化算法的迭代过程时，智能优化算法的核心迭代操作就成为了量子动力学理论框架下的基本要求。有的学者误认为近年提出的“黑洞算法”其结构来源于粒子群算法[82]，也有学者将MQHOA 算法误认为是一种量子粒子群算法，产生这些误解的原因皆源自智能优化算法可能具有统一的内在核心操作。差分进化算法[83-84]和烟火算法[85]的研究者也纷纷提出自己的“骨架”算法，这些骨架算法都存在相似的基本操作，如概率采样过程、采样步长的变化和群体策略等。通常这些看上去简单的骨架算法都具有不错的优化性能。这更是进一步证明了智能优化算法的核心操作是一种非常有效的操作，它已能满足智能优化算法对性能的基本要求。

综合量子动力学智能优化算法和其他智能优化算法的“骨架”，可以给出一个较为通用的迭代过程如下。

以上基本迭代过程看上去非常简单，仿佛也没有任何量子力学的痕迹，但却可以由智能优化算法的量子动力学通过扩散蒙特卡罗分解出来。而如果将正态采样视为格林函数，则其量子的面纱就揭开了。类似的，在QPSO 算法中也将其使用的拉普拉斯采样函数视为势阱下的基态波函数[86]。

智能优化算法的基本迭代过程可以作为智能优化算法设计和改进的基础，量子动力学可作为算法分析的理论框架，同时实验结果表明，上述基本迭代操作的骨架算法已出人意料地具有了相当的优化性能。而大量增加了许多操作机制的“重型”智能优化算法却仿佛只是为了走好最后一公里的性能而给出的，这使我们猜想：当目标函数为黑盒且没有针对目标函数做任何先验估计和假设的情况下，骨架算法可能已是“最优”算法了。

8 结束语

从量子视角来认识和研究智能优化算法是一个非常有前景的研究方向，从量子比特概念引入智能优化算法到直接采用量子动力学模型来为智能优化算法建模，该领域的研究正在走向纵深。通过量子视角来研究智能优化算法有望解释智能产生的原因并为研究隐含并行性产生的机制提供一条可行的道路。在当前量子科技成为我国战略性新兴技术的历史机遇下，基于量子技术的智能优化算法研究一定会取得长足的发展。