讲座：粒子群算法介绍研究

第3章粒子群优化算法SwarmIntelligenceSwarmIntelligence(SI)的概念最早由Beni、Hackwood和在分子自动机系统中提出。分子自动机中的主体在一维或二维网格空间中与相邻个体相互作用，从而实现自组织。1999年，Bonabeau、Dorigo和Theraulaz在他们的著作《SwarmIntelligence:FromNaturaltoArtificialSystems中对群智能进行了详细的论述和分析，给出了群智能的一种不严格定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。粒子群算法(particleswarmoptimization，PSO)由Kennedy和Eberhart在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于SwarmIntelligence的优化方法。同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。PSO的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。PSO算法简介PSO产生背景之一：复杂适应系统CAS理论的最基本的思想可以概述如下：我们把系统中的成员称为具有适应性的主体(AdaptiveAgent)，简称为主体。所谓具有适应性，就是指它能够与环境以及其它主体进行交流，在这种交流的过程中“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行为方式。整个系统的演变或进化，包括新层次的产生，分化和多样性的出现，新的、聚合而成的、更大的主体的出现等等，都是在这个基础上出现的。复杂适应系统（CAS）续CAS的四个基本特点：首先，主体(AdaptiveAgent)是主动的、活的实体；其次，个体与环境(包括个体之间)的相互影响，相互作用，是系统演变和进化的主要动力；再次，这种方法不象许多其他的方法那样，把宏观和微观截然分开，而是把它们有机地联系起来；最后，这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。基本PSO算法粒子群优化算法源于1987年Reynolds对鸟群社会系统boids的仿真研究，boids是一个CAS。在boids中，一群鸟在空中飞行，每个鸟遵守以下三条规则：1）避免与相邻的鸟发生碰撞冲突；2）尽量与自己周围的鸟在速度上保持协调和一致；3）尽量试图向自己所认为的群体中靠近。仅通过使用这三条规则，boids系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体。基本PSO算法（续）Reynolds仅仅将其作为CAS的一个实例作仿真研究，而并未将它用于优化计算中。Kennedy和Eberhart在中加入了一个特定点，定义为食物，鸟根据周围鸟的觅食行为来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群寻找食源的现象，然而实验结果却揭示这个仿真模型中蕴涵着很强的优化能力，尤其是在多维空间寻优中。基本PSO算法(续)PSO中，每个优化问题的解都是搜索空间中的一只鸟。称之为“粒子(Particle)”。所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索.PSO初始化为一群随机粒子。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest.另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外,也可以不用整个种群而只是用其中一部分的邻居。基本PSO算法(续)PSO算法数学表示如下：设搜索空间为D维，总粒子数为n。第i个粒子位置表示为向量Xi=(xi1,xi2,…,xiD)；第i个粒子“飞行”历史中的过去最优位置（即该位置对应解最优）为Pi=(pi1,pi2,…,piD)，其中第g个粒子的过去最优位置Pg为所有Pi(i=1,…,n)中的最优；第i个粒子的位置变化率（速度）为向量Vi=(vi1,vi2,…,viD)。每个粒子的位置按如下公式进行变化（“飞行”）：基本PSO算法(续)12(1)()()[()()]()[()()]ididididgdidvtwvtcrandptxtcrandptxt(1)()(1)11idididxtxtvtindD（1）（2）其中，C1,C2为正常数，称为加速因子；rand()为[0，1]之间的随机数；w称惯性因子，w较大适于对解空间进行大范围探查(exploration)，w较小适于进行小范围开挖(exploitation)。第d（1≤d≤D）维的位置变化范围为[-XMAXd,XMAXd]，速度变化范围为[-VMAXd,VMAXd]，迭代中若位置和速度超过边界范围则取边界值。基本PSO算法(续)粒子群初始位置和速度随机产生，然后按公式(1)(2)进行迭代，直至找到满意的解。目前，常用的粒子群算法将全体粒子群(Global)分成若干个有部分粒子重叠的相邻子群，每个粒子根据子群(Local)内历史最优Pl调整位置，即公式(2)中Pgd换为Pld。带时间窗车辆路径问题车辆路径问题(VehicleRoutingProblem，VRP)由Dantzig和Ramser于1959年首次提出的，它是指对一系列发货点(或收货点)，组成适当的行车路径，使车辆有序地通过它们，在满足一定约束条件的情况下，达到一定的目标(诸如路程最短、费用最小，耗费时间尽量少等)，属于完全NP问题，在运筹、计算机、物流、管理等学科均有重要意义。带时间窗车辆路径问题（续）带时间窗的车辆路径问题(VehicleRoutingProblemWithTimeWindows,VRPTW)是在VRP问题上加了客户要求访问的时间窗口。由于在现实生活中许多问题都可以归结为VRPTW问题来处理(如邮政投递、火车及公共汽车的调度等)，其处理的好坏将直接影响到企业的服务质量,所以对它的研究越来越受到人们的重视。先后出现了一般启发式算法和神经网络、遗传算法、禁忌搜索和模拟退火等智能化启发式算法，也取得了一些较好的效果。带时间窗车辆路径问题（续）时间窗车辆路径问题一般描述为：有一个中心仓库，拥有车K辆，容量分别为qk(k=1,..,K)；现有L个发货点运输任务需要完成，以1,…,L表示。第i个发货点的货运量为gi(i=1,…,L)，(max(g)i≤max(qi))，完成发货点i任务需要的时间(装贷或卸货)表示为Ti，且任务i且必须在时间窗口[ETi,LTi]完成，其中ETi为任务i的允许最早开始时间，LTi为任务i的允许最迟开始时间。如果车辆到达发货点i的时间早于ETi，则车辆需在i处等待；如果车辆到达时间晚于LTi，任务i将被延迟进行。求满足货运要求的运行费用最少的车辆行驶线路。)8(,,1,010)7(,,1,0,10)6()()5(,,1,0)4(,,1,0)3(,,11)2(..)1()0,max()0,max(min11；　或；　或；　；　　　　　kLiykLjixSxXkLiyxkLjyxLiykqygtsLTspsETpxczkiijkijkjkiijkikjijkkkiikkiiijkliliiiLiiEijkij时间窗车辆路径问题的数学描述：带时间窗车辆路径问题（续）这个模型通用性很强，经过参数的不同设定，可以将其转换为其他组合优化问题的数学模型。若(1)中ETi=0,LTi→∞，则VRPTW模型就变成了普通的VRP模型；若仅有一个车辆被利用，则该问题就变成了TSP问题；若去掉约束(2)，则变成了m－TSPTW问题。带时间窗车辆路径问题（续）如何找到一个合适的表达方法，使粒子与解对应，是实现算法的关键问题之一。构造一个2L维的空间对应有L个发货点任务的VRP问题，每个发货点任务对应两维：完成该任务车辆的编号k，该任务在k车行驶路径中的次序r。为表达和计算方便，将每个粒子对应的2L维向量X分成两个L维向量：Xv(表示各任务对应的车辆)和Xr(表示各任务在对应的车辆路径中的执行次序)。例如，设VRP问题中发货点任务数为7，车辆数为3，若某粒子的位置向量X为：发货点任务号:1234567Xv：1222233Xr：1431221则该粒子对应解路径为：车1：010车2：045320车3：0760粒子速度向量V与之对应表示为Vv和Vr。该表示方法的最大优点是使每个发货点都得到车辆的配送服务，并限制每个发货点的需求仅能由某一车辆来完成，使解的可行化过程计算大大减少。虽然该表示方法的维数较高，但由于PSO算法在多维寻优问题有着非常好的特性，维数的增加并未增加计算的复杂性，这一点在实验结果中可以看到。VRP问题为整数规划问题，因此在算法实现过程中要作相应修改。具体实现步骤如下：Step1：初始化粒子群。1.1粒子群划分成若干个两两相互重叠的相邻子群；1.2每个粒子位置向量Xv的每一维随机取1～K（车辆数）之间的整数，Xr的每一维随机取1～L(发货点任务数)之间的实数；1.3每个速度向量Vv的每一维随机取-(K-1)～(K-1)（车辆数）之间的整数，Vr的每一维随机取-(L-1)～(L-1)之间的实数；1.4用评价函数Eval评价所有粒子；1.5将初始评价值作为个体历史最优解Pi，并寻找各子群内的最优解Pl和总群体内最优解Pg。Step2：重复执行以下步骤，直到满足终止条件或达到最大迭代次数。2.1对每一个粒子，按式(1)计算Ｖv、Ｖr；按照式(2)计算Xv、Xr，其中Xv向上取整；当Ｖ、X超过其范围时按边界取值；2.2用评价函数Eval评价所有粒子；2.3若某个粒子的当前评价值优于其历史最优评价值，则记当前评价值为该历史最优评价值，同时将当前位置向量记为该粒子历史最优位置Pi;2.4寻找当前各相邻子群内最优和总群体内最优解，若优于历史最优解则更新Pl、Pg。对于子群内有多个体同为最优值的情况，则随机取其中一个为子群内当前最优解。其中，评价函数Eval完成以下任务:1、根据公式计算该粒子所代表路径方案的行驶成本Z，在计算中发货点任务的执行次序要根据对应Xr值的大小顺序，由小到大执行。2、将Xr按执行顺序进行重新整数序规范。例如，某粒子迭代一次后结果如下：Xv：1222233Xr：53.26.21.22.50.54.2则评价后重新规范的Xr是：1341212实验１：采用了无时间窗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.330.210.410.57注：序号0表示中心仓库，设车辆容量皆为q=1.0，由3辆车完成所有任务。(最优路径距离为217.81)GA参数：群体规模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实验1GA、PSO方法结果对比方法达到最优路径次数未达最优路径次数达到最优路径平均代数达到最优路径的平均时间(s)GA321853.932.3PSO50028.363.04实验2，采用VRPTW的例子，该问题有8项货物运输任务，货物点位置及时间窗略。实验结果如下：表6实验2GA、PSO方法结果对比搜索成功率平均行驶成本平均成功搜索时间GA24%993