群智能理論及粒子群優(yōu)化算法SwarmIntelligenceSwarmIntelligence(SI)的概念最早由Beni、Hackwood和在分子自動(dòng)機(jī)系統(tǒng)中提出。分子自動(dòng)機(jī)中的主體在一維或二維網(wǎng)格空間中與相鄰個(gè)體相互作用，從而實(shí)現(xiàn)自組織。1999年，Bonabeau、Dorigo和Theraulaz在他們的著作《SwarmIntelligence:FromNaturaltoArtificialSystems中對(duì)群智能進(jìn)行了詳細(xì)的論述和分析，給出了群智能的一種不嚴(yán)格定義：任何一種由昆蟲群體或其它動(dòng)物社會(huì)行為機(jī)制而激發(fā)設(shè)計(jì)出的算法或分布式解決問題的策略均屬于群智能。SwarmIntelligence(續(xù))Swarm可被描述為一些相互作用相鄰個(gè)體的集合體，蜂群、蟻群、鳥群都是Swarm的典型例子。魚聚集成群可以有效地逃避捕食者，因?yàn)槿魏我恢霍~發(fā)現(xiàn)異常都可帶動(dòng)整個(gè)魚群逃避。螞蟻成群則有利于尋找食物，因?yàn)槿我恢晃浵伆l(fā)現(xiàn)食物都可帶領(lǐng)蟻群來共同搬運(yùn)和進(jìn)食。一只蜜蜂或螞蟻的行為能力非常有限，它幾乎不可能獨(dú)立存在于自然世界中，而多個(gè)蜜蜂或螞蟻形成的Swarm則具有非常強(qiáng)的生存能力，且這種能力不是通過多個(gè)個(gè)體之間能力簡單疊加所獲得的。社會(huì)性動(dòng)物群體所擁有的這種特性能幫助個(gè)體很好地適應(yīng)環(huán)境，個(gè)體所能獲得的信息遠(yuǎn)比它通過自身感覺器官所取得的多，其根本原因在于個(gè)體之間存在著信息交互能力。SwarmIntelligence(續(xù))

信息的交互過程不僅僅在群體內(nèi)傳播了信息，而且群內(nèi)個(gè)體還能處理信息，并根據(jù)所獲得的信息（包括環(huán)境信息和附近其它個(gè)體的信息）改變自身的一些行為模式和規(guī)范，這樣就使得群體涌現(xiàn)出一些單個(gè)個(gè)體所不具備的能力和特性，尤其是對(duì)環(huán)境的適應(yīng)能力。這種對(duì)環(huán)境變化所具有適應(yīng)的能力可以被認(rèn)為是一種智能（關(guān)于適應(yīng)性與智能之間的關(guān)系存在著一些爭議，F(xiàn)ogel認(rèn)為智能就是具備適應(yīng)的能力），也就是說動(dòng)物個(gè)體通過聚集成群而涌現(xiàn)出了智能。因此，Bonabeau將SI的定義進(jìn)一步推廣為：無智能或簡單智能的主體通過任何形式的聚集協(xié)同而表現(xiàn)出智能行為的特性。這里我們關(guān)心的不是個(gè)體之間的競爭，而是它們之間的協(xié)同。SwarmIntelligence(續(xù))JamesKennedy和RussellC.Eberhart在2001年出版了《SwarmIntelligence》，是群智能發(fā)展的一個(gè)重要?dú)v程碑，因?yàn)榇藭r(shí)已有一些群智能理論和方法得到了應(yīng)用。他們不反對(duì)Bonabeau關(guān)于SI定義，贊同其定義的基本精神，但反對(duì)定義中使用“主體”一詞。其理由是“主體”所帶有自治性和特殊性是許多Swarm的個(gè)體所不具備和擁有的，這將大大限制Swarm的定義范圍。他們認(rèn)為暫時(shí)無法給出合適的定義，贊同由MarkMillonas（1994）提出的構(gòu)建一個(gè)SI系統(tǒng)所應(yīng)滿足的五條基本原則：SwarmIntelligence(續(xù))[1]ProximityPrinciple:群內(nèi)個(gè)體具有能執(zhí)行簡單的時(shí)間或空間上的評(píng)估和計(jì)算的能力。[2]QualityPrinciple:群內(nèi)個(gè)體能對(duì)環(huán)境（包括群內(nèi)其它個(gè)體）的關(guān)鍵性因素的變化做出響應(yīng)。[3]PrincipleofDiverseResponse:群內(nèi)不同個(gè)體對(duì)環(huán)境中的某一變化所表現(xiàn)出的響應(yīng)行為具有多樣性。[4]StabilityPrinciple:不是每次環(huán)境的變化都會(huì)導(dǎo)致整個(gè)群體的行為模式的改變。[5]AdaptabilityPrinciple:環(huán)境所發(fā)生的變化中，若出現(xiàn)群體值得付出代價(jià)的改變機(jī)遇，群體必須能夠改變其行為模式。SwarmIntelligence(續(xù))《SwarmIntelligence》最重要的觀點(diǎn)是：Mindissocial，也就是認(rèn)為人的智能是源于社會(huì)性的相互作用，文化和認(rèn)知是人類社會(huì)性不可分割的重要部分，這一觀點(diǎn)成為了群智能發(fā)展的基石。群智能已成為有別于傳統(tǒng)人工智能中連接主義和符號(hào)主義的一種新的關(guān)于智能的描述方法。群智能的思路，為在沒有集中控制且不提供全局模型的前提下尋找復(fù)雜的分布式問題求解方案提供了基礎(chǔ)。在計(jì)算智能領(lǐng)域已取得成功的兩種基于SI的優(yōu)化算法是蟻群算法和粒子群算法。SwarmIntelligence(續(xù))

目前，已有的基于SI的優(yōu)化算法都是源于對(duì)動(dòng)物社會(huì)通過協(xié)作解決問題行為的模擬，它主要強(qiáng)調(diào)對(duì)社會(huì)系統(tǒng)中個(gè)體之間相互協(xié)同作用的模擬。這一點(diǎn)與EC不同，EC是對(duì)生物演化中適者生存的模擬。與EC一樣的是，SI的目的并不是為了忠實(shí)地模擬自然現(xiàn)象，而是利用他們的某些特點(diǎn)去解決實(shí)際問題。另一個(gè)與EC的相同點(diǎn)是,基于SI的優(yōu)化算法也是概率搜索算法。SwarmIntelligence(續(xù))

目前，已有的群智能理論和應(yīng)用研究證明群智能方法是一種能夠有效解決大多數(shù)優(yōu)化問題的新方法，更重要是,群智能潛在的并行性和分布式特點(diǎn)為處理大量的以數(shù)據(jù)庫形式存在的數(shù)據(jù)提供了技術(shù)保證。無論是從理論研究還是應(yīng)用研究的角度分析,群智能理論及應(yīng)用研究都是具有重要學(xué)術(shù)意義和現(xiàn)實(shí)價(jià)值的。SwarmIntelligence(續(xù))

由于SI的理論依據(jù)是源于對(duì)生物群落社會(huì)性的模擬，因此其相關(guān)數(shù)學(xué)分析還比較薄弱，這就導(dǎo)致了現(xiàn)有研究還存在一些問題。首先，群智能算法的數(shù)學(xué)理論基礎(chǔ)相對(duì)薄弱，缺乏具備普遍意義的理論性分析，算法中涉及的各種參數(shù)設(shè)置一直沒有確切的理論依據(jù)，通常都是按照經(jīng)驗(yàn)型方法確定，對(duì)具體問題和應(yīng)用環(huán)境的依賴性比較大。其次，同其它的自適應(yīng)問題處理方法一樣，群智能也不具備絕對(duì)的可信性，當(dāng)處理突發(fā)事件時(shí),系統(tǒng)的反應(yīng)可能是不可測的,這在一定程度上增加了其應(yīng)用風(fēng)險(xiǎn)。另外,群智能與其它各種先進(jìn)技術(shù)(如:神經(jīng)網(wǎng)絡(luò)、模糊邏輯、禁忌搜索和支持向量機(jī)等)的融合還不足。蟻群算法

蟻群算法（AntColonyOptimization,ACO）由Colorni，Dorigo和Maniezzo在1991年提出，它是通過模擬自然界螞蟻社會(huì)的尋找食物的方式而得出的一種仿生優(yōu)化算法。自然界種蟻群尋找食物時(shí)會(huì)派出一些螞蟻分頭在四周游蕩，如果一只螞蟻找到食物，它就返回巢中通知同伴并沿途留下“信息素”（pheromone）作為蟻群前往食物所在地的標(biāo)記。信息素會(huì)逐漸揮發(fā)，如果兩只螞蟻同時(shí)找到同一食物，又采取不同路線回到巢中，那么比較繞彎的一條路上信息素的氣味會(huì)比較淡，蟻群將傾向于沿另一條更近的路線前往食物所在地。優(yōu)化問題簡介基本PSO算法

粒子群優(yōu)化算法源于1987年Reynolds對(duì)鳥群社會(huì)系統(tǒng)boids的仿真研究，boids是一個(gè)CAS。在boids中，一群鳥在空中飛行，每個(gè)鳥遵守以下三條規(guī)則：1）避免與相鄰的鳥發(fā)生碰撞沖突；2）盡量與自己周圍的鳥在速度上保持協(xié)調(diào)和一致；3）盡量試圖向自己所認(rèn)為的群體中靠近。僅通過使用這三條規(guī)則，boids系統(tǒng)就出現(xiàn)非常逼真的群體聚集行為，鳥成群地在空中飛行，當(dāng)遇到障礙時(shí)它們會(huì)分開繞行而過，隨后又會(huì)重新形成群體。基本PSO算法（續(xù)）Reynolds僅僅將其作為CAS的一個(gè)實(shí)例作仿真研究，而并未將它用于優(yōu)化計(jì)算中。

Kennedy和Eberhart在中加入了一個(gè)特定點(diǎn)，定義為食物，鳥根據(jù)周圍鳥的覓食行為來尋找食物。他們的初衷是希望通過這種模型來模擬鳥群尋找食源的現(xiàn)象，然而實(shí)驗(yàn)結(jié)果卻揭示這個(gè)仿真模型中蘊(yùn)涵著很強(qiáng)的優(yōu)化能力，尤其是在多維空間尋優(yōu)中。基本PSO算法(續(xù))PSO中，每個(gè)優(yōu)化問題的解都是搜索空間中的一只鳥。稱之為“粒子(Particle)”。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適應(yīng)值，每個(gè)粒子還有一個(gè)速度決定他們飛翔的方向和距離。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索.PSO初始化為一群隨機(jī)粒子。然后通過疊代找到最優(yōu)解。在每一次疊代中，粒子通過跟蹤兩個(gè)"極值"來更新自己。第一個(gè)就是粒子本身所找到的最優(yōu)解。這個(gè)解叫做個(gè)體極值pBest.另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解。這個(gè)極值是全局極值gBest。另外,也可以不用整個(gè)種群而只是用其中一部分的鄰居。基本PSO算法(續(xù))PSO算法數(shù)學(xué)表示如下：設(shè)搜索空間為D維，總粒子數(shù)為n。第i個(gè)粒子位置表示為向量Xi=(xi1,xi2,…,xiD

)；第i個(gè)粒子“飛行”歷史中的過去最優(yōu)位置（即該位置對(duì)應(yīng)解最優(yōu)）為Pi=(pi1,pi2,…,piD)，其中第g個(gè)粒子的過去最優(yōu)位置Pg為所有Pi(i=1,…,n)中的最優(yōu)；第i個(gè)粒子的位置變化率（速度）為向量Vi=(vi1,vi2,…,viD)。每個(gè)粒子的位置按如下公式進(jìn)行變化（“飛行”）：基本PSO算法(續(xù))（1）（2）其中，C1,C2為正常數(shù)，稱為加速因子；rand()為[0，1]之間的隨機(jī)數(shù)；w稱慣性因子，w較大適于對(duì)解空間進(jìn)行大范圍探查(exploration)，w較小適于進(jìn)行小范圍開挖(exploitation)。第d（1≤d≤D）維的位置變化范圍為[-XMAXd,XMAXd]，速度變化范圍為[-VMAXd,VMAXd]，迭代中若位置和速度超過邊界范圍則取邊界值。基本PSO算法(續(xù))

粒子群初始位置和速度隨機(jī)產(chǎn)生，然后按公式(1)(2)進(jìn)行迭代，直至找到滿意的解。目前，常用的粒子群算法將全體粒子群(Global)分成若干個(gè)有部分粒子重疊的相鄰子群，每個(gè)粒子根據(jù)子群(Local)內(nèi)歷史最優(yōu)Pl調(diào)整位置，即公式(2)中Pgd換為Pld。PSO與EC的異同

首先，PSO和EC所模擬的自然隨機(jī)系統(tǒng)不一樣。EC是模擬生物系統(tǒng)進(jìn)化過程，其最基本單位是基因，它在生物體的每一代之間傳播；而PSO模擬的是社會(huì)系統(tǒng)的變化，其最基本單位是“敏因”（Meme），這一詞由Dawkin在《TheSelfishGene》一書中提出，它是指思想文化傳播中的基本單位，個(gè)體在社會(huì)中會(huì)根據(jù)環(huán)境來改變自身的思想，Meme的傳播途徑是在個(gè)體與個(gè)體之間，在實(shí)際人類社會(huì)中它還可以在人腦與書本之間、人腦與計(jì)算機(jī)、計(jì)算機(jī)與計(jì)算機(jī)之間傳播。PSO與EC的異同（續(xù)）

其次，EC中強(qiáng)調(diào)“適者生存”，不好的個(gè)體在競爭中被淘汰；PSO強(qiáng)調(diào)“協(xié)同合作”，不好的個(gè)體通過學(xué)習(xí)向好的方向轉(zhuǎn)變，不好的個(gè)體被保留還可以增強(qiáng)群體的多樣性。EC中最好的個(gè)體通過產(chǎn)生更多的后代來傳播自己的基因，而PSO中的最佳個(gè)體通過吸引其它個(gè)體向它靠近來傳播自己的敏因。PSO與EC的異同（續(xù)）

再次，EC中的上一代到下一代轉(zhuǎn)移概率只與上一代的狀態(tài)相關(guān)，而與歷史無關(guān)，它的個(gè)體只包含當(dāng)前信息，其群體的信息變化過程是一個(gè)Markov鏈過程；而PSO中的個(gè)體除了有著位置和速度外，還有著過去的歷史信息（pBest、gBest），也就是具有記憶能力，上一代到下一代轉(zhuǎn)移概率不僅與上一代的狀態(tài)相關(guān)，而且與過去的歷史相關(guān)，如果僅從群體的位置及速度信息來看，群體的信息變化過程不是一個(gè)Markov鏈過程。PSO與EC的異同（續(xù)）

最后，EC的迭代由選擇、變異和交叉重組操作組成，而PSO的迭代中的操作是“飛行”。在某種程度上看，PSO的操作中隱含了選擇、變異和交叉重組操作，gBest和pBest的更新可以類似一種弱選擇；而粒子位置更新則類似于3個(gè)父代：Xi、gBest和pBest的之間重組，其中還包含了變異的成分。PSO中所隱含的變異是有偏好的，而并非通常的完全隨機(jī)變異，這與最近對(duì)實(shí)際生物系統(tǒng)變異行為的新研究成果相符。PSO與EC的異同（續(xù)）EC和PSO所分別模擬的兩個(gè)偉大的自然隨機(jī)系統(tǒng)：Evolution和Mind之間存在著顯著的差異，盡管它們都是基于群體的，都是由其中的隨機(jī)成分帶來創(chuàng)新，但其本質(zhì)是不同的，因此不能將PSO簡單地歸類于EC中。ParticleSwarm研究熱點(diǎn)IEEETRANSACTIONONEVOLUTIONARYCOMPUTION于2004年出版了第3卷：SPECIALISSUEONPSO。RussellC.Eberhart,YuhuiShi在卷首語中指出了當(dāng)前PSO研究的幾個(gè)主要方向及熱點(diǎn)：1。算法分析；2。粒子群拓?fù)浣Y(jié)構(gòu)；3。參數(shù)選擇與優(yōu)化；4。與其他演化計(jì)算的融合；5。應(yīng)用。simulation1

xyfitnessminmaxse