群集智能介紹

1、2021-10-241背景我們經(jīng)常能夠看到成群的鳥、魚或者浮游生物。這些生物的聚集行為有利于它們覓食和逃避捕食者。它們的群落動輒以十、百、千甚至萬計，并且經(jīng)常不存在一個統(tǒng)一的指揮者。它們是如何完成聚集、移動這些功能呢？2021-10-2422021-10-243群體智能群體智能(Swarm Intelligence)(Swarm Intelligence)2021-10-244研究意義群體智能概念 群體智能這個概念來自對蜜蜂和螞蟻的觀察。一組相互之間可以進行直接通信或者間接通信(通過改變局部環(huán)境)的主體，這組主體能夠合作進行分布問題求解 。 任何啟發(fā)于群居性昆蟲群體和其它動物群體的集體行為而設

2、計的算法和分布式問題解決裝置都稱為群體智能。 群體智能在沒有集中控制并且不提供全局模型的前提下，為尋找復雜的分布式問題的解決方案提供了基礎。 2021-10-245研究意義群體智能的特點 分布式：能夠適應當前網(wǎng)絡環(huán)境下的工作狀態(tài); 魯棒性：沒有中心的控制與數(shù)據(jù)，個體的故障不影響整個問題的求解; 擴充性：個體的增加，系統(tǒng)的通信開銷增加小; 簡單性：個體簡單，實現(xiàn)也比較簡單。 2021-10-246螞蟻尋找最短路徑原理A）蟻群到達決策點。B）一些螞蟻選擇上方路徑，一些螞蟻選擇下方路徑。選擇是隨機的。C）下方短路徑螞蟻到達相反方向的決策點的時間早于選擇上方長路徑的螞蟻。D）短路徑上外激素以較高的速度

3、積累。外激素多的短路徑將吸收更多的螞蟻，反過來，更多的螞蟻在短路徑上會留下更多的外激素，加上外激素揮發(fā)效應，最后，蟻群都選擇了最短路徑。 2021-10-247第k個螞蟻從城市i到城市j 的躍遷概率為：otherwiseallowedjtttpkallowedkikikijijkij0)()()( ij（t）為t時刻邊e(i,j)上外激素的強度可見度ij為1/dij 2021-10-248算法介紹 粒子群優(yōu)化算法（PSO）是一種進化計算技術（evolutionary computation）,由Eberhart博士和kennedy博士于1995年提出 (Kennedy J，Eberhart R

4、 Particle swarm optimizationProceedings of the IEEE International Conference on Neural Networks199519421948.)。源于對鳥群捕食的行為研究。粒子群優(yōu)化算法的基本思想是通過群體中個體之間的協(xié)作和信息共享來尋找最優(yōu)解 2021-10-249算法介紹設想這樣一個場景：一群鳥在隨機的搜索食物。在這個區(qū)域里只有一塊食物，所有的鳥都不知道食物在那。但是它們知道自己當前的位置距離食物還有多遠。那么找到食物的最優(yōu)策略是什么？最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。2021-10-2410算法介紹

5、抽象：鳥被抽象為沒有質(zhì)量和體積的微粒(點)，并延伸到N維空間，粒子I 在N維空間的位置表示為矢量 Xi(x1，x2，xn)，飛行速度表示為矢量Vi(v1，v2，vn),每個粒子都有一個由目標函數(shù)決定的適應值(fitness value)；并且知道自己到目前為止發(fā)現(xiàn)的最好位置(pbest) ；除此之外，每個粒子還知道到目前為止整個群體中所有粒子發(fā)現(xiàn)的最好位置(gbest)(gbest是pbest中的最好值)。粒子怎么樣到達下一步的運動？2021-10-2411粒子群優(yōu)化粒子群優(yōu)化粒子群優(yōu)化粒子群優(yōu)化(Particle Swarm Optimization, PSO)(Particle Swarm

6、 Optimization, PSO)，又稱微粒群算法，又稱微粒群算法，是由是由J. KennedyJ. Kennedy和和RC EberhartRC Eberhart等于等于19951995年開發(fā)的一種演化年開發(fā)的一種演化 機制。機制。 粒子粒子(particle)”(particle)”是一個折衷的選擇是一個折衷的選擇, ,因為既需要因為既需要 將群體中的成員描將群體中的成員描述為沒有質(zhì)量、沒有體積的述為沒有質(zhì)量、沒有體積的, ,同時也需要描述它的速度和加速狀態(tài)。同時也需要描述它的速度和加速狀態(tài)。 Particle Swarm Optimization (PSO) applies to c

7、oncept of Particle Swarm Optimization (PSO) applies to concept of social interaction to problem solving.social interaction to problem solving.It was developed in 1995 by James Kennedy and Russ Eberhart It was developed in 1995 by James Kennedy and Russ Eberhart Kennedy, J. and Eberhart, R. (1995). “

8、Particle Swarm Kennedy, J. and Eberhart, R. (1995). “Particle Swarm Optimization”, Optimization”, Proceedings of the 1995 IEEE International Proceedings of the 1995 IEEE International Conference on Neural NetworksConference on Neural Networks, pp. 1942-1948, IEEE Press. , pp. 1942-1948, IEEE Press.

9、( (/members/payman/swarm/kennedy95-/members/payman/swarm/kennedy95-ijcnn.pdfijcnn.pdf ) ) 2021-10-2412特點 分布式搜尋 具記憶性 組件較少，容易實現(xiàn) 適合在連續(xù)性連續(xù)性的范圍內(nèi)搜尋 2021-10-2413演算法介紹 每個尋優(yōu)的問題解都被想象成一只鳥，我們也稱為“Particle”。 所有的Particle 都有一個fitness function 以判斷目前的位置之好壞， 每一個Particle必須賦予記

10、憶性，能記得所搜尋到最佳位置。 每一個Particle 還有一個速度以決定飛行的距離與方向。 2021-10-2414速度更新(2) (1) )()()21ididididgdididididVxxxpRandcxpRandcVwVpVid：每一Particle在第d維之速度 i：Particle之編號 d：維度pw：Inertia Weightpc1、c2：學習 pRand()：一介于0至1的隨機數(shù)pPid：每一Particle到目前為止，所出現(xiàn)的最佳位置pPgd：所有Particle到目前為止，所出現(xiàn)的最佳位置pxid：每一Particle目前之所在2021-10-2415演算法流程1.

11、1.InitialInitial 將群族做初始化，以隨機的方式求出每一將群族做初始化，以隨機的方式求出每一Particle Particle 之初始位置與速度。之初始位置與速度。2. 2.EvaluationEvaluation： 依據(jù)依據(jù)fitness function fitness function 計算出其計算出其fitness value fitness value 以作為判斷每一以作為判斷每一ParticleParticle之好之好壞。壞。 3. 3.Fine the PbestFine the Pbest： 找出每一找出每一Particle Particle 到目前為止的搜尋過程

12、中最佳解，這個最佳解我們到目前為止的搜尋過程中最佳解，這個最佳解我們將之稱為將之稱為PbestPbest。 4. 4.Fine the GbestFine the Gbest： 找出所有找出所有Particle Particle 到目前為止所搜尋到的整體最佳解，此最佳解我們到目前為止所搜尋到的整體最佳解，此最佳解我們稱之為稱之為GbestGbest。 5. 5.Update the VelocityUpdate the Velocity： 依據(jù)式依據(jù)式(1) (1) 與式與式(2) (2) 更新每一更新每一ParticleParticle之速度與位置。之速度與位置。 6. 6. 回到步驟回到步

13、驟2. 2. 繼續(xù)執(zhí)行，直到獲得一個令人滿意的結(jié)果或符合終止條件繼續(xù)執(zhí)行，直到獲得一個令人滿意的結(jié)果或符合終止條件為止。為止。 2021-10-2416粒子群優(yōu)化粒子群優(yōu)化:Swarm Search Actually, we must adjust the v-vector before adding it to the x-vector as follows: vid = vid + 1*rnd()*(pid-xid) + 2*rnd()*(pgd-xid); xid = xid + vid; Where i is the particle, 1,2 are learning rates g

14、overning the cognition and social components Where g represents the index of the particle with the best p-fitness, and Where d is the dth dimension.2021-10-2417Schwefels function n :1=i 420.9687,= 418.9829;=)( minimum global500500 where)sin()()(1iiniiixnxfxxxxf2021-10-2418搜尋過程最初狀態(tài)2021-10-2419搜尋過程經(jīng)過5代2021-10-2420搜尋過程經(jīng)過10代2021-10-2421搜尋過程經(jīng)過15代2021-10-2422搜尋過程經(jīng)過20代2021-10-2423搜尋過程經(jīng)過25代2021-10-2424搜尋過程經(jīng)過100代2021-10-2425搜尋過程經(jīng)過500代2021-10-2426搜尋結(jié)果移動次數(shù)搜尋結(jié)果0416.2455995515.74879610759.40400615793.73201920834.813763100837.9115355000837.965771最佳解837.9658400450500550600650