现代优化智能算法-粒子群算法

1、现代优化智能算法-粒子群优化算法PSO算法粒子群优化算法概述 起源 算法提出 算法描述 算法标准流程 经典问题分析 优缺点 应用领域 研究现状算法起源-群智能概念假设你和你的朋友正在寻宝，每个人有个探测器，这个探测器可以知道宝藏到探测器的距离。你们一群人在找，每个人都可以把信息共享出去，就跟打dota时你可以有你队友的视野，你可以知道其他所有人距离宝藏的距离，这样，你看谁离宝藏最近，就向谁靠近，这样会使你发现宝藏的机会变大，而且，这种方法比你单人找要快的多。这是一个群行为(swarm behavior)的简单实例，群中各个体交互作用，使用一个比单一个体更有效的方法求解全局目标。可以把群(swa

2、rm)定义为某种交互作用的组织或Agent之结构集合，在群智能计算研究中，群的个体组织包括蚂蚁，白蚁，蜜蜂，黄蜂，鱼群，鸟群等。在这些群体中，个体在结构上是很简单的，而它们的集体行为却可能变得相当复杂。研究人员发现，蚂蚁在鸟巢和食物之间的运输路线，不管一开始多随机，最后蚂蚁总能找到一条最短路径。算法起源-粒子群优化概念 粒群优化(particle swarm optimization,PSO)算法是一种基于群体搜索的算法，它建立在模拟鸟群社会的基础上。粒群概念的最初含义是通过图形来模拟鸟群优美和不可预测的舞蹈动作，发现鸟群支配同步飞行和以最佳队形突然改变飞行方向并重新编队的能力。这个概念已经被

3、包含在一个简单有效的优化算法中。 在粒群优化中，被称为“粒子”(particle)的个体通过超维搜索空间“流动”。粒子在搜索空间中的位置变化是以个体成功地超过其他个体的社会心理意向为基础的，因此，群中粒子的变化是受其邻近粒子（个体）的经验或知识影响的。一个粒子的搜索行为受到群中其他粒子的搜索行为的影响。由此可见，粒群优化是一种共生合作算法。算法起源-模拟鸟群、鱼群Reynolds、Heppner和Grenader提出鸟群行为的模拟。他们发现，鸟群在行进中会突然同步的改变方向，散开或者聚集等。那么一定有某种潜在的能力或规则保证了这些同步的行为。这些科学家都认为上述行为是基于不可预知的鸟类社会行为

4、中的群体动态学。在这些早期的模型中仅仅依赖个体间距的操作，也就是说，这中同步是鸟群中个体之间努力保持最优的距离的结果。生物社会学家E.O.Wilson对鱼群进行了研究。提出：“至少在理论上，鱼群的个体成员能够受益于群体中其他个体在寻找食物的过程中的发现和以前的经验，这种受益超过了个体之间的竞争所带来的利益消耗，不管任何时候食物资源不可预知的分散。”这说明，同种生物之间信息的社会共享能够带来好处。这是PSO的基础。算法提出 1/2粒子群优化算法（PSO）是一种进化计算技术evolutionary computation）,由Eberhart博士和kennedy博士于1995年提出.源于对鸟群捕食

5、的行为研究。粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解.PSO的优势在于简单容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。算法提出 2/2设想这样一个场景：一群鸟在随机的搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在那。但是它们知道自己当前的位置距离食物还有多远。 那么找到食物的最优策略是什么呢？ 最简单有效的做法就是搜索目前距离食物最近鸟的周围区域。算法描述 1/5 模型抽象： 鸟被抽象为没有质量和体积的微粒(点)，并延伸到N维空间，粒子I 在N维空间的位置表示为矢量Xi(x1，x2

6、，xN)，飞行速度表示为矢量Vi(v1，v2，vN)每个粒子都有一个由目标函数决定的适应值(fitness value)，并且知道自己到目前为止发现的最好位置(pbest)和现在的位置Xi这个可以看作是粒子自己的飞行经验除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest)(gbest是pbest中的最好值)这个可以看作是粒子同伴的经验粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。算法描述 2/5PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个”极值“(pbest,gbest)来更新自己。在找到这两个最优值

7、后，粒子通过下面的公式来更新自己的速度和位置。(1)式 Vi=wVi+c1rand()(pbesti-xi)+c2rand()(gbesti-xi)(2)式 xi=xi+Vi在式(1)、(2)中，i=1,2,3.,M，M是该群体中粒子的总数算法描述 3/5Vi 是粒子的速度；pbest和gbest如前定义；rand()是介于（0、1）之间的随机数；Xi 是粒子的当前位置。c1和c2是学习因子，通常取c1 c22w称惯性因子，w较大适于对解空间进行大范围探查(exploration)，w较小适于进行小范围开挖(exploitation)。在每一维，粒子都有一个最大限制速度Vmax，如果某一维的速

8、度超过设定的Vmax ，那么这一维的速度就被限定为Vmax 。（ Vmax 0）算法描述 4/5从社会学的角度来看，公式(1)的第一部分称为记忆项，表示上次速度大小和方向的影响；公式第二部分称为自身认知项，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的部分；公式的第三部分称为群体认知项，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享。粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。以上面两个公式为基础，形成了后来PSO 的标准形式算法描述 5/5粒子群初始位置和速度随机产生，然后按公式(1)(2)进行迭代，直至找到满意的解。目前，常用的

9、粒子群算法将全体粒子群(Global)分成若干个有部分粒子重叠的相邻子群，每个粒子根据子群(Local)内历史最优Pl调整位置，即公式(1)中gbesti换为pbesti。 算法标准流程标准PSO算法的流程：Step1:初始化一群微粒(群体规模为m)，包括随机位置和速度；Step2:评价每个微粒的适应度；Step3:对每个微粒，将其适应值与其经过的最好位置 pbest作比 较，如果较好，则将其作为当前的最好位置pbest;Step4:对每个微粒，将其适应值与其经过的最好位置gbest作比 较，如果较好，则将其作为当前的最好位置gbest;Step5:根据(2)、(3)式调整微粒速度和位置；St

10、ep6：未达到结束条件则转Step2。根据具体问题一般选为最大迭代次数Gk或(和)微粒群迄今为止搜索到的最优位置满足预定最小适应阈值。经典问题分析-带时间窗车辆路径问题 1/11 时间窗车辆路径问题一般描述为：有一个中心仓库，拥有车K辆，容量分别为qk (k=1,.,K)；现有L个发货点运输任务需要完成，以1,L表示。第i个发货点的货运量为gi (i=1,L)，( max(g)imax(qi) )，完成发货点i任务需要的时间(装贷或卸货)表示为Ti，且任务i且必须在时间窗口ETi , LTi完成，其中ETi为任务i的允许最早开始时间，LTi为任务i的允许最迟开始时间。如果车辆到达发货点i的时间

11、早于ETi，则车辆需在i处等待；如果车辆到达时间晚于LTi，任务i将被延迟进行。求满足货运要求的运行费用最少的车辆行驶线路。经典问题分析-带时间窗车辆路径问题 2/11 时间窗车辆路径问题的数学描述：)8(, 1 , 010)7(, 1 , 0,10)6()()5(, 1 , 0)4(, 1 , 0)3(, 11)2(. .) 1 ()0 ,max()0 ,max(min11；或；或；kLiykLjixSxXkLiyxkLjyxLiykqygtsLTspsETpxczkiijkijkjkiijkikjijkkkiikkiiijkliliiiLiiEijkij经典问题分析-带时间窗车辆路径问题

12、3/11 如何找到一个合适的表达方法，使粒子与解对应，是实现算法的关键问题之一。构造一个2L维的空间对应有L个发货点任务的VRP问题，每个发货点任务对应两维：完成该任务车辆的编号k，该任务在k车行驶路径中的次序r。为表达和计算方便，将每个粒子对应的2L维向量X分成两个L维向量：Xv (表示各任务对应的车辆)和Xr(表示各任务在对应的车辆路径中的执行次序)。经典问题分析-带时间窗车辆路径问题 4/11 例如，设VRP问题中发货点任务数为7，车辆数为3，若某粒子的位置向量X为： 发货点任务号: 1 2 3 4 5 6 7 Xv ： 1 2 2 2 2 3 3 Xr ： 1 4 3 1 2 2 1

13、则该粒子对应解路径为： 车1：0 1 0 车2：0 4 5 3 2 0 车3：0 7 6 0 粒子速度向量V与之对应表示为Vv和Vr经典问题分析-带时间窗车辆路径问题 5/11 该表示方法的最大优点是使每个发货点都得到车辆的配送服务，并限制每个发货点的需求仅能由某一车辆来完成，使解的可行化过程计算大大减少。虽然该表示方法的维数较高，但由于PSO算法在多维寻优问题有着非常好的特性，维数的增加并未增加计算的复杂性，这一点在实验结果中可以看到。经典问题分析-带时间窗车辆路径问题 6/11 VRP问题为整数规划问题，因此在算法实现过程中要作相应修改。具体实现步骤如下： Step1：初始化粒子群。 1.

14、1 粒子群划分成若干个两两相互重叠的相邻子群； 1.2 每个粒子位置向量Xv的每一维随机取1K（车辆数）之间的整数，Xr的每一维随机取1L(发货点任务数)之间的实数； 1.3 每个速度向量Vv的每一维随机取-(K-1)(K-1)（车辆数）之间的整数，Vr的每一维随机取-(L-1)(L-1)之间的实数； 1.4 用评价函数Eval评价所有粒子； 1.5 将初始评价值作为个体历史最优解Pi，并寻找各子群内的最优解Pl和总群体内最优解Pg。经典问题分析-带时间窗车辆路径问题 7/11 Step2：重复执行以下步骤，直到满足终止条件或达到最大迭代次数。 2.1 对每一个粒子，按式(1)计算v、r；按照

15、式(2)计算Xv、Xr，其中Xv向上取整；当、X超过其范围时按边界取值； 2.2 用评价函数Eval评价所有粒子； 2.3 若某个粒子的当前评价值优于其历史最优评价值，则记当前评价值为该历史最优评价值，同时将当前位置向量记为该粒子历史最优位置Pi; 2.4 寻找当前各相邻子群内最优和总群体内最优解，若优于历史最优解则更新Pl 、Pg。对于子群内有多个体同为最优值的情况，则随机取其中一个为子群内当前最优解。 经典问题分析-带时间窗车辆路径问题 8/11 其中，评价函数Eval完成以下任务: 1、根据公式计算该粒子所代表路径方案的行驶成本Z，在计算中发货点任务的执行次序要根据对应Xr值的大小顺序，

16、由小到大执行。 2、将Xr按执行顺序进行重新整数序规范。例如，某粒子迭代一次后结果如下： Xv ： 1 2 2 2 2 3 3 Xr ： 5 3.2 6.2 1.2 2.5 0.5 4.2 则评价后重新规范的Xr是：1 3 4 1 2 1 2 经典问题分析-带时间窗车辆路径问题 9/11实验：采用了无时间窗VRP的例子，问题为一个有7个发货点任务的车辆路径问题，各任务点的坐标及货运量见下表：表1 各发货点坐标及货运量序 号01234567坐 标(18,54)(22,60)(58,69)(71,71)(83,46)(91,38)(24,42)(18,40)货运量(gi)0.890.140.280

17、.330.210.410.57注：序号0表示中心仓库，设车辆容量皆为q=1.0，由3辆车完成所有任务。(最优路径距离为217.81) 经典问题分析-带时间窗车辆路径问题 10/11GA参数：群体规模n=40；交叉概率Pc=0.6；变异概率Pm=0.2；轮盘赌法选择子代，最大代数200。PSO参数：粒子数n=40；分为2个子群，子群规模为22，子群间重叠的粒子数为2个（子群规模的1/10）；w=0.729；c1=c2=1.49445；最大代数200。两种方法各运行50次，结果如下表2所示。表2 实验1 GA、PSO方法结果对比方法达到最优路径次数未达最优路径次数达到最优路径平均代数达到最优路径的

18、平均时间(s)GA321853.932.3PSO50028.363.04经典问题分析-带时间窗车辆路径问题 11/11实验2，采用VRPTW的例子，该问题有8项货物运输任务，货物点位置及时间窗略。实验结果如下：表6 实验2 GA、PSO方法结果对比搜索成功率 平均行驶成本平均成功搜索时间GA24%993.618.41sPSO46%940.58.53s算法优缺点-优点优点：(1)PSO算法没有交叉和变异运算，依靠粒子速度完成搜索，并且在迭代进化中只有最优的粒子把信息传递给其它粒子，搜索速度快；(2)PSO算法具有记忆性，粒子群体的历史最好位置可以记忆并传递给其它粒子；(3)需调整的参数较少，结构简单，易于工程