智能優化算法的量子理論綱要

王 鵬 辛 罡

從上世紀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 優化問題解的概率化定義

智能優化算法,其主要指基于人類對自然規律的認知與借鑒而形成的智能優化系統,這些系統大部分都是概率性算法,其包含了大量概率化的迭代操作,通過放棄對解的確定性的要求,從而獲得在可接受時間內巨大解空間上的搜索能力.智能優化算法的角度看,優化問題解的獲得是一個不確定性的問題,甚至算法無法對得到的解給出任何確定性保證.優化問題的解采用概率形式來表達更能有效地反映解的特性.

首先來看數學上對優化問題的定義,為方便討論,在本文中以一維目標函數f(x)優化問題為例進行討論.從數學的角度一維函數優化問題可以定義如下:

針對目標函數f(x)在實數定義域 [a,b] 上的優化問題,就是要找到一個實數x0∈[a,b],對于任意x ∈[a,b],滿足f(x0)≤f(x),則稱x0為目標函數在實數定義域 [a,b] 全局最優解.

從以上定義可知,全局最優解是一個確定性的定義,優化過程理論上需要找到x0這一個確定的全局最優解.而對于智能優化算法,為確保算法的通用性,優化問題通常視為黑盒問題,黑盒問題認為:優化算法對目標函數的表達式f(x)是未知的,優化算法只能通過采樣確定從目標函數定義域集合到值域集合中的每一個映射.優化算法的每一次采樣就是對黑盒進行的一次測量,測量的次數越多所獲得的目標函數信息越多.

智能優化算法對目標函數f(x)全局最優解的位置同樣是不確定的.事實上算法在運行過程中并不知道它是否找到了全局最優解.所以采用當前采樣點的概率密度函數g(x)來描述優化問題的結果更能準確地反映優化問題的概率特性,P(a≤x≤b)表示全局最優解出現在區間 [a,b] 的概率.

對于智能優化算法,優化問題的解由數學上確定的全局最優解的位置x0轉變為描述算法當前采樣點的概率密度函數g(x).

在算法運行前全局最優解x0從算法的角度是可行域中的任意位置,而在優化算法運行后,最優解附近的g(x)會逐步增加,最終收斂為一個很小的區域.這一區域被認為是算法最優解可能存在的區域.針對最優化問題,我們通常只關心在最優化解附近的概率分布,所以通常g(x)為緊支撐函數.這樣概率分布會更集中在中心位置,例如高斯分布、柯西分布、拉普拉斯分布等.后面本文將采用量子模型說明g(x)的概率形式與對目標函數進行勢阱逼近的勢阱選擇有關.

優化問題解的概率定義從理論上建立起了優化問題的解與波函數概率解釋之間的聯系,為采用量子波函數對優化問題進行描述提供了可能.

2 優化問題的量子模型

智能優化系統中采樣點的運行方式是復雜的,鑒于不同的算法模型,很難有一套理論可以完整地給出對于不同智能優化算法動力學行為的描述.在量子理論中,粒子的運動狀態是由其對應的波函數ψ(x)所決定的.決定波函數的動力學方程是由粒子的質能方程和波動方程聯立得到的,本文希望利用量子力學中的確定的動力學方程代替智能優化算法中復雜且無法確定的運動學方程,從而為討論其核心迭代過程和搜索行為提供研究基礎.

早在1926 年Born[21]給出了波函數ψ(x)的概率解釋.Born 認為波函數模的平方 |ψ(x)|2描述了粒子在空間出現的概率分布.如果我們構造一個描述優化問題的量子化系統,將全局最優解的概率密度函數g(x)用波函數模的平方 |ψ(x)|2來進行表示,則優化問題就可以轉化為求量子系統波函數ψ(x)的量子化問題.

2.1 優化問題的薛定諤方程

在量子系統中,描述勢阱中粒子運動狀態的薛定諤方程可以用作描述粒子在勢阱函數約束下的運動狀態,通過求解薛定諤方程的基態波函數,可以獲得最低能量下的粒子概率分布函數,含時薛定諤方程為

其中,i 是虛數單位,V(x)為約束粒子的勢阱,m為粒子的質量,h為普朗克常數,?=h/(2π).利用薛定諤方程就可以求出粒子在被勢阱V(x)約束下的波函數.

從量子物理的觀點看,為了建立優化問題解的概率密度函數g(x)和量子波函數ψ(x)關系,優化問題可以看作是一個能量最低的問題,是以目標函數f(x)為勢阱約束下的量子系統,即V(x)=f(x).通過勢阱等效,并令S=?2/(2m),則優化問題的薛定諤方程定義為

其中,S在優化問題中決定著波函數的尺度,它的值越大波函數的尺度越大,對應的量子效應越明顯,反之則量子效應越弱,所以稱S為尺度系數.

通過薛定諤方程的轉換,優化問題轉化為求解在勢阱f(x)約束下粒子的波函數ψ(x,t)的問題,許多優化問題關注的是f(x)的全局最小值,在物理系統中最小值對應于能量的最小值,在量子力學中被稱為基態.對于優化問題而言,其薛定諤方程的基態波函數ψ0(x,t)就描述了全局最優解的概率分布.優化問題的解不再是一個確定的值,而是一個由基態波函數所描述的概率分布,這更符合隨機優化算法的特點.

優化問題的薛定諤方程就是對優化問題的量子化描述,也是優化問題量子模型的理論基礎,它從理論上建立起了基態波函數與優化問題解的概率密度函數之間的關系.

2.2 優化問題的波函數及相關物理量定義

波函數是量子理論中的一個重要的概念,優化問題的薛定諤方程和優化問題解的量子化定義使波函數成為了描述和研究優化問題的核心理論工具.波函數與算法的迭代過程緊密相連,決定著當前算法的采樣函數.通過對波函數的定義,可以進一步對優化算法的能量、量子隧道效應和熵進行定義和研究.

2.2.1 優化算法波函數的定義

從理論上講,優化算法的波函數就是優化算法薛定諤方程的解ψ(x,t),它的模方 |ψ(x,t)|2就代表了當前解的概率分布.考慮到薛定諤方程下,波函數的疊加性,在實際應用中對于群體算法我們可以將個體采樣概率的疊加作為算法當前的波函數,這樣定義的波函數的數學含義為當前全局最優解的分布和當前算法采樣分布,即

其中,?i(x,t)為t時刻第i個可能薛定諤方程的解,ci為該解出現的幾率,k為解的個數.這種表示方法在QPSO 算法中得到應用,其對應的波函數就是k個拉普拉斯分布的疊加.算法波函數在迭代過程中會不斷變化,從而可以直觀地觀察到算法的收斂過程,波函數收斂過程的示例參見文獻[18-19].

2.2.2 優化算法的能量

優化問題在量子模型下轉變為求量子系統最低能量的問題,優化算法在迭代過程中能量會逐步減小.在經典模型下能量就是目標函數的值,如模擬退火算法當前的最優解就是當前算法的能量,而在量子模型下優化算法當前的能量是由波函數的概率分布所決定的,其計算方法為

其中,ψ(x,t)為算法當前的波函數,E0為目標函數值的理論最小值.由于在量子模型下優化算法的解被波函數以概率分布的形式所描述,所以優化算法的能量E就是算法當前解的數學期望.E0在黑盒模型下對于優化算法來說是未知的,因此在算法實際應用時往往只跟蹤前面部分的值來研究算法的收斂過程,這一能量稱為相對能量.

當算法迭代到某一尺度的基態時,算法能量達到這一尺度的最小值,這時的能量稱為零點能,尺度S下的零點能為

2.2.3 優化算法的量子隧道效應

在量子系統中粒子能通過勢壘貫穿出現在經典禁區,我們稱之為隧道效應,這是量子系統所特有的現象.如圖1 所示,在一個雙阱勢能函數中,不同量子特性的系統,對應了不同尺度的波函數.而粒子從X移動到X′出現在禁區的幾率為圖中陰影部分的面積.

圖1 量子隧道效應示意圖Fig.1 Schematic diagram of quantum tunneling effect

在優化問題的量子模型下隧道效應是算法跳出局部最優的一個基本機制[22],也是優化問題概率性和波動性的表現,優化算法針對任意區域 [a,b] 發生隧道效應的概率Pab可以利用波函數進行計算,即

在一些經典的優化算法中通常會包含一些差解接受機制,如模擬退火算法的Metropolis 準則、遺傳算法的變異操作等,其目的都是為了使算法能有機會跳出局部最優區域.優化問題在量子模型下由波函數的概率解釋所引起的隧道效應為優化算法跳出局部最優化區域提供了一個“自然”機制,優化算法并不需要刻意地采用某種跳出局部最優的機制,而只需要按照波函數的概率分布進行迭代演化.

2.2.4 優化算法的熵

優化問題的波函數可以對優化算法的迭代過程進行跟蹤,但對于高維目標函數其波函數無法直觀地表達;同時對于迭代過程通常希望能給出一個具有明確物理意義的量來研究算法的收斂過程.所以根據波函數的概率解釋,類比熵的定義可以定義優化算法的熵H,即

優化算法熵的物理意義為當前全局最優解的確定度,優化算法熵在每一次迭代時都有一個確定的值,它的值是由當前波函數所決定的,通常隨著算法的收斂,算法熵的值會逐步減小,熵的值越小說明算法針對全局最優解的確定度越大,因此算法熵代表了優化算法對當前最優解確定性的認識,也可以認為是對高維波函數的降維參數.

優化算法的熵隨迭代次數變化的曲線稱為熵收斂曲線,熵收斂曲線能反映算法對解確定度的收斂情況,與傳統收斂曲線相比具有更深刻的物理意義.熵收斂曲線可以作為優化問題量子模型下研究算法收斂過程的數學工具.

3 優化問題在量子理論下的探索

3.1 薛定諤方程下的隨機搜索過程

在將優化問題引入量子系統之后,就可以使用量子物理的手段對優化問題的求解過程進行研究.我們將通過量子理論中求解系統基態波函數的一種重要方法,擴散蒙特卡羅法(Diffusion Monte Carlo,DMC)[23],分析在量子模型下群體優化算法的隨機行為.

3.1.1 優化問題薛定諤方程與擴散方程的同構

擴散蒙特卡羅的基礎是基于薛定諤方程與擴散方程的同構.為了構造方程的同構,將式(3)中的時間t替換為τ,τ=it/?,此時含時薛定諤方程轉化為實域的擴散方程,即

同時,一維無熱源的熱傳導方程可以寫為

其中,v為擴散系數,u(x)為溫度的分布.對照含時的薛定諤方程和一維熱傳導方程可以發現,這兩個方程具有相同的結構.特別地,當系統未被約束時f(x)=0,此時優化問題的約束態量子模型退化為自由粒子模型,即

此時優化問題的薛定諤方程從形式上與擴散方程完全相同,這說明波函數ψ(x,τ)隨時間的演化過程和溫度的分布u隨時間的演化具有相似的行為.而擴散蒙特卡羅方法則是通過構造隨機粒子的擴散行為,模擬薛定諤方程下粒子的行為,實現波函數的演化過程.

3.1.2 優化問題薛定諤方程的求解

在擴散蒙特卡羅方法中,因為優化算法的時間演化過程可以采用粒子的擴散過程來進行描述,我們可以通過向薛定諤方程引入一定的能量位移來影響量子模型下優化算法的收斂迭代過程.通常用含時薛定諤方程來表示,即

這里ψ(x,τ)為隨時間演化的波函數,ER為參考能量,參考能量可以認為是優化算法當前獲得的最低能量,隨著算法迭代的進行參考能量會逐步下降.

假設f(x)在x→∞是有限的,粒子被限制在一個有限的空間內,通過分離變量法求解,方程的解為

其中,En為量子化的能級.當ER=E0時,E0為系統的基態能量,其他非基態波函數所對應的指數部分都會隨時間演化變為無窮小,只保留基態所對應的指數項,所以方程變為

式(14)說明當ER=E0時對應量子系統的初始波函數ψ(x,0)一定會演化收斂為基態波函數?0,這意味著當參考能量等于基態能量時無論選擇什么波函數作為初始波函數,最終都能收斂到基態波函數.而當ER＞E0時,波函數會隨著時間的演化不斷發散,當ER＜E0時,波函數會隨著時間的演化不斷耗散.擴散蒙特卡羅據此設計了基于參考能量的“生滅過程”,讓不符合條件(會使得波函數發散或耗散)的采樣點不繼續繁殖,通過參考能量調節隨機行走的粒子的擴散行為,最終影響波函數的演化結果,從而獲得低能量約束條件對應的基態波函數(粒子分布狀態).

量子模型下波函數的時間演化從理論上說明了薛定諤方程下優化算法的收斂行為,優化算法的迭代過程就是參考能量不斷向基態能量的逼近過程,當參考能量等于基態能量時就能確保收斂到基態波函數.

3.1.3 優化問題波函數的構造

從熱力學的觀點來看,擴散過程是大量粒子的一種群體行為,優化問題在量子模型下與擴散方程的相似性從量子理論的角度解釋了大量優化算法都采用群體策略的原因.薛定諤方程的時間演化說明,通過隨機生成初始的波函數,可以通過模擬群體的擴散行,隨時間向系統的基態波函數演化.因此參考式(4)和式(13)優化問題的初始波函數可以采用如下的構造方法:

這一構造方法采用在k個不同的位置以xi為中心生成k個預測的可能基態波函數ψ0(x-xi),其出現幾率為ci,并以 |ψ0(x-xi)|2為鄰域采樣函數分別生成k個新的可能位置在演化迭代過程中,通過比較采樣值與ER的關系,逐步調整波函數演化的過程,使參考能量向E0逼近,在擴散蒙特卡羅中,參考能量是種群數量相關的一個參考量.

相似地,在許多優化算法中,可以將當前最好的解作為對參考能量的估算.例如PSO 算法在迭代過程中參考群體歷史上的最優解和個體歷史上最優解,事實上就是以群體歷史上的最優解和個體歷史上最優解為參考能量,對種群個體進行調節的過程.

擴散蒙特卡羅方法是可以借鑒研究優化算法的隨機過程的一種物理方法,除此之外許多量子力學中求解基態波函數的方法,都可以用于分析隨機優化過程.

3.2 簡單勢阱對目標函數的逼近

雖然可以利用擴散蒙特卡羅之類的方法對優化問題的薛定諤方程進行求解,但基于以下原因我們無法直接獲得一個復雜目標函數f(x)所對應的基態波函數,需要通過對目標函數進行近似來獲得基態波函數的解.

1)對于復雜目標函數f(x)其對應的基態波函數也是一個復雜的概率密度函數.

2)薛定諤方程非常難解,只有對一些簡單的勢阱才能準確地獲得波函數的解析解.

3)對于優化問題來說,只需要知道在全局最優解附近的概率分布,因此可以采用較為簡單的勢阱模型對復雜目標函數進行逼近.

Taylor 展開是關于某一個點x0展開的,它可以在點x0附近對目標函數進行逼近.假設目標函數f(x)滿足Taylor 展開的條件,在全局最優極值點x0的Taylor 展開為

對于滿足Taylor 展開的任意目標函數f(x)其零階、一階和二階Taylor 展開分別為(函數在極值點的一階導數的值f′(x0)=0)

目標函數f(x)的零階和一階Taylor 展開均為常數,對應的量子模型為自由粒子.目標函數的二階Taylor 展開為諧振子勢能,這種勢阱經常作為平衡位置附近復雜振動的一種近似,其對應的基態波函數為高斯分布.如MQHOA 算法就是在這種勢阱逼近模型下所構造的算法,采用目標函數的二階近似已能獲得較好的優化性能[24-29].更高階的Taylor 展開所對應勢能的薛定諤方程很難解出一個簡單的概率分布作為基態波函數,所以通常不采用更高階的Taylor 展開作為目標函數的逼近.

在采用簡單勢阱對優化問題近似逼近后,相應地,可以通過式(15),利用不同勢阱下的基態波函數構造算法的鄰域采樣函數,以獲得不同的算法性能.同時Taylor 展開也不是唯一的近似方法,一些算法也會采用其他的逼近方法,例如QPSO 算法采用δ勢阱對目標函數進行逼近[30].也可以采用方勢阱對目標函數進行逼近,則優化算法的鄰域采樣分布為余弦分布.

不同優化算法鄰域采樣函數的選擇,可以在量子理論下解釋為對目標函數的某種勢阱逼近的基態波函數.不同的鄰域函數的構造連同不同的參考能量的選擇策略共同影響了優化算法的性能.

3.3 多尺度過程的量子化解釋

多尺度過程在優化算法中往往是一個必不可少的過程,大多數優化算法都會引入采樣步長收縮策略實現從全局搜索向局部搜索的變化.例如模擬退火算法中溫度的逐步下降過程;粒子群算法中慣性權重的變化過程;蟻群算法路徑構建時信息素和距離項本質上是在實現全局搜索和局部搜索的平衡.多尺度過程是一個性能良好的全局優化算法所必須的過程,我們希望采用量子理論中的不確定性原理對優化算法中的多尺度過程加以證明.

不確定性原理(Uncertainty principle)是Heisenberg 在1927 年首次提出的,不確定性原理認為粒子的位置和動量是一對不相容的觀察量,我們不能同時對其進行精確測量.量子理論中不確定性原理的一般性表述如下: 對于兩個可觀察物理量(Observables)A和B所對應的算符不對易(Non commuting).

則這兩個物理量不能同時精確測量,即

其中,ΔA和 ΔB為測量精度.

類似地,為了證明優化問題的不確定性原理,需要首先定義位置算符和尺度算符.優化問題的量子模型認為優化問題的解是采用波函數ψ(x)來描述的,在這一前提下優化問題的解不再是一個確定的值而是一個概率分布,這使得優化問題的解具有位置和尺度(尺度為頻率的倒數)兩個特性.在量子理論中物理觀察量算符是通過其平均值來定義的,優化問題的波函數代表了全局最優解的概率分布,因此全局最優解位置的平均值可以利用波函數得出,即

為了得到優化問題解的頻率算符,利用優化算法的波函數的傅利葉變換對頻率平均值計算式進行如下的數學變換:

根據量子理論中不確定性關系的一般定義,優化算法的解的位置算符和頻率算符之間的對易關系為

這一結論說明在量子模型的解釋下,任意優化算法在一個尺度下都不能同時精確獲得優化問題的解ψ(x)的頻率信息和位置信息.根據傅利葉分析的原理,大尺度下的搜索可以有效獲得目標函數的頻率信息(全局信息),但位置精度會較低,小尺度下的搜索具有較低的頻率精度,但具有較高的位置精度(局部信息).

優化問題的不確定性關系可以表述為: 單一尺度的搜索不可能同時獲得精確的全局搜索能力和局部搜索能力,多尺度過程是優化算法的一個必要過程.多尺度過程在一些量子算法,如量子退火算法中也是一個重要的過程,這類方法構造的物理系統能不斷降低體系的量子效應,從而實現多尺度優化[31-32],這也證明了優化算法中廣泛存在的多尺度過程的必要性.

4 量子理論下智能優化算法的實現

為驗證量子理論框架對智能優化算法研究的有效性,本節將基于前面內容中的理論內容簡述一種基于擴散蒙特卡羅方法的智能優化算法.在第2 節中,智能優化系統中采樣點的運動行為被假設能夠被薛定諤方程所描述,建立起了智能優化算法的量子力學基礎;在第3 節中,我們提到量子力學中的蒙特卡羅方法可以用作模擬擴散方程中粒子的運動行為,從而求解薛定諤方程.蒙特卡羅方法是一種基于薛定諤方程和擴散方程的同構性,利用隨機行走模擬粒子受擴散方程約束下的物理運動過程對優化問題進行求解的優化方法,其基礎迭代過程可以認為是量子理論下智能優化系統的基礎迭代過程.在此基礎上,通過算符的方法證明了算法多尺度過程的必要性,通過目標函數的Taylor 二階近似,將擴散蒙特卡羅這樣求解基態問題的方法轉換為求解全局最優問題.因此,在本節中將首先簡述其基礎迭代過程,在此基礎上融入前述內容中的多尺度過程和Taylor 二階近似下的中值替換策略,構造出新的算法,并通過CEC2013 測試集對該算法進行簡單的測試.

4.1 基于蒙特卡羅方法的基礎迭代過程

在擴散蒙特卡羅方法中,經Wick 轉動(τ=it/?)之后,時變薛定諤方程下粒子的概率幅度可以通過無數條可能軌跡上的積分來計算.通過路徑積分的方式,薛定諤方程的解可以表達為

其中,從時刻 0 到時刻τ平均分為N個部分,Δτ=τ/N(N→∞);其中與空間中粒子動能項相關的蒙特卡羅采樣方程為

其中,與粒子擴散過程中出現概率相關的權重函數為

路徑積分的公式描述了粒子在擴散反應過程中的運動和密度的變化,因其可以被蒙特卡羅方法求解,故稱之為擴散蒙特卡羅方法.為了獲得 Ψ (x,τ),擴散蒙特卡羅方法包含了擴散方程采樣和權重函數計算兩個階段

其中,當存在初態 Ψ (x0,0)時,終態 Ψ (xN,τ)可以被由隨機擴散P(xn,xn-1)和權重函數W(xn)所組成的隨機過程所獲得;在隨機擴散環節,新的粒子根據蒙特卡羅采樣方程產生;在概率函數分配環節,較差的粒子“死亡”,較好的粒子產生更多的新粒子,這便是大家所熟知的擴散蒙特卡羅方法中的“生滅”過程.

擴散蒙特卡羅方法將求解含時薛定諤方程約束態的問題轉化為了一個計算機可執行的隨機算法過程.可以認為薛定諤方程約束下智能優化系統的隨機迭代過程由粒子的蒙特卡羅采樣行為和權重函數計算兩個部分所組成.

4.2 基于多種群的多尺度量子諧振子算法實現

文獻[33]實現了多種群的疊加態量子諧振子算法(Multiple-population-based superposition state MQHOA,MPSS-MQHOA),其利用多種群的思想對蒙特卡羅迭代過程進行擴展,并針對數值優化中的全局優化問題進行調整,在算法中融入多尺度過程和Taylor 二階近似下的中值替換策略.現簡述其主要策略如下.

1)參考能量的選擇: 在蒙特卡羅方法中,ER參考能量會隨著時間不斷的動態調整,其目的是通過分支過程平衡種群的規模.MPSS-MQHOA 為了方便計算將種群規模ps設置為常數,在優化過程中,往往希望表現較差的粒子被緩慢地排除,以維持整個種群的多樣性并避免算法早熟的問題.因此將整個種群中最差的粒子,設置為參考能量.與此同時,算法為了避免早熟,在每輪迭代中有且僅有一個最差的子種群會被淘汰.其基于適應度值的參考能量ER可計算為

2)多種群的蒙特卡羅采樣: 在該過程中,每個子種群中的粒子根據式(31)產生,來確定其在n時刻的位置,由此,可以給出g個子種群的蒙特卡羅采樣方程為

其中,g是子種群的個數,psi是第i個子種群的規模,其可以通過權重函數的計算動態調整,σs是當前的搜索尺度,是在第i個子種群的最優粒子附近產生的第j個粒子.

3)子種群規模的調整: 在該過程中,根據式(32),算法中子種群的權重函數算法通過第g個種群的最優值計算.為實現“生滅過程”所獲得在優勢區域的粒子數量的積聚,在多種群粒子系統中,為緩解數值優化問題中適應度值的波動會導致權重函數劇烈的變化這一問題,適應度值的排序將被用于計算子種群的規模,算法的子種群規?？捎上率接嬎?

MPSS-MQHOA 算法的偽代碼如下:

在初始化步驟中,在整個搜索空間中隨機設置g個子種群的位置,并將搜索規模σs設置為UB和LB之間的值(搜索空間的上界和下界).算法的迭代過程主要包括粒子密度調節和蒙特卡羅采樣兩個階段.首先,根據式(36)計算每個子種群的種群大小psi.隨后,使用式(35)生成psi粒子當f(xi)＜時,粒子被更新.粒子系統的最差子種群在該循環結束時被消除.在尺度調整步驟中,搜索尺度σs隨著系數Cr逐漸減小.迭代過程不斷循環直到滿足終止標準,輸出最優值.

4.3 實驗及分析

為了驗證本文理論對算法設計的有效性,本節選取了基于種群方差的自適應微分進化(Population's variance-based adaptive differential evolution,PVADE)[34]、標準粒子群優化(SPSO2011)[35]、QPSO[17]、失敗者出局競標賽煙花算法(Loser-out tournament based fireworks algorithm,LoTFWA)[36]作為對照組與MPSS-MQHOA 進行比較.

所有的算法將在CEC2013 標準函數測試集[37]上進行實驗,每組實驗重復51 次,單次運算的最大迭代次數為10 000×D,其中D為維度,實驗維度設置為30.測試集一共包括28 個測試函數,根據函數結構不同可劃分為單模函數 (F1～F5),多模函數(F6～F20),組合函數 (F21～F28).所有函數的定義域為 [-100,100].實驗環境為Intel(R)Core(TM)i7-1160G7 CPU @ 1.20 GHz 2.11 GHz,16.0 GB,程序采用MATLAB2019 編寫.其中MPSS-MQHOA的粒子數設置為ps=300,子種群個數g=30,α=3,Cr=1.2;其他算法參數根據其文獻設置.實驗結果見表1,其中Mean 為誤差均值,Std.為解的標準差,最優的實驗結果在表中用粗體標出.

表1 PVADE,SPSO2011,QPSO,LoTFWA 和MPSS-MQHOA 在30 維CEC2013 測試集下平均誤差和標準差的對比實驗,所有算法的終止條件為MaxFES=300 000,所有實驗獨立重復51 次Table 1 Comparison of mean errors and standard deviations of PVADE,SPSO2011,QPSO,LoTFWA,MPSS-MQHOA,under 30D CEC2013 benchmark functions.The stopping condition for all schemes is set at MaxFES=300 000.The experiments are repeated 51 times individually

在單模函數上,PVADE 表現出了優異的性能,在除F5 外的所有函數上都排名第一.SPSO2011的表現略好于MPSS-MQHOA,在單模函數上排名第二,MPSS-MQHOA 排名第三.QPSO 和LoTFWA 除了在F1 上表現較好,在其他四個函數上都落后于其他三種算法,并列排名第四.在多模函數和組合函數上,根據平均排名,MPSS-MQHOA 排名第一,LoTFWA 排名第二,PVADE 表現出的性能較為均衡,取得第三的排名成績.SPSO2011 和QPSO 表現較差,分別排名第四和第五.

總的來說,如表1 所示,PVADE 在30 維問題上28 個函數中的11 個函數獲得了最小的平均誤差.在單模函數上,MPSS-MQHOA 和LoTFWA的平均誤差排名遠落后于PVADE.但這三種算法在所有28 個函數上的平均排名卻比較接近,說明后兩種方法在多模函數和組合函數上具有良好的性能.同時,具有多種群的MPSS-MQHOA 在30 維問題中獲得了13 個函數的最小平均誤差,其平均排名為第一.該實驗結果證明了基于量子框架所設計的算法相比于其他智能優化算法具有一定的競爭力,也間接證明了本文理論對算法設計的有效性.

5 優化問題與量子理論相關性的討論

在前面的各節中,我們從不同角度分析了優化問題與量子理論的關系.本節中將進一步闡明這些理論的相互關系,見表2所示.

表2 優化算法與量子理論的對應關系Table 2 The relationship between optimization algorithm and quantum theory

正如1976 年圖靈獎獲得者Rabin 所認為的: “應該放棄的只是以完全確定的方式獲得結果,這種結果可能出錯,然而出錯的可能性微乎其微”.不確定性不僅是概率算法構造的一個重要概念,在本文中,它同時也是概率算法量子特性的基礎.

從優化問題的不確定性出發,優化問題解的表達方式從一個確定的位置x變為了一個概率分布ψ(x).在可行域內某區域的解的分布的積分代表了在該區域解出現的幾率,這與量子理論中波函數的概率解釋是一致的,所以我們把這樣的概率分布的表達方式稱之為優化問題解的波函數.這也是我們進一步嘗試利用量子理論對優化問題進行討論與研究的基礎.在優化算法的研究中,使用數學的方法對隨機過程進行研究是困難的,而且通常需要對算法框架進行極大的簡化.所以本文建立優化問題的量子基礎的核心思想是通過優化問題與勢阱的等效對比,把優化問題作為薛定諤方程的約束條件引入量子系統,從而建立起薛定諤方程對隨機搜索過程的動態描述.在量子物理領域中,存在許多計算量子體系勢能的優化問題,這類問題與計算機領域中的優化問題并無本質區別,這也是我們可以借用量子系統對優化問題做類比研究的基礎.

在此基礎上,我們從量子理論的角度出發嘗試對優化問題進行了以下幾方面的探索與討論:

1)薛定諤方程下的隨機搜索過程: 在這一部分中,我們通過類比量子力學與計算機領域的優化方法來研究隨機搜索過程.本文中討論了擴散蒙特卡羅方法這一比較有代表性的隨機優化方法.該方法首先基于薛定諤方程與擴散方程的同構,把薛定諤方程轉換至實數域中,再對薛定諤方程的勢能約束條件(目標函數)引入了參考能量的概念,通過參考能量調節隨機行走的粒子的擴散行為,最終影響波函數的演化結果,從而獲得低能量約束條件對應的基態波函數(粒子分布狀態).單純從優化算法的角度來看,擴散蒙特卡羅之類的算法與優化領域的算法沒有任何區別,因此這類的方法中采用的數學物理手段,都可以用于研究分析優化算法,這也是建立優化問題與量子理論聯系的優勢所在.

2)目標函數的近似: 由于計算機領域和量子物理領域對優化問題求解的不同需求,我們首先需要把求解復雜目標函數轉換成求解一個簡單勢阱的問題.本文在選擇勢阱逼近模型時采用二階Taylor 近似逼近目標函數時的量子模型為量子諧振子模型,其對應的基態波函數為高斯分布.相似地,在QPSO算法中,δ勢阱用于對目標函數進行逼近,其對應的基態波函數為Laplace 分布;同時根據薛定諤方程下波函數的疊加特性,利用簡單勢阱的基態波函數,構造出優化系統的鄰域函數.這與概率優化系統中群體的概念是類似的,在一定程度上印證了優化系統的量子特性.同時,這一概念的有效性已被我們的前期研究所證明.并在這個框架下引入了更精細的算法機制來提高算法的性能[25-28].

3)多尺度過程: 在許多優化算法中,搜索尺度策略是影響算法性能的一個重要因素.我們通過量子系統中優化問題的波函數的解釋,類比地定義了優化問題物理量的算符.并通過位置算符和頻率算符的相互關系,證明了優化問題的測不準關系,從而從量子物理的角度證明了優化問題多尺度策略必要性.

上述討論說明優化問題與優化算法在量子理論的框架下可以得到部分的解釋,這說明優化問題與量子理論存在一定的相關性.為分析優化算法提供數學物理理論的支持.

6 結束語

本文針對優化問題量子特性展開討論,其目的并不是為了提出一種新的優化算法,而是希望為優化問題和優化算法的研究和分析提供一種新的視角.

本文通過對比研究表明,量子理論與優化問題之間確實存在廣泛的內在聯系,量子理論給出了描述優化問題的較為完備的數學框架,為研究優化問題提供了一種有明確物理意義的數學工具.雖然本文未對細節進行展開討論,但我們現有的研究表明,在這一模型指導下的算法設計是有效的,并且可以得到一些不錯的結果.

從優化領域的發展趨勢看提出新的優化算法不再是現在的研究焦點,探索為優化問題建立統一的理論模型在現階段變得尤為重要.量子理論作為優化問題統一模型的理論基礎是一個不錯的選擇,本文的研究結果也支持這一結論.但相關的研究還有待進一步的深入,事實上的確還有一些重要問題并沒有得到解決,例如優化算法的隱含并行性問題(Implicit parallelism)[38-39]的量子解釋,我們希望在今后的工作中完成.