引用本文

焦育威, 王鹏. 基于种群个体数自适应的多尺度量子谐振子优化算法. 自动化学报, 2023, 49(7): 1587−1600 doi: 10.16383/j.aas.c200247

Jiao Yu-Wei, Wang Peng. Multi-scale quantum harmonic oscillator algorithm based on subpopulation number adaptive. Acta Automatica Sinica, 2023, 49(7): 1587−1600 doi: 10.16383/j.aas.c200247

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

关键词

优化算法，量子隧道效应，动态种群，多种群，蒙特卡洛 

摘要

优化算法中多种群采样方式可转化为蒙特卡洛对当前函数积分的评估, 针对不同子种群对整体评估的差异性, 提出子种群规模 (个体数) 自适应的改进策略, 并用于多尺度量子谐振子优化算法(Multi-scale quantum harmonic oscillator algorithm, MQHOA) 的改进, 同时阐述多种群策略所具有的量子特性以及量子隧道效应与寻优性能的相关性. 已有的优化算法忽视了动态调节子种群规模对寻优能力的影响, 该策略通过动态调节子种群规模, 提高适应度差的子种群发生量子隧道效应的概率, 增强了算法的寻优能力. 将改进后的算法MQHOA-d (Multi-scale quantum harmonic oscillator algorithm based on dynamic subpopulation) 与 MQHOA 及其他优化算法在 CEC2013 测试集上进行测试, 结果表明原算法 MQHOA“早熟”问题在 MQHOA-d 中得到解决, 且 MQHOA-d 对多峰函数和复合函数优化具有显著优势, 求解误差和计算时间均小于几种经典优化算法.

文章导读

伴随人工智能的发展, 大量的启发式算法相继提出, 如遗传算法、粒子群优化算法等, 这些算法在优化领域中有着出色的表现. 随着优化问题复杂程度的加深, 这些算法的弊端开始显现, 如算法“早熟”或种群多样性丧失导致精度下降、计算成本上升等问题, 为解决这些问题近年来大量的改进策略被提出, 这些改进策略可以划分为两大类.

第1类改进方案属于经典力学范畴, 如对算法的参数进行调节, 文献[1-3]对粒子群优化算法 (Particle swarm optimization, PSO) 的惯性系数进行研究, 分析惯性系数对全局搜索和局部搜索的影响, 以此提高 PSO 的性能. 或是融合其他算法的某种机制以提高自身性能, 如文献[4]将粒子群优化算法的局部快速收敛性与模拟退火算法的全局收敛性结合, 提出一种协同进化的算法, 新算法在全局收敛能力和收敛速度上都有所提高; 或是以算法迭代过程中的种群为入手点, 改变种群的更新方式或将单一种群进行分组或划分, 使其多种群化, 如基于生物学上物种划分的小生境遗传算法[5]. 2010 年 Luo 等[6]基于人工智能体的原始结构, 将人工智能体划分为几个独立的子群体, 不同的子群体中进行通信, 这一方法被证实有效. 同时也有学者基于拓扑结构或层次结构对 PSO 中粒子进行种群划分[7-9], 以此平衡算法的勘探能力和开采能力[10].

第2类改进方案是在原算法基础上引入量子机制, 从量子物理与优化问题在概率意义上的相似性出发, 通过引入量子机制提高算法的性能, 在优化算法中应用较为广泛的量子机制可分为如下几种:

1) 量子波动的引入. 1994 年 Finnila等[11]在模拟退火算法(Simulated annealing, SA)中引入量子波动, 利用系统中逐级递减的量子波动寻找经典系统的基态, 提出量子退火算法(Quantum annealing, QA). 量子波动的引入将函数优化问题转化为求解系统基态的问题, 目标函数f(x)则对应量子系统中的势阱, 伴随量子系统的演化, 粒子有一定的概率发生隧道效应, 在量子系统中粒子能通过势垒贯穿出现在经典禁区(可映射为最优解区间), 这称为隧道效应. 隧道效应增强了算法跳出局部最优的能力, 但量子退火算法并未对隧道效应的发生概率进行主观控制.

2) 势阱等效. 通过薛定谔方程建立采样函数与目标函数f(x)之间的关系, 文献[12-13]以 Delta 势阱下的波函数模方引导粒子位置更新, 提出量子粒子群优化算法(Quantum PSO, QPSO), 将粒子寻优空间等效为势阱, 粒子的搜索行为受势阱约束, 全局最优位置映射为势能最低点位置. 王鹏等[14]通过模拟量子谐振子从高能态向基态收敛过程, 将目标函数以谐振子势进行等效, 提出用于解决高维函数优化问题的多尺度量子谐振子优化算法(Multi-scale quantum harmonic oscillator algorithm, MQHOA), 并于 2019 年通过模拟量子系统下自由粒子的运动过程解决函数优化问题, 提出了基于自由粒子模型的优化算法框架[15]. 通过势阱等效, 采用某一势阱下的波函数对粒子搜索过程进行概率描述, 较经典力学的种群确定性演化过程而言该体系下算法的随机性更强.

3) 叠加态原理的应用. 首先是 Narayanan 等[16]在 1996 年通过多种群的方式将量子多宇宙的概念引入遗传算法; 随后, Han 等[17]将量子编码和量子旋转门应用在种群的编码和更新过程中, 提出量子遗传算法, 叠加态原理在遗传算法中的应用提升了算法的寻优能力, 采用量子编码的染色体可表达多个态的叠加, 通过量子手段增加了种群的多样性, 类似的改进工作有量子蚁群算法[18]; 同时文献[19]采用量子编码的方式对差分进化算法进行改进, 并在电力系统的优化问题中取得了不错的效果, 将量子叠加态的概率特性以量子编码的形式应用在已有的算法改进工作中已被证明是有效的.

无论是量子退火算法中以递减的量子波动寻找量子系统基态, 还是通过势阱等效的方法使粒子在量子系统下寻找势能最低点, 在算法的迭代过程中, 粒子都有一定的概率发生量子隧道效应, 发生隧道效应的概率在函数优化问题中可衡量采样点从局部最优跳到全局最优的能力. 隧道效应的发生是量子系统特有的现象, 目前应用量子机制改进算法的方案中虽然涉及隧道效应的发生, 但未对隧道效应发生概率有效控制以及隧道效应概率大小对算法性能影响进行研究. 势垒与粒子簇对量子隧道效应的发生概率具有较大的影响, 因此在算法迭代过程中对这两个变量信息的获取与利用变得尤为重要. 本文以经典力学中多种群搜索方式为基础, 将子种群的个体数映射为某一粒子簇中粒子的数量, 将子种群间分布的相对位置用于评估当前粒子簇(采样点) 到函数最优解间的势垒宽度, 将经典力学下的多种群搜索策略赋予量子意义, 通过动态调节迭代过程中子种群规模而增加种群整体量子隧道效应的发生概率, 达到增强算法性能的目的, 从控制隧道效应发生概率的角度为算法改进提供一种新思路.

本文结构安排如下. 第1节阐述优化算法的隧道效应, 并建立多种群搜索策略与隧道效应发生概率的关系; 第2节和第3节以 MQHOA 为例, 说明其优化过程背后的物理背景, 同时从发生隧道效应的角度分析该算法的不足之处, 证明通过多种群手段增加隧道效应发生概率的必要性, 然后基于蒙特卡洛评估的思想提出子种群规模自适应的策略; 第4节给出改进后具体的算法MQHOA-d (Multi-scale quantum harmonic oscillator algorithm based on dynamic subpopulation), 并以双阱函数为例设计实验跟踪算法在寻优过程中发生量子隧道效应点的数量变化情况, 同时说明隧道效应对算法寻优的影响; 第5节设计实验并对改进后的算法(MQHOA-d) 从寻优误差、计算资源消耗等方面进行分析.

图 1  不同采样中心概率密度曲线

图 2  MQHOA-d所生成种群在Ellipsoidal函数二维空间分布示意图

图 3  一维双阱函数图与隧道效应示意图

本文基于蒙特卡洛估计中不同子种群对总体评估误差的差异性, 提出动态调节子种群规模的寻优策略, 将此策略应用于 MQHOA 的改进, 改进后的算法(MQHOA-d)在未增加随机化特征, 或者添加扰动等多余步骤的前提下解决了原算法的“早熟” 现象[34]. 核心在于动态调节种群规模方式增大了种群迭代初期发生量子隧道效应的概率, 使其对解空间全局评估更加精准. 在迭代次数相同的情况下 MQHOA-d 对多峰函数和复合函数寻优误差更小, 根据适应度评估的多种群采样方式动态地调节了种群规模, 在解空间中更加合理地进行勘探和开发, 同时种群利用率得到了提高. 改进后的算法虽然结构上较之前相比变得复杂, 但时间复杂度上仍优于几大主流算法(SPSO2011、QPSO). 目前, MQHOA-d 仍有局限性, 如: 1) MQHOA 系列算法的随机性和隐含并行性尚不明确[35-36]; 2) MQHOA-d 种群个体行为所抽象的随机游走模型[37-38]尚未研究.

作者简介

焦育威

西南民族大学计算机科学与技术学院硕士研究生. 主要研究方向为量子启发式算法, 高性能计算. E-mail: jiaoyuwei@stu.swun.edu.cn

王鹏

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