楊云亭，王 鵬

（1.中國(guó)科學(xué)院成都計(jì)算機(jī)應(yīng)用研究所，成都610041； 2.中國(guó)科學(xué)院大學(xué)，北京100049；3.西南民族大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，成都610225）

（?通信作者電子郵箱wp002005@163.com）

0 引言

近些年來(lái)，元啟發(fā)式優(yōu)化算法［1］發(fā)展迅猛，不斷地被挖掘應(yīng)用到現(xiàn)實(shí)中的大規(guī)模問(wèn)題中，如神經(jīng)網(wǎng)絡(luò)模型及參數(shù)優(yōu)化、強(qiáng)化學(xué)習(xí)中的策略選擇等熱門(mén)技術(shù)中，相比傳統(tǒng)算法中的精確算法中的動(dòng)態(tài)規(guī)劃、分支限定等，更加靈活和通用。元啟發(fā)式優(yōu)化算法求解優(yōu)化問(wèn)題的過(guò)程中，不受限于目標(biāo)函數(shù)的可導(dǎo)性質(zhì)和優(yōu)化問(wèn)題的對(duì)偶規(guī)則，就可以對(duì)問(wèn)題進(jìn)行算法的求解，同時(shí)可以在非常大的候選解空間中進(jìn)行迭代搜索［2］。在通用的啟發(fā)式優(yōu)化算法中，模擬退火（Simulate Anneal，SA）算法［3-5］將優(yōu)化問(wèn)題看作是物理退火的過(guò)程，根據(jù)Metropolis準(zhǔn)則選擇是否接受搜索到的新解，直至退火過(guò)程結(jié)束；遺傳算法（Genetic Algorithm，GA）［6-8］在當(dāng)前搜索到解的基礎(chǔ)上進(jìn)行自然法則的變化：遺傳、變異、交叉產(chǎn)生新解，在新解中應(yīng)用“物競(jìng)天擇，適者生存”法則進(jìn)行最優(yōu)解的替換；粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［9］則根據(jù)鳥(niǎo)類(lèi)的飛行規(guī)律進(jìn)行解空間中的搜索，通過(guò)不同位置的速度和位移變化進(jìn)行新解的搜索和替換。這些不同的搜索方式會(huì)使解沿著某種方向趨近于全局最優(yōu)解，當(dāng)搜索足夠充分的情況下，這類(lèi)啟發(fā)式算法會(huì)以概率1收斂于全局最優(yōu)。本文模擬量子體系下自由粒子的波函數(shù)的概率解釋進(jìn)行優(yōu)化算法搜索行為的指導(dǎo)，提出了多尺度量子自由粒子優(yōu)化算法（Multi-scale Free Particle Optimization Algorithm，MFPOA）。

組合優(yōu)化問(wèn)題是現(xiàn)實(shí)生活中很多問(wèn)題的抽象，求解此類(lèi)問(wèn)題可以借助元啟發(fā)式優(yōu)化算法進(jìn)行離散狀態(tài)空間中的搜索。本文使用MFPOA對(duì)組合優(yōu)化問(wèn)題中的旅行商問(wèn)題（Travelling Salesman Problem，TSP）［10-12］進(jìn)行求解，首先對(duì)MFPOA進(jìn)行了物理模型和基本流程進(jìn)行了闡述，并采用了光骨頭煙花算法（Bare Bones Fireworks Algorithm，BBFWA）［13］中的尺度迭代策略對(duì)算法進(jìn)行了改進(jìn)，將算法應(yīng)用到TSP數(shù)據(jù)集上進(jìn)行優(yōu)化問(wèn)題的求解。另外，通過(guò)與目前較優(yōu)的啟發(fā)式優(yōu)化算法中的混合粒子群優(yōu)化（Hybrid Particle Swarm Optimization，HPSO）算法［14］、模擬退火算法、遺傳算法和蟻群優(yōu)化（Ant Colony Optimization，ACO）算法［15］進(jìn)行TSP求解能力的對(duì)比，進(jìn)一步驗(yàn)證自由粒子模型下優(yōu)化算法的性能。使用量子概率驅(qū)動(dòng)解的搜索過(guò)程是一種創(chuàng)新的方式，同時(shí)完善的量子理論可以支撐算法的求解可行性。

1 基于量子概率的MFPOA

1.1 MFPOA的物理模型描述

多尺度量子諧振子優(yōu)化算法（Multi-Scale Quantum Harmonic oscillator Optimization Algorithm，MQHOA）［16-18］是一種基于一維量子諧振子波函數(shù)原理提出的優(yōu)化算法，模擬量子系統(tǒng)下的諧振子運(yùn)動(dòng)規(guī)律，將優(yōu)化問(wèn)題的求解通過(guò)量子諧振子過(guò)程和多尺度過(guò)程實(shí)現(xiàn)全局區(qū)域的逐步搜索定位和局部區(qū)域的充分搜索。在該算法的基礎(chǔ)之上，對(duì)量子微觀系統(tǒng)下的自由粒子的運(yùn)動(dòng)方式進(jìn)行了分析，并將自由粒子的運(yùn)動(dòng)規(guī)律映射到函數(shù)優(yōu)化過(guò)程中。物理學(xué)中的薛定諤方程可以通過(guò)給定的勢(shì)阱函數(shù)求解出粒子的波函數(shù)，進(jìn)一步通過(guò)波函數(shù)平方計(jì)算得到粒子在勢(shì)阱下的概率密度函數(shù)。而復(fù)雜的勢(shì)阱較難通過(guò)薛定諤方程求解出波函數(shù)，在此通過(guò)勢(shì)阱函數(shù)的泰勒展開(kāi)公式的近似求得近似波函數(shù)，在波函數(shù)的指導(dǎo)下進(jìn)行可行解空間的采樣搜索。在優(yōu)化問(wèn)題中將優(yōu)化問(wèn)題的目標(biāo)函數(shù)近似薛定諤方程中的勢(shì)阱，采用勢(shì)阱函數(shù)的零階泰勒公式近似，可以得到簡(jiǎn)潔的勢(shì)阱表達(dá)，然后通過(guò)薛定諤方程求解出近似波函數(shù)形式。借助物理學(xué)中波函數(shù)的概率意義，指導(dǎo)優(yōu)化算法在空間中進(jìn)行采樣。

多尺度量子自由粒子優(yōu)化算法是從微觀系統(tǒng)中的自由粒子衍生出來(lái)，自由粒子是量子系統(tǒng)下簡(jiǎn)單的粒子之一，在空間中不受力的作用，并且沒(méi)有能級(jí)結(jié)構(gòu)，轉(zhuǎn)化到優(yōu)化求解過(guò)程中，可以實(shí)現(xiàn)簡(jiǎn)潔的搜索結(jié)構(gòu)。目標(biāo)函數(shù)的零階泰勒展開(kāi)式為常數(shù)，在薛定諤方程中使用0表示勢(shì)阱，這與自由粒子在空間中不受力等效。首先將自由粒子的勢(shì)阱0帶到薛定諤方程中得到波函數(shù)的表達(dá)，然后通過(guò)波函數(shù)的平方表征粒子在空間中出現(xiàn)的概率，該概率形式指導(dǎo)算法在當(dāng)前搜索的最優(yōu)解和當(dāng)前的搜索尺度下依此概率進(jìn)行迭代搜索。將量子空間中簡(jiǎn)單的粒子形式映射到優(yōu)化算法中，通過(guò)均勻分布采樣和尺度收縮在求解過(guò)程中實(shí)現(xiàn)當(dāng)前最優(yōu)解的替換，當(dāng)搜索足夠多次后實(shí)現(xiàn)最優(yōu)解的收斂。

量子理論中的不受力的自由粒子的薛定諤方程寫(xiě)作如下形式：

其中：?為普朗克常數(shù)，m為粒子的質(zhì)量，ψ(x)為粒子的波函數(shù)，E為粒子的能量。

通過(guò)方程求解的波函數(shù)如下所示。

粒子在空間中的存在是不確定的，但是可以通過(guò)波函數(shù)模的平方表示粒子在空間某位置上的概率，如式（3）：

式（3）可以看出自由粒子的波函數(shù)的概率意義表示粒子在空間中任何位置存在的概率是一個(gè)常數(shù)，也即在空間任何位置中存在的概率相同，在算法求解過(guò)程中可以使用均勻分布進(jìn)行近似。MFPOA模擬粒子的運(yùn)動(dòng)過(guò)程，采用均勻分布在可行域中進(jìn)行采樣，根據(jù)采樣點(diǎn)在優(yōu)化函數(shù)中的函數(shù)值的信息選取下次迭代過(guò)程中的采樣中心，并根據(jù)多次采樣信息決定尺度的收縮，直到搜索過(guò)程中達(dá)到結(jié)束條件，退出迭代。

1.2 MFPOA的基本工作流程

MFPOA在算法搜索過(guò)程中是逐漸減小搜索區(qū)域的，直至搜索區(qū)域減小到給定搜索區(qū)域的最小值，說(shuō)明算法求解已經(jīng)收斂到接近全局最優(yōu)的程度，算法結(jié)束。算法基于概率的形式進(jìn)行采樣，在某一個(gè)尺度是否達(dá)到充分的搜索只能通過(guò)一些預(yù)設(shè)條件的判斷，但是這種判斷一般都是存在一定誤差，在判定充分搜索后可能還存在跳過(guò)的區(qū)域?；谶@種判斷的誤差性，本節(jié)介紹了一種自適應(yīng)的尺度變化策略，這種策略不同于預(yù)先設(shè)定迭代充分搜索的次數(shù)，而是使用搜索過(guò)程中的信息進(jìn)行尺度的持續(xù)自適應(yīng)變化。模擬量子自由粒子在空間中的存在概率，MFPOA通過(guò)概率采樣在可行解空間中進(jìn)行搜索，并實(shí)現(xiàn)優(yōu)化問(wèn)題的求解，其偽代碼如下所示。

算法1 MFPOA。

算法初始化自由粒子的個(gè)數(shù)k，搜索空間的最小值min，最大值max，最后停止迭代的搜索空間的最小值δmin，初始的搜索區(qū)間在[min，max]，和充分搜索的判定條件c值，實(shí)驗(yàn)一般設(shè)定c值為10，f(x)表示目標(biāo)函數(shù)。2）～3）行表示隨機(jī)生成k個(gè)解空間中粒子，并計(jì)算每個(gè)粒子的在目標(biāo)函數(shù)中的函數(shù)值，并記錄其中最優(yōu)解f(x)best；4）～12）行表示算法迭代搜索的過(guò)程，分別以k個(gè)粒子為中心進(jìn)行均勻分布采樣產(chǎn)生新的粒子，采樣的尺度跟當(dāng)前的δ有關(guān)。采樣后的粒子在目標(biāo)函數(shù)中表現(xiàn)更優(yōu)的情況下進(jìn)行粒子的替換，并將當(dāng)前粒子中的最差用當(dāng)前k個(gè)粒子中的最好粒子更新。若此次迭代過(guò)程中的最優(yōu)值相較上次迭代過(guò)程中的最優(yōu)值沒(méi)有發(fā)生變化，則最優(yōu)值的優(yōu)越性系數(shù)為2，下次迭代若最優(yōu)值依然不變，優(yōu)越系數(shù)增加1，如此累計(jì)，直到優(yōu)越系數(shù)等于c時(shí)，表示此搜索區(qū)域已搜索充分，搜索區(qū)域減半，進(jìn)行更精細(xì)的搜索。否則，在當(dāng)前尺度下進(jìn)行最優(yōu)值替換，進(jìn)一步地迭代搜索，尺度不減小。

模擬自由粒子在空間中存在的概率分布的形式，MFPOA通過(guò)均勻分布采樣，探索可行域中最優(yōu)解的存在位置，不斷地通過(guò)迭代進(jìn)行中心替換和搜索尺度變化，逼近可行域中的最優(yōu)解。這種方式是將最終解的形式看作是一種在特定區(qū)域的概率分布，而不再是一個(gè)特定的值。當(dāng)無(wú)限次迭代后，可行解會(huì)慢慢逼近到一個(gè)極小的區(qū)域中，回到最終的值的形式。從偽代碼中也可以看出，算法中控制搜索區(qū)域變化的參數(shù)c決定整個(gè)算法求解在當(dāng)前搜索尺度下收斂的情況。c值設(shè)置得過(guò)小，在當(dāng)前尺度下進(jìn)行采樣搜索不夠充分，進(jìn)行尺度減半會(huì)丟失大部分解空間，導(dǎo)致算法求解性能下降。c值設(shè)置得過(guò)大，會(huì)使算法在解空間中進(jìn)行大量采樣和最優(yōu)值判斷及替換，大幅增加算法求解的時(shí)間，而使算法求解速度不可忍受。c值的設(shè)定使算法增加了可調(diào)參數(shù)的設(shè)置，c值設(shè)置的不合理性會(huì)嚴(yán)重影響算法的收斂能力和求解精度，一般設(shè)置為10。

基于此，本文參考了2018年提出的BBFWA中搜索區(qū)域變化的策略。BBFWA在煙花算法的基礎(chǔ)上簡(jiǎn)化了算法求解的結(jié)構(gòu)，對(duì)煙花爆炸的半徑距離進(jìn)行了動(dòng)態(tài)的調(diào)整來(lái)提高算法的求解效果。煙花算法模型同樣采用了均勻分布的采樣方式進(jìn)行可行解的探索，不同的是MFPOA在搜索過(guò)程中通過(guò)判斷當(dāng)前尺度搜索的充分性進(jìn)行尺度的縮小，而B(niǎo)BFWA在搜索過(guò)程中根據(jù)采樣前后最優(yōu)值的變化情況進(jìn)行尺度的更新。這種尺度的自適應(yīng)更新實(shí)質(zhì)是對(duì)尺度持續(xù)衰減的一種改變，在每次采樣完后進(jìn)行在原尺度的更新，在最優(yōu)值變得更優(yōu)的情況下，下一次采樣尺度在當(dāng)前尺度上擴(kuò)大至原來(lái)的1.2倍；否則，在當(dāng)前尺度上縮小至原來(lái)的0.9倍。這種尺度的變化更加緩慢，相對(duì)于尺度減半策略不會(huì)丟失解空間中的大部分信息。

為了減少M(fèi)FPOA中可調(diào)參數(shù)c值的影響和避免尺度減半導(dǎo)致的解空間的信息的丟失，采用了BBFWA中煙花爆炸半徑的改變策略對(duì)算法的搜索尺度進(jìn)行了一種改進(jìn)，使用迭代過(guò)程中的信息指導(dǎo)尺度的減小，去掉c值的判定條件，采用量子自由粒子的概率解釋在搜索空間中尋優(yōu)的方式是一種新型搜索算法的框架。BBFWA實(shí)質(zhì)上是對(duì)自由粒子模型下的算法進(jìn)行了搜索尺度的改進(jìn)，在MFPOA簡(jiǎn)單結(jié)構(gòu)的基礎(chǔ)上進(jìn)一步地改進(jìn)策略的指導(dǎo)，可以產(chǎn)生性能更優(yōu)的算法，同樣自由粒子算法可以對(duì)同樣機(jī)理搜索的算法進(jìn)行可行性的解釋。光骨頭煙花算法在自由粒子優(yōu)化算法的解釋下的偽代碼可以進(jìn)一步改寫(xiě)成如下形式，并記為MFPOA-DS（Multi-scale Free Particle Optimization Algorithm-Dynamic Search）。

從算法1和算法2中的兩段偽代碼中可以明顯看出，MFPOA-DS版本中尺度的更新使用了公式δ=δ*λ，其中λ的取值有兩種0.9和1.2：只有迭代中產(chǎn)生的新粒子比上一次迭代中的粒子的最優(yōu)值好，設(shè)置λ=1.2，進(jìn)行搜索區(qū)域的擴(kuò)大；否則進(jìn)行搜索區(qū)域的衰減。MFPOA減半的搜索方式使得算法搜索過(guò)程中會(huì)忽視搜索中心外圍區(qū)域，過(guò)于關(guān)注內(nèi)部區(qū)域，這種方式會(huì)導(dǎo)致可行解空間中的部分信息丟失，從而對(duì)優(yōu)化問(wèn)題的求解不準(zhǔn)確。這種策略引入動(dòng)態(tài)尺度搜索的概念，將前后兩次搜索到的解的變化情況代替尺度收斂的控制條件值c的判斷，可以使尺度靈活縮放，進(jìn)而改善算法的性能。

2 自由粒子模型求解TSP的基本過(guò)程

TSP一直是組合優(yōu)化問(wèn)題中經(jīng)典的NP難問(wèn)題。TSP的描述是給定若干城市和城市之間的距離，通過(guò)算法求解訪問(wèn)每座城市并返回出發(fā)城市的最小回路距離，也稱(chēng)為最短路徑問(wèn)題。啟發(fā)式優(yōu)化算法往往更擅長(zhǎng)連續(xù)空間中的優(yōu)化問(wèn)題，在求解組合優(yōu)化問(wèn)題時(shí)需要先對(duì)組合優(yōu)化問(wèn)題進(jìn)行合適的映射，進(jìn)而按照函數(shù)優(yōu)化求解的思路進(jìn)行求解。相比連續(xù)空間中的函數(shù)優(yōu)化，組合優(yōu)化問(wèn)題需要先選擇優(yōu)化問(wèn)題解的編碼方式以及可行解的更新方式。TSP解的編碼與給定的城市數(shù)目有關(guān)，路徑距離基于城市序列計(jì)算歐幾里得距離得出，所以城市序列的表示尤為重要，簡(jiǎn)單的一種表達(dá)方式是對(duì)城市進(jìn)行編號(hào)，比如5個(gè)城市，分別給每個(gè)城市編成1，2，…，5。城市序列123451便表示TSP的一個(gè)可行解，表示從城市1出發(fā)，分別經(jīng)過(guò)城市2，3，4，5，再回到城市1。在編碼方式的基礎(chǔ)之上，通過(guò)隨機(jī)選擇兩個(gè)位置進(jìn)行交換產(chǎn)生新解。

TSP作為離散問(wèn)題求解的代表，一直是組合優(yōu)化問(wèn)題中經(jīng)典問(wèn)題。如何求解城市序列的最優(yōu)路徑，使得旅行商經(jīng)過(guò)的總路程最小，也一直以來(lái)被用來(lái)測(cè)試啟發(fā)式算法的性能。MFPOA求解TSP的策略主要包含兩個(gè)步驟：1）在當(dāng)前尺度下進(jìn)行城市序列的迭代并記錄最優(yōu)解的情況和采樣中心的變化；2）在不同尺度下進(jìn)行城市序列在已搜索到最優(yōu)區(qū)域的精細(xì)搜索。根據(jù)多尺度量子自由粒子模型，MFPOA-DS求解TSP的基本工作流程的偽代碼如下所示：

由偽代碼和算法的基本思想，可以將自由粒子模型求解TSP的基本過(guò)程概述為以下3個(gè)主要步驟：

1）隨機(jī)初始化k個(gè)城市序列，2，…，k）作為當(dāng)前尺度（初始尺度）下的搜索中心。

2）在當(dāng)前尺度δ上的收斂過(guò)程，以每次迭代過(guò)程中保留的k個(gè)較好的采樣位置作為k個(gè)局部搜索區(qū)域的中心，形成k個(gè)區(qū)間為δ的均勻分布函數(shù)U(xi-δ2，xi+δ2)。分別根據(jù)每個(gè)中心序列進(jìn)行隨機(jī)位置的交換產(chǎn)生新解，在迭代過(guò)程中記錄最優(yōu)解和最優(yōu)解的位置，實(shí)現(xiàn)單一均勻分布的收斂，多個(gè)均勻分布采樣迭代的過(guò)程實(shí)現(xiàn)當(dāng)前尺度下的基本收斂。

3）搜索區(qū)域的聚焦過(guò)程，在上一尺度搜索下達(dá)到基本收斂的情況下，根據(jù)實(shí)際求解到的最優(yōu)解的變化情況進(jìn)行當(dāng)前尺度的變化，實(shí)現(xiàn)局部區(qū)域的精細(xì)搜索，直到搜索區(qū)域減小到足夠小或者得到預(yù)設(shè)定的迭代次數(shù)。

當(dāng)給定n個(gè)城市的坐標(biāo)時(shí)，可以通過(guò)歐幾里得距離計(jì)算城市之間的距離?？尚薪饪臻g表示為n個(gè)城市的全排列，一共有n！種方案，算法的求解便在這些方案中進(jìn)行搜索求解。一一窮舉這些解在城市數(shù)目很多的情況下是不可行的，啟發(fā)式算法在求解過(guò)程中根據(jù)當(dāng)前最優(yōu)解的分布進(jìn)行下一步的搜索，有選擇地進(jìn)行搜索區(qū)域的迭代來(lái)避免全部空間的窮盡搜索。在求解TSP時(shí)，算法中δ的初始值設(shè)為城市總數(shù)，δmin設(shè)置為1，在[1，δ]區(qū)間內(nèi)進(jìn)行均勻分布隨機(jī)位置的產(chǎn)生，當(dāng)δ小于1時(shí)沒(méi)有意義。l(x)表示城市序列的路程長(zhǎng)度，從一個(gè)城市出發(fā)，歷經(jīng)所有城市后回到原始出發(fā)的城市的路徑長(zhǎng)度。在MFPOA求解中δ隨著迭代過(guò)程按照固定倍數(shù)進(jìn)行減小，在MFPOA-DS中δ隨著迭代過(guò)程中搜索到的解的情況進(jìn)行自適應(yīng)的尺度增減。這一尺度的變化控制著算法求解TSP的收斂情況，當(dāng)尺度縮小到一定程度(δmin=1)，算法終止。

MFPOA本身模擬量子系統(tǒng)下的自由粒子的特點(diǎn)進(jìn)行優(yōu)化問(wèn)題中的可行域的搜索，搜索策略簡(jiǎn)潔，通過(guò)均勻分布采樣和最優(yōu)值替換得到最終整體的最優(yōu)解。同樣在TSP中通過(guò)簡(jiǎn)單的城市序列變換在可變的搜索空間中進(jìn)行最優(yōu)解的搜索。當(dāng)?shù)銐虺浞?，算法求解的最?yōu)城市序列會(huì)逼近最優(yōu)解。

3 仿真實(shí)驗(yàn)與分析

本章使用組合優(yōu)化問(wèn)題中代表性的TSP測(cè)試自由粒子模型算法的性能。連續(xù)優(yōu)化問(wèn)題更容易針對(duì)不同的問(wèn)題在合適的范圍進(jìn)行采樣，組合優(yōu)化問(wèn)題需要先進(jìn)行合適的映射，將問(wèn)題中的求解結(jié)果用合適的序列表示，同時(shí)采樣過(guò)程需要根據(jù)問(wèn)題制定。使用自由粒子優(yōu)化算法求解TSP時(shí)，將問(wèn)題映射成一個(gè)在初始解的基礎(chǔ)上進(jìn)行交換位置的均勻分布采樣產(chǎn)生新解，根據(jù)新解比當(dāng)前解的效果進(jìn)行采樣尺度的變化（采樣尺度初始為城市序列中的城市個(gè)數(shù)）。在MFPOA中的尺度變化根據(jù)迭代過(guò)程中的解不發(fā)生變化的次數(shù)進(jìn)行尺度的減半策略。在尺度自適應(yīng)改變版本MFPOA-DS的算法中，根據(jù)搜索中的解的變化進(jìn)行采樣尺度的放縮變化，相比原始做法，降低了算法的復(fù)雜度，使算法更加靈活。

所有仿真實(shí)驗(yàn)均在Intel Xeon CPU E5-1630 v3 3.7 GHz，16 GB內(nèi)存的計(jì)算機(jī)上進(jìn)行，程序采用Matlab 2018a實(shí)現(xiàn)。經(jīng)過(guò)反復(fù)實(shí)驗(yàn)測(cè)試，在本次TSP上測(cè)試過(guò)程中使用參數(shù)設(shè)置如下，初始粒子個(gè)數(shù)k為30，初始的搜索尺度δ為求解TSP時(shí)的城市數(shù)目，算法停止迭代的條件δmin設(shè)置為1，最大迭代次數(shù)w0設(shè)置為30 000，搜索尺度變化系數(shù)λ初始為1，在迭代過(guò)程中隨最優(yōu)解的變化在1.2和0.9之間變化。城市間的距離采用歐幾里得距離進(jìn)行度量。

3.1 尺度自適應(yīng)變換策略的有效性

實(shí)驗(yàn)采用不同的對(duì)稱(chēng)性TSP的數(shù)據(jù)驗(yàn)證算法求解的可行性。實(shí)驗(yàn)采用了 ulysses16、ulysses22、eli51、burma14、bayg29的實(shí)驗(yàn)數(shù)據(jù)，通過(guò)這些數(shù)據(jù)測(cè)試了MQHOA和使用尺度自適應(yīng)改進(jìn)策略的MQHOA（MQHOA-DS）、MFPOA和MFPOA-DS。由于算法的隨機(jī)性，采用了10次重復(fù)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行對(duì)比，實(shí)驗(yàn)數(shù)據(jù)如表1。

表1 10次重復(fù)實(shí)驗(yàn)在不同實(shí)驗(yàn)數(shù)據(jù)上的結(jié)果對(duì)比Tab.1 Result comparison of 10 repeated experiments on different experimental data

MFPOA在MQHOA的啟發(fā)下，考察了量子系統(tǒng)中的不同粒子在微觀系統(tǒng)下的運(yùn)動(dòng)形式對(duì)算法指導(dǎo)優(yōu)化求解過(guò)程的影響，主要考察了10次獨(dú)立重復(fù)實(shí)驗(yàn)的最優(yōu)值（Global Best，GB），10次實(shí)驗(yàn)結(jié)果的平均值（Mean Best，MB）和10次實(shí)驗(yàn)結(jié)果的平均值與最優(yōu)值間的差距（MB-GB）。對(duì)比MFPOA和MFPOA-DS，MFPOA-DS在5種數(shù)據(jù)集上性能比MFPOA都有相應(yīng)的提升。根據(jù)迭代過(guò)程中得到的解的情況進(jìn)行尺度的縮減和放大，可以有效提高算法的搜索能力。而且通過(guò)觀察重復(fù)實(shí)驗(yàn)中最好值和平均值的差距，可以發(fā)現(xiàn)使用自適應(yīng)尺度變化策略后的算法會(huì)減弱算法每次運(yùn)行的隨機(jī)性，每次實(shí)驗(yàn)的差距變小，說(shuō)明實(shí)驗(yàn)的性能更加穩(wěn)定。對(duì)比基于量子諧振子的概率進(jìn)行尋優(yōu)的算法，自由粒子模型求解的結(jié)果更好，在eli51和bayg29數(shù)據(jù)上的數(shù)據(jù)對(duì)比尤為明顯。這從側(cè)面驗(yàn)證了自由粒子中的搜索模型更適合求解TSP，均勻分布采樣過(guò)程在求解組合優(yōu)化問(wèn)題上比高斯采樣具有一定的優(yōu)勢(shì)。在TSP中，由于解空間的離散化很難保證解之間的相互關(guān)系，這種相互關(guān)系在函數(shù)優(yōu)化問(wèn)題中體現(xiàn)得較為明顯，一般最優(yōu)解和次優(yōu)解緊挨或者距離很近。這也就導(dǎo)致了算法求解過(guò)程中依高斯概率在當(dāng)前次優(yōu)解周?chē)蓸雍蟮男陆?，回路距離減少不代表新解跟最優(yōu)解的相對(duì)距離更近。這種相對(duì)距離可以理解成城市序列在相同位置上不一樣的城市的個(gè)數(shù)。

3.2 拓展實(shí)驗(yàn)

本節(jié)是對(duì)自由粒子算法框架改進(jìn)算法和其他啟發(fā)式優(yōu)化算法的對(duì)比實(shí)驗(yàn)分析。對(duì)比實(shí)驗(yàn)分析了自由粒子模型的算法跟HPSO、SA、GA、ACO性能。HPSO混合了遺傳算法中的交叉變異操作，將標(biāo)準(zhǔn)粒子群中的速度更新和位置更新替換為粒子與個(gè)體最優(yōu)和全體最優(yōu)進(jìn)行交叉的過(guò)程，算法的初始參數(shù)設(shè)置如下：粒子數(shù)目為1 000，進(jìn)化次數(shù)為1 000；SA的初始參數(shù)設(shè)置如下初始溫度為1000，終止溫度為0.001，在每個(gè)溫度下迭代500次，降溫速率設(shè)置為0.9；GA的初始參數(shù)設(shè)置如下：種群個(gè)數(shù)為100，最大遺傳代數(shù)為1 000，交叉概率為0.9，變異概率為0.05，選擇進(jìn)行交叉和變異的染色體數(shù)目的控制系數(shù)（有時(shí)被稱(chēng)為個(gè)體間的代溝）為0.9；ACO的初始參數(shù)設(shè)置如下：螞蟻數(shù)量為50，信息素重要程度因子為1，啟發(fā)函數(shù)重要程度因子為5，信息素?fù)]發(fā)因子為0.1，最大迭代次數(shù)為1 000。在這些參數(shù)下相應(yīng)的算法均能求解出相對(duì)較好的性能解。

為保證算法的穩(wěn)定性，分別對(duì)6種算法進(jìn)行了10次重復(fù)實(shí)驗(yàn)，對(duì)比了6種算法的最優(yōu)值如表2所示，平均花費(fèi)時(shí)間如表3所示，表中MV（Mean Value）表示10次重復(fù)實(shí)驗(yàn)中求解結(jié)果的平均值，MT（Mean Time）表示10次重復(fù)實(shí)驗(yàn)中求解所花時(shí)間的平均值。

表2 不同算法求解的最優(yōu)值結(jié)果對(duì)比Tab.2 Comparison of theoptimal valuesobtained by different algorithms

表2中加粗?jǐn)?shù)字表示不同算法求出的解中最好的結(jié)果。對(duì)比一些其他的優(yōu)化算法，可以看出自由粒子模型算法的求解效果與HPSO、AS、GA、ACO在eli51、bayg29數(shù)據(jù)集上的求解精度有些差距，在burma14、ulysses16、ulysses22數(shù)據(jù)集上求解結(jié)果更好。在這些數(shù)據(jù)集中的MFPOA-DS比MFPOA求解的結(jié)果都是更優(yōu)的，自適應(yīng)尺度的變化有效提高了算法的求解性能。內(nèi)部機(jī)制搜索的有效性保證了算法求解的可行性，自由粒子模型是一種基礎(chǔ)的骨架模型，算法性能在此基礎(chǔ)上通過(guò)一些策略機(jī)制的加入，可以進(jìn)一步提高算法的性能。以上是對(duì)算法求解精度層面進(jìn)行的對(duì)比，接下來(lái)對(duì)算法的求解時(shí)間上進(jìn)行對(duì)比。

表3 求解TSP實(shí)例時(shí)不同算法求解時(shí)間的對(duì)比 單位：sTab.3 Solving timecomparison of different algorithms in solving TSPexamples unit：s

表4表示在不同的測(cè)試集上，MFPOA-DS相對(duì)HPSO、AS、GA、ACO在求解時(shí)間上減少的百分比，分別用IT1、IT2、IT3、IT4表示：

IT2、IT3、IT4同IT1。由表4可見(jiàn)，MFPOA-DS并不比AS算法有時(shí)間上的優(yōu)勢(shì)，所以表格中的數(shù)據(jù)為負(fù)值。

從相對(duì)節(jié)省時(shí)間數(shù)據(jù)可以得出，AS比其他算法求出最優(yōu)解的求解時(shí)間最少，在時(shí)間復(fù)雜度上求解更優(yōu)，在時(shí)間效率上MFPOA-DS僅次于 AS。相比HPSO、GA和 ACO，MFPOA-DS在5個(gè)測(cè)試集上將運(yùn)行速度分別平均提升了80.42%、55.72%、66.45%?？梢?jiàn)基于自由粒子簡(jiǎn)單結(jié)構(gòu)構(gòu)造的優(yōu)化算法，具有更小的時(shí)間復(fù)雜度，能夠快速、相對(duì)高效的求解組合優(yōu)化問(wèn)題。

值得注意的是，自由粒子優(yōu)化算法結(jié)構(gòu)簡(jiǎn)潔，在求解TSP時(shí)卻有著比較好的表現(xiàn)。這種結(jié)構(gòu)更適合對(duì)領(lǐng)域定義不是非常明確的問(wèn)題，MFPOA的均勻分布結(jié)構(gòu)對(duì)任何可行解都是同等看待，會(huì)使在可行空間上的搜索更加充分。后續(xù)工作會(huì)繼續(xù)驗(yàn)證。

表4 不同測(cè)試集下MFPOA-DS相對(duì)其他算法在求解時(shí)間上減少的百分比 單位：%Tab.4 MFPOA-DSreducesthepercentageof thesolution timeof other algorithms respectively under different test sets unit：%

4 結(jié)語(yǔ)

多尺度量子自由粒子優(yōu)化算法模擬了量子系統(tǒng)下自由粒子的簡(jiǎn)單運(yùn)動(dòng)過(guò)程，在優(yōu)化問(wèn)題中通過(guò)粒子在空間中的運(yùn)動(dòng)進(jìn)行可行域中解的采樣，根據(jù)采樣信息對(duì)搜索空間進(jìn)行縮放控制，實(shí)現(xiàn)在同一搜索尺度下的精細(xì)搜索和不同尺度下搜索中心的聚焦。自由粒子優(yōu)化算法作為基于量子算法模型中的骨架模型，結(jié)構(gòu)簡(jiǎn)潔，易于實(shí)現(xiàn)，通過(guò)對(duì)算法進(jìn)行策略的改進(jìn)，會(huì)使得算法的性能得到很好的提升。在自由粒子模型下的零勢(shì)阱和諧振子模型下的高斯勢(shì)阱的啟發(fā)下，將優(yōu)化問(wèn)題中的目標(biāo)函數(shù)進(jìn)行勢(shì)阱等效和泰勒近似實(shí)現(xiàn)量子模型下的轉(zhuǎn)化，通過(guò)粒子在空間中的存在形式指導(dǎo)優(yōu)化算法的尋優(yōu)過(guò)程，實(shí)現(xiàn)量子模型的搜索機(jī)制。MFPOA和MFPOA-DS求解TSP的結(jié)果可以證明自適應(yīng)尺度改進(jìn)策略的有效性，MFPOA-DS改進(jìn)算法與HPSO、AS、ACO和GA在TSP上的求解數(shù)據(jù)表明，MFPOA-DS算法在不同數(shù)據(jù)集上的求解結(jié)果表現(xiàn)不同，但在保持較好結(jié)果精度的情況下，在求解速度上比HPSO，ACO和GA平均提升50%，但是在求解精度方面算法并不總是比其他的優(yōu)化算法最好，如何使算法的求解精度進(jìn)一步提升成為下一步研究工作中的重點(diǎn)。

MFPOA的搜索結(jié)構(gòu)簡(jiǎn)單，作為優(yōu)化問(wèn)題求解的一種基本的搜索框架，能夠衍射出很多基于均勻分布為采樣方式的算法。未來(lái)的工作將重點(diǎn)對(duì)算法的改進(jìn)和算法間的聯(lián)系進(jìn)行深入研究，找出算法在不同應(yīng)用上的優(yōu)勢(shì)。