《智能機(jī)器人創(chuàng)新設(shè)計(jì)》 課件 第12章 多機(jī)器人協(xié)調(diào)調(diào)度-粒子群算法

第12章多機(jī)器人協(xié)同調(diào)度-粒子群算法智慧物流系統(tǒng)：從設(shè)計(jì)到實(shí)現(xiàn)教學(xué)內(nèi)容CONTENTS3粒子群算法-信息迭代2粒子群算法-粒子與粒子群4粒子群算法原理5算法評(píng)價(jià)1粒子群算法起源3

章節(jié)目標(biāo)了解粒子群算法的概念和作用；掌握粒子群算法的生物原理和在計(jì)算機(jī)中的原理。4粒子群算法(ParticleSwarmOptimization，PSO)：1995年，受到鳥(niǎo)群覓食行為的規(guī)律性啟發(fā)，JamesKennedy和RussellEberhart建立了一個(gè)簡(jiǎn)化算法模型，經(jīng)過(guò)多年改進(jìn)最終形成了粒子群優(yōu)化算法(ParticleSwarmOptimization,PSO)，也可稱為粒子群算法或鳥(niǎo)群覓食算法。1粒子群算法起源一群鳥(niǎo)在某一區(qū)域中隨機(jī)地搜尋一塊食物，每只鳥(niǎo)都不知道這塊食物的位置，但知道自身與食物的距離，每只鳥(niǎo)將自身的信息在鳥(niǎo)群中共享。所以要想找到這塊食物，最快的方法就是在距離食物最近的那只鳥(niǎo)的周邊進(jìn)行搜尋。51粒子群算法起源62粒子群算法-粒子與粒子群同遺傳算法類似，粒子群算法中也有一些特別的計(jì)算機(jī)“仿生定義”，其核心可概括為“兩個(gè)對(duì)象兩個(gè)過(guò)程”：對(duì)象指鳥(niǎo)（粒子）和鳥(niǎo)群（粒子群）；過(guò)程指食物搜尋和信息共享。對(duì)象屬性行為粒子（鳥(niǎo)）速度、位置、歷史位置最優(yōu)搜尋（計(jì)算適應(yīng)度）粒子群（鳥(niǎo)群）全局位置最優(yōu)信息共享（迭代）用一串實(shí)數(shù)表示一個(gè)粒子群；用若干串實(shí)數(shù)表示粒子群；7每個(gè)粒子都具有3個(gè)屬性：速度、位置、歷史最優(yōu)位置。屬性符號(hào)描述速度vi當(dāng)前粒子所具有的速度由兩部分組成：由先前速度影響遺留下來(lái)的慣性速度w；若當(dāng)前粒子不是粒子群中最接近目標(biāo)的粒子時(shí)，該粒子有向著最優(yōu)方向移動(dòng)的趨勢(shì)速度。位置xi當(dāng)前粒子所在的位置，用以衡量粒子與目標(biāo)的距離歷史最優(yōu)位置pi當(dāng)前粒子在搜尋目標(biāo)的過(guò)程中，距離目標(biāo)最近時(shí)的位置。粒子在移動(dòng)的過(guò)程中分享當(dāng)前自身的位置，衡量粒子與目標(biāo)的距離，根據(jù)自身的速度調(diào)整移動(dòng)方向，向著最優(yōu)方向移動(dòng)。當(dāng)粒子在移動(dòng)過(guò)程中，自己位于距離目標(biāo)最近的位置時(shí)，不改變方向和速度繼續(xù)移動(dòng)。2粒子群算法-粒子與粒子群8在搜索過(guò)程中，和遺傳算法類似，粒子群算法中也需要定義一個(gè)適應(yīng)度函數(shù)，用以評(píng)估每個(gè)解的優(yōu)異度。在鳥(niǎo)群覓食的過(guò)程中，可以使用粒子（鳥(niǎo)）位置與目標(biāo)（食物的曼哈頓距離作為適應(yīng)度函數(shù)，假設(shè)粒子的坐標(biāo)為(Xparticle，Ypartice)，目標(biāo)點(diǎn)坐標(biāo)為(Xtarget，Ytarget)，粒子坐標(biāo)到目標(biāo)點(diǎn)的適應(yīng)函數(shù)（曼哈頓距離）為：

由上式可知，適應(yīng)度S越接近于1，適應(yīng)度越好，粒子的位置越好。2粒子群算法-粒子與粒子群9適應(yīng)度最大的粒子會(huì)在粒子群中共享自己的位置，使得其他粒子向其靠近。在尋找全局最優(yōu)解的過(guò)程中，粒子群中的粒子需要不斷更新自己的速度和位置，計(jì)算粒子更新的速度，需要用到的參數(shù)：慣性因子w：用來(lái)控制繼承粒子當(dāng)前的速度的因子，越大則對(duì)于當(dāng)前速度的繼承程度越小，越小則對(duì)于當(dāng)前速度的繼承程度越大；當(dāng)前粒子的速度vi：粒子當(dāng)前移動(dòng)的速度；學(xué)習(xí)因子c1、c2：c1粒子的加速因子，c2粒子群的加速因子；粒子歷史最優(yōu)位置pi：當(dāng)前粒子在搜尋目標(biāo)的過(guò)程中，距離目標(biāo)最近時(shí)的位置；當(dāng)前粒子的位置xi:當(dāng)前粒子所在的位置；粒子群的歷史最優(yōu)位置pg：粒子群中當(dāng)前最接近全局最優(yōu)解的粒子的位置；3粒子群算法-信息迭代10更新粒子的速度：

更新粒子的速度：慣性因子w粒子當(dāng)前速度vi粒子加速因子c1[0,1]之間的隨機(jī)數(shù)粒子歷史最佳位置pi粒子當(dāng)前位置xi粒子群加速因子c2粒子群歷史最佳位置pg3粒子群算法-信息迭代11更新粒子的位置：

更新粒子的位置：

結(jié)束迭代：通過(guò)信息的迭代，不斷地更新粒子自身的位置和速度，向食物靠近。當(dāng)粒子和食物的適應(yīng)度(距離越短，適應(yīng)度越高)，距離為0時(shí)，粒子到達(dá)食物的位置，結(jié)束迭代。3粒子群算法-信息迭代124粒子群算法原理粒子群算法需要調(diào)節(jié)的常用參數(shù)：粒子群的規(guī)模m：粒子使用n位的實(shí)數(shù)串構(gòu)成，粒子群是由m個(gè)長(zhǎng)度為n的實(shí)數(shù)串構(gòu)成；慣性因子w：慣性因子越大，全局搜索能力越強(qiáng)，局部搜索能力弱；慣性因子越小，則相反；粒子加速因子c1：代表粒子的個(gè)體認(rèn)知，一般c1

范圍在0和4之間；粒子群加速因子c2：代表粒子的社會(huì)認(rèn)知，一般c2

范圍在0和4之間；最大迭代次數(shù)：根據(jù)經(jīng)驗(yàn)一搬設(shè)為20次；更新粒子的位置和速度體現(xiàn)了粒子群算法的搜索能力，更新粒子的歷史最佳位置和粒子群的歷史最佳位置防止粒子群算法收斂到局部最優(yōu)解。13先設(shè)定一個(gè)粒子群規(guī)模m，即粒子群數(shù)量，再規(guī)定用于表示粒子的實(shí)數(shù)串長(zhǎng)度n；在初始化時(shí)，隨機(jī)生成m個(gè)粒子，即隨機(jī)生成m個(gè)長(zhǎng)度為n的實(shí)數(shù)串；給所有粒子設(shè)置固定或是隨機(jī)的初始速度，也可全部設(shè)置為0；計(jì)算粒子的適應(yīng)度，根據(jù)適應(yīng)度更新粒子的移動(dòng)速度和位置；然后進(jìn)行反復(fù)的搜索和迭代過(guò)程，直到產(chǎn)生最優(yōu)解或者超出最大迭代次數(shù)，結(jié)束迭代；4粒子群算法原理14以下用一個(gè)實(shí)例直觀演示粒子群優(yōu)化算法的迭代過(guò)程。假定目標(biāo)位置坐標(biāo)為(5,5)，即圖中黑色“X”處；設(shè)定慣性系數(shù)w=0.6；設(shè)定學(xué)習(xí)因子c_1=1.2、c_2=1.5。01234567899876543210X(1)初始化粒子群，隨機(jī)生成10個(gè)粒子的位置和初始速度，分布在10*10的范圍內(nèi)，初始速度于區(qū)間[-0.5,0.5]4粒子群算法實(shí)例1501234567899876543210X初代粒子及相關(guān)數(shù)據(jù)：粒子位置xi速度vi歷史最優(yōu)位置pi1[7.902,9.143][-0.158,0.112][7.902,9.143]2[3.793,4.72][-0.211,0.456][3.793,4.72]3[8.505,6.29][0.069,-0.473][8.505,6.29]4[0.3,5.237][0.319,-0.18][0.3,5.237]5[7.438,4.7][0.198,0.343][7.438,4.7]6[0.989,0.697][0.371,-0.476][0.989,0.697]7[0.998,1.706][0.426,0.496][0.998,1.706]8[0.573,6.524][0.353,-0.392][0.573,6.524]9[5.492,0.356][0.427,-0.174][5.492,0.356]10[1.881,3.0][-0.279,0.273][1.881,3.0]4粒子群算法實(shí)例16(2)搜尋最優(yōu)位置：

01230123

4粒子群算法實(shí)例17(2)搜尋最優(yōu)位置：根據(jù)適應(yīng)度函數(shù)，找到距離目標(biāo)點(diǎn)最近的粒子位置pg=[3.793,4.72]。01234567899876543210X粒子位置xi速度vi歷史最優(yōu)位置pi1[7.902,9.143][-0.158,0.112][7.902,9.143]2[3.793,4.72][-0.211,0.456][3.793,4.72]3[8.505,6.29][0.069,-0.473][8.505,6.29]4[0.3,5.237][0.319,-0.18][0.3,5.237]5[7.438,4.7][0.198,0.343][7.438,4.7]6[0.989,0.697][0.371,-0.476][0.989,0.697]7[0.998,1.706][0.426,0.496][0.998,1.706]8[0.573,6.524][0.353,-0.392][0.573,6.524]9[5.492,0.356][0.427,-0.174][5.492,0.356]10[1.881,3.0][-0.279,0.273][1.881,3.0]接下來(lái)，所有粒子向粒子2靠近，繼續(xù)搜尋目標(biāo)點(diǎn)4粒子群算法實(shí)例18(3)信息迭代：利用更新粒子位置、速度的公式進(jìn)行信息迭代。更新所有粒子的位置和速度(以粒子1和粒子2為例)：粒子1：

初代粒子的歷史最佳位置就是粒子的初始位置，因此可以省略更新粒子的歷史最佳位置的步驟。4粒子群算法實(shí)例19(3)信息迭代：利用更新粒子位置、速度的公式進(jìn)行信息迭代。更新所有粒子的位置和速度(以粒子1和粒子2為例)：粒子2：

根據(jù)適應(yīng)度函數(shù)，粒子2為最佳粒子，因此可以省略更新粒子的歷史最佳位置和粒子群的歷史最佳位置兩項(xiàng)步驟。4粒子群算法實(shí)例2001234567899876543210X第一次迭代初代粒子中，粒子2為最佳粒子，所有粒子都快速向粒子2的位置靠近，但因?yàn)槊總€(gè)粒子都還具有不小的速度，因此結(jié)果并沒(méi)有收斂，歷史最佳位置的粒子是紫色點(diǎn)，需要繼續(xù)迭代，更新粒子的位置和速度。01234567899876543210X初代粒子4粒子群算法實(shí)例21第二代粒子，所有粒子的信息，如下：粒子位置xi速度vi歷史最優(yōu)位置pi1[5.163,6.364][-2.739,-2.779][7.902,9.143]2[3.667,4.993][-0.127,0.273][3.793,4.72]3[5.514,4.996][-2.99,-1.294][8.505,6.29]4[2.739,4.796][2.439,-0.441][0.3,5.237]5[5.211,4.918][-2.226,0.218][7.438,4.7]6[3.016,3.0][2.027,2.303][0.989,0.697]7[3.053,3.943][2.055,2.237][0.998,1.706]8[2.857,5.128][2.284,-1.396][0.573,6.524]9[4.655,3.06][-0.837,2.704][5.492,0.356]10[2.944,4.27][1.063,1.271][1.881,3.0]粒子群歷史最佳位置pg[3.743,4.72]最佳距離1.239第二代粒子4粒子群算法實(shí)例2201234567899876543210X第二次迭代第二代粒子01234567899876543210X第二代粒子中，粒子5為最佳粒子，更新所有粒子的位置和速度。所有粒子都快速向粒子5的位置靠近，但是同樣沒(méi)有收斂到目標(biāo)位置，需要繼續(xù)迭代。4粒子群算法實(shí)例23經(jīng)歷20次迭代的結(jié)果，將迭代次數(shù)作為z軸，時(shí)間軸；底部二維坐標(biāo)為設(shè)定的粒子運(yùn)動(dòng)范圍10×10；最終粒子基本都聚集在一點(diǎn)，即結(jié)果收斂在目標(biāo)坐標(biāo)(5,5)。4粒子群算法實(shí)例24任意取其中單個(gè)粒子，其迭代軌跡為：4粒子群算法實(shí)例25(4)調(diào)節(jié)參數(shù)：將慣性系數(shù)從w=0.6改成w=0.2。觀察發(fā)現(xiàn)，將慣性系數(shù)減小后，粒子群迅速收斂，大約在第7代后，粒子群都聚集在

(5,5)處，由此收斂排列成一條直線狀。這樣調(diào)整參數(shù)可以獲得較快的收斂速度，但也容易使得收斂得到的是局部最優(yōu)解，而非全局最優(yōu)。4粒子群算法實(shí)例26PSO算法采用簡(jiǎn)單的速度位移模型，避免了復(fù)雜的遺傳操作，同時(shí)它特有的記憶功能使其可以動(dòng)態(tài)的跟蹤當(dāng)前的搜索情況并及時(shí)調(diào)整搜索策略，具有較強(qiáng)的全局搜索能力和魯棒性。PSO算法有計(jì)算簡(jiǎn)單、易于實(shí)現(xiàn)、控制參數(shù)少的特點(diǎn)。在實(shí)際的多機(jī)器人物流系統(tǒng)中，粒子群算法分配任務(wù)的過(guò)程中，通過(guò)計(jì)算適應(yīng)度來(lái)判斷粒子位置是否為最優(yōu)，在物流機(jī)器人、貨架、取貨點(diǎn)的分配過(guò)程中，將計(jì)算路徑規(guī)劃算法的執(zhí)行時(shí)間(最后一個(gè)機(jī)器人執(zhí)行完成后的時(shí)間)作為分配算法的適應(yīng)度，時(shí)間越短對(duì)應(yīng)路徑就越短，對(duì)應(yīng)路徑越