引用本文

王鹏, 辛罡. 智能优化算法的量子理论纲要. 自动化学报, 2023, 49(11): 2396−2408 doi: 10.16383/j.aas.c190761

Wang Peng, Xin Gang. Quantum theory of intelligent optimization algorithms. Acta Automatica Sinica, 2023, 49(11): 2396−2408 doi: 10.16383/j.aas.c190761

http://www.aas.net.cn/cn/article/doi/10.16383/j.aas.c190761

关键词

优化问题，优化算法，量子理论，波函数，基态 

摘要

针对一些智能优化算法缺乏完备数学物理理论基础的现状, 利用优化问题和量子物理在概率意义上的相似性, 建立优化问题的薛定谔方程, 将优化问题转化为以目标函数为约束条件的基态波函数问题, 同时利用波函数定义了算法的能量、隧道效应和熵, 实现了以波函数为中心的优化问题量子模型. 这一纲要利用了量子物理完备的理论框架, 建立起了优化问题与量子理论广泛的内在联系. 从量子物理的角度回答了优化问题解的概率描述, 邻域采样函数的选择, 算法演化的过程设计, 多尺度过程的必要性等问题. 智能优化算法的量子理论纲要可以作为研究与构造算法的理论工具, 其有效性已得到初步验证.

文章导读

从上世纪70年代开始, 智能优化算法经历了持续近30年的黄金时期, 其标志就是大量经典的优化算法被提出, 并得到广泛的应用. 1975年Holland[1]提出了遗传算法(Genetic algorithm, GA), 这一算法演变为一类重要的算法簇——进化算法. 1983年Kirkpatrick利用Metropolis准则[2]提出了模拟退火算法(Simulated annealing, SA)[3]; Dorigo于1992年在他的博士论文中提出了蚁群算法(Ant colony optimization, ACO)[4-5], 这一算法对解决组合优化问题具有较好的效果; 1995年Eberhart等[6] 基于鸟类的飞行和社会行为提出了粒子群算法(Particle swarm optimization, PSO), 这些算法的提出为优化算法的研究打下了基础. 进入21世纪, 智能优化算法发展的黄金时代已逐渐过去, 但各种新的算法仍然不断出现, 特别是自然启发式算法, 这些优化算法在不同的模型掩盖下存在着“核心”操作同质化的问题. 新提出的优化算法模型大都与现有的算法存在或多或少的相似之处, 这使优化领域的研究者们逐渐意识到, 当前优化算法所面临的挑战不是提出新的算法, 而是为优化问题和优化算法寻找一种合适的统一模型, 智能优化算法的研究进入了一个新的时代.

对于优化算法核心规则和策略的研究早已被一些研究者所关注, 粒子群算法的提出者Kennedy也意识到优化算法存在统一的简单模型和通用的基本迭代操作, 他针对粒子群算法提出了相应的“骨架”(Bare bone)算法, Kennedy认为: “希望利用这种骨架算法揭示随机群体算法之间相似性的奥秘, 并发现新的方法”[7]. 随后差分进化算法[8]和烟火算法[9]的骨架算法也相继提出. 2016年蚁群算法的提出者Dorigo在一份声明中也表达出对于当前不断提出的新的自然算法的谨慎态度. 其他一些研究者, 如Sörensen也认为, “现在优化计算领域的研究, 重要的不是提出新的算法而是为优化算法建立普遍适用的规则和策略, 研究优化问题和优化算法中的共性问题”[10]. 萤火虫算法、布谷鸟算法、蝙蝠算法及鲜花授粉算法等多种优化算法的提出者Yang在自己的专著中提醒读者: “不鼓励大家再提出新的优化算法, 这些新算法可能只会分散解决优化中真正具有挑战性和真正重要的问题的注意力”[11]. 相似的看法在其他一些学者的论述中也有表述, 如文献[12]认为和声优化算法本质上就是一种进化策略. 广义上讲遗传算法、粒子群算法、蚁群算法等算法的基本模型都是基于人对世界的主观认识对优化问题进行的建模, 这些模型往往缺乏完备的数学、物理体系的支持, 一定程度上也阻碍了优化算法这一学科的发展.

优化算法的统一模型需要同时具备通用性、深刻性和数学完备性. 20世纪初量子理论在一大批杰出科学家的努力下获得了快速的发展, 建立起了完备的理论体系, 并在实践中得到了反复的检验. 与其他理论相比, 量子理论深刻地反映了大自然的基本运行规律, 特别是量子理论中对波函数的概率解释与基于概率采样的优化算法具有很大的相似性[13].

事实上, 量子理论的思想在优化算法中早已得到了应用, 早在1996年Narayanan等[14]利用量子理论中的“多宇宙” (Multi-universe) 的观点提出多宇宙衍生遗传算法 (Quantum-inspired genetic algorithm, QIGA), 该算法尝试把量子特性融入到进化算法中去, 后来量子遗传算法的思想也应用于解决组合优化问题[15]. 随后量子蚁群算法(Quantum ant colony optimization, QACO)[16], 量子粒子群(Quantum-behaved particle swarm optimization, QPSO)[17]等受量子理论启发的算法相继提出. 本文作者也于2013年提出了一种基于量子谐振子波函数构造的多尺度量子谐振子算法(Multiscale quantum harmonic oscillator algorithm, MQHOA)[18], 通过对MQHOA算法的研究, 我们发现了薛定谔方程和波函数在优化算法的描述中具有重要作用[19]. 这些结果可以认为是量子理论与优化问题在概率特性上存在内在一致性的证据.

基于随机行为的智能优化算法通常都放弃了对最优解准确性的要求, 这与量子理论中采用波函数对粒子进行概率化描述的思想是一致的. 粒子群算法的提出者Kennedy在著作Swarm Intelligence中指出“随机性的程度决定了智能的高低”, 这一论断指出了智能的本质是随机性[20]. 2018年11月李国杰院士在《中国计算机学会通讯》上发表了题为“计算机科学基础理论需要重塑”的卷首语, 他指出“量子力学改变了传统的逻辑定义, 把概率看成了逻辑的内在组成. 在计算机领域, 构造一台完全公理化驱动的自动机也不现实, 而对复杂环境, 我们需要放弃严格逻辑而改用概率逻辑”.

由于量子理论已经过长期的充分发展, 其理论体系及数学表达已非常完备和丰富, 建立了如扩散蒙特卡罗法、路径积分法、微扰理论等基态波函数的求解方法. 本文基于对优化问题概率特性的认识, 采用量子物理理论对优化问题进行研究, 从量子理论的角度尝试解答优化问题的波函数表达、概率采样函数的选择、算法演化过程和多尺度过程的必要性等问题, 希望能为优化算法的分析与研究提供新的视角.

图 1  量子隧道效应示意图

本文针对优化问题量子特性展开讨论, 其目的并不是为了提出一种新的优化算法, 而是希望为优化问题和优化算法的研究和分析提供一种新的视角.

本文通过对比研究表明, 量子理论与优化问题之间确实存在广泛的内在联系, 量子理论给出了描述优化问题的较为完备的数学框架, 为研究优化问题提供了一种有明确物理意义的数学工具. 虽然本文未对细节进行展开讨论, 但我们现有的研究表明, 在这一模型指导下的算法设计是有效的, 并且可以得到一些不错的结果.

从优化领域的发展趋势看提出新的优化算法不再是现在的研究焦点, 探索为优化问题建立统一的理论模型在现阶段变得尤为重要. 量子理论作为优化问题统一模型的理论基础是一个不错的选择, 本文的研究结果也支持这一结论. 但相关的研究还有待进一步的深入, 事实上的确还有一些重要问题并没有得到解决, 例如优化算法的隐含并行性问题(Implicit parallelism)[38-39]的量子解释, 我们希望在今后的工作中完成.

作者简介

王鹏

西南民族大学计算机科学与技术学院教授. 2001年获四川大学核技术及应用专业硕士学位. 2004年获中国科学院成都计算机应用研究所计算机软件与理论专业博士学位. 主要研究方向为量子理论, 量子启发式算法, 计算智能与高性能计算. 本文通信作者. E-mail: qhoalab@163.com

辛罡

中国科学院成都计算机应用研究所博士研究生. 2011年获德累斯顿工业大学微电子与固体电子专业硕士学位. 主要研究方向为量子启发式算法, 高性能计算. E-mail: xin_gang@vip.126.com