王 鵬，王 方

(1.西南民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 成都 610225；2.廣東省國產(chǎn)服務(wù)器工程技術(shù)研究中心 廣州 510535；3.中國科學(xué)院成都計(jì)算機(jī)應(yīng)用研究所 成都 610041；4.中國科學(xué)院大學(xué) 北京 石景山區(qū) 100049)

量子力學(xué)誕生于20 世紀(jì)初，是在Einstein、Bohr、Schr?dinger、Heisenberg 等一大批天才的物理學(xué)家的共同努力下建立起來的，這是人類歷史上少有的由科學(xué)家群體共同努力建立的科學(xué)理論框架[1-2]。量子力學(xué)打破了人們從宏觀世界獲得的確定性世界觀“常識(shí)”，為我們描述了一個(gè)被概率和不確定性統(tǒng)治的微觀世界。物質(zhì)世界的運(yùn)動(dòng)規(guī)律本質(zhì)上是概率化的，電子雙縫實(shí)驗(yàn)、波函數(shù)和不確定性關(guān)系等量子力學(xué)中的實(shí)驗(yàn)和理論都在不斷地證明這一結(jié)論。量子力學(xué)揭示了物質(zhì)世界本質(zhì)的運(yùn)動(dòng)規(guī)律并被應(yīng)用于各個(gè)技術(shù)領(lǐng)域，成為現(xiàn)代科學(xué)和技術(shù)的基石。同時(shí)量子力學(xué)的普遍適用性也在不斷地得到證明，量子技術(shù)已成為一個(gè)國家科技實(shí)力的標(biāo)志性技術(shù)，是繼云計(jì)算、大數(shù)據(jù)、人工智能、區(qū)塊鏈技術(shù)之后，我國未來的一個(gè)新的戰(zhàn)略性新興技術(shù)領(lǐng)域。

不少文章在表述量子算法時(shí)都有所混淆。算法主要概括為兩種：1)采用物質(zhì)的量子效應(yīng)制造的量子計(jì)算機(jī)及其在上面運(yùn)行的算法。這種算法主要又包括兩類，一類是基于量子門的量子計(jì)算機(jī)及其算法[3-6]，另一類是基于量子退火原理的量子退火計(jì)算機(jī)及其算法[7-10]。其中量子退火計(jì)算機(jī)并不是通用量子計(jì)算機(jī)，它主要用于對(duì)優(yōu)化問題的求解[11-12]。2)借鑒量子力學(xué)中的一些概念，如量子比特、量子門，將這些概念用于改進(jìn)現(xiàn)有算法性能。這類算法還是運(yùn)行在經(jīng)典計(jì)算機(jī)上的，其所使用的量子特性可被認(rèn)為僅僅是一種數(shù)學(xué)上的操作。本文所介紹的優(yōu)化算法指的是后一種運(yùn)行在經(jīng)典計(jì)算機(jī)上的優(yōu)化算法。

由于優(yōu)化算法具有廣泛的應(yīng)用場(chǎng)景，經(jīng)過長期發(fā)展，經(jīng)歷了百花齊放的過程。量子理論中的一些觀點(diǎn)和方法在優(yōu)化算法中也得到過成功的應(yīng)用，但優(yōu)化領(lǐng)域一直面臨缺乏完備理論支持的問題，大量的優(yōu)化算法模型特別是自然模型都在從各自的視角對(duì)優(yōu)化算法進(jìn)行解釋。但由于這些自然模型往往缺乏完備的數(shù)學(xué)框架，所以一些自然模型所提出的理論框架事實(shí)上是人為“杜撰”的。量子力學(xué)是描述大自然最基礎(chǔ)、最本質(zhì)規(guī)律的一門學(xué)科，同時(shí)量子力學(xué)通過長期的發(fā)展已具備了完備的數(shù)學(xué)框架并被大量的實(shí)驗(yàn)所證明[13-14]，因此，將量子力學(xué)作為描述優(yōu)化算法的物理模型是可行的。

量子視角下的智能優(yōu)化算法研究有兩個(gè)方向：

1) 將量子計(jì)算中一些概念和數(shù)學(xué)機(jī)制應(yīng)用于已有的優(yōu)化算法，其目的是提升現(xiàn)有算法的性能。如量子遺傳算法(quantum-inspired genetic algorithms,QGA)利用量子位和量子疊加態(tài)對(duì)染色體進(jìn)行編碼，使一個(gè)染色體表示多個(gè)狀態(tài)的信息的同時(shí)使用量子旋轉(zhuǎn)門對(duì)種群進(jìn)行更新，以當(dāng)前最優(yōu)個(gè)體的信息為引導(dǎo)進(jìn)化[15]。在迭代過程中，每個(gè)量子位的疊加態(tài)將會(huì)塌縮到一個(gè)確定的狀態(tài)，從而趨于穩(wěn)定和達(dá)到收斂，最后實(shí)現(xiàn)尋優(yōu)的目的。量子蟻群算法(quantum ant colony algorithm,QACA)將量子計(jì)算和蟻群算法相結(jié)合，把量子計(jì)算中的態(tài)矢量和量子旋轉(zhuǎn)門引入到蟻群算法中，加速了算法的收斂速度[16]。量子人工魚群算法(quantum artificial fish school algorithm,QAFSA)用量子計(jì)算的方法重新描述了人工魚的行為，用量子比特對(duì)人工魚進(jìn)行編碼，用量子旋轉(zhuǎn)門實(shí)現(xiàn)人工魚的更新操作，用量子非門進(jìn)行人工魚變異，從而實(shí)現(xiàn)了目標(biāo)的優(yōu)化求解[17]。該方向應(yīng)用量子理論的目的不是為了解釋智能優(yōu)化算法，而只是單純地將量子力學(xué)中的一些方法作為提升算法性能的手段。由于量子力學(xué)描述的是一個(gè)概率化的微觀世界，量子機(jī)制通常都是概率化的，該方向的工作證明量子機(jī)制在智能優(yōu)化算法中常常是有效的。目前在智能優(yōu)化算法中使用的量子比特并不試圖從量子力學(xué)的角度對(duì)智能優(yōu)化算法做出解釋，而僅被作為一種可以借鑒的編碼機(jī)制。

2)基于智能優(yōu)化算法和量子力學(xué)在概率行為上的相似性，將優(yōu)化問題的目標(biāo)函數(shù)視為量子系統(tǒng)中的約束勢(shì)能，從而將優(yōu)化問題轉(zhuǎn)化為求量子系統(tǒng)的基態(tài)波函數(shù)問題。第二個(gè)方向的特點(diǎn)是將優(yōu)化問題從模型上視為量子問題，這樣量子力學(xué)的整個(gè)數(shù)學(xué)框架就能被應(yīng)用于對(duì)智能優(yōu)化算法的研究和分析，得到智能優(yōu)化算法迭代過程中的基本動(dòng)力學(xué)規(guī)律和基本操作。量子退火算法(quantum annealing algorithm,QAA)是這個(gè)研究方向的先驅(qū)，其利用Schr?dinger 方程，對(duì)優(yōu)化問題進(jìn)行了初步的建模，提出了勢(shì)能?優(yōu)化問題等效的概念，量子退火算法利用量子力學(xué)的隧穿效應(yīng)，在尋找全局最小值時(shí)更快地穿過局部極值點(diǎn)旁的勢(shì)壘從而找到最優(yōu)或接近最優(yōu)的解[18]。多尺度量子諧振子算法(multi-scale quantum harmonic oscillator algorithm,MQHOA)也使用Schr?dinger 方程[19]，將優(yōu)化過程轉(zhuǎn)換為在諧振子勢(shì)約束下的多尺度退火過程[20]，利用多尺度的概念，實(shí)現(xiàn)了量子擾動(dòng)的逐步減小和優(yōu)化系統(tǒng)對(duì)基態(tài)能量的逼近。這樣利用Schr?dinger方程構(gòu)建優(yōu)化模型的方法還有量子粒子群算法(quantum-behaved particle swarm optimization,QPSO)，其利用Delta 勢(shì)阱的假設(shè)，假設(shè)PSO 粒子群在虛擬的約束條件下運(yùn)行，構(gòu)建了其模擬量子優(yōu)化系統(tǒng)[21-22]。

從當(dāng)前研究情況來看，基于量子比特的智能優(yōu)化算法研究已進(jìn)行得相對(duì)充分，其主要應(yīng)用場(chǎng)景是性能改進(jìn)領(lǐng)域。而采用量子力學(xué)對(duì)智能優(yōu)化算法進(jìn)行建模，并利用量子力學(xué)的數(shù)學(xué)體系對(duì)智能優(yōu)化算法進(jìn)行研究目前尚處于初級(jí)階段，是今后一個(gè)非常有前途的研究方向，將對(duì)解決智能優(yōu)化算法領(lǐng)域當(dāng)前的一些挑戰(zhàn)具有建設(shè)性的作用。

本文結(jié)合智能優(yōu)化算法的最新研究進(jìn)展，對(duì)量子力學(xué)在智能優(yōu)化算法中的應(yīng)用進(jìn)行綜述。介紹了從基于量子比特的智能優(yōu)化算法向智能優(yōu)化算法的量子動(dòng)力學(xué)發(fā)展的過程，重點(diǎn)對(duì)智能優(yōu)化算法量子動(dòng)力學(xué)當(dāng)前取得的一些研究結(jié)果進(jìn)行了介紹，并展望了未來的研究方向。

1 智能優(yōu)化算法當(dāng)前面臨的挑戰(zhàn)

優(yōu)化問題是一類常見問題，在實(shí)際工程應(yīng)用中有大量的問題都可被抽象為優(yōu)化問題。求函數(shù)的最小值、尋找最優(yōu)路線和神經(jīng)網(wǎng)絡(luò)算法中獲得最優(yōu)的連接權(quán)重值等，都可被視為優(yōu)化問題。

以函數(shù)優(yōu)化為例，從數(shù)學(xué)的角度，一維函數(shù)優(yōu)化問題可以定義如下：

針對(duì)目標(biāo)函數(shù)f(x)在 實(shí)數(shù)定義域 [a,b]上的優(yōu)化問題，找到一個(gè)實(shí)數(shù)x0∈[a,b]，對(duì)于任意x∈[a,b]，滿足f(x0)≤f(x)，則稱x0為目標(biāo)函數(shù)在實(shí)數(shù)定義域[a,b]的全局最優(yōu)解。

以上定義是數(shù)學(xué)上對(duì)優(yōu)化問題的一個(gè)確定性的定義。數(shù)學(xué)上的優(yōu)化問題是要從理論上找到x0這一個(gè)確定的全局最優(yōu)解。而從算法的視角來看函數(shù)優(yōu)化問題則是將目標(biāo)函數(shù)假設(shè)為黑盒。黑盒假設(shè)認(rèn)為：目標(biāo)函數(shù)的表達(dá)式f(x)是未知的，智能優(yōu)化算法只能通過采樣確定從目標(biāo)函數(shù)定義域集合到值域集合中的每一個(gè)映射。每一次采樣就是對(duì)黑盒進(jìn)行的一次測(cè)量，測(cè)量的次數(shù)越多所獲得的目標(biāo)函數(shù)信息也越多。由于通常無法對(duì)目標(biāo)函數(shù)定義域進(jìn)行遍歷，所以智能優(yōu)化算法對(duì)目標(biāo)函數(shù)f(x)全局最優(yōu)解的位置的測(cè)量結(jié)果是不確定的，算法在運(yùn)行過程中并不知道它是否找到了全局最優(yōu)解。

回顧經(jīng)典計(jì)算機(jī)上的智能優(yōu)化算法的歷史，其發(fā)展經(jīng)歷了一個(gè)黃金時(shí)期，遺傳算法[23]、退火算法[24]、蟻群算法[25]和粒子群算法[26]等經(jīng)典的方法都在這一時(shí)期被提出，并很快被廣泛地應(yīng)用于各個(gè)領(lǐng)域。隨后，針對(duì)這些經(jīng)典智能優(yōu)化算法的改進(jìn)研究也成為了該領(lǐng)域的研究熱點(diǎn)，這使智能優(yōu)化算法的性能得到了快速的提升，并開始向高維大規(guī)模問題進(jìn)行挑戰(zhàn)。受前期經(jīng)典智能優(yōu)化算法構(gòu)造思路的啟發(fā)，許多算法研究者不斷地采用新的啟發(fā)式模型并據(jù)此不斷提出新的方法。很快智能優(yōu)化算法領(lǐng)域變得百花齊放，每一個(gè)性能優(yōu)良的新智能優(yōu)化算法后面都有一批跟進(jìn)的研究者，并形成一個(gè)又一個(gè)的研究團(tuán)體和派別，此時(shí)智能優(yōu)化算法的研究進(jìn)入了鼎盛時(shí)期。

然而智能優(yōu)化算法研究的隱憂卻也在逐漸顯現(xiàn)出來，總結(jié)為以下兩點(diǎn)：

1) 大量的智能優(yōu)化算法模型來自于對(duì)自然現(xiàn)象的模擬，在理論分析時(shí)很難為這些復(fù)雜的體系建立完備的理論模型，這阻礙了對(duì)智能優(yōu)化算法的深入研究；

2) 不同的智能優(yōu)化算法中存在著同質(zhì)化的機(jī)制和操作。如很多算法都采用了均勻采樣或正態(tài)采樣，抑或是多尺度行為，但卻由于算法模型的不同被割裂地解釋為不同的原理。

這些問題已被一些優(yōu)化領(lǐng)域的學(xué)者注意到了。文獻(xiàn)[27]提出“現(xiàn)在優(yōu)化計(jì)算領(lǐng)域的研究，重要的不是提出新的算法而是為優(yōu)化算法建立普遍適用的規(guī)則和策略，研究?jī)?yōu)化問題和優(yōu)化算法中的共性問題”。文獻(xiàn)[28]提出“不鼓勵(lì)大家再提出新的優(yōu)化算法，這些新算法可能只會(huì)分散解決優(yōu)化中真正具有挑戰(zhàn)性和真正重要問題的注意力”。因此，有研究者認(rèn)為當(dāng)前大量的新算法是對(duì)舊算法的新偽裝，并認(rèn)為這一時(shí)代即將結(jié)束[29-30]。這時(shí)需要更深刻地去認(rèn)識(shí)優(yōu)化問題，解釋智能優(yōu)化算法的基本操作和核心迭代過程，避免在漫無目的的探索中去提出各種所謂的新算法，這可能是當(dāng)前智能優(yōu)化算法研究的一個(gè)重要方向。

2 選擇量子力學(xué)

量子力學(xué)所描述的是被概率所統(tǒng)治的世界圖像，而智能優(yōu)化算法在不確定性算法的基礎(chǔ)上大量地在使用概率化的搜索行為。這使得量子力學(xué)所描述的世界體系與智能優(yōu)化系統(tǒng)在概率上存在著一定的相似性，這正是采用量子力學(xué)視角對(duì)智能優(yōu)化算法進(jìn)行研究的基礎(chǔ)。事實(shí)上，量子力學(xué)對(duì)現(xiàn)代計(jì)算機(jī)技術(shù)的發(fā)展有著深刻的影響，不少計(jì)算機(jī)科學(xué)的開創(chuàng)者都在研究量子力學(xué)，甚至還為量子力學(xué)做出過巨大貢獻(xiàn)?，F(xiàn)代計(jì)算機(jī)之父von Neumann 寫出了《量子力學(xué)的數(shù)學(xué)基礎(chǔ)》[31]，1931 年Turing 認(rèn)真研讀了這本書。而且早在1929 年，Turing 還著迷于天文學(xué)家Eddington 所著的《物理世界的本質(zhì)》[32]，Eddington 也認(rèn)為“大腦也是由原子、電子組成的，量子物理或許能為人類意識(shí)、思維提供產(chǎn)生的機(jī)會(huì)和空間”。

1926 年Schr?dinger 提出了量子力學(xué)中最為著名的方程——Schr?dinger 方程：

式中，V(x) 為 勢(shì)能；ψ (x,t)為波函數(shù)。1927 年，Born給出了Schr?dinger 方程中波函數(shù)的概率解釋[33]，他認(rèn)為波函數(shù)代表了微觀粒子的概率分布，而且波函數(shù)也完整地表達(dá)了一個(gè)微觀粒子的運(yùn)動(dòng)狀態(tài)。Born的解釋建立了波函數(shù)與概率分布之間的關(guān)系，揭示了一個(gè)由概率行為所統(tǒng)治的微觀世界。

量子力學(xué)在Born 的概率解釋下與智能優(yōu)化算法搜索過程中的隨機(jī)性存在著深刻的內(nèi)在聯(lián)系。這一點(diǎn)提示我們采用量子理論的視角對(duì)優(yōu)化問題和智能優(yōu)化算法進(jìn)行建模是一種可行的思路。隨機(jī)性也是計(jì)算機(jī)智能產(chǎn)生的根源之一，文獻(xiàn)[34]指出“隨機(jī)性的程度決定了智能的高低”，這一論斷指出了智能的本質(zhì)是隨機(jī)性。包括人類的智能也來自于隨機(jī)性，一個(gè)充滿了隨機(jī)性的世界通過長期演化才出現(xiàn)了人類。1976 年，圖靈獎(jiǎng)獲得者Rabin 認(rèn)為“應(yīng)該放棄的只是以完全確定的方式獲得結(jié)果，這種結(jié)果可能出錯(cuò)，然而出錯(cuò)的可能性微乎其微，也就是說可以把概率算法用到這類問題中來”。Rabin 的論斷可以理解為以犧牲確定性來獲得較高的計(jì)算效率，他從技術(shù)層面給出了實(shí)現(xiàn)智能的方法就是放棄對(duì)確定性的追求?，F(xiàn)代人工智能算法幾乎無一例外的采納了Rabin 的建議，這說明越來越多的學(xué)者認(rèn)識(shí)到智能產(chǎn)生于隨機(jī)性。而由量子力學(xué)所描述的物質(zhì)世界的本質(zhì)運(yùn)行規(guī)律正好是概率化的，采用量子力學(xué)對(duì)智能優(yōu)化算法進(jìn)行研究是基于自然哲學(xué)的本質(zhì)要求。2018 年11 月李國杰院士在《中國計(jì)算機(jī)學(xué)會(huì)通訊》上發(fā)表了題為《計(jì)算機(jī)科學(xué)基礎(chǔ)理論需要重塑》的卷首語，他指出“量子力學(xué)改變了傳統(tǒng)的邏輯定義，把概率看成了邏輯的內(nèi)在組成。在計(jì)算機(jī)領(lǐng)域，構(gòu)造一臺(tái)完全公理化驅(qū)動(dòng)的自動(dòng)機(jī)也不現(xiàn)實(shí)，而對(duì)復(fù)雜環(huán)境，需要放棄嚴(yán)格邏輯而改用概率邏輯”。正如著名量子物理學(xué)家Feynman 所說：“自然不是經(jīng)典的，如果你想模擬自然，你最好把它變成量子力學(xué)?！倍?Feynman也最早指出了量子計(jì)算機(jī)的可行性，開啟了量子計(jì)算時(shí)代[35]。對(duì)于量子力學(xué)在智能優(yōu)化算法中的應(yīng)用不應(yīng)只是停留在借鑒層面，由于優(yōu)化問題和智能優(yōu)化算法自身的概率特性，智能優(yōu)化算法的迭代過程或可能被量子理論的基本規(guī)律所描述。

3 隱含并行性

研究量子視角下的智能優(yōu)化算法，可以先從隱含并行性開始。量子力學(xué)中的概率機(jī)制所帶來的不確定性正是用量子模型來描述智能優(yōu)化算法的原因。隱含并行性的起源也是來自于不確定性，這或許也是智能算法所具有的解空間高速搜索能力的原因。雖然量子智能優(yōu)化算法研究的是經(jīng)典計(jì)算機(jī)上的智能優(yōu)化算法，但由不確定性造成的隱含并行計(jì)算能力也是不應(yīng)該回避的話題。

各類智能優(yōu)化算法獲得高效的解空間搜索能力的原因都是在某種程度上犧牲了對(duì)解的確定性的要求。如果要求以100%的概率找到最優(yōu)解則只能使用強(qiáng)力搜索，這在大多數(shù)復(fù)雜優(yōu)化問題中是不可能實(shí)現(xiàn)的。因此幾乎所有的智能優(yōu)化算法都不同程度地使用了隨機(jī)數(shù)和概率策略，這些策略的引入使智能優(yōu)化算法能在可以接受的時(shí)間內(nèi)獲得準(zhǔn)確度可以接受的解。這種搜索速度提高的現(xiàn)象被稱為算法的隱含并行性(implicit parallelism)。

算法的隱含并行性有別于算法的內(nèi)在并行性(inherent parallelism)。內(nèi)在并行性是指算法本身非常適合大規(guī)模并行，可以同時(shí)讓幾百甚至數(shù)千臺(tái)計(jì)算機(jī)各自獨(dú)立進(jìn)行計(jì)算，運(yùn)行過程中基本不做任何消息通信。對(duì)于隱含并行性在其他智能優(yōu)化算法中的情況，目前的研究資料還極度缺乏，其實(shí)這是一個(gè)十分重要的研究課題，它涉及到了智能算法的內(nèi)在核心問題，但由于本身問題的理論困難，研究一直相對(duì)緩慢。

隱含并行性的研究開始于20 世紀(jì)70 年代，目前對(duì)隱含并行性的研究多集中于遺傳算法。1975年文獻(xiàn)[36]首次提出了隱含并行性的概念，并指出隱含并行性是遺傳算法能夠快速有效搜索的根本原因。雖然隱含并行性是廣泛存在于智能算法中的一個(gè)重要特性，但有關(guān)其他智能算法隱含并行性的研究長期以來沒有得到國內(nèi)外學(xué)者的重視。

根據(jù)文獻(xiàn)[36]定義的隱含并行性，結(jié)構(gòu)重組等遺傳操作可以使被采樣的模式數(shù)盡可能的多，這樣可以帶來較大的隱含并行性。遺傳算法每代雖然只處理了N個(gè)個(gè)體，但隱含處理的模式數(shù)遠(yuǎn)遠(yuǎn)大于N。針對(duì)這一定義，文獻(xiàn)[37]指出遺傳算法每代雖然只顯示處理N個(gè)個(gè)體串，實(shí)際隱含處理的模式數(shù)下界為，其中c1為 一個(gè)小整數(shù)，l為串長。這一下界表明模式數(shù)和N3成正比，也就是說遺傳算法每代雖然只顯示處理N個(gè)個(gè)體串，但是隱含處理了至少N3個(gè)模式。遺傳算法這種隱含處理能力正是該算法在解空間快速搜索的原因，隨后其他學(xué)者對(duì)這一結(jié)論展開了進(jìn)一步研究[38-41]。遺傳算法[42]在這一結(jié)論的基礎(chǔ)上進(jìn)一步證明了隱含處理的模式數(shù)的下界為緊下界。國內(nèi)有關(guān)隱含并行性的研究也是針對(duì)遺傳算法進(jìn)行的，文獻(xiàn)[43]進(jìn)一步研究了遺傳算法隱含處理的模式數(shù)，給出了對(duì)任意串長l及群體規(guī)模N，在等概率抽取每個(gè)群體的條件下，遺傳算法每代所處理的模式長度不超過ls的不同模式期望數(shù)的精確表達(dá)。文獻(xiàn)[44]給出了每代至少產(chǎn)生O(2N?1)數(shù)量級(jí)的新模式。

1975 年Rabin 等人提出的檢測(cè)素?cái)?shù)的不確定性方法Miller-Rabin 檢測(cè)法正是一種以犧牲確定性來獲得快速檢測(cè)素?cái)?shù)的方法。Miller-Rabin 檢測(cè)法對(duì)待檢測(cè)數(shù)n進(jìn) 行k次試驗(yàn)所需的時(shí)間為O(log3n)，而出錯(cuò)的概率不超過1 /2k。目前這一素?cái)?shù)檢測(cè)方法也是檢測(cè)素?cái)?shù)最快的方法之一，其本質(zhì)上也是通過犧牲確定性構(gòu)造出具有隱含并行性的算法，其獲得的隱含并行計(jì)算能力也是指數(shù)級(jí)的。

文獻(xiàn)[45]從遺傳算法和模擬退火算法的隱含并行性入手，利用物理學(xué)中的不確定性原理以及熱力學(xué)中的熵對(duì)隱含并行性進(jìn)行分析，指出算法隱含并行性的根源是不確定性和高熵態(tài)。文獻(xiàn)[46-47]分析了隱含并行性與不確定性的關(guān)系，并從哲學(xué)角度對(duì)不確定性進(jìn)行了分析。研究表明隱含并行性是智能算法中普遍存在的重要機(jī)制。隱含并行性的研究結(jié)果為智能優(yōu)化算法的設(shè)計(jì)指出了一個(gè)重要的原則：犧牲算法確定性可能獲得更好的計(jì)算效率。由于隱含并行性可能是指數(shù)級(jí)的，因此這種確定性的犧牲在算法實(shí)踐中是可以接受的，事實(shí)上大多數(shù)的智能優(yōu)化算法和智能算法都不同程度地采用了這種策略。

總之，隱含并行性作為一種反映算法內(nèi)在快速搜索能力的指標(biāo)一直以來未被研究者所重視。算法隱含并行性至今還沒有嚴(yán)格的數(shù)學(xué)定義，特別是不確定性與隱含并行性之間的對(duì)應(yīng)關(guān)系還未得出結(jié)論，相關(guān)研究工作主要也還是針對(duì)遺傳算法在進(jìn)行。近年來算法隱含并行性的研究更是處在停頓狀態(tài)，幾乎無法檢索到相關(guān)論文，國內(nèi)的研究者更是寥寥，這個(gè)非常重要的研究方向被大家所忽略了。

4 基于量子比特的智能優(yōu)化算法

算法的隱含并行性要求一個(gè)算法要構(gòu)造一個(gè)具有概率特性的算法結(jié)構(gòu)和算法操作，量子力學(xué)所具有的天然的概率特性成為了描述和研究?jī)?yōu)化問題的一個(gè)有力的理論武器。量子力學(xué)中的粒子可以處于多種本征態(tài)的疊加態(tài)，這是量子力學(xué)所描述的一種非常奇特的現(xiàn)象，最有名的思想實(shí)驗(yàn)就是Schr?dinger 的貓，量子疊加態(tài)在經(jīng)典世界是非常難以理解的。量子比特是量子疊加態(tài)原理的一種特殊情況，如果一個(gè)量子系統(tǒng)只有兩個(gè)狀態(tài)，采用Dirac 算符分別用 |0〉和 |1〉來表示這兩個(gè)狀態(tài)，它可以用來描述一個(gè)基于二進(jìn)制編碼的系統(tǒng)。在經(jīng)典計(jì)算機(jī)中一個(gè)bit 只能是0 或1，也就是說只能處于|0〉態(tài)和|1〉態(tài)。而在量子系統(tǒng)中一個(gè)量子比特可以處于兩種狀態(tài)的疊加，即：

式中，α 和 β 是分別處于兩種態(tài)的概率幅，α2+β2=1。狀態(tài)φ 既不是0 也不是1，而是處于0 和1 的疊加態(tài)。在對(duì)這種疊加態(tài)進(jìn)行觀察時(shí)會(huì)按概率坍縮到其中一個(gè)態(tài)。

量子比特這一概念是智能優(yōu)化算法設(shè)計(jì)時(shí)常采用的一個(gè)機(jī)制。最早應(yīng)用這一機(jī)制的是遺傳算法，1996 年文獻(xiàn)[15]提出了量子遺傳算法(quantuminspired genetic algorithms,QGA)求解旅行商問題，并將這一算法稱為量子啟發(fā)式算法，他們借鑒了量子疊加原理構(gòu)造了一個(gè)具有“多宇宙”的策略，可以認(rèn)為是一個(gè)多種群的策略。

2000 年，文獻(xiàn)[48]提出遺傳量子算法，采用量子比特的概念提高對(duì)背包問題的求解能力，量子比特提高了算法的隨機(jī)性，對(duì)于算法的全局搜索能力是有益的。2002 年文獻(xiàn)[49]將算法的名稱改為量子進(jìn)化算法(quantum-inspired evolutionary algorithm,QEA)，完整的結(jié)果發(fā)表在TEVC 雜志上。他們的基本思路是將量子比特的概念與遺傳算法的基本操作相結(jié)合，采用量子比特來改造遺傳算法二進(jìn)制編碼機(jī)制，使遺傳算法的經(jīng)典二進(jìn)制編碼串成為量子比特串。通過量子比特改造的具有n位長度的遺傳算法二進(jìn)制編碼可以表示為：

與經(jīng)典的二進(jìn)制表達(dá)相比，量子比特使二進(jìn)制串的不確定性大大增加。如果采用量子比特所構(gòu)成的串并對(duì)其進(jìn)行多次測(cè)量，則任意一個(gè)可能解都會(huì)以一定的概率出現(xiàn)。如具有3 個(gè)量子比特的量子串為：

這個(gè)串是由3 個(gè)量子比特構(gòu)成：

量子比特所構(gòu)成的量子比特串擁有強(qiáng)大的表達(dá)力，它蘊(yùn)含了所有解出現(xiàn)的概率。假設(shè)最優(yōu)解為二進(jìn)制串101，則其在測(cè)量過程中出現(xiàn)的概率為，也就是說量子比特串中以一定概率隱含最優(yōu)解。量子比特串使確定性的二進(jìn)制串變成了解的概率疊加，從而大大增加了算法迭代過程中解的不確定性。對(duì)于長度為n的量子比特串的任何操作等效于對(duì) 2n個(gè)不同經(jīng)典比特串的操作。

量子比特在理論和實(shí)踐上的成功使不少研究者進(jìn)入這一領(lǐng)域，構(gòu)造出了一批基于量子比特的量子智能優(yōu)化算法。2007 年同樣采用量子比特機(jī)制的量子蟻群算法被提出[16]，2010 年量子魚群算法被提出[17]，文獻(xiàn)[50-51]也將量子比特用于免疫克隆算法中并提出了量子免疫克隆算法。

這一類基于量子比特的算法是將量子比特的數(shù)學(xué)框架作為一種通用手段應(yīng)用于已有的算法，以提高已有算法的性能，特別是全局搜索性能。由于量子比特的引入必然會(huì)增加算法迭代過程中的不確定性，從而使迭代過程不易陷入局部最優(yōu)。理論上這對(duì)基礎(chǔ)算法效果的改進(jìn)是可行的，但這類研究并未從智能優(yōu)化算法本身量子特性的角度來考慮，因此無法依據(jù)量子力學(xué)的知識(shí)獲得智能優(yōu)化算法的核心基礎(chǔ)操作。

5 量子退火算法與優(yōu)化問題的量子可描述性

采用量子比特來構(gòu)造量子計(jì)算機(jī)和智能優(yōu)化算法是基于對(duì)經(jīng)典計(jì)算機(jī)的慣性認(rèn)識(shí)，量子計(jì)算不一定要采用基于比特的邏輯運(yùn)算來實(shí)現(xiàn)。在量子計(jì)算領(lǐng)域中，優(yōu)化問題是被解決得最好的，這得益于優(yōu)化問題可以有效的被量子模型所描述。量子退火理論及量子退火計(jì)算機(jī)的出現(xiàn)為這一問題提供了確切的證據(jù)。

1994 年文獻(xiàn)[52]提出可以將優(yōu)化問題的目標(biāo)函數(shù)f(x)視 為量子系統(tǒng)中的勢(shì)能V(x)(稱為勢(shì)能等效關(guān)系，equivalence of potential energy,EPE)，即V(x)=f(x)，從而可以通過量子退火過程或擴(kuò)散蒙特卡羅方法(Diffusion Monte Carlo,DMC)來獲得系統(tǒng)的基態(tài)[52]。如果將勢(shì)能等效關(guān)系條件下量子系統(tǒng)的基態(tài)視為優(yōu)化問題的解，則該工作從理論上證明了智能優(yōu)化算法的迭代過程演化可以采用含時(shí)Schr?dinger 方程來描述。并認(rèn)為量子退火與經(jīng)典退火的不同之處在于量子退火通過量子隧道效應(yīng)在優(yōu)化過程中實(shí)現(xiàn)跳出局部最優(yōu)，并且隧道效應(yīng)的大小與量子系統(tǒng)的質(zhì)量有關(guān)，這一點(diǎn)指出了智能優(yōu)化算法的多尺度過程。文獻(xiàn)[52]還采用這一方法計(jì)算了 Lennard-Jones 勢(shì)下的分子團(tuán)簇最低能量。DMC 方法是上世紀(jì)70 年代文獻(xiàn)[53]首次提出的一種采用隨機(jī)行走(random walk)求解分子Schr?dinger 方程基態(tài)波函數(shù)的方法。DMC 利用了Schr?dinger 方程和擴(kuò)散方程之間的同構(gòu)性，模擬擴(kuò)散過程推動(dòng)波函數(shù)逐步向基態(tài)演化，從而實(shí)現(xiàn)對(duì)目標(biāo)函數(shù)全局最優(yōu)化解的搜索。文獻(xiàn)[54]對(duì)擴(kuò)散蒙特卡羅方法進(jìn)行了非常深入細(xì)致的介紹，文獻(xiàn)[55]針對(duì)量子退火的綜述是目前國內(nèi)較為完整的。

1998 年文獻(xiàn)[56]提出可以采用位于橫向磁場(chǎng)中的Ising 模型實(shí)現(xiàn)量子退火過程的方案，并對(duì)此方案進(jìn)行數(shù)值仿真，證明其比經(jīng)典退火過程具有更好的收斂于基態(tài)的能力。在這一模型中，橫向磁場(chǎng)被作為與溫度相似的擾動(dòng)能量，推動(dòng)量子系統(tǒng)以絕熱過程的方式向基態(tài)演化。此工作的意義在于為量子退火計(jì)算機(jī)的研究提供了具體實(shí)現(xiàn)路徑。

Ising 模型是統(tǒng)計(jì)物理中的一種模型，它具有表述簡(jiǎn)單、內(nèi)涵豐富和應(yīng)用廣泛的特點(diǎn)，甚至在社會(huì)科學(xué)中都得到了成功的應(yīng)用。將Ising 模型作為實(shí)現(xiàn)量子退火算法的理論方案，這意味著只要能找到可以形成Ising 模型的實(shí)際物理系統(tǒng)，就能按照他們的方案實(shí)現(xiàn)量子退火計(jì)算機(jī)。

Ising 模型由具有向上和向下兩個(gè)方向的小磁針排列組合而成，向上取1，向下取?1：

在小磁針排列為 {si}時(shí) 系統(tǒng)的總能量為：

式中，J為能量耦合常數(shù)；〈ij〉代表對(duì)所有相鄰小磁針進(jìn)行求和，如si=sj總能量減小J；H為外磁場(chǎng)強(qiáng)度，磁場(chǎng)向上為正，向下為負(fù)，如果小磁針方向也和外場(chǎng)一致，總能量減少一個(gè)單位。這表明在Ising 模型中所有磁針方向一致并與外磁場(chǎng)方向相同時(shí)能量最低。當(dāng)外界溫度T越高時(shí)，就有數(shù)量越多的小磁針發(fā)生隨機(jī)翻轉(zhuǎn)。翻轉(zhuǎn)后小磁針的排列狀態(tài)為，如果此時(shí)能量則接受這次翻轉(zhuǎn)；如果此時(shí)能量，則以概率接受這一翻轉(zhuǎn)。在這一機(jī)制下系統(tǒng)會(huì)向能量較低方向演化，最終到達(dá)如下的能量分布狀態(tài)，即玻爾茲曼分布：

文獻(xiàn)[56]設(shè)計(jì)的量子退火方法采用橫向磁場(chǎng)Γ(t)作 為能量擾動(dòng)，橫向磁場(chǎng)強(qiáng)度 Γ(t)隨時(shí)間逐步降低，推動(dòng)系統(tǒng)達(dá)到基態(tài)。

因此量子退火過程采用Schr?dinger 方程描述為：

從智能優(yōu)化算法的角度看這其實(shí)是表達(dá)一個(gè)多尺度的搜索過程，Γ (t)的值逐步減小時(shí)量子隧道效應(yīng)逐步降低，搜索尺度減小。

1999 年文獻(xiàn)[57]在《Science》上報(bào)道他們成功地采用Ising 磁體材料在橫向磁場(chǎng)內(nèi)實(shí)現(xiàn)了簡(jiǎn)單的量子自旋模型。這一成果為采用量子退火計(jì)算機(jī)實(shí)現(xiàn)對(duì)優(yōu)化問題的求解找到了一個(gè)具體實(shí)現(xiàn)方案，并首次從實(shí)驗(yàn)上證明了量子退火在求解優(yōu)化問題中的可行性。意大利高等國際研究院(International School for Advanced Studies,SISSA)的一個(gè)項(xiàng)目組也對(duì)量子退火在優(yōu)化問題中的實(shí)現(xiàn)進(jìn)行了大量的研究，證明了這一方法在實(shí)踐中的可行性[58-59]。

2011 年基于量子退火原理的D-Wave 量子計(jì)算機(jī)成為了世界上第一臺(tái)可以商用的量子退火計(jì)算機(jī)，D-Wave 同樣采用了橫向場(chǎng)Ising 模型，D-Wave中的量子比特不是用于量子門操作的，而是用于構(gòu)造Ising 模型的[60]。D-Wave 主要的用途就是進(jìn)行優(yōu)化問題的求解，D-Wave 在求解優(yōu)化問題時(shí)并不涉及具體的算法，而是通過退火過程由大自然給出問題的答案。

從隱含并行性的觀點(diǎn)來看，D-Wave 獲得快速求解優(yōu)化問題的能力也是由于對(duì)于最終解的確定性的放松，其加速效果是針對(duì)強(qiáng)力搜索算法而言的。事實(shí)上大多數(shù)運(yùn)行在經(jīng)典計(jì)算機(jī)上的智能優(yōu)化算法都能在較短的時(shí)間內(nèi)獲得一個(gè)組合優(yōu)化問題的可行解，其采用的方法也放松了對(duì)解正確性的嚴(yán)格要求。量子退火計(jì)算機(jī)和經(jīng)典計(jì)算機(jī)上的智能優(yōu)化算法獲得的快速計(jì)算能力都可以利用隱含并行性得到解釋，量子退火計(jì)算機(jī)并不一定會(huì)比經(jīng)典計(jì)算機(jī)上的智能優(yōu)化算法快，只是兩者運(yùn)行的物理載體不一樣。

量子退火技術(shù)在解決優(yōu)化問題的理論和實(shí)踐上的成功證明了優(yōu)化問題具有量子可描述性，即可以采用一個(gè)量子模型對(duì)優(yōu)化問題進(jìn)行描述，同時(shí)智能優(yōu)化算法的迭代演化過程也可以由一個(gè)量子系統(tǒng)的演化過程來描述。當(dāng)按照量子退火算法中的勢(shì)能等效關(guān)系對(duì)智能優(yōu)化算法進(jìn)行建模后，可以發(fā)現(xiàn)智能優(yōu)化算法的迭代采樣過程就是滿足Schr?dinger 方程所描述的演化過程的。

量子動(dòng)力學(xué)在智能優(yōu)化算法中的應(yīng)用得益于量子科學(xué)領(lǐng)域中量子退火算法的出現(xiàn)。智能優(yōu)化算法的研究人員在廣泛借鑒量子比特這一概念時(shí)，對(duì)物理學(xué)中的量子退火方法有所忽略，而正是量子退火算法才真正的指出了智能優(yōu)化算法與量子理論之間密切的聯(lián)系，而不僅僅是概念的借鑒。

將量子力學(xué)引入智能優(yōu)化算法更為重要的目的是希望能采用量子力學(xué)的數(shù)學(xué)框架分解出智能優(yōu)化算法迭代過程的基本操作。智能優(yōu)化算法的迭代過程是一個(gè)時(shí)間演化過程，因此描述智能優(yōu)化算法的數(shù)學(xué)工具應(yīng)該是一種動(dòng)力學(xué)方程。量子退火思想的引入為建立智能優(yōu)化算法的量子模型提供了契機(jī)，量子退火在處理優(yōu)化問題時(shí)具有獨(dú)特的優(yōu)勢(shì)。

量子退火的核心思想有4 點(diǎn)：

1) 將優(yōu)化問題的目標(biāo)函數(shù)視為量子系統(tǒng)中的粒子勢(shì)能；

2) 量子系統(tǒng)能量最低的基態(tài)就是優(yōu)化問題的解；

3) 通過逐步降低外在能量擾動(dòng)使量子系統(tǒng)能量逐步演化到基態(tài)；

4) 優(yōu)化問題的解采用概率化的波函數(shù)進(jìn)行表達(dá)。

6 量子動(dòng)力學(xué)理論

量子退火的思想為建立智能優(yōu)化算法的量子模型提供了思路，智能優(yōu)化算法有可能自身就是一個(gè)可以被量子力學(xué)所描述的過程，即可以用Schr?dinger方程來完整地描述智能優(yōu)化算法的時(shí)間演化過程。與量子退火理論相似，如果將優(yōu)化問題的目標(biāo)函數(shù)f(x)作 為量子系統(tǒng)中粒子的約束勢(shì)能V(x)，即V(x)=f(x)，就可以得到如下的智能優(yōu)化算法的Schr?dinger方程：

這一思想在文獻(xiàn)[21-22]提出的量子粒子群算法中得到了部分的采用。QPSO 算法的經(jīng)典版本采用 δ勢(shì)阱對(duì)應(yīng)的基態(tài)波函數(shù)來構(gòu)造采樣函數(shù)，受粒子群算法的影響并未明確指出V(x)=f(x)的關(guān)系，算法的整體構(gòu)造思路不是徹底量子化的，算法的核心迭代結(jié)構(gòu)還是以粒子群算法為基礎(chǔ)。QPSO 算法在性能上獲得了成功，但在高維函數(shù)優(yōu)化時(shí)容易陷入局部最優(yōu)。QPSO 將采樣函數(shù)與波函數(shù)對(duì)應(yīng)起來的想法具有了智能優(yōu)化算法量子模型的雛形。這使智能優(yōu)化算法向量子理論邁進(jìn)了一步，但其并未建立起智能優(yōu)化算法和量子力學(xué)之間的數(shù)學(xué)物理關(guān)系，也沒有意識(shí)到目標(biāo)函數(shù)與勢(shì)能之間的關(guān)系，這使得QPSO 算法不能真正的成為量子化的算法，更未能為智能優(yōu)化算法建立量子模型。

明確將智能優(yōu)化算法的目標(biāo)函數(shù)視為Schr?dinger 方程中勢(shì)能的算法是多尺度量子諧振子算法(MQHOA)[61-64]。MQHOA 算法依據(jù)量子諧振子的波函數(shù)構(gòu)造了智能優(yōu)化算法，這一提法使智能優(yōu)化算法向量子模型前進(jìn)了一步。在該算法中還定義了波函數(shù)、零點(diǎn)能等量子物理中的重要概念[65]，并對(duì)多尺度過程和不確定性關(guān)系進(jìn)行了研究[66]。但有意思的是從量子動(dòng)力學(xué)的角度看MQHOA 算法的模型并不是完全正確的，在模型的應(yīng)用上顯得牽強(qiáng)。然而其構(gòu)造出的算法結(jié)構(gòu)卻就是智能優(yōu)化算法量子動(dòng)力學(xué)所指出的基本迭代操作，而且MQHOA算法及其改進(jìn)算法的性能也得到了一定程度的驗(yàn)證[67-72]。這些結(jié)果“意外”地證明了智能優(yōu)化算法量子動(dòng)力學(xué)給出的基本操作是簡(jiǎn)單而有效的，可以作為構(gòu)造性能更好的算法的基礎(chǔ)。MQHOA 算法利用了智能優(yōu)化算法的Schr?dinger 方程[73]，但卻未能明確指出并利用Schr?dinger 方程作為動(dòng)力學(xué)方程來研究智能優(yōu)化算法。雖然其在算法結(jié)構(gòu)上基本與動(dòng)力學(xué)模型給出的操作相似，但物理解釋卻不正確。MQHOA 算法和QPSO 算法都可以認(rèn)為是量子動(dòng)力學(xué)模型的萌芽。

為解決該問題，文獻(xiàn)[74]對(duì)智能優(yōu)化算法的量子基礎(chǔ)進(jìn)行了討論，確立了勢(shì)能等效、優(yōu)化問題的含時(shí)Schr?dinger 方程等一系列從量子視角研究智能優(yōu)化算法的理論基礎(chǔ)。為了利用經(jīng)典計(jì)算機(jī)模擬智能優(yōu)化算法在搜索過程中的隨機(jī)馬爾可夫過程，對(duì)Schr?dinger 方程做Wick轉(zhuǎn)動(dòng)[75]，將時(shí)間轉(zhuǎn)變?yōu)樘摃r(shí)間并令，則智能優(yōu)化算法的含時(shí)Schr?dinger 方程重新寫為：

智能優(yōu)化算法的含時(shí)Schr?dinger 方程就是智能優(yōu)化算法的量子動(dòng)力學(xué)方程，它從量子力學(xué)的角度描述了智能優(yōu)化算法的時(shí)間演化過程，智能優(yōu)化算法的迭代演化過程通過Schr?dinger 方程轉(zhuǎn)化為波函數(shù) ψ (x,τ)的時(shí)間演化過程。Schr?dinger 方程所對(duì)應(yīng)的基態(tài)波函數(shù)就是優(yōu)化問題所對(duì)應(yīng)的解。從理論上講，在f(x)已知的情況下可以通過求解Schr?dinger方程獲得基態(tài)波函數(shù)。

該文采用擴(kuò)散蒙特卡羅方法來求解基態(tài)波函數(shù)。雖然擴(kuò)散方程和Schr?dinger 方程在形式上是相似的，但優(yōu)化問題約束條件f(x)的引入?yún)s破壞了式(12)格林函數(shù)的歸一性，其格林函數(shù)為：

式中，勢(shì)能項(xiàng)因子 exp(?τV)破壞了上式的歸一性，因此需要向上述格林函數(shù)中引入一個(gè)收斂因子exp(τER)，使式(12)所描述的系統(tǒng)得到穩(wěn)定收斂的解，改變后的格林函數(shù)是調(diào)整后的Schr?dinger方程的解，其公式如下：

式中，ER是參考能量，是對(duì)當(dāng)前優(yōu)化系統(tǒng)能量的估計(jì)值；f(x)?ER是系統(tǒng)的勢(shì)能項(xiàng)，反應(yīng)優(yōu)化問題對(duì)優(yōu)化系統(tǒng)的影響。隨著優(yōu)化系統(tǒng)的演化，粒子的分布將不斷的變化從而使參考能量ER不斷逼近基態(tài)能量。式(14)即為一般意義上優(yōu)化問題的含時(shí)Schr?dinger 方程。

建立智能優(yōu)化算法的Schr?dinger 方程具有兩個(gè)重要的理論意義：

1) 從物理意義上，優(yōu)化問題通過Schr?dinger方程被轉(zhuǎn)化為求解受勢(shì)能f(x)約束的量子系統(tǒng)的基態(tài)波函數(shù)ψ0(x)；

2) 從數(shù)學(xué)意義上，將優(yōu)化問題和優(yōu)化系統(tǒng)納入統(tǒng)一的方程描述，即Schr?dinger 方程這個(gè)線性偏微分動(dòng)力學(xué)方程。這意味著量子力學(xué)中求解該方程的過程可以用作解釋量子動(dòng)力學(xué)理論下的智能優(yōu)化算法的優(yōu)化過程。

通過Schr?dinger 方程，智能優(yōu)化算法在量子視角下被轉(zhuǎn)換為一個(gè)模擬的物理優(yōu)化系統(tǒng)，該系統(tǒng)由量子空間中的虛擬粒子組成，優(yōu)化問題的目標(biāo)函數(shù)轉(zhuǎn)換為加之于該系統(tǒng)的約束勢(shì)場(chǎng)，而該系統(tǒng)的運(yùn)行方式符合Schr?dinger 方程的描述。

對(duì)于智能優(yōu)化算法的Schr?dinger 方程，可以通過Feynman 積分的方法，利用初態(tài) ψ(x0,0)在A至B 所有路徑上的積分，描述粒子從A 到B 的狀態(tài)變化。Schr?dinger 方程任意位置x和 時(shí)間 τ的解ψ(x,τ)可以表達(dá)如下：

式中，P(xn,xn?1)為虛擬粒子隨機(jī)運(yùn)動(dòng)的動(dòng)能相關(guān)項(xiàng)，描述了粒子的運(yùn)動(dòng)行為，與當(dāng)前粒子位置xn?1和 粒子的質(zhì)量m有關(guān)，其公式如下：

式(15)中，W(xn)為概率權(quán)重項(xiàng)，描述了粒子通過隨機(jī)運(yùn)動(dòng)出現(xiàn)在xn的幾率，與當(dāng)前采樣結(jié)果f(x)和 參考能量ER有關(guān)，其公式如下：

式(15)以積分的形式描述了在擴(kuò)散過程中自由粒子運(yùn)動(dòng)和密度的變化，由于標(biāo)準(zhǔn)數(shù)值積分方法難以求解該積分，因此采用了擴(kuò)散蒙特卡羅方法。在擴(kuò)散蒙特卡羅方法中，如果函數(shù)h(x)可以分解為函數(shù)f(x)和 概率函數(shù)p(x)的乘積，則該積分可以表示為f(x)在 密度p(x)下的期望，其公式如下：

根據(jù)式(15)，采樣密度函數(shù)為：

狀態(tài)函數(shù)f(x1···xN)為：

因此，式(15)可以通過p(x1,···,xN)密度下的采樣和權(quán)重函數(shù)W(xn)對(duì)采樣結(jié)果的調(diào)整來獲?。?/p>

由“擴(kuò)散采樣?權(quán)重調(diào)整”組成的迭代循環(huán)即為量子力學(xué)中求解Schr?dinger 方程常用的擴(kuò)散蒙特卡羅方法，其模擬了粒子在Schr?dinger 方程下通過隨機(jī)運(yùn)動(dòng)向基態(tài)能量演化的過程。

同時(shí)，多尺度退火過程是通過逐步降低模擬量子優(yōu)化系統(tǒng)的動(dòng)能實(shí)現(xiàn)的，公式如下：

式(22)中HT與粒子擴(kuò)散公式(16)中的搜索尺度是正相關(guān)的。其原因是因?yàn)樵趦?yōu)化過程中，目標(biāo)函數(shù)的規(guī)模與模擬量子優(yōu)化系統(tǒng)的規(guī)模不總是一致的，因此需要不斷的改變優(yōu)化系統(tǒng)的搜索尺度HT以匹配動(dòng)能HV，這也是量子退火中減少能量擾動(dòng)的原因。

智能優(yōu)化算法量子動(dòng)力學(xué)下的基本對(duì)應(yīng)關(guān)系和操作匯總?cè)绫?。

表1 智能優(yōu)化算法量子動(dòng)力學(xué)下的基本對(duì)應(yīng)關(guān)系和操作

特別有意思的是量子動(dòng)力學(xué)模型并非想象中的那樣給出一個(gè)量子化的新智能優(yōu)化算法，而是得到了一些操作和基本迭代方法。其核心操作主要包括：正態(tài)采樣、權(quán)重計(jì)算、多尺度過程，其他很多智能優(yōu)化算法都可以視為在這一核心操作的基礎(chǔ)上進(jìn)行改進(jìn)。智能優(yōu)化算法的量子動(dòng)力學(xué)解釋了智能優(yōu)化算法的量子化本質(zhì)，為利用量子力學(xué)對(duì)智能優(yōu)化算法進(jìn)行分析提供了基礎(chǔ)。

7 智能優(yōu)化算法的核心操作

從量子動(dòng)力學(xué)可以得到一些Schr?dinger 方程下的智能優(yōu)化算法的基本操作，這一結(jié)果提示：一些基于不同算法模型的智能優(yōu)化算法都是從這些基本操作過程中衍生出來的。這一問題似乎也被不少研究者所注意到了，雖然他們可能并未從量子力學(xué)的視角去解釋，但卻發(fā)現(xiàn)智能優(yōu)化算法可能存在“骨架”結(jié)構(gòu)。

7.1 Kennedy 對(duì)粒子群算法基本框架的探索

粒子群算法(particle swarm optimization,PSO)是Kennedy 和Eberhart 在1995 年提出的一種群體智能優(yōu)化算法[76]。Kennedy 認(rèn)為這一算法的迭代過程模擬了鳥群的社會(huì)行為，這一算法的核心思想是通過個(gè)體行為和社會(huì)行為的綜合來決定每一個(gè)體下一步的行為。

在PSO 算法中每次迭代都要保存?zhèn)€體的最好位置 pbest 和群體中的最好位置 gbest，每一個(gè)粒子的位置更新公式如下：

式中，學(xué)習(xí)因子c1和c2需 要人為確定，c1=0時(shí)粒子運(yùn)動(dòng)不考慮自己的個(gè)體歷史信息，c2=0時(shí)粒子運(yùn)動(dòng)不考慮群體的歷史信息。其參數(shù)值的設(shè)定帶有很強(qiáng)的主觀色彩，什么時(shí)候要考慮、考慮多少都是人為定的，這給算法性能優(yōu)化造成很大的困難。同時(shí)由于這一算法最初沒有采樣尺度的遞減策略，其性能并不是太好。直到1998 年文獻(xiàn)[77]在PSO 算法的速度公式中引入遞減的慣性權(quán)重因子w，才使PSO 算法成為一個(gè)多尺度算法，新的速度計(jì)算公式如下：

在迭代過程中通過逐步減小w的值，實(shí)現(xiàn)全局搜索和局部搜索的平衡。后來Clerc 又增加了控制速度的約束因子α，約束因子成為了一個(gè)不折不扣的多尺度參數(shù)[78]，也使PSO 算法成為一個(gè)多尺度搜索算法。

多尺度策略是智能優(yōu)化算法量子模型中不確定性原理所預(yù)言的一種基本迭代操作[65]。如同量子理論中位置和動(dòng)量不能同時(shí)被測(cè)定[64]一樣，智能優(yōu)化算法在同一尺度下不能同時(shí)實(shí)現(xiàn)良好的全局搜索和局部搜索能力。加入慣性權(quán)重后，PSO 算法成為一種多尺度群體算法。慣性權(quán)重的引入在算法上是正確的，但在模型上卻顯得牽強(qiáng)，這使得PSO 算法逐步離開了Kennedy 他們所提出的基本模型。特別是后來大量的改進(jìn)算法和混合算法更是走得越來越遠(yuǎn)，PSO 也就逐漸成了一個(gè)算法名稱的符號(hào)。

在PSO 算法提出近十年時(shí)，也就是2003 年左右，Kennedy 也意識(shí)到PSO 算法的參數(shù)變化太多而使算法難以理解，因此想簡(jiǎn)化PSO 算法。并且他認(rèn)為PSO 算法與其他算法存在相似性，這一點(diǎn)與采用從量子動(dòng)力學(xué)中得到智能優(yōu)化算法的基本迭代操作是相似的。因此他提出了PSO 算法的骨架(bare bone)算法[79]，在這篇文章中Kennedy 采用隨機(jī)正態(tài)采樣取代了速度，取得了更好的性能。他認(rèn)為正態(tài)采樣既有很好的鄰域采樣能力，又能以較小的概率采到距離當(dāng)前位置較遠(yuǎn)的位置。Kennedy在文中也自嘲道：“這樣鳥在空間里的‘飛行’就變?yōu)椤w濺’了?！蓖瑫r(shí)他還認(rèn)為PSO 算法和其他的一些進(jìn)化算法有可能應(yīng)該被歸類到一個(gè)統(tǒng)一的優(yōu)化種類中去。雖然他并未明確地給出統(tǒng)一模型，只是進(jìn)行粗略的描述，但這一認(rèn)識(shí)可能是對(duì)智能優(yōu)化算法進(jìn)行統(tǒng)一建模思想的雛形。Kennedy 所得到的一些結(jié)論與采用量子動(dòng)力力學(xué)作為統(tǒng)一模型所得到的結(jié)論幾乎完全吻合。就在PSO 算法的骨架提出的第二年即2004 年的CEC 會(huì)議上，Kennedy明確放棄了從鳥群模型構(gòu)造的速度項(xiàng)，提出了一種基于正態(tài)隨機(jī)采樣的更為簡(jiǎn)潔的算法[80]，其采樣公式如下：

對(duì)于其在算法中采用的正態(tài)隨機(jī)采樣在量子動(dòng)力學(xué)中也曾早有預(yù)言。在擴(kuò)散蒙特卡羅方法中，量子動(dòng)力學(xué)方程轉(zhuǎn)化為擴(kuò)散方程，而擴(kuò)散方程的格林函數(shù)就是正態(tài)函數(shù)，它代表了擴(kuò)散過程中粒子在下一時(shí)刻到達(dá)某一位置的概率，其含義就是隨機(jī)采樣時(shí)的采樣概率函數(shù)，從量子力學(xué)來看也就是波函數(shù)，即粒子出現(xiàn)在某一位置的概率。

至此Kennedy 將PSO 算法的演化過程簡(jiǎn)化為簡(jiǎn)單的正態(tài)概率采樣過程，其基本結(jié)構(gòu)與量子動(dòng)力學(xué)給出的智能優(yōu)化算法基本迭代結(jié)構(gòu)已較為接近，但量子動(dòng)力學(xué)給出的迭代過程則更為簡(jiǎn)單清晰。

7.2 智能優(yōu)化算法的基本迭代過程

當(dāng)從智能優(yōu)化算法的量子動(dòng)力學(xué)的角度去解釋智能優(yōu)化算法的迭代過程時(shí)，智能優(yōu)化算法的核心迭代操作就成為了量子動(dòng)力學(xué)理論框架下的基本要求。有的學(xué)者誤認(rèn)為近年提出的“黑洞算法”其結(jié)構(gòu)來源于粒子群算法[82]，也有學(xué)者將MQHOA 算法誤認(rèn)為是一種量子粒子群算法，產(chǎn)生這些誤解的原因皆源自智能優(yōu)化算法可能具有統(tǒng)一的內(nèi)在核心操作。差分進(jìn)化算法[83-84]和煙火算法[85]的研究者也紛紛提出自己的“骨架”算法，這些骨架算法都存在相似的基本操作，如概率采樣過程、采樣步長的變化和群體策略等。通常這些看上去簡(jiǎn)單的骨架算法都具有不錯(cuò)的優(yōu)化性能。這更是進(jìn)一步證明了智能優(yōu)化算法的核心操作是一種非常有效的操作，它已能滿足智能優(yōu)化算法對(duì)性能的基本要求。

綜合量子動(dòng)力學(xué)智能優(yōu)化算法和其他智能優(yōu)化算法的“骨架”，可以給出一個(gè)較為通用的迭代過程如下。

以上基本迭代過程看上去非常簡(jiǎn)單，仿佛也沒有任何量子力學(xué)的痕跡，但卻可以由智能優(yōu)化算法的量子動(dòng)力學(xué)通過擴(kuò)散蒙特卡羅分解出來。而如果將正態(tài)采樣視為格林函數(shù)，則其量子的面紗就揭開了。類似的，在QPSO 算法中也將其使用的拉普拉斯采樣函數(shù)視為勢(shì)阱下的基態(tài)波函數(shù)[86]。

智能優(yōu)化算法的基本迭代過程可以作為智能優(yōu)化算法設(shè)計(jì)和改進(jìn)的基礎(chǔ)，量子動(dòng)力學(xué)可作為算法分析的理論框架，同時(shí)實(shí)驗(yàn)結(jié)果表明，上述基本迭代操作的骨架算法已出人意料地具有了相當(dāng)?shù)膬?yōu)化性能。而大量增加了許多操作機(jī)制的“重型”智能優(yōu)化算法卻仿佛只是為了走好最后一公里的性能而給出的，這使我們猜想：當(dāng)目標(biāo)函數(shù)為黑盒且沒有針對(duì)目標(biāo)函數(shù)做任何先驗(yàn)估計(jì)和假設(shè)的情況下，骨架算法可能已是“最優(yōu)”算法了。

8 結(jié)束語

從量子視角來認(rèn)識(shí)和研究智能優(yōu)化算法是一個(gè)非常有前景的研究方向，從量子比特概念引入智能優(yōu)化算法到直接采用量子動(dòng)力學(xué)模型來為智能優(yōu)化算法建模，該領(lǐng)域的研究正在走向縱深。通過量子視角來研究智能優(yōu)化算法有望解釋智能產(chǎn)生的原因并為研究隱含并行性產(chǎn)生的機(jī)制提供一條可行的道路。在當(dāng)前量子科技成為我國戰(zhàn)略性新興技術(shù)的歷史機(jī)遇下，基于量子技術(shù)的智能優(yōu)化算法研究一定會(huì)取得長足的發(fā)展。