量子計算智能 課件 第 5 章 量子粒子群優(yōu)化

1提綱第5章量子粒子群優(yōu)化2提綱第5章量子粒子群優(yōu)化5.1協(xié)同量子粒子群優(yōu)化

5.1.1協(xié)同量子粒子群算法5.1.2改進的協(xié)同量子粒子群算法

5.1.3實驗結果及分析5.2基于多次塌陷-正交交叉的量子粒子群優(yōu)化

5.2.1量子多次塌陷5.2.2正交交叉試驗簡介5.2.3多次塌陷-正交交叉的量子粒子群算法5.2.4實驗及分析5.3結論與討論3提綱第5章量子粒子群優(yōu)化5.1協(xié)同量子粒子群優(yōu)化

5.1.1協(xié)同量子粒子群算法5.1.2改進的協(xié)同量子粒子群算法

5.1.3實驗結果及分析5.2基于多次塌陷-正交交叉的量子粒子群優(yōu)化

5.2.1量子多次塌陷5.2.2正交交叉試驗簡介5.2.3多次塌陷-正交交叉的量子粒子群算法5.2.4實驗及分析5.3結論與討論45.1協(xié)同量子粒子群優(yōu)化

量子機制的粒子群算法是指粒子的搜索過程是滿足量子行為的粒子的運動過程，和粒子群算法是兩種不同的運動方式，并不是在粒子算法的基礎上添加算子，因此理論上并不會增加算法復雜度，即量子粒子群算法和粒子群算法的復雜度是相當?shù)?。雖然QPSO算法的全局搜索能力遠遠優(yōu)于一般的PSO算法。但是與標準的PSO算法一樣，在QPSO算法中同樣存在早熟的趨勢，也就是當群體進化的時候，群體的多樣性不可避免地減少。這是因為每個粒子都是通過學習自身的當前局部最優(yōu)值和全局最優(yōu)值進行下一步的搜索，而不管自身的信息是否有趨向局部最優(yōu)的傾向。如果搜索空間是有許多局部最優(yōu)值的復雜系統(tǒng)，在這種情況下，粒子就很有可能陷入局部最優(yōu)。55.1.1協(xié)同量子粒子群算法

近幾年來國內外學者提出了多種關于協(xié)作思想的算法。VanDenBergh[1]提出了一種協(xié)作的方法，將粒子間的協(xié)作思想加入到粒子群算法中來。在粒子群算法中，每個粒子都代表一個潛在的解，每一步更新都在這個粒子的所有維的基礎上更新，這將會導致粒子中的某些分量越來越靠近最優(yōu)解而另一些分量越來越遠離最優(yōu)解。但是粒子群的更新過程卻只考慮這個粒子的整體性能是好的，忽略了其中的很差的一些分量，因此對于一個高維的問題就很難去找到這個全局最優(yōu)解。H.Gao[2]等人又將協(xié)作的思想引入到量子粒子群算法中來，提出了協(xié)同量子粒子群算法，全局搜索能力進一步提高了。在協(xié)同量子粒子群算法中，跟以往量子粒子算法不同的是，這里是每一個粒子去一65.1.1協(xié)同量子粒子群算法維一維的優(yōu)化，而不是整體去優(yōu)化一個個體。也就是說本書不僅從這個粒子的整體來評價測試這個粒子的好壞，還去評價它的每一維的好壞。每個粒子的分量分別去優(yōu)化，那么就不能直接計算這個粒子的適應度值，因為在不同的個體里它在每一維的貢獻是沒法直接被描述的。為了解決這個問題，文中提出了背景變量(contextvector)的概念，它提供一個合適的背景使得粒子的每一維能在一個公平的環(huán)境下進行評價。文章用全局最優(yōu)作為背景變量。為了計算粒子第維的適應度值，背景變量的第維被粒子的第維代替，然后計算這個更新后的背景變量來評價這個粒子在第維上是否得到了一個比個體最優(yōu)和全局最優(yōu)更精確的值。因此這個方法中粒子的每一維都對種群做出了貢獻。這樣就完成了粒子間的協(xié)作。75.1.1協(xié)同量子粒子群算法下面介紹一個證明協(xié)作的重要性的例子。給一個三維變量和一個誤差函數(shù)，其中。也就是全局最優(yōu)等于?，F(xiàn)在，假設一個種群包含由量子粒子群更新公式得到的兩個個體和，假設在代個體為：

(5-1)(5-2)(5-3)利用上面的誤差函數(shù)評價上面的個體可以得到，，這表明比全局最優(yōu)位置好，如果是沒有協(xié)作的量子粒子群算法，那么直接被所代替，而就會被丟棄掉。然而，的第一維分量20卻是最優(yōu)值的一個分量，它卻沒有為全局最優(yōu)做任何85.1.1協(xié)同量子粒子群算法貢獻，而卻得到了這個比較差的分量中的5。協(xié)作方法可以幫助取得合適的分量。用背景變量分別一維一維去評價的各個分量可以得到，，，因此說明的第二維分量是可以給全局最優(yōu)做出貢獻的，那么用此維數(shù)據(jù)去代替全局最優(yōu)的此維數(shù)據(jù)，得到最終的這一代的全局最優(yōu)位置為，這樣就得到了一個比沒有協(xié)作思想的量子粒子群算法更精確的值?；谏厦娴乃枷?，H.Gao等人提出了協(xié)同量子粒子群算法，算法的性能得到了提高。95.1.2改進的協(xié)同量子粒子群算法1.算法提出大多數(shù)的隨機搜索算法（包括粒子群算法和遺傳算法）都存在維數(shù)災難的問題，也就是會隨著維數(shù)的增多性能會下降。種群中的每個粒子的適應度值(fitnessvalue)都是同時由它的每一維決定的，所以有些粒子的某一維可能已經達到全局最優(yōu)卻因為其他維的壞的搜索結果而要被放棄，這種情況下個體中好的分量就被丟棄了。從前面的描述可以看出協(xié)作思想的重要性，這樣思想的出現(xiàn)就避免了浪費很多時間代價得到的新個體因為整體的不好而直接丟棄掉造成浪費，可以分別去評價每一維數(shù)據(jù)，將有用的信息保存下來，加快收斂速度，對于多維問題的優(yōu)化是有很大幫助的。受此啟發(fā)，本書105.1.2改進的協(xié)同量子粒子群算法提出了改進的協(xié)同量子粒子群算法（Improvedcooperativequantum-behavedparticleswarmoptimization,ICQPSO），并將其在函數(shù)優(yōu)化上進行了測試。量子力學中的不確定性原理告訴我們，量子世界是概率支配的世界，不存在精確預言，只有發(fā)生某一件事的概率。即量子粒子群算法在更新的過程中是遵循量子力學中量子世界的運動規(guī)律的，它是一個完全不確定的位置，它可以搜索到遠離目前個體最優(yōu)的位置，正因為如此，它跳出局部最優(yōu)的可能才大大提高了，但是要評價一個粒子的好壞必須有它的具體位置，那么本書利用蒙特卡洛思想進行觀測，以往存在的量子粒子群算法，一個個體更新只進行了一次觀測得到一個新位置，這樣并沒有充分利用到量子的思想。在[3]中，作者提到了115.1.2改進的協(xié)同量子粒子群算法“對每個量子染色體按不同的觀察方式產生個個體”，受此啟發(fā)并為了充分利用量子力學的不確定性原理，本書在QPSO算法中提出了多次測量的思想，并利用了協(xié)作思想，提出了改進的協(xié)作量子粒子群算法。2.算法描述量子粒子群算法粒子更新過程中是通過觀測而得到的新個體，觀測之前粒子處在一個未知的狀態(tài)，而且以一定的概率出現(xiàn)在一個位置，即給定一個概率去觀測它，那么本書就會得到它的一個位置，對于一個個體，本書隨機產生多個概率，利用蒙特卡洛測量進行了多次觀測，得到多個個體，并選這多個個體中適應度值最好的與個體最優(yōu)值進行比較，然后選取個體最優(yōu)作為背景個體，再來依次評價其余個體的每一維分量，最終得到下一代個體，如此進行一步步搜索。125.1.2改進的協(xié)同量子粒子群算法改進的協(xié)同量子粒子群算法改進部分在多次測量產生多個個體和通過協(xié)作產生新個體部分，其中多次測量是根據(jù)下面的量子粒子群算法更新公式給定不同的隨機數(shù)即可分別產生多個個體，假設產生了五個新個體、、、、。（5-4）（5-5）觀測次數(shù)越多，不確定性利用越充分，收斂速度也越快，但是同時時間也是成線性增長的，因此實際問題中可以根據(jù)需要設置觀測的次數(shù)。算法的流程圖如圖5-1所示：135.1.2改進的協(xié)同量子粒子群算法圖5-1改進的協(xié)同量子粒子群算法流程圖145.1.2改進的協(xié)同量子粒子群算法圖5-2改進的協(xié)同量子粒子群算法過程:初始化種群:XiPbest=XiGbest=bestPbestift<Gmaxforeachparticle

根據(jù)QPSO更新公式產生5個粒子

令Xi=XLXc=XljforeachparticleXkforeachdimensionjiff(Xc(j,Xkj))<f(Xc)Xij=XkjEndifXc=XLendendiff(Xi)<f(pbesti)pbesti=Xiendififf(pbesti)<f(gbest)

gbest=pbestiendifend155.1.2改進的協(xié)同量子粒子群算法協(xié)作的具體操作方法為，從多次測量得到的五個個體中根據(jù)適應度值選出適應度最好的一個個體，假設為，將設為背景變量（contextvector）即，并令，分別用的每一維分量來代替背景變量的相應維度的變量得到新的背景變量，然后計算此時的背景變量的適應度值，若好于，則說明這一維分量是可以為全局最優(yōu)做貢獻的，那么用這個數(shù)據(jù)來替代的相應維度的數(shù)據(jù)，這樣用就可依次將其余四個個體中較好維度的信息評價出來，得到最后的，后面就可根據(jù)量子粒子群算法進化原則求得個體最優(yōu)和全局最優(yōu)個體。過程如圖5-2所示。協(xié)作的過程也可參考下面的圖5-3。165.1.2改進的協(xié)同量子粒子群算法圖5-3改進的協(xié)同量子粒子群算法協(xié)作過程175.1.3實驗結果及分析1.實驗條件為了能夠直觀的考察“改進的協(xié)同量子粒子群算法”的性能，本書列舉了改進的協(xié)同量子粒子群算法（Improvedcooperativequantum-behavedparticleswarmoptimization,ICQPSO）與量子粒子群算法（quantum-behavedparticleswarmoptimization,QPSO）[4]、帶權值的量子粒子群算法（quantum-behavedparticleswarmoptimizationalgorithmwithweightedmeanbestposition,WQPSO）[5]、孫俊等人提出的協(xié)同量子粒子群算法（cooperativequantum-behavedparticleswarmoptimization,CQPSO）[2]的比較。圖5-3改進的協(xié)同量子粒子群算法協(xié)作過程185.1.3實驗結果及分析表5-1基準函數(shù)測試的函數(shù)包括表1中的五個基準函數(shù)和文獻[6]中復雜函數(shù)。其中基準函數(shù)是最小值為0的最小化問題，初始化范圍和限制范圍在表5-1中，下面詳細描述測試的復雜函數(shù)，包括F4、F5、F7、F8、F13和F14。F4(ShiftedSchwefel’sProblem1.2withNoiseinFitness)函數(shù)是一個對基本Schwefel’s問題進行旋轉加噪聲的問題，表達式如下：函數(shù)名表達式初始化區(qū)間最大范圍Spherefunction(-50,100)100Rosenbrockfunction(15,30)100Rastrigrinfunction(2.56,5.12)10Griewankfunction(-300,600)600DeJong,sfunction

(-30,100)100195.1.3實驗結果及分析（5-6）其中，，，。圖5-4函數(shù)F4三維圖205.1.3實驗結果及分析

F5(Schwefel’sProblem2.6withGlobalOptimumonBounds)是一個全局最優(yōu)值在邊界上的Schwefel’s問題，表達式如下：

（5-7）其中，是一個的矩陣，是-500到500間的隨進整數(shù)，是的第行，，，是一個D*1的向量，是-100到100間的隨機數(shù)。時，，，，，，，最小值。圖5-5函數(shù)F5三維圖215.1.3實驗結果及分析

F7(ShiftedRotatedGriewank’sFunctionwithoutBounds)是一個無邊界旋轉函數(shù)，表達式如下：（5-8）其中，,是線性轉換矩陣，conditionnumber=3，最小值。圖5-6函數(shù)F7三維圖225.1.3實驗結果及分析F8(ShiftedRotatedAckley’sFunctionwithGlobalOptimumonBounds)是一個全局最優(yōu)值在邊界上的旋轉函數(shù)，表達式如下：（5-9）其中，

，

是分布在搜索空間的隨數(shù)，

，

，

，最小值

。圖5-7函數(shù)F8三維圖235.1.3實驗結果及分析

F13(ShiftedExpandedGriewank’splusRosenbrock’sFunction(F8F2)是由兩個函數(shù)F2和F8復合成的旋轉函數(shù)，表達式如下：F8:Griewank’sFunction:F2:Rosenbrock’sFunction:（5-10）其中，

，

，

，最小值

。245.1.3實驗結果及分析圖5-8函數(shù)F13三維圖F14(ShiftedRotatedExpandedScaffer’sF6Function)是一個旋轉函數(shù)，表達式如下：（5-11）其中

，

，

是線性轉換矩陣，conditionnumber=3，

，

，最小值

。255.1.3實驗結果及分析圖5-9函數(shù)F14三維圖

實驗中，四種算法種群數(shù)目都為20，在QPSO和WQPSO中，

從1.0線性遞減到0.5，并且WQPSO中的權重值

根據(jù)適應度從1.5線性遞減到0.5，CQPSO參數(shù)和QPSO參數(shù)設置相同，在本書提出的算法ICQPSO中，多次測量的次數(shù)設為5，其他參數(shù)與QPSO相同。對于基準函數(shù)，分別獨立運行50次，比較不用維度下不同迭代次數(shù)的平均最好適應度值和方差。對于復雜函數(shù)，分別獨立運行25次，比較不用維265.1.3實驗結果及分析度下不同迭代次數(shù)的平均最好適應度值和方差。

實驗所用微機的CPU為IntelCore2Duo2.33GHz，內存為2GB，編程平臺為MatlabR2009a。

2.實驗結果及分析1)測量次數(shù)

本書提出了多次觀測的思想，為了確定觀測次數(shù)不同造成的影響，本書對基準函數(shù)f1(Spherefunction)和復雜函數(shù)F4進行了測試，分別設定觀測次數(shù)為1、2、3、4和5，如下圖5-10和圖5-11所示，圖5-12為f1不同測量次數(shù)相同迭代次數(shù)下所花費的時間圖。275.1.3實驗結果及分析

圖5-10f1不同測量次數(shù)收斂速度比較

圖5-10f4不同測量次數(shù)收斂速度比較020406080100100105迭代次數(shù)/次算法適應度

x1x1234546810121416182022迭代次數(shù)/次時間/秒

圖5-10f1不同測量次數(shù)下的時間比較算法適應度值285.1.3實驗結果及分析

從圖5-10和圖5-11可以看出，測量次數(shù)越多，收斂速度越快，圖5-11中線段收斂結束的表明已收斂到最優(yōu)值0，因為圖中是用適應度值的對數(shù)來表示的，所以達到0線段即終止，同時圖5-12也可以看出，測量次數(shù)越多，時間代價也會呈線性增長，本書取測量次數(shù)為5。2)測試基準函數(shù)

表5-2和表5-3為QPSO算法、WQPSO算法、CQPSO算法和本書提出的ICQPSO算法的運行，每個測試函數(shù)運行50次，記錄平均最優(yōu)適應度值和方差。為了測試算法的穩(wěn)定性和算法對于不同函數(shù)的性能，維數(shù)分別為20、30和100，迭代次數(shù)為1500次、2000次和3000次，種群數(shù)為20。295.1.3實驗結果及分析

從表5-2和表5-3可以看出，本書提出的改進的協(xié)同量子粒子群算法的平均最優(yōu)結果和方差都好于QPSO和WQPSO，大部分也都好于孫俊等人提出的協(xié)同量子粒子群算法，在很大程度上全局搜索能力提高了。表5-2QPSO和WQPSO測試基準函數(shù)結果比較fMDGmaxQPSOWQPSOMeanMinSt.VarMeanMinSt.Varf1202015001.3208E-233.3218E-232.4267E-385.8824E-383020001.5767E-154.0566E-156.9402E-321.2879E-3110030001.5077E+011.5926E+014.2014E-114.0006E-11f2202015009.0260E+011.3274E+024.4948E+015.8837E+013020001.8484E+022.6972E+027.6625E+011.0193E+0210030001.9117E+051.7949E+052.4832E+021.9868E+02f3202015001.5697E+015.6303E+001.2945E+014.0725E+003020003.0375E+017.3978E+002.4259E+017.9174E+0010030003.0458E+023.8518E+012.1121E+023.5535E+01f4202015001.8823E-021.9380E-022.4863E-022.3981E-023020004.7967E-037.8878E-039.0994E-031.2641E-0210030001.1076E+003.3209E-014.4359E-039.0706E-03f5202015001.4444E-306.7034E-302.4224E-501.5425E-493020003.0627E-181.1664E-171.5686E-405.9721E-4010030001.8609E+053.4648E+057.7518E-117.8925E-11305.1.3實驗結果及分析

基準函數(shù)維數(shù)為20維、迭代次數(shù)為1500，運行次數(shù)50時，畫出各個方法的盒圖比較圖，如圖5-13-圖5-17所示，可以看出，ICQPSO不管是最小值還是穩(wěn)定程度都取得了較好的結果，只有在Rastrigrin函數(shù)稍差于孫俊提出的CQPSO算法，但是也優(yōu)于QPSO算法和WQPSO算法。說明本書提出的算法在優(yōu)化性能上得到了提高。表5-3sunCQPSO和ICQPSO測試基準函數(shù)結果比較fMDGmaxCQPSOICQPSOMeanMinSt.VarMeanMinSt.Varf1202015004.946880e-3170.0000E+000.0000E+000.0000E+003020000.0000E+000.0000E+004.4466E-3230.0000E+0010030002.4209E-2180.0000E+003.6129E-982.5448E-97f2202015003.7499E+014.8401E+012.9140E+015.6023E+013020005.5191E+016.4979E+012.9660E+014.6534E+0110030008.4586E+014.2951E+011.4697E+029.3562E+01315.1.3實驗結果及分析表5-3sunCQPSO和ICQPSO測試基準函數(shù)結果比較

圖5-13Sphere函數(shù)盒圖

圖5-14Rosenbrock函數(shù)盒圖fMDGmaxCQPSOICQPSOMeanMinSt.VarMeanMinSt.Varf3202015000.0000E+000.0000E+001.2198E+016.4537E+003020005.9698E-022.3869E-011.8049E+016.3279E+0010030009.1352E+007.0400E+001.1293E+021.7379E+01f4202015004.2273E-024.3296E-021.9176E-021.6191E-023020006.1817E-026.9100E-021.0279E-021.5108E-0210030004.4409E-182.1977E-172.6110E-035.1311E-03f5202015000.0000E+000.0000E+000.0000E+000.0000E+003020000.0000E+000.0000E+000.0000E+000.0000E+0010030005.3694E-2850.0000E+003.7938E-1041.4349E-103目標函數(shù)值目標函數(shù)值算法算法325.1.3實驗結果及分析

圖5-15Rastrigrin函數(shù)盒圖

圖5-16Griewank函數(shù)盒圖圖5-17DeJong,s函數(shù)盒圖目標函數(shù)值目標函數(shù)值目標函數(shù)值算法算法算法335.1.3實驗結果及分析3)測試復雜函數(shù)

為了更好的檢驗本書提出的改進協(xié)同量子粒子群算法的性能，又對復雜函數(shù)進行了測試，測試結果如表5-4和表5-5。從表5-4和表5-5可以看出，本書提出的ICQPSO算法的性能遠遠優(yōu)于QPSO算法和WQPSO算法，雖然在F7和F8中CQPSO算法取得了相對好的結果，但是隨著維數(shù)的增高，ICQPSO算法在F7取得了好的結果。說明了隨著問題越來越復雜和維數(shù)越來越高，ICQPSO算法的優(yōu)勢越來越明顯，由此可說明ICQPSO算法的搜索能力提高了。345.1.3實驗結果及分析表5-4QPSO和WQPSO測試復雜函數(shù)結果比較FMinDGmaxQPSOWQPSOMeanMinSt.VarMeanMinSt.VarF4-450101000-449.93641.2208E-01-448.08669.3343E-013030003816.72803.4424E+032712.26602.0903E+0350500035606.90001.1361E+0423635.23007.2601E+03F5-310101000-309.93242.2213E-01-305.41611.3473E+003030003193.76801.0230E+033041.38501.0065E+035050006630.84801.4831E+035908.65701.6307E+03F7-180101000-179.54213.1670E-01-179.07441.2846E-01303000-179.96632.8176E-02-177.95863.1768E-01505000-179.85971.9968E-01-176.12825.3809E-01F8-140101000-119.54019.4892E-02-119.54518.9466E-02303000-118.98415.2917E-02-118.97535.6180E-02505000-118.81863.4865E-02-118.80493.4791E-02F13-130101000-128.76935.2452E-01-128.57785.3839E-01303000-125.42012.3376E+00-121.18742.3874E+00505000-117.74734.2147E+00-108.75924.5567E+00F14-300101000-299.94263.8619E-02-299.93703.5529E-02303000-299.74057.6293E-02-299.73035.5841E-02505000-299.58021.4488E-01-299.56411.1844E-01355.1.3實驗結果及分析表5-5CQPSO和ICQPSO測試復雜函數(shù)結果比較FMinDGmaxCQPSOICQPSOMeanMinSt.VarMeanMinSt.VarF4-450101000-450.00002.5043E-06-450.00007.6966E-14303000-358.69356.5472E+01-450.00001.7589E-1050500010018.28005.3364E+03-449.99565.4487E-03F5-310101000294.07561.2651E+03-309.99923.2831E-033030007562.14702.0838E+032628.13106.5155E+0250500017936.75003.0209E+034317.44601.1770E+03F7-180101000-179.08616.0709E-01-179.27873.3788E-01303000-179.97792.6466E-02-179.97781.7880E-02505000-178.17289.0499E+00-179.99559.1090E-03F8-140101000-119.68911.7260E-01-119.76834.4329E-02303000-119.42851.6130E-01-119.17644.0630E-02505000-119.40072.0131E-01-118.97292.4966E-02F13-130101000-129.33493.4762E-01-129.41011.6906E-01303000-128.28434.8307E-01-127.27983.5150E-01505000-125.78721.6563E+00-125.52637.3139E-01F14-300101000-299.93394.6257E-02-299.99678.8522E-03303000-299.77851.2705E-01-299.99525.0671E-03505000-299.33261.7327E+00-299.99633.5155E-03365.1.3實驗結果及分析

同樣，本書將復雜函數(shù)維數(shù)為10維、迭代次數(shù)為1000，運行次數(shù)25時，畫出各個方法的盒圖比較圖，如圖5-18-圖5-23所示，可以看出，ICQPSO不管是最小值還是穩(wěn)定程度都全部取得了最好的結果。進一步說明本書提出的算法在優(yōu)化性能上得到了提高，并且對于復雜的函數(shù)效果更明顯。

圖5-18F4函數(shù)盒圖

圖5-19F5函數(shù)盒圖目標函數(shù)值目標函數(shù)值算法算法375.1.3實驗結果及分析

圖5-20F7函數(shù)盒圖

圖5-21F8函數(shù)盒圖

圖5-22F13函數(shù)盒圖

圖5-23F14函數(shù)盒圖目標函數(shù)值目標函數(shù)值目標函數(shù)值目標函數(shù)值385.1.3實驗結果及分析

為了更進一步說明本書算法的性能，本書進行了t-test實驗，基準函數(shù)維數(shù)是20，迭代次數(shù)1500，復雜函數(shù)維數(shù)是10，迭代次數(shù)是1000。數(shù)據(jù)如下表5-6。其中s+表示前面算法明顯好于后面算法，s-表示前面算法明顯壞于后面算法，+表示前面算法好于后面算法，-表示前面算法壞于后面算法。

從表中同樣可以看出，ICQPSO在大部分情況下是明顯好于其他量子粒子群算法的，更說明了該算法的良好搜索性能。表5-6ICQPSO,QPSO,WQPSOandCQPSOt-test測試結果t-testResultf1f2f3f4f5F4F5F7F8F13F14ICQPSO-QPSOs+s+s-+s+++s-s+s+s+ICQPSO-WQPSO+s+-++s+s+s+s+s+s+ICQPSO-CQPSOs++s-+s++s+s+s++s+39提綱第5章量子粒子群優(yōu)化5.1協(xié)同量子粒子群優(yōu)化

5.1.1協(xié)同量子粒子群算法5.1.2改進的協(xié)同量子粒子群算法

5.1.3實驗結果及分析5.2基于多次塌陷-正交交叉的量子粒子群優(yōu)化

5.2.1量子多次塌陷5.2.2正交交叉試驗簡介5.2.3多次塌陷-正交交叉的量子粒子群算法5.2.4實驗及分析5.3結論與討論405.2基于多次坍塌-正交交叉的量子粒子群優(yōu)化

優(yōu)化問題是現(xiàn)代數(shù)學的一個重要課題，優(yōu)化方法的理論研究對改進算法、擴展算法應用領域和完善算法體系具有重要作用。在實驗中，優(yōu)化測試函數(shù)代替實際問題評價，作為比較不同算法的性能的衡量。在現(xiàn)有的解決優(yōu)化問題的算法中，啟發(fā)式優(yōu)化算法代替經典優(yōu)化算法被廣泛研究，粒子群算法是其中的一個代表。但是，眾所周知，粒子群算法并不是全局算法，易陷入局部最優(yōu)。基于量子機制的量子粒子群算法(QPSO)可以解決上面的問題，該算法已經被證實具有全局尋優(yōu)性，且具有較快的收斂速度。415.2基于多次坍塌-正交交叉的量子粒子群優(yōu)化

本書把QPSO應用到函數(shù)優(yōu)化問題上，其全局搜索的優(yōu)勢得到發(fā)揮。而在深入研究其性能的過程中發(fā)現(xiàn)，量子體系的概率不確定性并沒有得到較好的利用，結合正交交叉實驗，本書提出了多次塌陷-正交交叉的量子粒子群算法。在優(yōu)化測試函數(shù)的選取上，本書選取公認的常用函數(shù)測試基準函數(shù)，并對較復雜的CEC05復合函數(shù)進行實驗。實驗結果表明，該算法不僅可以更有效地搜索到全局最優(yōu)值，而且收斂速度更快，局部和全局的搜索平衡能力更強。425.2.1量子多次坍塌

(5-12)(5-13)

一個粒子從量子不確定狀態(tài)獲得一個具體位置的過程被稱為單次塌陷。正如公式(5-13)所示，每個u對應著一個位置X，因此，多次塌陷就意味著通過公式(5-13)和(5-14)需使用多個不同的u值以獲得若干個不同的X值。這個過程就被稱為多次塌陷。(5-14)435.2.2正交交叉試驗簡介

正交試驗設計[8][9]能夠均衡地在解空間進行采樣，對實驗結果進行量化的分析和預測，這些優(yōu)秀的特性也吸引了算法設計領域的眾多專家對其進行研究和借鑒。香港學者Leung等人于1999年首次將正交試驗設計應用于優(yōu)化流媒體組播路由的遺傳算法中，創(chuàng)新地提出了正交交叉算子，并提出了用于離散變量的正交遺傳算法。

本書的工作是將正交交叉算子引入到量子粒子群算法中，設計出了多次塌陷-正交交叉量子粒子群算法。445.2.2正交交叉試驗簡介1.正交試驗設計

正交試驗設計是多因素的優(yōu)化試驗設計方法，也稱正交設計，一般是從實驗的全部樣本點中挑選出部分有代表性的樣本點進行實驗，利用這些代表點所做的實驗能夠反映出每個因素各個水平對實驗結果的影響。由于這些代表點具有正交性，因此稱這組實驗為正交試驗，挑選正交的樣本點，安排正交試驗的過程，稱為正交試驗設計。

正交試驗一般用正交表（orthogonalarray）來安排實驗，表5.7為4因素(factor)、3個水平(level)的正交表，記為

，其中L代表正交表，M表示要做M次實驗；

表示有N個因素，每個因素有Q個水平。表中每一縱裂代表同一因素的不同水平；每一橫行代表要運行的一次實驗，實驗完成后，將實驗結果(Ri)寫在右側。455.2.2正交交叉試驗簡介

表5-7正交矩陣

正交矩陣的正交性包含以下三種含義[10][11]：(1)對于每一列的因素，每個水平作用的次數(shù)相等。(2)對于任何兩列的兩個因素，兩個水平的組合發(fā)生的次數(shù)相同。(3)所選出的組合均勻地分布在所有可能組合的整個空間。利用正交表來安排實驗，其優(yōu)點是明顯的：1)減少實驗次數(shù)。對于上述實驗，如果要進行全面實驗共需要34=81次實驗，而按照正交表的安排只需要9次實驗，也就是說只需要部分實驗實驗數(shù).因素實驗結果RABCD11111R121222R231333R342123R452231R562312R673132R783213R893321R9465.2.2正交交叉試驗簡介即可。2)樣本點分布的均衡性。在正交表的每一列中，不同的數(shù)字出現(xiàn)的次數(shù)相等，且都為M/Q次；將任意兩列中同一行的兩個數(shù)字看成有序數(shù)對，則每種數(shù)對出現(xiàn)的次數(shù)相等，都為M/Q2次。圖5-24所示的

的空間模型可以進一步說明正交實驗設計的均衡性。圖中每個軸線代表一個因素，正方體的8個頂點代表了全面實驗的8個實驗點，用正交表確定的4個樣本點（墨點所示）均衡散布其中。具體來說，正方體每個面4個頂點中恰有2個點是樣本點；每條棱上2個頂點中恰有1個是樣本點；分別沿軸線方向投射，在映射面上樣本點恰好完全遍布其中。這些特點適應于一般情況。475.2.2正交交叉試驗簡介圖5-24正交矩陣

的正交性示意圖

利用正交表來安排實驗的另一個顯著優(yōu)點是可以獨立地量化評價同一個因素的各個水平，從而對未進行實驗的因素組合進行預測。有如下定義：(5-15)因素3因素2因素1(2,1,2)(1,2,2)(2,2,1)(1,1,1):選擇的因素水平組合485.2.2正交交叉試驗簡介其中，

表示因素j的水平對實驗的主要影響，

表示輸出結果。當?shù)趇個實驗中因素j的水平等于k時，=1；否則，=0；例如，

觀察表5-7可以發(fā)現(xiàn)，當因素A中同一水平的輸出結果相加時，因素B的水平在3個相加結果中恰好都存在，因此，

，

和

就可以判斷出因素A中3個水平對實驗的不同影響，同理也可以忽略C和D的影響。這樣，通過比較

，

和

就可以判斷出A中3個水平對實驗的不同影響。分別計算

就可以得到每個因素各個水平對于實驗的影響，從而可以預測出最佳的因素水平組合搭配方式。通過計算同一因素各個水平主要影響的標準方差還可以判斷出各個因素對實驗結果影響的劇烈程度。495.2.2正交交叉試驗簡介

正交試驗設計既保證了樣本點分布的均衡性，也能在整個實驗過程中獨立地評價每個因素的各個水平，而且能夠估計各個因素對實驗結果影響的劇烈程度。這些特性對于增加算法的搜索效率、減少函數(shù)的評價次數(shù)、判斷不同變量對函數(shù)優(yōu)化的影響，必定大有裨益。文獻[9]給出了產生一般正交表的構造方法。B.基于正交矩陣的正交交叉

在這部分，本書將正交設計引入到交叉操作并采用正交矩陣來進行一個合理的有代表性的交叉并得到在整個空間均勻分布的子代，這個過程被稱為正交交叉。

為了簡要地說明正交交叉的主要思想，如圖5-25所示，本書采用正交矩陣

來指導兩個二進制父代交叉。

有三個因素，于是父代被分為三部分，隨之產生四個二進制子串。505.2.2正交交叉試驗簡介圖5-25基于

的正交交叉

一般地，通常選擇正交矩陣

來指導正交交叉，其中，用來交叉的父代的個數(shù)是Q，通過正交交叉得到的組合的個數(shù)是M。詳細過程如下所示[9]：515.2.2正交交叉試驗簡介輸入：Q個父代

，

；輸出：M個子代

，

；步驟1：獨立隨機產生隨機數(shù)

，

，;步驟2：基于正交矩陣

中因素和水平的第i個組合

產生新子串

,.

一般地，正交矩陣越大，產生的新組合數(shù)越多，多樣性也越好，然而，所帶來的計算復雜度也越高，因此需要在多樣性和算法時間復雜度上進行平衡。在文章[9]中已被證實，一般情況下對于實際問題的規(guī)模

已是一個較好的選擇。525.2.3多次坍塌-正交交叉的量子粒子群算法

量子粒子群算法將粒子群引入量子空間，利用量子測不準原理代替牛頓力學確定粒子在空間中的位置，通過采用概率波函數(shù)代替粒子群中固定的運動軌跡，保證了粒子可以在整個可行解區(qū)域的搜索，增強了算法的全局搜索能力，理論上保證以概率1收斂到全局最優(yōu)解。然而，量子的不確定特性并沒有得到很好的利用：通過一次塌陷粒子得到一個經典值，而實際上通過它可能通過另外一次塌陷會得到一個更好的值；通過式子

，最好的粒子根據(jù)適應度值被選出，而可能包含更有用信息的其余的粒子均被丟棄。在某種程度上，可以說這是信息的一種浪費。535.2.3多次坍塌-正交交叉的量子粒子群算法

算法流程:

基于上面存在的問題，結合多次塌陷和正交交叉算子本書提出了多次塌陷-正交交叉的量子粒子群算法(multiplecollapsethenorthogonalcrossoverQPSO，MOQPSO)。假設函數(shù)f是最小化問題，MOQPSO的算法流程如下:

步驟1：根據(jù)函數(shù)自變量的取值范圍，隨機初始化種群中各粒子的位置

；

步驟2：評價粒子群的平均最優(yōu)位置mbest；

步驟3：粒子塌陷Q次，得到粒子的Q個位置。

步驟4：Q個粒子正交交叉得到M個新個體，并根據(jù)粒子的適應度值選出最優(yōu)的作為該粒子的位置信息。545.2.3多次坍塌-正交交叉的量子粒子群算法

步驟5：評價粒子的當前適應值，并與前一次迭代的個體最好適應度比較，如果當前適應值小于前一次迭代的個體最好適應值，即

步驟:6：計算群體當前的全局最優(yōu)位置，即

，其中

步驟7：比較當前全局最優(yōu)位置與前一次迭代的全局最優(yōu)位置，如果當前全局最優(yōu)位置的位置較好，則群體的全局最優(yōu)位置更新為它的值；

步驟8：更新種群中各粒子的位置；

步驟9：若終止條件滿足，輸出群體的全局最優(yōu)位置；否則，返回步驟2。555.2.3多次坍塌-正交交叉的量子粒子群算法

從上述算法流程中可以看出，MOQPSO采用多次塌陷可以充分利用量子系統(tǒng)的不確定性以提高種群的多樣性，正交交叉不僅保證了采樣樣本的均衡性，而且可以獨立地評價每個組合的優(yōu)劣以便選出最優(yōu)者。這也是與QPSO的主要區(qū)別之處。這些特點可能改進的算法的性能可以通過實驗得到驗證。MOQPSO的結構圖如圖5-26所示：565.2.3多次坍塌-正交交叉的量子粒子群算法圖5-26MOQPSO的結構圖575.2.4實驗及分析1.實驗設置

為了測試改進算法MOQPSO的性能，十個基準測試函數(shù)和兩個CEC05復合函數(shù)被用來進行測試，并與QPSO、WQPSO、AQPSO、PSO進行比較。

所選函數(shù)都是最小化問題，為了較全面地測試MOQPSO的性能，所選的函數(shù)既包括最優(yōu)值為零和非零的簡單基準測試函數(shù)，又包括具有轉換和旋轉特性的復合函數(shù)。其中，Sphere函數(shù)是單峰函數(shù)，其在原點最優(yōu)值零，因此它經常被用來測試算法的局部搜索能力；Rosenbrock函數(shù)是一個多峰函數(shù)，而且它的最優(yōu)值位于一個狹窄的區(qū)域內很難被搜索到，因此它經常被用來測試算法的局部和全局搜索能力；Rastrigrin函數(shù)是多峰函數(shù)經常被用來測試算法的全局搜索能力。復合函數(shù)F1和F2是從較新的用來測試算法性能的CEC05函數(shù)集[12]中585.2.4實驗及分析提取的。

為了測試算法的穩(wěn)定性，首先，不同的種群規(guī)模、迭代次數(shù)和粒子維數(shù)被采用。種群的規(guī)模分別是20、40、80，最大迭代次數(shù)依次為1000、1500和2000，對應的維數(shù)分別為10、20、30.其次，在依次測試完Sphere、Rosenbrock和Rastrigrin函數(shù)后，為保證測試的效率，在研究測試結果之后本書將種群規(guī)模、迭代次數(shù)和維數(shù)分別選定為40、1000和10來測試其余的七個基準函數(shù)和兩個復合函數(shù)。

為保證比較的合理性，測試算法中的所有參數(shù)設置均根據(jù)相關文獻取值以保證各算法均取得最佳效果。在PSO中，系數(shù)C1=C2=2，初始權重W從0.9降到0.4.在QPSO和MOQPSO中，收縮-擴張因子

的最大值是1.0，最小值為0.5。在WQPSO中，權重系數(shù)因子根據(jù)適應度值595.2.4實驗及分析從1.5到0.5線性遞減。在MOQPSO中，所采用的正交矩陣為

，塌陷次數(shù)Q=3。三個測試函數(shù)如表5-8所示，10個基準函數(shù)如表5-9所示。表5-8三個測試函數(shù)函數(shù)公式變量區(qū)域最優(yōu)值Spherefunctionf1[-100,100]0Rosenbrockfunctionf2[-100,100]0Rastrigrinfunctionf3[-10,10]0605.2.4實驗及分析表5-9所測試的10個基準函數(shù)（D表示變量維數(shù)，

表示變量區(qū)域，Min表示最優(yōu)值）問題維度變量區(qū)域最優(yōu)值10[-100,100]010[-100,100]010[-10,10]010[-10,10]010[-100,100]010[-5,5]-78.332362[-10,10]-186.732[-1,1]-2.262[-1,1]-0.2400352[-5.12,5.12]-1.031628615.2.4實驗及分析2.實驗結果及分析1)基準測試函數(shù)的測試結果及分析。

首先，本書測試了表5-9中的十個優(yōu)化函數(shù)問題，并與PSO、QPSO算法進行比較。

表5-10-5-12分別給出了Sphere、Rosenbrock、Rastrigrin三個函數(shù)在不同種群規(guī)模、空間維數(shù)、迭代次數(shù)條件下獨立運行50代所取得的平均最優(yōu)值和均方差。從Sphere的結果上可以看出，MOQPSO在最優(yōu)值和方差上均為零，也就是說總能較好地搜索到最優(yōu)值，較前兩種算法有所改善。這說明，改進后的算法具有較好的局部搜索能力。由于Rosenbrock函數(shù)比較特殊，一般的算法都較難搜索到最優(yōu)值，效果都不太理想。盡管如此，表5-11顯示，MOQPSO搜索到的結果相對來說625.2.4實驗及分析比PSO、QPSO都要好很多，因此，可以說改進后的算法在局部和全局的搜索能力和平衡能力上均有所提高。對于Rastrigrin函數(shù)，表5-12顯示的結果表明改進后的算法在全局搜索能力上明顯提高。表5-10Sphere函數(shù)的平均值和方差MDGer.PSOQPSOMOQPSOMeanbestSt.dev.MeanbestSt.dev.MeanbestSt.dev.201010000.52710.61381.9898e-279.4410e-27002015003.58521.93445.8370e-142.2693e82083.42325.0027e-091.3539e-0800401010000.09100.14123.6428e-551.8209e-54002015001.99941.39041.6300e-291.1451e-28003020004.95792.52604.5547e-213.0213e-2000801010000.04730.16629.9341e-786.5523e-77002015000.83250.68336.9710e-544.8015e-53003020004.14483.82018.3320e-414.9279e-4000635.2.4實驗及分析

從上述結果中還可以發(fā)現(xiàn)，在相同的種群規(guī)模下，隨著維數(shù)和迭代次數(shù)的增加，函數(shù)的結果隨之變壞；而在空間維數(shù)和迭代代數(shù)保持不變的情況下，隨著種群規(guī)模的增大，函數(shù)的實驗結果越好。這是因為隨著種群規(guī)模的增大，種群的多樣性得到提高，因此搜索到的結果也會有所改善。但種群規(guī)模越大，算法計算復雜度的代價也會越大，在綜合考慮搜索復雜度和優(yōu)化結果之后，本書將種群規(guī)模、空間維數(shù)和迭代代數(shù)分別設定為40、10、1000，并測試后續(xù)的基準函數(shù)和復合函數(shù)。645.2.4實驗及分析表5-11ROSENBROCK函數(shù)的平均值和方差表5-12RASTRIGRIN函數(shù)的平均值和方差MDGer.PSOQPSOMOQPSOMeanbestSt.dev.MeanbestSt.dev.MeanbestSt.dev.2010100084.160980.630547.814490.12046.36680.6404201500170.9015106.0103102.5762184.673716.56101.0230302000342.0081127.6591121.7741160.748826.23741.5560e35557.875734.841567.04096.23746.2944e-1520150087.036544.459946.461944.378216.23741.4083e0328113.128167.366182.551726.30210.4575801010005.73714.04533.50273.70746.23744.2500e-1520150057.873638.200634.046533.427316.23728.8926e761461.320144.630842.880326.23741.9212e-14MDGer.PSOQPSOMOQPSOMeanbestSt.dev.MeanbestSt.dev.MeanbestSt.dev.2010100026.176110.40055.31872.58550.55710.782620150099.540219.457818.32195.23390.59691.2585302000180.600431.277236.53447.76630.91532.16344010100020.24498.76333.36781.71740.29840.731620150071.000721.066314.16025.19870.21880.4163302000150.356436.126328.98347.33270.19890.40208010100022.734712.23462.33031.61430020150061.794224.598211.44604.47670.03970.1969302000123.24029.018023.06856.09980.01980.1407655.2.4實驗及分析表5-13十個測試函數(shù)的平均值和方差

表5-13給出了PSO、QPSO和MOQPSO三種算法對十個基準測試函數(shù)的實驗結果，包括平均值和方差。表中結果可以看出，MOQPSO的搜索結果均等于或非常接近函數(shù)的最優(yōu)值，且具有較小的方差，尤其對于函數(shù)1、2、3、5和7。這證實了本書提出的算法的有效性。函數(shù)PSOQPSOMOQPSOMeanbestSt.dev.MeanbestSt.dev.MeanbestSt.dev.f10.15440.46722.3904e-581.5590e-5700f244.916443.319628.713866.368.10048.9719e-15f321.307110.67013.49261.839500f42.5261e-34.3049e-33.8873e-041.9232e-31.9431e-41.3740e-3f53.64812.74735.2673e-283.5928e-2700f6-66.73137.8987-76.07042.7394-74.54362.3279f7-186.69380.0888-183.966219.5478-186.73097.2012e-7f8-Inf-Inf-2.25991.8080e-7-2.25991.0917e-9f9-0.23992.8037e-17-0.23998.7196e-12-0.22340.0818f10-1.03166.7289e-16-1.03161.5692e-9-1.03165.8053e-11665.2.4實驗及分析迭代次數(shù)/代迭代次數(shù)/代迭代次數(shù)/代迭代次數(shù)/代迭代次數(shù)/代迭代次數(shù)/代f1f3f4f1f5f6f2675.2.4實驗及分析迭代次數(shù)/代迭代次數(shù)/代迭代次數(shù)/代迭代次數(shù)/代f7f8f9f10圖5-27三個算法在十個測試函數(shù)上獨立運行50代的收斂曲線圖比較685.2.4實驗及分析

為了證實算法的收斂速度，圖5-27給出了三種算法對十個測試函數(shù)分別獨立運行50次之后得到的收斂曲線圖?？梢园l(fā)現(xiàn)，對于大多數(shù)函數(shù)，MOQPSO的收斂速度均為最快。因為在QPSO和MOQPSO中算法的參數(shù)設置是一樣的，因此可以說新算法中引入的多次塌陷和正交交叉起了積極作用。695.2.4實驗及分析適應度值適應度值適應度值適應度值適應度值適應度值適應度值適應度值函數(shù)（1）函數(shù)（2）函數(shù)（3）函數(shù)（4）函數(shù)（5）函數(shù)（6）函數(shù)（7）函數(shù)（8）705.2.4實驗及分析圖5-28PSO、QPSO、MOQPSO三種算法對十個測試函數(shù)的盒圖測試結果比較

每一個函數(shù)獨立運行50次的結果的盒圖描述如圖5-28所示。其中，M代表MOQPSO算法，Q代表QPSO算法，而P代表PSO算法。盒圖常用來測評算法的魯棒性。圖示結果顯示，M所獲得的函數(shù)值較密集于最優(yōu)值周圍，也就是說，MOQPSO的魯棒性均要優(yōu)于QPSO，除了函數(shù)9；同時在大多數(shù)函數(shù)上也要優(yōu)于PSO，除了函數(shù)9和10?？傮w來看，MOQPSO的統(tǒng)計結果顯示其性能是由于其它兩種算法的，尤其在函適應度值適應度值函數(shù)（9）函數(shù)（10）715.2.4實驗及分析數(shù)2、3、4、5、6和8上效果更加明顯?？傊?，在測試上述是個函數(shù)的過程中不難發(fā)現(xiàn)，無論是在算法收斂速度、魯棒性，還是在優(yōu)化結果上，改進后的算法都更勝一籌。2)復合函數(shù)測試結果及分析

為了進一步測試算法的性能，本書采用四個具有轉換和旋轉特性的CEC05復合函數(shù)進行測試。測試函數(shù)F1、F3分別為具有轉換特性的ShiftedSphere、Rosenbrock’s函數(shù)，在原點取得最優(yōu)值-450、390；F2、F4分別為具有轉換和旋轉特性的ShiftedRotatedWeierstrass、Ackley’s函數(shù)，最優(yōu)值為90、-140。725.2.4實驗及分析表5-14CEC05復合函數(shù)的測試結果problemsPSOQPSOMOQPSOMeanbestSt.dev.MeanbestSt.dev.MeanbestSt.dev.F12.1801e+32.2248e+3-4500-4500F297.93841.3479101.57642.952295.49202.9946F39.6533e+062.2919e+07396.76127.2330394.27283.5650F4-119.66388.9924e-02 119.570.0645-119.70200.0578735.2.4實驗及分析迭代次數(shù)/代迭代次數(shù)/代f1f20250500026x109迭代次數(shù)/次適應度值

MOQPSOQPSOPSO05001000-119.7-119.3-119-118.7迭代次數(shù)/次適應度值

MOQPSOQPSOPSO適應度值適應度值圖5-29三個算法分別對復合函數(shù)獨立測試50次的收斂曲線圖745.2.4實驗及分析圖5-29三個算法分別對復合函數(shù)獨立測試50次的收斂曲線圖0200040006000MQP函數(shù)(1)9296100104MQP函數(shù)(1)0246x107MQP-119.8-119.7-119.6-119.5MQP適應度值適應度值適應度值適應度值f1f2f3f4圖5-30三種算法對復合函數(shù)獨立運行50次的測試結果的盒圖

表