《智能机器人创新设计》 课件 第12章 多机器人协调调度-粒子群算法

第12章多机器人协同调度-粒子群算法智慧物流系统：从设计到实现教学内容CONTENTS3粒子群算法-信息迭代2粒子群算法-粒子与粒子群4粒子群算法原理5算法评价1粒子群算法起源3

章节目标了解粒子群算法的概念和作用；掌握粒子群算法的生物原理和在计算机中的原理。4粒子群算法(ParticleSwarmOptimization，PSO)：1995年，受到鸟群觅食行为的规律性启发，JamesKennedy和RussellEberhart建立了一个简化算法模型，经过多年改进最终形成了粒子群优化算法(ParticleSwarmOptimization,PSO)，也可称为粒子群算法或鸟群觅食算法。1粒子群算法起源一群鸟在某一区域中随机地搜寻一块食物，每只鸟都不知道这块食物的位置，但知道自身与食物的距离，每只鸟将自身的信息在鸟群中共享。所以要想找到这块食物，最快的方法就是在距离食物最近的那只鸟的周边进行搜寻。51粒子群算法起源62粒子群算法-粒子与粒子群同遗传算法类似，粒子群算法中也有一些特别的计算机“仿生定义”，其核心可概括为“两个对象两个过程”：对象指鸟（粒子）和鸟群（粒子群）；过程指食物搜寻和信息共享。对象属性行为粒子（鸟）速度、位置、历史位置最优搜寻（计算适应度）粒子群（鸟群）全局位置最优信息共享（迭代）用一串实数表示一个粒子群；用若干串实数表示粒子群；7每个粒子都具有3个属性：速度、位置、历史最优位置。属性符号描述速度vi当前粒子所具有的速度由两部分组成：由先前速度影响遗留下来的惯性速度w；若当前粒子不是粒子群中最接近目标的粒子时，该粒子有向着最优方向移动的趋势速度。位置xi当前粒子所在的位置，用以衡量粒子与目标的距离历史最优位置pi当前粒子在搜寻目标的过程中，距离目标最近时的位置。粒子在移动的过程中分享当前自身的位置，衡量粒子与目标的距离，根据自身的速度调整移动方向，向着最优方向移动。当粒子在移动过程中，自己位于距离目标最近的位置时，不改变方向和速度继续移动。2粒子群算法-粒子与粒子群8在搜索过程中，和遗传算法类似，粒子群算法中也需要定义一个适应度函数，用以评估每个解的优异度。在鸟群觅食的过程中，可以使用粒子（鸟）位置与目标（食物的曼哈顿距离作为适应度函数，假设粒子的坐标为(Xparticle，Ypartice)，目标点坐标为(Xtarget，Ytarget)，粒子坐标到目标点的适应函数（曼哈顿距离）为：

由上式可知，适应度S越接近于1，适应度越好，粒子的位置越好。2粒子群算法-粒子与粒子群9适应度最大的粒子会在粒子群中共享自己的位置，使得其他粒子向其靠近。在寻找全局最优解的过程中，粒子群中的粒子需要不断更新自己的速度和位置，计算粒子更新的速度，需要用到的参数：惯性因子w：用来控制继承粒子当前的速度的因子，越大则对于当前速度的继承程度越小，越小则对于当前速度的继承程度越大；当前粒子的速度vi：粒子当前移动的速度；学习因子c1、c2：c1粒子的加速因子，c2粒子群的加速因子；粒子历史最优位置pi：当前粒子在搜寻目标的过程中，距离目标最近时的位置；当前粒子的位置xi:当前粒子所在的位置；粒子群的历史最优位置pg：粒子群中当前最接近全局最优解的粒子的位置；3粒子群算法-信息迭代10更新粒子的速度：

更新粒子的速度：惯性因子w粒子当前速度vi粒子加速因子c1[0,1]之间的随机数粒子历史最佳位置pi粒子当前位置xi粒子群加速因子c2粒子群历史最佳位置pg3粒子群算法-信息迭代11更新粒子的位置：

更新粒子的位置：

结束迭代：通过信息的迭代，不断地更新粒子自身的位置和速度，向食物靠近。当粒子和食物的适应度(距离越短，适应度越高)，距离为0时，粒子到达食物的位置，结束迭代。3粒子群算法-信息迭代124粒子群算法原理粒子群算法需要调节的常用参数：粒子群的规模m：粒子使用n位的实数串构成，粒子群是由m个长度为n的实数串构成；惯性因子w：惯性因子越大，全局搜索能力越强，局部搜索能力弱；惯性因子越小，则相反；粒子加速因子c1：代表粒子的个体认知，一般c1

范围在0和4之间；粒子群加速因子c2：代表粒子的社会认知，一般c2

范围在0和4之间；最大迭代次数：根据经验一搬设为20次；更新粒子的位置和速度体现了粒子群算法的搜索能力，更新粒子的历史最佳位置和粒子群的历史最佳位置防止粒子群算法收敛到局部最优解。13先设定一个粒子群规模m，即粒子群数量，再规定用于表示粒子的实数串长度n；在初始化时，随机生成m个粒子，即随机生成m个长度为n的实数串；给所有粒子设置固定或是随机的初始速度，也可全部设置为0；计算粒子的适应度，根据适应度更新粒子的移动速度和位置；然后进行反复的搜索和迭代过程，直到产生最优解或者超出最大迭代次数，结束迭代；4粒子群算法原理14以下用一个实例直观演示粒子群优化算法的迭代过程。假定目标位置坐标为(5,5)，即图中黑色“X”处；设定惯性系数w=0.6；设定学习因子c_1=1.2、c_2=1.5。01234567899876543210X(1)初始化粒子群，随机生成10个粒子的位置和初始速度，分布在10*10的范围内，初始速度于区间[-0.5,0.5]4粒子群算法实例1501234567899876543210X初代粒子及相关数据：粒子位置xi速度vi历史最优位置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粒子群算法实例16(2)搜寻最优位置：

01230123

4粒子群算法实例17(2)搜寻最优位置：根据适应度函数，找到距离目标点最近的粒子位置pg=[3.793,4.72]。01234567899876543210X粒子位置xi速度vi历史最优位置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]接下来，所有粒子向粒子2靠近，继续搜寻目标点4粒子群算法实例18(3)信息迭代：利用更新粒子位置、速度的公式进行信息迭代。更新所有粒子的位置和速度(以粒子1和粒子2为例)：粒子1：

初代粒子的历史最佳位置就是粒子的初始位置，因此可以省略更新粒子的历史最佳位置的步骤。4粒子群算法实例19(3)信息迭代：利用更新粒子位置、速度的公式进行信息迭代。更新所有粒子的位置和速度(以粒子1和粒子2为例)：粒子2：

根据适应度函数，粒子2为最佳粒子，因此可以省略更新粒子的历史最佳位置和粒子群的历史最佳位置两项步骤。4粒子群算法实例2001234567899876543210X第一次迭代初代粒子中，粒子2为最佳粒子，所有粒子都快速向粒子2的位置靠近，但因为每个粒子都还具有不小的速度，因此结果并没有收敛，历史最佳位置的粒子是紫色点，需要继续迭代，更新粒子的位置和速度。01234567899876543210X初代粒子4粒子群算法实例21第二代粒子，所有粒子的信息，如下：粒子位置xi速度vi历史最优位置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粒子群算法实例2201234567899876543210X第二次迭代第二代粒子01234567899876543210X第二代粒子中，粒子5为最佳粒子，更新所有粒子的位置和速度。所有粒子都快速向粒子5的位置靠近，但是同样没有收敛到目标位置，需要继续迭代。4粒子群算法实例23经历20次迭代的结果，将迭代次数作为z轴，时间轴；底部二维坐标为设定的粒子运动范围10×10；最终粒子基本都聚集在一点，即结果收敛在目标坐标(5,5)。4粒子群算法实例24任意取其中单个粒子，其迭代轨迹为：4粒子群算法实例25(4)调节参数：将惯性系数从w=0.6改成w=0.2。观察发现，将惯性系数减小后，粒子群迅速收敛，大约在第7代后，粒子群都聚集在

(5,5)处，由此收敛排列成一条直线状。这样调整参数可以获得较快的收敛速度，但也容易使得收敛得到的是局部最优解，而非全局最优。4粒子群算法实例26PSO算法采用简单的速度位移模型，避免了复杂的遗传操作，同时它特有的记忆功能使其可以动态的跟踪当前的搜索情况并及时调整搜索策略，具有较强的全局搜索能力和鲁棒性。PSO算法有计算简单、易于实现、控制参数少的特点。在实际的多机器人物流系统中，粒子群算法分配任务的过程中，通过计算适应度来判断粒子位置是否为最优，在物流机器人、货架、取货点的分配过程中，将计算路径规划算法的执行时间(最后一个机器人执行完成后的时间)作为分配算法的适应度，时间越短对应路径就越短，对应路径越