【正文】 勻分布隨機(jī)數(shù)進(jìn)行初始化實(shí)現(xiàn)容易但尤其對高維空間效果差，并另外比較了3種初始化分布方法。 鄰域拓?fù)?根據(jù)粒子鄰域是否為整個(gè)群體，PSO分為全局模型和局部模型 [20]。對于模型，每個(gè)粒子與整個(gè)群體的其他粒子進(jìn)行信息交換，并有向所有粒子中的歷史最佳位置移動(dòng)的趨勢。Kennedy[21]指出，模型雖然具有較快的收斂速度，但更容易陷入局部極值。為了克服全局模型的缺點(diǎn)，研究人員采用每個(gè)粒子僅在一定的鄰域內(nèi)進(jìn)行信息交換，提出各種局部模型[21,]。根據(jù)現(xiàn)有的研究成果，本文將鄰域分為空間鄰域(spatial neighborhood)、性能空間(performance space)鄰域和社會(huì)關(guān)系鄰域(sociometric neighborhood)?？臻g鄰域直接在搜索空間按粒子間的距離(如歐式距離)進(jìn)行劃分，如Suganthan[23]引入一個(gè)時(shí)變的歐式空間鄰域算子：在搜索初始階段，將鄰域定義為每個(gè)粒子自身；隨著迭代次數(shù)的增加，將鄰域范圍逐漸擴(kuò)展到整個(gè)種群。性能空間指根據(jù)性能指標(biāo)(如適應(yīng)度、目標(biāo)函數(shù)值)劃分的鄰域，如文獻(xiàn)[24]采用適應(yīng)度距離比值(fitnessdistanceratio)來選擇粒子的相鄰粒子。社會(huì)關(guān)系鄰域通常按粒子存儲(chǔ)陣列的索引編號進(jìn)行劃分[25]，這也是研究最多的一種劃分手段，主要有[21]：環(huán)形拓?fù)?ring or circle topology)、輪形拓?fù)?wheel topology)或星形拓?fù)?star topology)、塔形拓?fù)?pyramid topology)、馮－諾以曼拓?fù)?Von Neumann topology)以及隨機(jī)拓?fù)?random topology)等。針對不同的優(yōu)化問題，這些拓?fù)涞男阅鼙憩F(xiàn)各異；但總的來說，隨機(jī)拓?fù)渫鶎Υ蠖鄶?shù)問題能表現(xiàn)出較好的性能，其次是馮－諾以曼拓?fù)鋄22]。M. Clerc[25]對隨機(jī)拓?fù)溥M(jìn)行了進(jìn)一步分析，并在2006年版和2007年版的標(biāo)準(zhǔn)PSO[23]中采用了隨機(jī)拓?fù)洹４送?，文獻(xiàn)[21]提出動(dòng)態(tài)社會(huì)關(guān)系拓?fù)?Dynamic sociometry)，初始階段粒子采用環(huán)形拓?fù)?ringtype topology)，隨著迭代次數(shù)的增加，逐漸增加粒子間連接，最后形成星形拓?fù)?startype topology)。 此外，還有其它一些主要對群體進(jìn)行劃分的鄰域結(jié)構(gòu)(本文暫稱“宏觀鄰域”；則上述鄰域稱為“微觀鄰域”)。文獻(xiàn)[19]引入了子種群，子種群間通過繁殖(Breeding)實(shí)現(xiàn)信息交流。Kennedy[20]提出了社會(huì)趨同(Stereotyping)模型，使用簇分析將整個(gè)粒子群劃分為多個(gè)簇，然后用簇中心代替帶收縮因子PSO中的粒子歷史最佳位置或群體歷史最佳位置。X. Li[21]根據(jù)粒子相似性動(dòng)態(tài)地將粒子群體按種類劃分為多個(gè)子種群，再以每個(gè)子種群的最佳個(gè)體作為每個(gè)粒子的鄰域最佳位置。Stefan Janson等人[22]提出等級PSO(hierarchical particle swarm optimizer, HPSO)，采用動(dòng)態(tài)等級樹作為鄰域結(jié)構(gòu)，歷史最佳位置更優(yōu)的粒子處于上層，每個(gè)粒子的速度由自身歷史最佳位置和等級樹中處于該粒子上一個(gè)節(jié)點(diǎn)的粒子的歷史最佳位置決定。文獻(xiàn)[13]采用主－仆模型(master–slaver model)，其中包含一個(gè)主群體，多個(gè)仆群體，仆群體進(jìn)行獨(dú)立的搜索，主群體在仆群體提供的最佳位置基礎(chǔ)上開展搜索。文獻(xiàn)[14]將小生境(niche)技術(shù)引入到PSO中，提出了小生境PSO(Niching Particle Swarm Optimizer)。文獻(xiàn)[15]采用多群體進(jìn)行解的搜索。文獻(xiàn)[14]則每間隔一定代數(shù)將整個(gè)群體隨機(jī)地重新劃分，提出動(dòng)態(tài)多群體PSO。 在標(biāo)準(zhǔn)的PSO算法中，所有粒子僅僅向自身和鄰域的歷史最佳位置聚集，而沒有向鄰域內(nèi)其他個(gè)體(即使這些個(gè)體很優(yōu)秀)學(xué)習(xí)，造成信息資源的浪費(fèi)，甚至因此而陷入局部極值；考慮到此因素，Kennedy 等人[17]提出了全信息粒子群(fully informed particle swarm, FIPS)，在FIPS中，每個(gè)粒子除了自身和鄰域最佳歷史位置外，還學(xué)習(xí)鄰域內(nèi)其他粒子的成功經(jīng)驗(yàn)。 上述粒子間學(xué)習(xí)是在整個(gè)維空間中構(gòu)造鄰域進(jìn)行的，這樣當(dāng)搜索空間維數(shù)較高時(shí)往往容易遭受“維數(shù)災(zāi)(curse of dimensionality)”的困擾[14]?；谶@方面的考慮，Van den Bergh等人[18]提出了協(xié)作PSO(Cooperative PSO)算法，其基本思路就是采用協(xié)作行為，利用多個(gè)群體分別在目標(biāo)搜索空間中的不同維度上進(jìn)行搜索，也就是一個(gè)優(yōu)化解由多個(gè)獨(dú)立群體協(xié)作完成，每個(gè)群體只負(fù)責(zé)優(yōu)化這個(gè)解矢量部分維上的分量。Baskar和Suganthan[19]提出一種類似的協(xié)作PSO，稱為并發(fā)PSO(concurrent PSO， CONPSO)，它采用兩個(gè)群體并發(fā)地優(yōu)化一個(gè)解矢量。近來，ElAbd 等人[20]結(jié)合文獻(xiàn)[18,19]的技術(shù)，提出了等級協(xié)作PSO(hierarchal cooperative PSO)。 無論是粒子群在D維的搜索還是多個(gè)粒子群在不同維上的協(xié)作搜索，其目的都是為了每個(gè)粒子能夠找到有利于快速收斂到全局最優(yōu)解的學(xué)習(xí)對象。J. Liang 等人[4]提出了一種既可以進(jìn)行D維空間搜索、又能在不同維上選擇不同學(xué)習(xí)對象的新的學(xué)習(xí)策略，稱為全面學(xué)習(xí)PSO (Comprehensive Learning Particle Swarm Optimizer，CLPSO)。與傳統(tǒng)PSO只向自身歷史最佳位置和鄰域歷史最佳位置學(xué)習(xí)不同，CLPSO的每個(gè)粒子都隨機(jī)地向自身或其它粒子學(xué)習(xí)，并且其每一維可以向不同的粒子學(xué)習(xí)；該學(xué)習(xí)策略使得每個(gè)粒子擁有更多的學(xué)習(xí)對象，可以在更大的潛在空間飛行，從而有利于全局搜索。CLPSO的速度更新公式為： （）其中為加速因子，為[0,1]內(nèi)的均勻隨機(jī)數(shù)，表示粒子在第維的學(xué)習(xí)對象，它通過下面的策略決定：產(chǎn)生[0,1]內(nèi)的均勻隨機(jī)數(shù)，如果該隨機(jī)數(shù)大于為粒子預(yù)先給定的學(xué)習(xí)概率，則學(xué)習(xí)對象為自身歷史最佳位置；否則，從種群內(nèi)隨機(jī)選取兩個(gè)個(gè)體，按錦標(biāo)賽選擇(tournament selection)策略選出兩者中最好的歷史最佳位置作為學(xué)習(xí)對象。同時(shí)，為了確保粒子盡可能向好的對象學(xué)習(xí)而不把時(shí)間浪費(fèi)在較差的對象上，上述學(xué)習(xí)對象選擇過程設(shè)定一個(gè)更新間隔代數(shù)(refreshing gap)，在此期間的學(xué)習(xí)對象保持上次選擇的學(xué)習(xí)對象不變。以上的各種鄰域結(jié)構(gòu)，無論是微觀拓?fù)溥€是宏觀鄰域，也無論是在整個(gè)搜索空間進(jìn)行信息交流還是以空間的不同維分量為單位協(xié)作搜索，都不主動(dòng)改變鄰域狀態(tài)，而只是在給定的鄰域內(nèi)進(jìn)行學(xué)習(xí)交流，本文稱之為PSO的被動(dòng)局部模型。還有一類局部模型就是主動(dòng)改變粒子鄰域空間，避免碰撞和擁擠，本文稱之為PSO的主動(dòng)局部模型。Blackwell 等人[3]將粒子分為自然粒子和帶電粒子，當(dāng)帶電粒子過于接近時(shí)產(chǎn)生斥力，使之分開以提高粒子多樣性；L248。vbjerg 等人為每個(gè)粒子引入與相鄰粒子距離成反比的自組織危險(xiǎn)度(selforganized criticality)指標(biāo)，距離越近則危險(xiǎn)度越高，當(dāng)達(dá)到一定閾值后，對該粒子進(jìn)行重新初始化或推開一定距離降低危險(xiǎn)度，達(dá)到提高群體多樣性的目的；文獻(xiàn)[15]提出一種帶空間粒子擴(kuò)展的PSO，為每個(gè)粒子賦一半徑，以檢測兩個(gè)粒子是否會(huì)碰撞，并采取隨機(jī)彈離、實(shí)際物理彈離、簡單的速度—直線彈離等措施將其分開。 混合策略 混合策略混合PSO就是將其它進(jìn)化算法或傳統(tǒng)優(yōu)化算法或其它技術(shù)應(yīng)用到PSO中，用于提高粒子多樣性、增強(qiáng)粒子的全局探索能力，或者提高局部開發(fā)能力、增強(qiáng)收斂速度與精度。這種結(jié)合的途徑通常有兩種：一是利用其它優(yōu)化技術(shù)自適應(yīng)調(diào)整收縮因子/慣性權(quán)值、加速常數(shù)等；二是將PSO與其它進(jìn)化算法操作算子或其它技術(shù)結(jié)合。文獻(xiàn)[16]將螞蟻算法與PSO結(jié)合用于求解離散優(yōu)化問題；Robinson 等人[17]和Juang[18]將GA與PSO結(jié)合分別用于天線優(yōu)化設(shè)計(jì)和遞歸神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)；文獻(xiàn)[19]將種群動(dòng)態(tài)劃分成多個(gè)子種群，再對不同的子種群利用PSO或GA或爬山法進(jìn)行獨(dú)立進(jìn)化；Naka等人[10]將GA中的選擇操作引入到PSO中，按一定選擇率復(fù)制較優(yōu)個(gè)體；Angeline [11]則將錦標(biāo)賽選擇引入PSO 算法，根據(jù)個(gè)體當(dāng)前位置的適應(yīng)度，將每一個(gè)個(gè)體與其它若干個(gè)個(gè)體相比較，然后依據(jù)比較結(jié)果對整個(gè)群體進(jìn)行排序，用粒子群中最好一半的當(dāng)前位置和速度替換最差一半的位置和速度，同時(shí)保留每個(gè)個(gè)體所記憶的個(gè)體最好位置；ElDib 等人[12]對粒子位置和速度進(jìn)行交叉操作；Higashi [13]將高斯變異引入到PSO中；Miranda等人[14]則使用了變異、選擇和繁殖多種操作同時(shí)自適應(yīng)確定速度更新公式中的鄰域最佳位置以及慣性權(quán)值和加速常數(shù)；Zhang等人[8]利用差分進(jìn)化(DE)操作選擇速度更新公式中的粒子最佳位置；而Kannan 等人[18]則利用DE來優(yōu)化PSO的慣性權(quán)值和加速常數(shù)。 此外，其它一些搜索技術(shù)與PSO結(jié)合以提高算法的局部搜索能力，如文獻(xiàn)[9]提出一種基于PSO和LevenbergMarquardt的混合方法。文獻(xiàn)[10]將PSO與單純形法相結(jié)合；文獻(xiàn)將PSO與序貫二次規(guī)劃相結(jié)合；文獻(xiàn)[12]將模擬退火與PSO結(jié)合；文獻(xiàn)[13]將禁忌技術(shù)與PSO結(jié)合；文獻(xiàn)[8]將爬山法與PSO結(jié)合；文獻(xiàn)[15]將PSO與擬牛頓法結(jié)合。 還有作者引入其它一些機(jī)制，以改進(jìn)PSO的性能。文獻(xiàn)[6]根據(jù)耗散結(jié)構(gòu)的自組織性，提出一種耗散粒子群優(yōu)化算法(dissipative PSO)。該算法通過附加噪聲持續(xù)為粒子群引入負(fù)熵(negative entropy)，使得系統(tǒng)處于遠(yuǎn)離平衡態(tài)的狀態(tài)，又由于群體中存在內(nèi)在的非線性相互作用，從而形成自組織耗散結(jié)構(gòu)，使粒子群能夠“持續(xù)進(jìn)化”，抑制早熟停滯。文獻(xiàn)[7]將自然進(jìn)化過程中的群體滅絕現(xiàn)象引入PSO，在微粒的位置和速度更新之后，按照一個(gè)預(yù)先定義的滅絕間隔重新初始化所有微粒的速度。文獻(xiàn)[8]通過模擬自然界的被動(dòng)聚集(Passive Congregation)行為修改速度更新公式，實(shí)現(xiàn)種群內(nèi)信息充分共享，防止了微粒因缺乏足夠的信息而判斷失誤所導(dǎo)致陷入局部極小。文獻(xiàn)[9]將引力場模型引入到PSO。此外，還有其它一些混合PSO： 1）高斯PSO：由于傳統(tǒng)PSO往往是在全局和局部最佳位置的中間進(jìn)行搜索，搜索能力和收斂性能嚴(yán)重依賴加速常數(shù)和慣性權(quán)值的設(shè)置，為了克服該不足，Secrest等人[10]將高斯函數(shù)引入PSO算法中，用于引導(dǎo)粒子的運(yùn)動(dòng)；GPSO不再需要慣性權(quán)值，而加速常數(shù)由服從高斯分布的隨機(jī)數(shù)產(chǎn)生。 2）拉伸PSO(Stretching PSO, SPSO)：SPSO將所謂的拉伸技術(shù)(stretching technique)[11]以及偏轉(zhuǎn)和排斥技術(shù)應(yīng)用到PSO中，對目標(biāo)函數(shù)進(jìn)行變換，限制粒子向已經(jīng)發(fā)現(xiàn)的局部最小解運(yùn)動(dòng)，從而利于粒子有更多的機(jī)會(huì)找到全局最優(yōu)解[4, 6]。 混沌粒子群優(yōu)化：混沌是自然界一種看似雜亂、其實(shí)暗含內(nèi)在規(guī)律性的常見非線性現(xiàn)象，具有隨機(jī)性、遍歷性和規(guī)律性特點(diǎn)。文獻(xiàn)[3]利用混沌運(yùn)動(dòng)的遍歷性以粒子群的歷史最佳位置為基礎(chǔ)產(chǎn)生混沌序列，并將此序列中的最優(yōu)位置隨機(jī)替代粒子群中的某個(gè)粒子的位置，提出混沌PSO (chaos particle swarm optimization, CPSO)。除此之外，文獻(xiàn)[4]利用慣性權(quán)值自適應(yīng)于目標(biāo)函數(shù)值的自適應(yīng)PSO進(jìn)行全局搜索、利用混沌局部搜索對最佳位置進(jìn)行局部搜索，提出一種PSO與混沌搜索相結(jié)合的混沌PSO；文獻(xiàn)[15]則利用混沌序列確定PSO的參數(shù)(慣性權(quán)值和加速常數(shù))。文獻(xiàn)[9]提出一種不含隨機(jī)參數(shù)、基于確定性混沌Hopfield神經(jīng)網(wǎng)絡(luò)群的粒子群模型。 3）免疫粒子群優(yōu)化：生物免疫系統(tǒng)是一個(gè)高度魯棒性、分布性、自適應(yīng)性并具有強(qiáng)大識別能力、學(xué)習(xí)和記憶能力的非線性系統(tǒng)。文獻(xiàn)[6]將免疫系統(tǒng)的免疫信息處理機(jī)制(抗體多樣性、免疫記憶、免疫自我調(diào)節(jié)等)引入到PSO中，分別提出了基于疫苗接種的免疫PSO和基于免疫記憶的免疫PSO。 4）量子粒子群優(yōu)化：文獻(xiàn)[9]采用量子個(gè)體提出離散PSO；文獻(xiàn)[9]則基于量子行為更新粒子位置。 5）卡爾曼PSO：文獻(xiàn)[9]利用Kalman濾波更新粒子位置。 主成分PSO：文獻(xiàn)[10]結(jié)合主成分分析技術(shù)，粒子不僅按照傳統(tǒng)算法在維的x空間飛行，而且還在維的z空間同步飛行。 對參數(shù)的仿真研究PSO的參數(shù)主要包括最大速度、兩個(gè)加速常數(shù)和慣性常數(shù)或收縮因等。 a) 最大速度的選擇：如式()所示的粒子速度是一個(gè)隨機(jī)變量，由粒子位置更新公式()產(chǎn)生的運(yùn)動(dòng)軌跡是不可控的，使得粒子在問題空間循環(huán)跳動(dòng)[3, 6]。為了抑制這種無規(guī)律的跳動(dòng)，速度往往被限制在內(nèi)。增大，有利于全局探索(global exploration)；減小，則有利于局部開發(fā)(local exploitation)[3]。但是過高，粒子運(yùn)動(dòng)軌跡可能失去規(guī)律性，甚至越過最優(yōu)解所在區(qū)域，導(dǎo)致算法難以收斂而陷入停滯狀態(tài)；相反太小，粒子運(yùn)動(dòng)步長太短，算法可能陷入局部極值[16]。的選擇通常憑經(jīng)驗(yàn)給定，并一般設(shè)定為問題空間的 [3]。此外，文獻(xiàn)[17]提出了的動(dòng)態(tài)調(diào)節(jié)方法以改善算法性能；而文獻(xiàn)[48]提出了自適應(yīng)于群體最佳和最差適應(yīng)度值的選擇方法。b) 加速常數(shù)的選擇：式(1)中的加速常數(shù)和分別用于控制粒子指向自身或鄰域最佳位置的運(yùn)動(dòng)。文獻(xiàn)[20]建議，并通常取。Ratnaweera 等人[13]則提出自適應(yīng)時(shí)變調(diào)整策略。與傳統(tǒng)PSO取正數(shù)加速常數(shù)不同，Riget和Vesterstrom[11]提出一種增加種群多樣性的粒子群算法，根據(jù)群體多樣性指標(biāo)調(diào)整加速常數(shù)的正負(fù)號，動(dòng)態(tài)地改變“吸引”(Attractive)和“擴(kuò)散”(Repulsive)狀態(tài)，以改善算法過早收斂問題。 c) 慣性權(quán)值或收縮因子的選擇：當(dāng)PSO的速度更新公式采用式(1)時(shí)，即使和兩個(gè)加速因子選擇合適，粒子仍然可能飛出問題空間，甚至趨于無窮大，發(fā)生群體“爆炸(explosion)”現(xiàn)象[12]。有兩種方法控制這種現(xiàn)象：慣性常數(shù)(inertia constant)[3]和收縮因子(constriction factor)[12]。帶慣性常數(shù)PSO的速度更新公式如下：