生物社會(huì)學(xué)家對(duì)鳥(niǎo)群尋找食物行為的研究

1、NTU GICE Lab507Introduction to Particle Swarm Optimization(PSO)Group MeetingJen-chian Chen02/26 2009NTU GICE Lab507OutlineoParticle Swarm Optimization (PSO) TutorialoBasic Principle of PSOoExampleoFuture workParticle Swarm Optimisation.簡(jiǎn)介簡(jiǎn)介o起源n生物社會(huì)學(xué)家對(duì)鳥(niǎo)群尋找食物行為的研究o原理n我們可以設(shè)想這樣的一個(gè)場(chǎng)景，一群鳥(niǎo)再隨機(jī)搜尋食物。這個(gè)區(qū)域裡只有一塊

2、食物。所有的鳥(niǎo)都不知道食物再哪裡，但他們知道目前距離食物還有多遠(yuǎn)，那麼找到食物的最佳策略是什麼？最簡(jiǎn)單的方法就是找尋距離食物最近的鳥(niǎo)距離食物最近的鳥(niǎo)之周圍區(qū)域及根據(jù)自己本身飛行的經(jīng)驗(yàn)飛行的經(jīng)驗(yàn)判斷食物的所在。oJames Kennedy, Russell Eberhart (1995)鳥(niǎo)群的覓食行為鳥(niǎo)群的覓食行為FoodGlobal Best SolutionPast Best SolutionFig.1 Concept of modification of a searching point by PSOsk : current searching point. sk+1: modified

3、 searching point. vk: current velocity. vk+1: modified velocity. vpbest : velocity based on pbest. vgbest : velocity based on gbestskvkvpbestvgbestsk+1vk+1skvkvpbestvgbestsk+1vk+1Particle Swarm Optimization (PSO)xy特點(diǎn)特點(diǎn)o分散式搜尋o具記憶性o元件較少，容易實(shí)現(xiàn)o適合在連續(xù)性連續(xù)性的範(fàn)圍內(nèi)搜尋特點(diǎn)特點(diǎn)o分散式搜尋o具記憶性o元件較少，容易實(shí)現(xiàn)o適合在連續(xù)性連續(xù)性的範(fàn)圍內(nèi)搜尋演算法介

4、紹演算法介紹 o每個(gè)尋優(yōu)的問(wèn)題解都被想像成一隻鳥(niǎo)，我們也稱為“Particle”。o所有的Particle 都有一個(gè)fitness function 以判斷目前的位置之好壞，o每一個(gè)Particle必須賦予記憶性，能記得所搜尋到最佳位置。o每一個(gè)Particle 還有一個(gè)速度以決定飛行的距離與方向。演算法流程演算法流程1.1.InitialInitial：將群族做初始化，以隨機(jī)的方式求出每一Particle 之初始位置與速度。2.2.EvaluationEvaluation：依據(jù)fitness function 計(jì)算出其fitness value 以作為判斷每一Particle之好壞。3.3.

5、Fine the PbestFine the Pbest：找出每一Particle 到目前為止的搜尋過(guò)程中最佳解，這個(gè)最佳解我們將之稱為Pbest。4.4.Fine the GbestFine the Gbest：找出所有Particle 到目前為止所搜尋到的整體最佳解，此最佳解我們稱之為Gbest。5.5.Update the VelocityUpdate the Velocity：依據(jù)式(1) 與式(2) 更新每一Particle之速度與位置。6.回到步驟2. 繼續(xù)執(zhí)行，直到獲得一個(gè)令人滿意的結(jié)果或符合終止條件為止。NTU GICE Lab507速度更新速度更新(2) (1) )()()2

6、1ididididgdididididVxxxpRandcxpRandcVwVpVid：每一Particle在第d維之速度i：Particle之編號(hào) d：維度pw：Inertia Weightpc1、c2：學(xué)習(xí)常數(shù) pRand()：一介於0至1的亂數(shù)pPid：每一Particle到目前為止，所出現(xiàn)的最佳位置pPgd：所有Particle到目前為止，所出現(xiàn)的最佳位置pxid：每一Particle目前之所在Example: Schwefels function n :1=i 420.9687,= 418.9829;=)( minimum global500500 where)sin()()(1ii

7、niiixnxfxxxxf搜尋過(guò)程最初狀態(tài)搜尋過(guò)程最初狀態(tài)搜尋過(guò)程經(jīng)過(guò)搜尋過(guò)程經(jīng)過(guò)5 5代代搜尋過(guò)程經(jīng)過(guò)搜尋過(guò)程經(jīng)過(guò)1010代代搜尋過(guò)程經(jīng)過(guò)搜尋過(guò)程經(jīng)過(guò)1515代代搜尋過(guò)程經(jīng)過(guò)搜尋過(guò)程經(jīng)過(guò)2020代代搜尋過(guò)程經(jīng)過(guò)搜尋過(guò)程經(jīng)過(guò)2525代代搜尋過(guò)程經(jīng)過(guò)搜尋過(guò)程經(jīng)過(guò)100100代代搜尋過(guò)程經(jīng)過(guò)搜尋過(guò)程經(jīng)過(guò)500500代代搜尋結(jié)果搜尋結(jié)果移動(dòng)次數(shù)搜尋結(jié)果0416.2455995515.74879610759.40400615793.73201920834.813763100837.9115355000837.965771最佳解837.9658400450500550600650700750800850

8、14166425610244096sample.datFuture workoFor RSS based localization, we need a transformation to remove redundancy of information before fingerprinting the position.oEg: Y=H*X Y is a RSS-Vector H is a transformation matrixoUsing PSO to optimize the transformation and search for the best matrix.oBut what is the evaluation function(fitness function)?NTU GICE Lab507ReferenceoKennedy, J., Eberhart, R., 1995, Particle Swarm Optimizatio