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

鄭偉博，張紀(jì)會(huì)

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

?

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

鄭偉博，張紀(jì)會(huì)

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

摘要:針對(duì)PSO算法搜索精度較低，并且在復(fù)雜多模態(tài)函數(shù)優(yōu)化中，容易陷入局部極值的問(wèn)題，提出了一種改進(jìn)的量子行為粒子群優(yōu)化算法。研究了該算法的基本原理、給出了算法流程并采用正交試驗(yàn)的方式獲得了一套通用性較強(qiáng)的算法參數(shù)。并以CEC’13的28個(gè)測(cè)試函數(shù)作為測(cè)試集，采用Wilcoxon符號(hào)秩檢驗(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)勢(shì)。

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

0引言

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

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

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

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

PSO將每個(gè)個(gè)體抽象為粒子，并僅僅賦予該粒子兩個(gè)屬性，即第t次迭代的粒子位置X(t)和粒子速度V(t)。同時(shí)，每個(gè)粒子記憶其歷史最優(yōu)位置Pi(t)和群體歷史最優(yōu)位置Pg(t)。迭代公式見(jiàn)文獻(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)勢(shì)。QPSO算法不再采用PSO算法中確定的速度-位置更新策略，取消了速度屬性，引入量子思想，認(rèn)為粒子可能出現(xiàn)在搜索空間中的任何位置，在某一位置出現(xiàn)的概率由一個(gè)分布函數(shù)決定。每一代粒子出現(xiàn)的具體位置由一次“觀察”操作來(lái)確定，在算法實(shí)現(xiàn)上，利用Monte Carlo方法在第t次迭代遞推第t+1次迭代時(shí)粒子的具體位置。算法流程見(jiàn)文獻(xiàn)[13]。孫俊從理論上推導(dǎo)出當(dāng)創(chuàng)新系數(shù)λ<1.782時(shí)，粒子收斂，同時(shí)做了試驗(yàn)驗(yàn)證[13]。但是在實(shí)際應(yīng)用中，一般取值不大于1，取值大于1時(shí)會(huì)大大影響種群的收斂速度。

1.3Nelder-Mead單純形搜索算法

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

1.4基于Nelder-Mead單純形法的Pg自?xún)?yōu)化QPSO算法

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

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

該算法的流程為：

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

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

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

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

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

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

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

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

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

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

采用CEC’13的28個(gè)測(cè)試函數(shù)(參見(jiàn)文獻(xiàn)[15])，分別對(duì)這4個(gè)控制參數(shù)進(jìn)行L9(34)的正交試驗(yàn)，每組試驗(yàn)100次，取維數(shù)D=5，誤差系數(shù)為0.1，最大迭代次數(shù)為100 000。超過(guò)最大迭代次數(shù)時(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)率為評(píng)價(jià)標(biāo)準(zhǔn)，在達(dá)優(yōu)率相同時(shí)，以每組試驗(yàn)迭代次數(shù)的平均數(shù)為評(píng)價(jià)標(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遞減取值的對(duì)照試驗(yàn)，統(tǒng)計(jì)達(dá)優(yōu)率以判斷固定創(chuàng)新系數(shù)是否優(yōu)于、差于遞減取值，或者無(wú)明顯差異。其中,符號(hào)“NA”表明二者無(wú)明顯差異,即二者達(dá)優(yōu)率差≤±5%，“+”表示固定創(chuàng)新系數(shù)“好”于遞減取值，“-”表示“差”于遞減取值。試驗(yàn)結(jié)果如表2。

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

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

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

3對(duì)比測(cè)試結(jié)果

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

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

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

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

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

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

4結(jié)論

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

參考文獻(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)化問(wèn)題中的應(yīng)用研究[J].儀器儀表學(xué)報(bào),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)化算法及其收斂性分析,自動(dòng)化學(xué)報(bào),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].無(wú)錫:江南大學(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

文章編號(hào)：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)

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

中圖分類(lèi)號(hào)：TP18

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