王 鹏,黄 焱,袁亚男,都 政,安俊秀

(1.西南民族大学,四川成都 610225;2.中国科学院成都计算机应用研究所,四川成都 610041;3.中国科学院大学,北京 100049;4.国家超级计算深圳中心,广东深圳518055;5.成都信息工程大学并行计算实验室,四川成都 610225)



多尺度量子谐振子算法的收敛特性

王 鹏1,黄 焱2,3,袁亚男2,3,都 政4,安俊秀5

(1.西南民族大学,四川成都 610225;2.中国科学院成都计算机应用研究所,四川成都 610041;3.中国科学院大学,北京 100049;4.国家超级计算深圳中心,广东深圳518055;5.成都信息工程大学并行计算实验室,四川成都 610225)

多尺度量子谐振子算法的收敛特性证明单一尺度的收敛过程不能同时获得良好的全局搜索精度和局部搜索精度,只有采用多尺度迭代才能实现对全局最优解的逐步精确定位,所以MQHOA算法利用量子谐振子收敛过程(QHO收敛)和多尺度收敛过程(M收敛)两个嵌套的收敛过程实现对优化问题的求解.QHO收敛过程按谐振子波函数由高能态向低能态的变化实现搜索区域的收缩,M收敛过程以2的倍数逐步减小尺度提高搜索精度.算法的波函数收敛定理证明QHO收敛时采样分布为高斯分布.QHO收敛过程算法模型中不同能级和不同尺度下的波函数图像为跟踪研究算法的迭代收敛过程提供了直观的具有物理含义的手段.实验证明算法在收敛过程中基态波函数形态和基态时零点能的存在都与算法物理模型的理论描述和预言是高度吻合的.

优化算法;量子算法;收敛;量子谐振子

电子学报URL:http://www.ejournal.org.cn DOI:10.3969/j.issn.0372-2112.2016.08.031

1 引言

多尺度量子谐振子算法(Multi-scale Quantum Harmonic Oscillator Algorithm,MQHOA)是2009年提出的一种模仿量子谐振子波函数能级模型的优化算法[1,2].文献[2]中的结果表明MQHOA算法能以较少的迭代次数准确地获得全局最优解,对于15种2维标准测试函数分别进行1000次重复计算都能以100%的概率获得全局最优解,同时对于高维测试函数如6维Griewank函数,8维Rastrigrin函数,10维Levy函数、Zakharov函数、Sum Square函数,15维Sphere函数也都能以100%的概率获得全局最优解.该算法在2009年首次提出后(最初版本称为模拟谐振子算法SHO),就引起了国内一些学者的关注和研究,并将这一算法成功应用于多个领域[3～7].MQHOA算法作为一种新的优化算法,在近期研究中还被成功地应用到组合优化、聚类及大规模数据中心相空间分析方法中,预计将具有广阔的应用前景.

近年提出的与MQHOA结构最为相似的优化算法是文献[8,9]所提出的具有很好收敛性的量子粒子群算法(QPSO),QPSO取消了传统粒子群算法的速度参数并利用δ势阱所得到的量子波函数构造算法[10],而本文所提出的MQHOA算法则直接利用谐振子势阱所得到的量子波函数构造算法,通过多尺度收敛实现对目标函数的全局搜索,本文算法的收敛过程具有更为精巧的数学结构和更为明确的物理意义,其收敛过程完全符合量子谐振子物理模型的预言.

MQHOA算法的收敛过程是由量子谐振子收敛(Quantum Harmonic Oscillator,QHO收敛)和多尺度收敛(Multi-scale,M收敛)两个嵌套的迭代过程构成,这两个收敛过程的特性决定了整个算法的性能,本文从MQHOA算法的收敛特性入手,发现MQHOA的收敛过程的理论和实验结果与量子谐振子物理模型所预言的收敛特性高度吻合.

2 MQHOA算法的基本收敛过程和参数选择

2.1 MQHOA算法的基本收敛过程

MQHOA算法的收敛过程包含两个迭代步骤,一个是在同一尺度下的量子谐振子收敛过程,一个是多尺度收敛过程.QHO收敛过程实现对搜索空间的逐步收缩定位,M收敛过程实现对采样精度的逐步提高,MQHOA算法从数学的角度也可以认为是一种多尺度高斯邻域采样群体算法.由于整个算法在迭代过程中只采用了不同尺度下的高斯邻域采样,使MQHOA与其他自然算法相比具有简单的数学描述和算法结构.我们在文献[2]中对MQHOA算法的基本过程进行了详细描述.

在MQHOA算法收敛过程中当前k个最优解位置的方差σk是一个十分重要的参数,算法在QHO收敛时每一次迭代都是以σk作为收敛判据的.σk在收敛过程中的变化反映了算法的整体收敛状态,图1为二维Levy函数和Griewank函数求最优解迭代时σk与迭代次数的关系(纵轴是以2为底的对数坐标).对于Levy函数，迭代总次数为7,x方向的σk在第6次迭代时为0,y方向的σk在第7次迭代时为0,x方向首先实现收敛,而算法的结束条件是所有采样坐标位置都同时满足收敛条件,所以算法总收敛次数为迭代次数最多的变量方向;对于Griewank函数，迭代总次数为11,x、y方向的σk均在第11次迭代时变为0,最后收敛时σk为0表明算法收敛时k个较优解的位置全部相同.σk在整个收敛过程中通常都是逐步减小的,σk与迭代次数的曲线关系能反映算法的基本收敛进程.

2.2k、m参数的选择对算法收敛性的影响

MQHOA算法的控制参数非常少,主要就是群体参数k和采样参数m,群体参数k是实验中算法每次迭代保留的高斯采样区域数量,采样参数m是一个采样区域内按N(xi,σ2)生成新的采样位置的个数,适量的采样区域数量和采样区域内的采样密度是精确求解全局优化问题的前提,作为MQHOA算法中的重要参数对算法的收敛特性有重要影响,所以首先需要确定参数k、m的数值.

图2(a)、(b)、(c)所示为2维、3维和4维Griewank函数在不同k、m组合下获得最优解时总的迭代次数变化曲线,当m<100时,随着m的增大,每个采样区域采样密度逐渐增大,算法迭代次数快速降低,当m大于100后继续增大时,迭代次数逐渐趋于稳定,m>100后m的值对迭代次数的影响不大,这说明对于一个高斯采样区域进行100次采样就能基本符合形成概率波函数的要求.综合以上对k,m参数的收敛特征研究,本文在实验中通常统一取k=20,m=100.MQHOA算法控制参数少而且通常不需要人为进行调整正是由于算法具有简洁的数学结构.

3 MQHOA算法的QHO收敛过程研究

3.1 QHO收敛过程的收敛性分析

MQHOA算法包含QHO和M两个收敛过程,但M收敛过程是确定的2倍收缩过程,因此只需证明QHO收敛过程在任意尺度σs下的收敛性即可.

QHO收敛过程的收敛条件为σk≤σs,只需证明在QHO收敛过程中k个高斯邻域采样区域的中心点位置的标准差σk一定能满足收敛条件即可.

假设在σs尺度下k个高斯邻域采样区域的中心点xi中当前最优解位置为xmin,则根据高斯采样的定义,xmin所对应的采样区域在下一次迭代进行m个采样时,如果存在一个ε邻域,使在区间[xmin-ε,xmin+ε]内的采样位置对应的目标函数值均小于其他k-1个采样区域,根据采样函数的概率含义,则出现这一结果的概率可以用下式计算得到:

(1)

其中ε邻域不存在的情况为:被优化函数有多个全局最优位置,此时在某一尺度的k个采样中心有可能会向多个全局最优位置聚集,使在区间[xmin-ε,xmin+ε]内的采样函数值均小于其他k-1个采样区域的条件有可能无法满足,从而σk≤σs的QHO收敛条件也无法满足,QHO收敛过程将无法退出并入下一个尺度的迭代.

上面的分析表明MQHOA的基本算法在目标函数有多个全局最优解时是有可能不收敛的,但在一些应用场合我们反而需要算法能找到多个全局最优解,甚至是找到多个极值区域.如在聚类应用中就希望算法能找到多个可能的聚类区域.

3.2 QHO收敛过程中的波函数收敛定理

在QHO收敛过程中我们把每次迭代时k个标准差为σ的高斯采样函数的叠加称为算法的波函数,归一化的算法波函数定义如下式:

(2)

算法波函数的概率分布ψQHO(x)就是对目标函数在定义域上进行采样的概率分布,单尺度量子谐振子算法迭代过程中标准差σ的值保持不变,算法对最小值的搜索只能在一个尺度上进行,算法波函数在收敛过程中将呈现出与量子谐振子波函数相似的波函数能级图像.

在QHO迭代过程中算法波函数都扮演了重要的角色,算法的采样概率分布、算法向量子基态单一高斯分布的收敛、算法的量子隧道效应都是在波函数的作用下形成的,具有概率含义的算法波函数反映了量子谐振子算法的收敛过程与其物理模型是非常吻合的,波函数直观地描述了算法的运行状态.

因此在尺度σs下QHO过程收敛到基态,满足σk≤σs时可以得出:

算法的物理模型表明QHO收敛过程就是系统能级从高能态不断降低到基态的过程,为了研究算法在QHO收敛过程中的能量变化情况,可以对QHO迭代中的能量定义如下:

(3)

根据零点能的定义在尺度σs下QHO收敛到基态时零点能的理论值可以由下式计算:

(4)

3.4 QHO收敛过程的波函数特性

MQHOA算法的物理模型认为在同一尺度的QHO收敛过程中可以观察到与量子谐振子相似的不同能级的波函数图像.图4中所示为对2维Griewank函数在尺度σs=0.625进行QHO迭代时x方向的波函数投影.

4 MQHOA算法的M收敛过程研究

4.1 M收敛过程分析

(5)

双尺度方程提示我们在M收敛过程中为了更精确地进行采样并保证信息的完整可以在每次尺度M迭代时将采样概率函数收缩1倍.由于MQHOA算法所使用的采样概率函数为高斯函数,可以得到以下定理.

定理2 (尺度变换定理):高斯函数收缩1倍与标准差σ减小1倍是等效的.

根据这一定理在算法设计时可以通过改变高斯函数的σ参数来实现采样函数尺度的变化,从而实现对目标函数更为精确的采样和探查.

4.2 M收敛过程实验

MQHOA算法的M收敛过程是QHO收敛过程的外层迭代,M收敛过程在QHO收敛过程结束时实现了搜索区域的收缩和改变采样函数的尺度,从而实现在更小区域内更高的搜索精度.

图5为二维Griewank函数在σs=5和σs=2.5两个尺度间的M收敛过程波函数图,图中第一排为波函数在搜索空间中的波函数图像,第二排为波函数搜索空间中的等高投影,各维变量位置的定义域都取[-10,10].

图5(a1),(b1)为尺度σs=5,QHO迭代开始时高能态波函数图像,此时量子谐振子波函数处于高能态,图5(a2),(b2)为尺度σs=5时QHO迭代在基态收敛时的波函数图,由于此时σs较大收敛时部分细节信息被混迭,通过将σs减小为σs/2的M迭代操作,使算法进入尺度为σs/2的QHO收敛过程,图5(a3),(b3)就是尺度σs/2的高能态,此时可以看到在大尺度下被混迭的搜索空间细节情况.图5(a4),(b4)为尺度σs/2收敛过程的基态波函数,对比图5(a2),(b2)可以看到在尺度σs/2下收敛后采样区域明显缩小,只出现了较少的细节混迭现象.MQHOA算法的M收敛过程会一直持续到σs<σmin时停止,采样精度逐步提高,搜索区域逐步缩小,此时获得的最优解即是满足精度σmin要求的全局最优解.

5 总结

本文以MQHOA算法的收敛特性为研究对象,分别对MQHOA算法的QHO收敛和M收敛两个重要嵌套收敛过程进行了研究.QHO收敛实现了对搜索区域的逐步收缩,M收敛实现了采样精度的逐步提高,因此MQHOA算法的整个收敛过程就是由QHO收敛过程和M收敛过程相互嵌套,逐步实现对最优解位置的精确定位.MQHOA算法收敛过程的理论和实验结果表明MQHOA具有精巧的数学结构并与物理模型符合较好.

[1]王鹏.云计算的关键技术与应用实例[M].北京:人民邮电出版社,2010:168-194.

[2]王鹏,黄焱,任超,郭又铭.多尺度量子谐振子高维函数全局优化算法[J].电子学报,2013,41(12):2468-2473.

Wang P,Huang Y,Ren C,Guo YM.Multi-scale quantum harmonic oscillator for high-dimensional function global optimization algorithm[J].Acta Electronica Sinica,2013,41(12):2468-2473.(in Chinese)

[3]王培崇,钱旭.模拟谐振子算法及其全局收敛性分析[J].计算机工程,2013,39(3):209-212.

Wang PC,Qian X.Simulated harmonic oscillator algorithm and its global convergence analysis[J].Computer Engineering,2013,39(3):209-212.(in Chinese)

[4]倪霖,段超,钟辉.基于模拟谐振子算法的多项目调度[J].计算机应用,2011,31(9):2559-2562.

Ni L,Duan C,Zhong H.Multi-project scheduling based on simulated harmonic oscillator algorithm[J].Journal of Computer Applications,2011,31(9):2559-2562.(in Chinese)

[5]姚明.模拟谐振子算法在求解整数规划问题中的应用[J].微型机与应用,2013,32(7):77-79.

Yao M.Application of simulated harmonic oscillator algorithm in integer programming[J].Microcomputer &Its Application,2013,32(7):77-79.(in Chinese)

[6]于海涛,王慧强,李梓,韩立娟.基于模拟谐振子的优化K-means聚类算法[J].计算机工程与应用,2012,48(30):122-127.

Yu HT,Wang HQ,Li Z,et al.Optimized k-means clustering algorithm based on simulated harmonic oscillator[J].Computer Engineering and Application,2012,48(30):122-127.(in Chinese)

[7]程勖,李文辉,刘裕斌.基于模拟谐振子算法的服务调度技术[J].大连海事大学学报(自然科学版),2013,39 (2):78-81.

Cheng X,Li WH,Liu YB.Service scheduling technique based on simulated harmonic oscillator algorithm[J].Journal of Dalian Maritime University,2013,39(2):78-81.(in Chinese)

[8]Feng B,Sun J,Xu WB.A global search strategy of quantum-behaved particle swarm optimization[A].IEEE Conference on Cybernetics and Intelligent Systems[C].Singapore:IEEE,2004.111-116.

[9]Sun J,Wu XJ,Vasile Palade,et al.Convergence Analysis and improvements of quantum-behaved particle swarm optimization[J].Information Sciences,2012,193(15):81-103.

[10]Sun J,Fang W,Wu XJ,et al.Quantum-behaved particle swarm optimization:analysis of the individual particle behavior and parameter selection[J].Evolutionary Computation,2012,20(3):349-393.

王 鹏(通信作者) 男,1975年8月出生于四川省犍为县.现为西南民族大学教授、博士生导师,研究方向为智能算法、云计算、并行计算.

E-mail:wp002005@163.com

黄 焱 男,1982年7月出生于江苏省泗阳县.博士研究生.主要研究方向为智能算法、云计算、并行计算.

E-mail:16481339@qq.com

Convergence Characteristics of Multi-scale Quantum Harmonic Oscillator Algorithm

WANG Peng1,HUANG Yan2,3,YUAN Ya-nan2,3,DU Zheng4,AN Jun-xiu5

(1.SouthwestUniversityforNationalities,Chengdu,Sichuan610225,China;2.ChengduInstituteofComputerApplication,ChineseAcademyofSciences,Chengdu,Sichuan610041,China;3.UniversityofChineseAcademyofSciences,Beijing100049,China;4.NationalSupercomputingCenterinShenzhen,Shenzhen,Guangdong518055,China;5.ParallelComputingLaboratory,ChengduUniversityofInformationTechnology,Chengdu,Sichuan610225,China)

The convergence characteristics of Multi-scale Quantum Harmonic Oscillator Algorithm (MQHOA) prove that single scale convergence process cannot simultaneously get global search accuracy and local search accuracy.Only by multi-scale iteration can we gradually get the accurate position of the global optimum solution.MQHOA solves the optimization problem by two nested convergence processes:Quantum Harmonic Oscillator convergence process (QHO process) and Multi-scale convergence process (M process).QHO process shrinks the searching areas by the manner harmonic oscillator's wave function moving from high-energy state to low-energy state.M process shrinks the search areas by half cutting to improve searching precision.The wave function convergence theorem proves that sampling distribution is Gauss distribution when QHO process is convergent.By the wave function diagram in different energy level and scale,we can track the algorithm iterative process explicitly.The experiments demonstrate the shape of ground-state wave function,the existence of zero-point energy on the ground state,all of which exactly match the physical model of MQHOA.

optimization algorithm;quantum algorithm;convergence;quantum harmonic oscillator

2014-12-17;

2015-08-09;责任编辑:马兰英

国家自然科学基金(No.60702075);广东省科技厅高新技术产业化科技攻关项目(No.2011B010200007);四川省青年科学基金(No.09ZQ026-068);成都市科技局创新发展战略研究项目(No.11RXYB016ZF)

TP301

A

0372-2112 (2016)08-1988-06