【正文】 gence(續(xù) ) 由于 SI的理論依據(jù)是源于對(duì)生物群落社會(huì)性的模擬，因此其相關(guān)數(shù)學(xué)分析還比較薄弱，這就導(dǎo)致了現(xiàn)有研究還存在一些問(wèn)題。 蟻群算法 蟻群算法（ Ant Colony Optimization, ACO）由Colorni， Dorigo和 Maniezzo在 1991年提出，它是通過(guò)模擬自然界螞蟻社會(huì)的尋找食物的方式而得出的一種仿生優(yōu)化算法。根據(jù) “信息素較濃的路線更近 ”的原則，即可選擇出最佳路線。 蟻群算法 (續(xù) )其它群智能優(yōu)化算法 目前，還有一些不成熟的群智能優(yōu)化算法，國(guó)內(nèi)值得關(guān)注的有以下幾種。每個(gè)神經(jīng)元被看成一個(gè)主體，主體之間的通訊連接看成各神經(jīng)元之間的連接，但連接是隨機(jī)而不是固定的，即用一個(gè)隨機(jī)連接的神經(jīng)網(wǎng)絡(luò)來(lái)描述一個(gè)群體，這種神經(jīng)網(wǎng)絡(luò)來(lái)描述一個(gè)群體。同遺傳算法類(lèi)似，也是一種基于群體疊代的，但并沒(méi)有遺傳算法用的交叉以及變異，而是粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索。整個(gè)系統(tǒng)的演變或進(jìn)化，包括新層次的產(chǎn)生，分化和多樣性的出現(xiàn)，新的、聚合而成的、更大的主體的出現(xiàn)等等，都是在這個(gè)基礎(chǔ)上出現(xiàn)的。 我們現(xiàn)在關(guān)注的是第二部分的內(nèi)容。在boids中，一群鳥(niǎo)在空中飛行，每個(gè)鳥(niǎo)遵守以下三條規(guī)則：1）避免與相鄰的鳥(niǎo)發(fā)生碰撞沖突；2）盡量與自己周?chē)镍B(niǎo)在速度上保持協(xié)調(diào)和一致；3）盡量試圖向自己所認(rèn)為的群體中靠近。他們的初衷是希望通過(guò)這種模型來(lái)模擬鳥(niǎo)群尋找食源的現(xiàn)象，然而實(shí)驗(yàn)結(jié)果卻揭示這個(gè)仿真模型中蘊(yùn)涵著很強(qiáng)的優(yōu)化能力，尤其是在多維空間尋優(yōu)中。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索 . PSO 初始化為一群隨機(jī) 粒子。這個(gè)解叫做個(gè)體極值 pBest. 另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解。第 i個(gè)粒子位置表示為向量 Xi=( xi1, xi2,…, x iD )；第 i個(gè)粒子 “飛行 ”歷史中的過(guò)去最優(yōu)位置（即該位置對(duì)應(yīng)解最優(yōu)）為 Pi=( pi1,pi2,…,p iD )，其中第 g個(gè)粒子的過(guò)去最優(yōu)位置 Pg為所有 Pi ( i=1, …,n )中的最優(yōu)；第 i個(gè)粒子的位置變化率（速度）為向量 Vi=(vi1, vi2,…, v iD)。目前，常用的粒子群算法將全體粒子群(Global)分成若干個(gè)有部分粒子重疊的相鄰子群，每個(gè)粒子根據(jù)子群 (Local)內(nèi)歷史最優(yōu) Pl調(diào)整位置，即公式 (2)中 Pgd換為 Pld。 EC中最好的個(gè)體通過(guò)產(chǎn)生更多的后代來(lái)傳播自己的基因，而 PSO中的最佳個(gè)體通過(guò)吸引其它個(gè)體向它靠近來(lái)傳播自己的敏因。 PSO中所隱含的變異是有偏好的，而并非通常的完全隨機(jī)變異，這與最近對(duì)實(shí)際生物系統(tǒng)變異行為的新研究成果相符。算法分析；2。應(yīng)用。 粒子運(yùn)動(dòng)軌跡的分析（續(xù)） 同理，對(duì)（ ）做 Z變換，由 Routh判據(jù)，可得到差分方程（ ）穩(wěn)定的條件為： （ ）粒子運(yùn)動(dòng)軌跡的分析（續(xù)） 當(dāng)滿足條件（ ），由 Z變換的終值定理可得： （ ） 這說(shuō)明，在不考慮隨機(jī)量且 pBest、 gBest位置不變的假設(shè)下，當(dāng)滿足式（ ）中條件時(shí)，單個(gè)粒子的位置將趨向 粒子運(yùn)動(dòng)軌跡的分析（續(xù)） 本文以上分析方法所得到的結(jié)果（ ）式與文獻(xiàn)[9]所得的最終結(jié)果（ ）式不一致，圖 兩種不同約束條件所得到的范圍，細(xì)斜線左上方的灰色區(qū)域?yàn)楸疚乃玫降膯蝹€(gè)粒子可收斂區(qū)域，而文獻(xiàn) [9]中（ ）式所對(duì)應(yīng)的僅是粗實(shí)線上所有的點(diǎn)，顯然本文約束條件（ ）式所得的范圍比文獻(xiàn) [9]的范圍大很多，并包含了文獻(xiàn) [9]的范圍，而文獻(xiàn) [9]約束條件（ ）式的表達(dá)要比式（）復(fù)雜些。 粒子運(yùn)動(dòng)軌跡的分析（續(xù)） 若 f(x)不是 （ NFL定理）中所說(shuō)的欺騙函數(shù)和隨機(jī)函數(shù)，而是第三類(lèi)函數(shù)，而且 f(pi(t)),f(Pg(t))的變化 pi(t),pg(t)與的變化之間存在著類(lèi)似梯度信息的規(guī)律。去掉隨機(jī)量后，單個(gè)粒子的運(yùn)動(dòng)過(guò)程成為了一個(gè)二階線性系統(tǒng)，使得分析變得比較簡(jiǎn)單，但這個(gè)便于分析的假設(shè)條件使得以上對(duì)粒子運(yùn)動(dòng)行為的分析具有很大的局限性。顯然，隨機(jī)性的存在使得粒子運(yùn)動(dòng)軌跡是否收斂到一個(gè)固定點(diǎn)并不完全遵照式（ ）所給出的規(guī)律。一般而言， w越大不收斂的概率越大， c c2越大不收斂的概率越大，其中 w的影響更大些。 粒子運(yùn)動(dòng)軌跡的分析（續(xù)） 粒子群中的粒子運(yùn)動(dòng)軌跡處于發(fā)散振蕩狀態(tài)顯然是對(duì)算法收斂無(wú)益的，而處于幅值有限的振蕩狀態(tài)對(duì)算法是有非常重要的作用。式（ ）表明，盡管存在隨機(jī)量，但通過(guò)選擇和調(diào)節(jié) PSO參數(shù)還是可以對(duì)粒子的振蕩幅值實(shí)現(xiàn)控制的。因此，式（ ）和（ ）是有重要價(jià)值的，有助于實(shí)際應(yīng)用 PSO算法參數(shù)擇和使用的理論公式和條件。PSO算法 收斂性分析 (續(xù) )條件 H2： 對(duì) ，有： 。條件 H3： 對(duì) ， 為緊集，且 ， 和 ，有：PSO算法 收斂性分析 (續(xù) ) 定理 （算法全局收斂）： 假設(shè) f是可測(cè)度的，可行解空間 A是 Rn上可測(cè)度的子集，算法 D滿足條件 (H1)(H2)， 是算法 D產(chǎn)生數(shù)列，則有： 定理 （算法局部收斂） ：假設(shè) f是可測(cè)度的，可行解空間 A是 Rn上可測(cè)度的子集，算法滿足條件 (H1)(H3)， 是算法D產(chǎn)生數(shù)列，則有：PSO算法 收斂性分析 (續(xù) ) 定義 （粒子狀態(tài)和粒子狀態(tài)空間） 粒子的位置 x，速度 v以及歷史最佳位置 p（ pBest）構(gòu)成粒子的狀態(tài)O=(x,v,p)，簡(jiǎn)稱粒子，其中 x,p在可行解集 A中，且x,p∈ A,在速度范圍 [vmin,vmax]內(nèi)。 PSO算法 收斂性分析 (續(xù) )定義 （粒子群等價(jià)） 對(duì)于 ，記 ，其中 表示事件 A的示性函數(shù)， 表示粒子群狀態(tài)中包含粒子狀態(tài)的數(shù)目。 v 定理 等價(jià)關(guān)系 “~”在 S上誘導(dǎo)的等價(jià)類(lèi)劃分 L=~/S的個(gè)數(shù)為： PSO算法 收斂性分析 (續(xù) )v 定理 在數(shù)字計(jì)算機(jī)實(shí)現(xiàn)的標(biāo)準(zhǔn) PSO算法中，粒子群狀態(tài)序列 是有限齊次Markov鏈。 PSO算法 收斂性分析 (續(xù) )v 定理 PSO算法中，對(duì)粒子群狀態(tài)序列 而言，最優(yōu)粒子群狀態(tài)集合 G是狀態(tài)空間 S上的一個(gè)閉集。本節(jié)研究結(jié)果的意義首先可用于指導(dǎo)算法的改進(jìn)。 隨機(jī)過(guò)程中的其它方法 本文采用了隨機(jī)過(guò)程中的 Markov鏈方法對(duì)PSO算法做分析。 基于混沌動(dòng)力學(xué)理論 一個(gè)好的 PSO系統(tǒng)既非穩(wěn)定態(tài)也非混沌態(tài)，而是一種處于兩者之間臨界態(tài)的自組織復(fù)雜系統(tǒng)。另外，非線性系統(tǒng)的穩(wěn)定性只能針對(duì)某個(gè)解來(lái)談的，而不能一般地討論系統(tǒng)的穩(wěn)定性，而且系統(tǒng)的穩(wěn)定性與優(yōu)化算法的收斂性之間存在什么樣的關(guān)系也是未知的，因此如何通過(guò)這類(lèi)方法來(lái)分析算法的收斂性和性能是目前是未知的。 Else LogjamStep=LogjamStep+1。由于在現(xiàn)實(shí)生活中許多問(wèn)題都可以歸結(jié)為 VRPTW問(wèn)題來(lái)處理 (如郵政投遞、火車(chē)及公共汽車(chē)的調(diào)度等 )，其處理的好壞將直接影響到企業(yè)的服務(wù)質(zhì)量 ,所以對(duì)它的研究越來(lái)越受到人們的重視。如果車(chē)輛到達(dá)發(fā)貨點(diǎn) i的時(shí)間早于 ETi，則車(chē)輛需在 i處等待；如果車(chē)輛到達(dá)時(shí)間晚于 LTi，任務(wù) i將被延遲進(jìn)行。 帶時(shí)間窗車(chē)輛路徑問(wèn)題（續(xù)） 如何找到一個(gè)合適的表達(dá)方法，使粒子與解對(duì)應(yīng)，是實(shí)現(xiàn)算法的關(guān)鍵問(wèn)題之一。 該表示方法的最大優(yōu)點(diǎn)是使每個(gè)發(fā)貨點(diǎn)都得到車(chē)輛的配送服務(wù)，并限制每個(gè)發(fā)貨點(diǎn)的需求僅能由某一車(chē)輛來(lái)完成，使解的可行化過(guò)程計(jì)算大大減少。 粒子群劃分成若干個(gè)兩兩相互重疊的相鄰子群； 每個(gè)粒子位置向量 Xv的每一維隨機(jī)取 1～ K（車(chē)輛數(shù)）之間的整數(shù)， Xr的每一維隨機(jī)取 1～ L(發(fā)貨點(diǎn)任務(wù)數(shù) )之間的實(shí)數(shù)； 每個(gè)速度向量 Vv的每一維隨機(jī)取 (K1)～ (K1)（車(chē)輛數(shù)）之間的整數(shù)， Vr的每一維隨機(jī)取 (L1)～ (L1)之間的實(shí)數(shù)； 用評(píng)價(jià)函數(shù) Eval評(píng)價(jià)所有粒子； 將初始評(píng)價(jià)值作為個(gè)體歷史最優(yōu)解 Pi，并尋找各子群內(nèi)的最優(yōu)解 Pl和總?cè)后w內(nèi)最優(yōu)解 Pg。對(duì)于子群內(nèi)有多個(gè)體同為最優(yōu)值的情況，則隨機(jī)取其中一個(gè)為子群內(nèi)當(dāng)前最優(yōu)解。 (最 優(yōu) 路徑距離 為 ) GA參數(shù)：群體規(guī)模 n=40；交叉概率 Pc=；變異概率 Pm=；輪盤(pán)賭法選擇子代，最大代數(shù) 200。實(shí)驗(yàn)結(jié)果如下： 表 6 實(shí)驗(yàn) 2 GA、 PSO方法 結(jié) 果 對(duì) 比搜索成功率 平均行 駛 成本 平均成功搜索 時(shí)間GA 24% PSO 46% Evolving Neural Networksv Evolve neural work capable of being universal approximator, such as backpropagation or radial basis function work.v In backpropagation, most mon PE transfer function is sigmoidal function: output = 1/(1 + e input )v PSO can also be used to indirectly evolve the structure of a work. An added benefit is that the preprocessing of input data is made unnecessary.Evolving Neural Networksv Evolve both the work weights and the slopes of sigmoidal transfer functions of hidden and output PEs.v If transfer function now is: output = 1/(1 + e k*input ) then we are evolving k in addition to evolving the weights.v The method is general, and can be applied to other topologies and other transfer functions.v Flexibility is gained by allowing slopes to be positive or negative. A change in sign for the slope is equivalent to a change in signs of all input weights.Evolving Neural Networksv If evolved slope is sufficiently small, sigmoidal output can be clamped to , and hidden PE can be removed. Weights from bias PE to each PE in next layer are increased by onehalf the value of the weight from the PE being removed to the nextlayer PE. PEs are thus pruned, reducing work plexity.v If evolved slope is suffi