基于Nelder-Mead單純形法的改進(jìn)量子行為粒子群算法

鄭偉博，張紀(jì)會

(青島大學(xué)復(fù)雜性科學(xué)研究所，山東 青島 266071)

?

基于Nelder-Mead單純形法的改進(jìn)量子行為粒子群算法

鄭偉博，張紀(jì)會

(青島大學(xué)復(fù)雜性科學(xué)研究所，山東 青島 266071)

摘要:針對PSO算法搜索精度較低，并且在復(fù)雜多模態(tài)函數(shù)優(yōu)化中，容易陷入局部極值的問題，提出了一種改進(jìn)的量子行為粒子群優(yōu)化算法。研究了該算法的基本原理、給出了算法流程并采用正交試驗(yàn)的方式獲得了一套通用性較強(qiáng)的算法參數(shù)。并以CEC’13的28個測試函數(shù)作為測試集，采用Wilcoxon符號秩檢驗(yàn)將NM-QPSO算法分別與PSO算法和QPSO算法的誤差進(jìn)行比較試驗(yàn)。試驗(yàn)表明：NM-QPSO算法在統(tǒng)計(jì)意義上優(yōu)于傳統(tǒng)的PSO算法和QPSO算法，并且在高維函數(shù)優(yōu)化中，具有顯著優(yōu)勢。

關(guān)鍵詞：群體智能；粒子群優(yōu)化算法；量子行為粒子群優(yōu)化算法；Nelder Mead單純形法

0引言

群體智能(Swarm Intelligence，SI)算法是模擬自然界生物的群體行為設(shè)計(jì)的隨機(jī)優(yōu)化算法。它通過簡單個體的交互過程突顯出智能行為，因此群體智能具有自組織性。Millonas[1]于1994年提出了群體智能的5個基本原則：距離原則，種群可以進(jìn)行簡單的空間和時間運(yùn)算；質(zhì)量原則，種群能夠?qū)Νh(huán)境中的質(zhì)量因素做出反應(yīng)；反應(yīng)的多樣性原則，種群的反應(yīng)行為具有一定的多樣性，不能太單一；穩(wěn)定性原則，種群不應(yīng)在每次環(huán)境改變時都改變自己的行為模式；適應(yīng)性原則，種群應(yīng)能在改變行為模式是值得的情況下改變其行為模式。目前群體智能研究主要包括蟻群算法和粒子群算法，并衍生出一系列的優(yōu)化算法、聚類算法和多機(jī)器人協(xié)同合作系統(tǒng)等，它們都滿足Millonas提出的群體智能基本原則。其中，蟻群優(yōu)化算法和粒子群優(yōu)化算法在求解實(shí)際問題中應(yīng)用最為廣泛。粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法由Kenney等[2]在1995年提出，其基本思想來源于對鳥群覓食行為的模擬，是一種典型的群體智能優(yōu)化技術(shù)。在該算法中，尋優(yōu)空間中的每一個個體被抽象為一個粒子，僅考慮其位置屬性和速度屬性。其運(yùn)動的速度受自身和群體的歷史最優(yōu)位置的影響，并受到學(xué)習(xí)因子的協(xié)調(diào)，從而較好地協(xié)調(diào)粒子本身和種群之間的關(guān)系。PSO具有算法簡單、搜索效率較高、通用性較強(qiáng)等優(yōu)勢。但它在高維空間搜索時效率較低而且容易出現(xiàn)早熟收斂。眾多學(xué)者對此進(jìn)行了研究。馮奇峰[3]提出將搜索區(qū)域分區(qū)，使用多個子種群并通過微粒間的距離來保持多樣性，然而這類算法在有些情況下會有大量粒子做無用搜索，影響搜索效率。Gülcü和Kodaz H[4]提出一種新的并行學(xué)習(xí)策略PCLPSO，利用所有其它粒子的歷史最優(yōu)信息來更新粒子速度，并加入主從模式。該策略可以保持種群多樣性，防止早熟收斂，可以提高PSO算法在多模態(tài)問題上的性能，但是該算法大大增加了粒子間的交互信息，進(jìn)一步增加了計(jì)算的復(fù)雜度。張勇等[5]提出了一種結(jié)合Nelder-Mead單純型法的PSO改進(jìn)算法，該算法通過并行協(xié)同運(yùn)行兩種算法，以達(dá)到平衡全局和局部尋優(yōu)能力的目的。Meng等[6]提出了一種采用交叉搜索的加速粒子群搜索算法。孫俊等[7—8]將量子理論中的概率云和觀測行為引入PSO，提出了一種具有全局性的量子行為粒子群算法(Quantum-behaved Particle Swarm Optimization，QPSO)，在處理高維多模態(tài)優(yōu)化中取得了較好的效果。在該算法中，取消了PSO算法中的速度屬性，每個粒子的下一次位置依概率彌散在整個搜索域，其概率受自身和群體的歷史最優(yōu)位置影響，其具體位置的確定由一次觀察操作來完成。QPSO算法有效地克服了PSO算法容易陷入局部極值的缺點(diǎn)，即使在所有粒子均收斂到一個較小的區(qū)域時，仍有可能在下次迭代時出現(xiàn)在搜索域的任何位置，并且在高維多模態(tài)優(yōu)化中顯著優(yōu)于PSO算法。但是由于QPSO算法仍舊采用粒子本身做局部搜索，這就要求在搜索到全局最優(yōu)點(diǎn)附近時，全部粒子需要收斂在一個極小的范圍內(nèi)進(jìn)行搜索，這一特性導(dǎo)致難以有效平衡算法的全局和局部搜索能力這一對矛盾。近年來國內(nèi)外學(xué)者還對QPSO進(jìn)行了一系列改進(jìn)研究，Liu等[9]提出了一種結(jié)合模擬退火和協(xié)同進(jìn)化理論的QPSO改進(jìn)算法。

Nelder-Mead 單純形法(Nelder Mead Simplex, NM Simplex)是一個非常實(shí)用的直接搜索技術(shù)，同時也不要求目標(biāo)函數(shù)連續(xù)和可導(dǎo)，具有極強(qiáng)的局部搜索能力，在多維無約束優(yōu)化問題中應(yīng)用非常廣泛[10]。本文受此啟發(fā)，希望在維持QPSO算法全局性的基礎(chǔ)上，提高其局部搜索效率，因此對QPSO算法的群體歷史最優(yōu)點(diǎn)Pg在每次迭代時引入Nelder-Mead單純形搜索，提出了一種具有Pg自優(yōu)化功能的量子行為粒子群優(yōu)化算法。使得這一算法既具有QPSO的全局性強(qiáng)的特點(diǎn)，又具有Nelder-Mead法精細(xì)的局部搜索能力。

1基于NM單純形法的改進(jìn)量子行為粒子群優(yōu)化算法

1.1粒子群優(yōu)化算法

PSO將每個個體抽象為粒子，并僅僅賦予該粒子兩個屬性，即第t次迭代的粒子位置X(t)和粒子速度V(t)。同時，每個粒子記憶其歷史最優(yōu)位置Pi(t)和群體歷史最優(yōu)位置Pg(t)。迭代公式見文獻(xiàn)[11]。其慣性因子，通常設(shè)置為t的線性遞減函數(shù)[12]，以在算法后期加速收斂。

1.2量子行為粒子群優(yōu)化算法

2004年，孫俊等[13]將量子行為引入PSO算法，提出了量子行為粒子群優(yōu)化算法。QPSO算法較PSO算法相比具有更強(qiáng)的隨機(jī)性，因而具有更高的群體智能程度，可以有效地克服PSO算法早熟收斂的不足，并且在處理高維函數(shù)優(yōu)化中具有明顯優(yōu)勢。QPSO算法不再采用PSO算法中確定的速度-位置更新策略，取消了速度屬性，引入量子思想，認(rèn)為粒子可能出現(xiàn)在搜索空間中的任何位置，在某一位置出現(xiàn)的概率由一個分布函數(shù)決定。每一代粒子出現(xiàn)的具體位置由一次“觀察”操作來確定，在算法實(shí)現(xiàn)上，利用Monte Carlo方法在第t次迭代遞推第t+1次迭代時粒子的具體位置。算法流程見文獻(xiàn)[13]。孫俊從理論上推導(dǎo)出當(dāng)創(chuàng)新系數(shù)λ<1.782時，粒子收斂，同時做了試驗(yàn)驗(yàn)證[13]。但是在實(shí)際應(yīng)用中，一般取值不大于1，取值大于1時會大大影響種群的收斂速度。

1.3Nelder-Mead單純形搜索算法

Nelder和Mead[10]于1965年提出了一種用于優(yōu)化多維無約束問題的搜索算法，被稱作Nelder-Mead單純形法。它通過取N維空間中的N+1個點(diǎn)構(gòu)成一個多胞體，計(jì)算頂點(diǎn)評價值。然后對最差點(diǎn)進(jìn)行反射、擴(kuò)展、壓縮等方法獲得一個較好點(diǎn)，用它取代最差點(diǎn)，構(gòu)成一個新的單純形，或者通過向最好點(diǎn)收縮來形成新的單純形，以逼近極小點(diǎn)。該算法具有收斂速度快，并有極強(qiáng)的局部搜索能力，在處理高維問題時，也可以以極小的時間成本搜索到局部最優(yōu)點(diǎn)。而且與PSO算法一樣，該算法并不要求被優(yōu)化函數(shù)連續(xù)，可微和可導(dǎo)。

1.4基于Nelder-Mead單純形法的Pg自優(yōu)化QPSO算法

在高維多模態(tài)問題中，QPSO算法明顯優(yōu)于傳統(tǒng)的PSO算法，但是收斂速度較低，而QPSO算法在局部的搜索主要依靠多個粒子在小范圍里運(yùn)動，這就要求種群必須最終收斂在群體歷史最優(yōu)點(diǎn)Pg附近進(jìn)行搜索。雖然文獻(xiàn)[14]中將λ設(shè)定為1～0.5遞減取值，提高了收斂速度，但是其搜索效果仍舊不盡人意。并且通過分析QPSO迭代公式可知，當(dāng)種群收斂在Pg附近進(jìn)行搜索時，只有當(dāng)u取接近于0時粒子才有可能出現(xiàn)在距Pg較遠(yuǎn)的位置，這樣就使QPSO算法在進(jìn)行精細(xì)搜索的時候較難兼顧全局性。為了克服這一問題，希望在種群粒子不收斂在一個較小的范圍中時，算法仍舊擁有較好的局部搜索能力，以平衡局部搜索效果和全局性這一對矛盾，因此本文提出了基于Nelder-Mead單純形法的改進(jìn)QPSO算法。

NM-QPSO算法的核心思想是通過對QPSO算法的群體歷史最優(yōu)點(diǎn)Pg進(jìn)行Nelder-Mead單純形搜索，使Pg在不借助種群中任何粒子的情況下，自行進(jìn)行優(yōu)化，搜索當(dāng)前Pg所在位置周圍的局部最優(yōu)解?？紤]到NM單純形法在搜索到全局最優(yōu)解的吸引域時，其向極值點(diǎn)的搜索精度顯著高于PSO和QPSO算法，但是初始解的選擇會對NM單純形法的優(yōu)化效果造成較大影響。因此利用QPSO算法為NM單純形法提供一個較好的初始解，從而更容易搜索到全局最優(yōu)解的吸引域。而QPSO的全局性也極大地提高了整個系統(tǒng)在進(jìn)入局部極值吸引域后，擺脫局部極值吸引的能力。

該算法的流程為：

步驟1：初始化每個粒子的當(dāng)前位置Xi，并將當(dāng)前位置Xi記錄為自身歷史最優(yōu)位置Pi。初始化Ω矩陣，其中Ω為D×D矩陣，用于保存D個點(diǎn)的坐標(biāo)，D為目標(biāo)函數(shù)維數(shù)。

步驟2：計(jì)算每個粒子自身歷史最優(yōu)位置Pi的評價值，將最優(yōu)評價值所對應(yīng)的Pi記為種群歷史最優(yōu)位置Pg。

步驟3：將Pg和Ω矩陣對應(yīng)的D個點(diǎn)構(gòu)成一個D+1維多胞體，進(jìn)行一次Nelder-Mead單純形法優(yōu)化。將得到的新單純形中評價值最優(yōu)的點(diǎn)作為Pg，其余D個點(diǎn)的坐標(biāo)作為新的Ω矩陣。

步驟4：根據(jù)QPSO算法迭代公式，更新每個粒子的當(dāng)前位置Xi，并計(jì)算Xi的評價值。

步驟5：對每個粒子，將當(dāng)前位置Xi的評價值與自身歷史最優(yōu)位置Pi的評價值進(jìn)行比較，若優(yōu)于Pi的評價值，則令Pi=Xi。

步驟6：對每個粒子，將當(dāng)前位置Xi的評價值與種群歷史最優(yōu)位置Pg的評價值進(jìn)行比較，若優(yōu)于Pg的評價值，則令Pg=Xi。

步驟7：檢查終止條件，若未達(dá)到終止條件，返回Step3。

2NM-QPSO算法的控制參數(shù)選擇

在NM-QPSO算法中，雖然可以采用Nelder-Mead單純形法和QPSO算法相關(guān)文獻(xiàn)的參數(shù)取值，但是這樣取值并不能保證算法的效果。因此針對NM-QPSO算法的4個控制參數(shù)：α,β,γ,λ進(jìn)行了取值試驗(yàn)。其中α為反射系數(shù)，β為壓縮系數(shù)，γ為擴(kuò)展系數(shù)，λ為創(chuàng)新系數(shù)。

為減少試驗(yàn)次數(shù)，同時不失一般性，設(shè)計(jì)了正交試驗(yàn)?？刂茀?shù)的試驗(yàn)取值選取3個水平，分別為可選取值的最小值，中間值和最大值。如表1所示：

采用CEC’13的28個測試函數(shù)(參見文獻(xiàn)[15])，分別對這4個控制參數(shù)進(jìn)行L9(34)的正交試驗(yàn)，每組試驗(yàn)100次，取維數(shù)D=5，誤差系數(shù)為0.1，最大迭代次數(shù)為100 000。超過最大迭代次數(shù)時認(rèn)為該次試驗(yàn)未能找到全局最優(yōu)位置，定義找到全局最優(yōu)位置的試驗(yàn)次數(shù)占該組試驗(yàn)總次數(shù)的比例為達(dá)優(yōu)率。

本試驗(yàn)中優(yōu)先以達(dá)優(yōu)率為評價標(biāo)準(zhǔn)，在達(dá)優(yōu)率相同時，以每組試驗(yàn)迭代次數(shù)的平均數(shù)為評價標(biāo)準(zhǔn)。鑒于將λ設(shè)為1～0.5遞減取值的參數(shù)設(shè)計(jì)在QPSO算法中取得了較好的效果，為了驗(yàn)證NM-QPSO算法固定創(chuàng)新系數(shù)的合理性，增加一組經(jīng)由正交試驗(yàn)得到的通用控制參數(shù)與將λ設(shè)為1～0.5遞減取值的對照試驗(yàn)，統(tǒng)計(jì)達(dá)優(yōu)率以判斷固定創(chuàng)新系數(shù)是否優(yōu)于、差于遞減取值，或者無明顯差異。其中,符號“NA”表明二者無明顯差異,即二者達(dá)優(yōu)率差≤±5%，“+”表示固定創(chuàng)新系數(shù)“好”于遞減取值，“-”表示“差”于遞減取值。試驗(yàn)結(jié)果如表2。

其中，影響度為單個因素的極差與4個因素的極差和之比，其大小反映該因素的影響程度，值越大表明影響程度越高，影響最高的項(xiàng)已加粗表示。

通過統(tǒng)計(jì)表2可以得出，NM-QPSO算法通用程度較強(qiáng)的一套控制參數(shù)取值方案為：α=1.2,β=0.5,γ=1.5,λ=1。同時分析各函數(shù)特點(diǎn)可以看出，對于非常陡峭的函數(shù)和局部極值非常密集的函數(shù)，為了獲得更快的收斂速度和在小范圍內(nèi)跳出局部極值的能力，往往需要取較小的創(chuàng)新系數(shù)；對于局部極值相隔較遠(yuǎn)的多峰函數(shù)，應(yīng)取較大的創(chuàng)新系數(shù)以獲得較高的全局搜索性能。同時，在優(yōu)化大多數(shù)測試函數(shù)時，創(chuàng)新系數(shù)λ為主要的控制參數(shù)。

對比試驗(yàn)結(jié)果表明，取固定創(chuàng)新系數(shù)的通用控制參數(shù)在函數(shù)優(yōu)化上7個優(yōu)于5個差于創(chuàng)新系數(shù)遞減取值的參數(shù)選擇方案，分析對應(yīng)函數(shù)可以看出在處理局部極值較少，且距離較大的函數(shù)時，取大的固定創(chuàng)新系數(shù)具有更好的全局性，而在處理局部極值較多，極值較為密集的函數(shù)時，創(chuàng)新系數(shù)遞減取值優(yōu)勢在于可以在迭代后期將種群集中在更小的范圍內(nèi)，防止浪費(fèi)搜索資源，但是這會削弱種群的全局搜索性能，總體上取通用控制參數(shù)效果更優(yōu)。

3對比測試結(jié)果

本試驗(yàn)采用了CEC’13的28個測試函數(shù)，每個函數(shù)進(jìn)行n=100次試驗(yàn)，測試5維迭代10 000次和20維迭代100 000次情況下的誤差，對PSO算法，QPSO算法以及NM-QPSO算法分別進(jìn)行了試驗(yàn)。經(jīng)過對試驗(yàn)數(shù)據(jù)做K-S檢驗(yàn)發(fā)現(xiàn)數(shù)據(jù)并不符合正態(tài)分布，不能進(jìn)行t-檢驗(yàn)，并且由于Wilcoxon符號秩檢驗(yàn)較配對t-檢驗(yàn)靈敏度更高[14]，因此執(zhí)行顯著性水平α=0.05的Wilcoxon符號秩檢驗(yàn)以判斷NM-QPSO算法是否顯著優(yōu)于、差于PSO和QPSO算法，或者在統(tǒng)計(jì)意義上無顯著性差異。其中，顯著性符號(Sig.符號)“NA”表明二者無顯著差異，“+”表示NM-QPSO算法顯著“好”，“-”表示NM-QPSO算法顯著“差”。為保證公平，本試驗(yàn)采用本文第2節(jié)得出的NM-QPSO算法通用控制參數(shù)進(jìn)行測試，PSO算法程序采用CEC’13官方測試程序，QPSO算法采用文獻(xiàn)[16]中的參數(shù)選擇。測試結(jié)果如表3～表6。

通過分析以上試驗(yàn)結(jié)果可以看出，NM-QPSO算法較另外兩種算法在處理下降速度較快的單峰函數(shù)時具有顯著優(yōu)勢，例如函數(shù)F2、F4這類非常陡峭的函數(shù)，這種結(jié)果是由于另外兩種算法缺少精細(xì)搜索能力導(dǎo)致的，說明引入NM單純形法這類局部精細(xì)搜索算法對這類函數(shù)的優(yōu)化性能改進(jìn)是顯著有效的。

同時QPSO算法本身較PSO算法在處理全局最優(yōu)解吸引域較小，局部極值的差也較小的多峰函數(shù)時，例如函數(shù)F8，F(xiàn)16等，具有顯著優(yōu)勢。因?yàn)镻SO算法在這類函數(shù)中，獲取的全局歷史最優(yōu)解的吸引能力往往并不能很好地引導(dǎo)其他粒子找到全局最優(yōu)解，而QPSO算法的全局性強(qiáng)在這類問題上的優(yōu)勢顯著存在，同時NM單純形法可以使粒子一進(jìn)入吸引域就可以在極少的迭代次數(shù)中將群體最優(yōu)解Pg固定到極值點(diǎn)附近。這說明NM-QPSO算法在處理這類函數(shù)時顯著優(yōu)于PSO算法。

但是諸如函數(shù)F17,F19這類有下降趨勢，同時在全局最優(yōu)解附近具有大量局部極值的函數(shù)，由于QPSO算法相對于PSO算法為了全局性犧牲了一部分精細(xì)搜索能力，而對于在全局最優(yōu)解附近具有大量局部極值的函數(shù)，例如F17，在全局最優(yōu)解附近[-1,1]D局部極值點(diǎn)個數(shù)隨維度D的上升迅速增長，只要Pg沒有進(jìn)入全局最優(yōu)解的吸引域，NM單純形法的精細(xì)搜索所能提供的幫助就非常有限，只有在維數(shù)較高時才能顯著提高QPSO算法在這類函數(shù)上的搜索效果，并且是顯著差于PSO算法的。因此考慮到顯著增加的計(jì)算量，NM-QPSO算法并不適用于這類函數(shù)。

如圖1和圖2，選取代表性的函數(shù)F2、F8、F16、F17為例，可以明顯看出NM-QPSO在搜索速度上優(yōu)于其他兩種算法，即使在函數(shù)F17這類NM-QPSO算法并不擅長的函數(shù)優(yōu)化中，其在高維搜索時仍舊占據(jù)一定優(yōu)勢。其中直線代表NM-QPSO，點(diǎn)線代表QPSO，虛線代表PSO。

最后，通過橫向?qū)Ρ?維和20維測試結(jié)果可以得出，在被優(yōu)化函數(shù)維數(shù)越高，NM-QPSO算法的效果越好。說明，引入NM單純形法可以有效地提高QPSO算法的精細(xì)搜索能力，并且在QPSO算法優(yōu)勢較為明顯的高維函數(shù)優(yōu)化中，NM-QPSO算法更具有顯著優(yōu)勢。

4結(jié)論

本文結(jié)合QPSO算法和NM單純形法提出了一種基于Nelder-Mead單純形法的Pg自優(yōu)化QPSO算法，給出了NM-QPSO算法的算法流程，討論了控制參數(shù)的選擇，提出了一套通用性較強(qiáng)的參數(shù)選擇方案，并利用測試函數(shù)對NM-QPSO算法和PSO、QPSO算法進(jìn)行了對比試驗(yàn)，驗(yàn)證了NM-QPSO算法具有更好的搜索性能，今后的研究將進(jìn)一步探討Ω矩陣的取點(diǎn)策略，以及在具有某些特征的函數(shù)中在Pg因QPSO算法更新時，對Ω矩陣進(jìn)行小范圍重置等策略。并且今后將進(jìn)一步研究NM-QPSO算法對無約束單目標(biāo)多維優(yōu)化問題的應(yīng)用，并嘗試求解多目標(biāo)、帶約束的多維優(yōu)化問題。

參考文獻(xiàn):

[1]Millonas M M. Swarms, phase transitions, and collective intelligence[C]//Marks R J, Palaniswami M, Fogel D B. Computational Intelligence: A Dynamic System Perspective. Richmond, TX, USA: Institute of Electrical & Electronics Engineers(IEEE).1994: 137-151.

[2]Kennedy J. Particle swarm optimization[C]//International Conference on Neural Networks. Western Austalia, 1995: 1942-1948.

[3]馮奇峰,李言.改進(jìn)粒子群優(yōu)化算法在工程優(yōu)化問題中的應(yīng)用研究[J].儀器儀表學(xué)報,2006,26(9): 984-987.

Feng Qi Feng,Li Yan. Application of improved particle swarm optimization algorithm in engineering optimization problems[J].Chinese Journal of Scientific Instrument, 2006, 26(9):984-987.

[5]張勇,鞏敦衛(wèi),張婉秋.一種基于單純形法的改進(jìn)微粒群優(yōu)化算法及其收斂性分析,自動化學(xué)報,2009,35(3):289-298.

Zhang Yong, Gong Dun Wei, Zhang Wan Qiu.A simplex method based improved particle swarm optimization and analysis on its global convergence[J]. Acta Automatica Sinica,2009,35(3):289-298.

[6]Meng A, Li Z, Yin H, et al. Accelerating particle swarm optimization using crisscross search[J]. Information Sciences, 2016, 329: 52-72.

[7]Sun J, Feng B, Xu W B. Particle swarm optimization with particles having quantum behavior[C]//IEEE Proceedings of Congress on Evolutionary Computation, Portland, USA. 2004: 325-331.

[8]Sun J, Xu W B, Feng B, A global search strategy of quantum-behaved particle swarm optimization[C]// IEEE Proceedings of Cybernetics and Intelligent Systems, Singapore.2004: 111-116.

[9]Liu F, Zhou Z. An improved QPSO algorithm and its application in the high-dimensional complex problems[J]. Chemometrics and Intelligent Laboratory Systems, 2014, 132: 82-90.

[10] Nelder J A, Mead R. A simplex method for function minimization[J]. The computer journal, 1965, 7(4): 308-313.

[11] Shi Y, Eberhart R C. A modified particle swarm optimizer[C]// Proceedings of the IEEE Congress on Evolutionary Computation, Piscataway, N J. 1998: 69-73.

[12] Ma G, Zhou W, Chang X L. A novel particle swarm global optimization algorithm based on particle migration[J]. Applied Mathematics and Computation, 2012, 218(11): 6620-6626.

[13] 孫俊.量子行為粒子群優(yōu)化算法研究[D].無錫:江南大學(xué),2009.

Sun Jun. Research on quantum behaved particle swarm optimization algorithm[D].Wuxi: Jiangnan University,2009.

[14] Derrac J, García S, Molina D, et al. A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J]. Swarm and Evolutionary Computation, 2011, 1(1): 3-18.

[15] Liang J J, Qu B Y, Suganthan P N, et al. Problem definitions and evaluation criteria for the CEC 2013 special session on real-parameter optimization[R]. Singapore: Nanyang Technological University,2013.

[16] Pant M, Thangaraj R, Abraham A. A new quantum behaved particle swarm optimization[C]//The 10th annual conference on Genetic and evolutionary computation. Atlanta, GA, USA, 2008: 87-94.

(責(zé)任編輯耿金花)

A Improved Quantum Behaved Particle Swarm Optimization Algorithm Using Nelder and Mead′s Simplex Algorithm

ZHENG Weibo, ZHANG Jihui

(Institute of Complexity Science, Qingdao University, Qingdao 266071, China)

Abstract：PSO algorithm is poor in search accuracy and prone to fall into the local extremum when solving complex multimodal function optimization problem. So， we propose an improved quantum behaved particle swarm optimization algorithm. This paper studies the fundamentals and basic procedure of that algorithm, An orthogonal test for parameter selection is designed to select a set of reasonable control parameters. We use a suite of 28 test functions from CEC’13 as test set. NM-QPSO is compared with both of traditional PSO and QPSO by using the Wilcoxon Signed Ranks Test respectively. Tests show that the NM-QPSO algorithm has better performance than the traditional PSO and QPSO algorithms in statistical sense, and it has obvious advantages in the high-dimensional function optimization.

Key words：swarm intelligence； particle swarm optimization； nelder mead simplex method

文章編號：1672—3813(2016)02—0097—08;

DOI:10.13306/j.1672-3813.2016.02.012

收稿日期：2015-07-10；修回日期：2015-10-12

基金項(xiàng)目：山東省自然科學(xué)基金(ZR2010GM006)

作者簡介：鄭偉博(1989-)，男，山東濰坊人，碩士研究生，主要研究方向?yàn)槲锪飨到y(tǒng)工程，智能優(yōu)化。 通信作者：張紀(jì)會(1969-)，男，山東青島人，博士，教授，主要研究方向?yàn)槲锪飨到y(tǒng)工程，智能優(yōu)化。

中圖分類號：TP18

文獻(xiàn)標(biāo)識碼：A