【正文】 brium error () Interference (mm) 0 0 0Computation time(s) 648 306 287 Layout Pattern of the global optima and usual local optima of show in Fig 2, if λ1 =1, λ2 =1, λ3 =.Fig 2 Layout Pattern of the global optima and usual local optima To measure the effectiveness and viability of PSO with mutation operator, results are pared with basic local PSO and Multi Start PSO. The max iteration is 1000，size of population is 60, MaxStep=10,ρ=20% and . Results are presented in Table 7, 50 runs for each algorithm. 帶時間窗車輛路徑問題 車輛路徑問題 (Vehicle Routing Problem，VRP)由 Dantzig和 Ramser于 1959年首次提出的，它是指對一系列發(fā)貨點 (或收貨點 )，組成適當(dāng)?shù)男熊嚶窂?，使車輛有序地通過它們，在滿足一定約束條件的情況下，達到一定的目標(biāo) (諸如路程最短、費用最小，耗費時間盡量少等 )，屬于完全 NP問題，在運籌、計算機、物流、管理等學(xué)科均有重要意義。 Else LogjamStep=LogjamStep+1。 ActualErrorAcceptableError If LogjamStep=MaxStep If SwarmRadiusBorderRadius Rerandom the position and velocity of several data of each particles according to mutation probability ρ。另外，非線性系統(tǒng)的穩(wěn)定性只能針對某個解來談的，而不能一般地討論系統(tǒng)的穩(wěn)定性，而且系統(tǒng)的穩(wěn)定性與優(yōu)化算法的收斂性之間存在什么樣的關(guān)系也是未知的，因此如何通過這類方法來分析算法的收斂性和性能是目前是未知的。 基于混沌動力學(xué)理論（續(xù)） 此類分析方法能充分體現(xiàn) PSO系統(tǒng)中粒子間的相互作用的意義和隨機性的價值。 基于混沌動力學(xué)理論 一個好的 PSO系統(tǒng)既非穩(wěn)定態(tài)也非混沌態(tài)，而是一種處于兩者之間臨界態(tài)的自組織復(fù)雜系統(tǒng)。同時也可以看到，要保證算法的收斂，有兩個參數(shù)很重要：一個是過程進入滿意解之后下一步脫離滿意解的可能性；另一個是未進入滿意解時下一步仍不能進入滿意解的可能性。 隨機過程中的其它方法 本文采用了隨機過程中的 Markov鏈方法對PSO算法做分析。 PSO理論分析的其它可能方法 目前，能對 PSO算法進行理論分析的有效數(shù)學(xué)手段還很少，本文了提出的兩個新的分析手段，在微觀上采用差分方程，在宏觀上采用 Markov鏈。本節(jié)研究結(jié)果的意義首先可用于指導(dǎo)算法的改進。v 定理 時， PSO算法是無法保證局部收斂的。 PSO算法 收斂性分析 (續(xù) )v 定理 PSO算法中，對粒子群狀態(tài)序列 而言，最優(yōu)粒子群狀態(tài)集合 G是狀態(tài)空間 S上的一個閉集。PSO算法 收斂性分析 (續(xù) )v 定義 （最優(yōu)粒子狀態(tài)集） 設(shè)優(yōu)化問題 的全局最優(yōu)解為 ，定義粒子最優(yōu)狀態(tài)集 。 v 定理 等價關(guān)系 “~”在 S上誘導(dǎo)的等價類劃分 L=~/S的個數(shù)為： PSO算法 收斂性分析 (續(xù) )v 定理 在數(shù)字計算機實現(xiàn)的標(biāo)準(zhǔn) PSO算法中，粒子群狀態(tài)序列 是有限齊次Markov鏈。定理 “～ ”是 S上的等價關(guān)系。 PSO算法 收斂性分析 (續(xù) )定義 （粒子群等價） 對于 ，記 ，其中 表示事件 A的示性函數(shù)， 表示粒子群狀態(tài)中包含粒子狀態(tài)的數(shù)目。 定義 （粒子群狀態(tài)和粒子群狀態(tài)空間） 粒子群中所有N個粒子的狀態(tài)的集合稱為粒子群狀態(tài)，簡稱粒子群 。條件 H3： 對 ， 為緊集，且 ， 和 ，有：PSO算法 收斂性分析 (續(xù) ) 定理 （算法全局收斂）： 假設(shè) f是可測度的，可行解空間 A是 Rn上可測度的子集，算法 D滿足條件 (H1)(H2)， 是算法 D產(chǎn)生數(shù)列，則有： 定理 （算法局部收斂） ：假設(shè) f是可測度的，可行解空間 A是 Rn上可測度的子集，算法滿足條件 (H1)(H3)， 是算法D產(chǎn)生數(shù)列，則有：PSO算法 收斂性分析 (續(xù) ) 定義 （粒子狀態(tài)和粒子狀態(tài)空間） 粒子的位置 x，速度 v以及歷史最佳位置 p（ pBest）構(gòu)成粒子的狀態(tài)O=(x,v,p)，簡稱粒子，其中 x,p在可行解集 A中，且x,p∈ A,在速度范圍 [vmin,vmax]內(nèi)。算法滿足條件 H2意味著， A中任意滿足 的子集 B，算法 D連續(xù)無窮次未搜索到 A中點的幾率為 0。PSO算法 收斂性分析 (續(xù) )條件 H2： 對 ，有： 。 條件 H1： ，且若 ，則有 。因此，式（ ）和（ ）是有重要價值的，有助于實際應(yīng)用 PSO算法參數(shù)擇和使用的理論公式和條件。針對優(yōu)化問題的特點，通過式（ ）和（ ）可以選擇合理的 PSO參數(shù)，調(diào)整粒子運動軌跡的振蕩幅值使得粒子群的開拓能力和開掘能力均能得到兼顧，從而可提高算法的成功率。式（ ）表明，盡管存在隨機量，但通過選擇和調(diào)節(jié) PSO參數(shù)還是可以對粒子的振蕩幅值實現(xiàn)控制的。是否能通過 PSO參數(shù)的選擇來調(diào)整粒子運動軌跡的振蕩幅值呢？ 粒子運動軌跡的分析（續(xù)）粒子運動軌跡的分析（續(xù)） 若 PSO參數(shù)一直滿足條件（ ） ,則粒子運動軌跡振蕩的幅值是有限的。 粒子運動軌跡的分析（續(xù)） 粒子群中的粒子運動軌跡處于發(fā)散振蕩狀態(tài)顯然是對算法收斂無益的，而處于幅值有限的振蕩狀態(tài)對算法是有非常重要的作用。當(dāng)參數(shù)不滿足式（ ）時，振蕩幅值很大，甚至發(fā)散；滿足式（ ）時，振蕩幅值要小許多，且振蕩的幅值在一定范圍內(nèi)，在某種意義上粒子處于廣義穩(wěn)定狀態(tài)，這樣的狀態(tài)對粒子群的搜索是有益的。一般而言， w越大不收斂的概率越大， c c2越大不收斂的概率越大，其中 w的影響更大些。當(dāng)參數(shù)不滿足式（ ）所給出條件時，絕大多數(shù)粒子的運動軌跡都是不收斂到一個固定點的，除了一些特例，例如粒子群中某個粒子找到全局最優(yōu)解，且當(dāng)前速度為 0，則該粒子運動軌跡肯定收斂。顯然，隨機性的存在使得粒子運動軌跡是否收斂到一個固定點并不完全遵照式（ ）所給出的規(guī)律。粒子運動軌跡的分析（續(xù)） 為便于分析，式（ ）中初始值取 ，并對也取 Z變換可得到： （ ） 不考慮 與 之間存在的弱反饋關(guān)系，式（ ）所對應(yīng)的系統(tǒng)如圖。去掉隨機量后，單個粒子的運動過程成為了一個二階線性系統(tǒng)，使得分析變得比較簡單，但這個便于分析的假設(shè)條件使得以上對粒子運動行為的分析具有很大的局限性。因此當(dāng)搜索時間無限時，所有粒子的位置將逐步靠近并停止于 處。 粒子運動軌跡的分析（續(xù)） 若 f(x)不是 （ NFL定理）中所說的欺騙函數(shù)和隨機函數(shù)，而是第三類函數(shù)，而且 f(pi(t)),f(Pg(t))的變化 pi(t),pg(t)與的變化之間存在著類似梯度信息的規(guī)律。這個系統(tǒng)的輸入的變化過程是未知的，而且與粒子本身的運動過程還存在著弱反饋關(guān)系，那么式（ ）所給出的粒子最終位置是否僅是一種理想狀態(tài)的結(jié)果呢？ 當(dāng) pBest、 gBest發(fā)生變化時，粒子的位置是否能跟蹤上是不肯定的。 粒子運動軌跡的分析（續(xù)） 同理，對（ ）做 Z變換，由 Routh判據(jù)，可得到差分方程（ ）穩(wěn)定的條件為： （ ）粒子運動軌跡的分析（續(xù)） 當(dāng)滿足條件（ ），由 Z變換的終值定理可得： （ ） 這說明，在不考慮隨機量且 pBest、 gBest位置不變的假設(shè)下，當(dāng)滿足式（ ）中條件時，單個粒子的位置將趨向 粒子運動軌跡的分析（續(xù)） 本文以上分析方法所得到的結(jié)果（ ）式與文獻[9]所得的最終結(jié)果（ ）式不一致，圖 兩種不同約束條件所得到的范圍，細(xì)斜線左上方的灰色區(qū)域為本文所得到的單個粒子可收斂區(qū)域，而文獻 [9]中（ ）式所對應(yīng)的僅是粗實線上所有的點，顯然本文約束條件（ ）式所得的范圍比文獻 [9]的范圍大很多，并包含了文獻 [9]的范圍，而文獻 [9]約束條件（ ）式的表達要比式（）復(fù)雜些。 （ ） （ ） 粒子運動軌跡的分析（續(xù)） 將式（ ）和（ ）遞推可得到： （ ） （ ） 由上可知，粒子的速度和位置變化過程均是二階差分方程，本節(jié)將對它們做分析。應(yīng)用。參數(shù)選擇與優(yōu)化；4。算法分析；2。 Particle Swarm研究熱點 IEEE TRANSACTION ON EVOLUTIONARY COMPUTION于 2022年出版了第 3卷： SPECIAL ISSUE ON PSO。 PSO中所隱含的變異是有偏好的，而并非通常的完全隨機變異，這與最近對實際生物系統(tǒng)變異行為的新研究成果相符。 PSO與 EC的異同（續(xù)） 最后， EC的迭代由選擇、變異和交叉重組操作組成，而 PSO的迭代中的操作是 “飛行 ”。 EC中最好的個體通過產(chǎn)生更多的后代來傳播自己的基因，而 PSO中的最佳個體通過吸引其它個體向它靠近來傳播自己的敏因。EC是模擬生物系統(tǒng)進化過程，其最基本單位是基因，它在生物體的每一代之間傳播；而 PSO模擬的是社會系統(tǒng)的變化，其最基本單位是 “敏因 ”（Meme），這一詞由 Dawkin在 《 The Selfish