离散粒子群算法在车辆路径问题中的应用
计算机科学与技术学院
毕业设计(论文)
论文题目离散粒子群算法在车辆路径问题中的应用
指导教师职称讲师
学生姓名学号
专业班级
系主任院长
起止时间2013年10月11日至2014年5月23日
2014年5月23日
目录
摘要 (i)
Abstract. (ii)
第一章绪论 (1)
1.1 课题背景 (1)
1.2 课题意义 (1)
1.3 国内外研究现状 (2)
1.3.1国外的研究现状 (2)
1.3.2国外的研究现状 (3)
1.4 论文的结构 (4)
第二章离散粒子群算法 (6)
2.1粒子群优化算法 (6)
2.1.1算法介绍 (6)
2.1.2 算法原理 (6)
2.1.3 算法流程 (8)
2.1.4 本节小结 (9)
2.2 离散粒子群算法 (10)
2.2.1 算法引入 (10)
2.2.2 算法原理 (11)
2.2.3 算法应用 (12)
2.2.4 本节小结 (15)
第三章车辆路径问题分析 (16)
3.1 物流配送 (16)
3.2 车辆路径问题的概述 (17)
3.3 车辆路径问题的分析 (17)
3.3.1 VRP的研究要素 (18)
3.3.2 VRP的优化目标 (18)
3.3.3 VRP的实现算法 (19)
3.4 本章小结 (19)
第四章车辆路径问题的建模与实现 (21)
4.1 车辆路径问题的建模 (21)
4.2 算法实现 (21)
4.3 实现代码 (22)
4.4 演示结果 (25)
4.5 DPSO算法与其他算法的比较 (25)
4.5.1 DPSO算法与免疫算法的比较 (25)
4.5.2 DPSO算法与最小生成树的比较 (28)
4.5.3 DPSO算法与遗传算法的比较 (28)
4.6 本章小结 (29)
第五章结论和展望 (30)
参考文献 (31)
谢辞 (34)
离散粒子群算法在车辆路径问题中的应用
摘要：在这个高速发展的经济社会，各行各业对科学技术的革新的要求愈发的强烈，同时对人们的日常生活产生愈来愈广的影响。其中物流企业也逐渐凸显期重要性，然而物流配送则是物流企业日常生产中一个最为重要的环节，物流配送效率的高低直接将会影响到整个物流企业的运作效益，同时对于电子商务活动物流配送也必不可少。
物流配送中亟待解决的问题是怎样得到一条费用最小的车辆路径并将货物配送给每个客户，即车辆路径问题(VRP)[33]。优化车辆路径问题(VRP)则需要优化配送速度、服务质量、配送成本等决定性因素，因此在这些问题中涉及到多种多样优化方案。应用离散粒子群算法(DPSO)[22]这种群体智能算法能更好更快地解决这些多样化的问题，该算法以快速收敛性而获取最佳是通过模拟鸟群觅食得到的。
应用于车辆路径问题中的离散粒子群算法同时也克服了其他算法的不足和缺点，离散粒子群算法编码比较简单克服遗传算法实现的复杂性，并且该算法具有一般的特性，适用于绝大多数的目标优化问题。粒子依据自身和群体经验进行优化更新，具有记忆和学习能力，克服其他算法的众多参数的问题。因此离散粒子群算法适合应用在车辆路径问题。
关键词：粒子群算法、离散粒子群算法、车辆路径问题、物流配送、路径优化问题、免疫算法
Discrete Particle Swarm Optimization for Vehicle
Routing Problem
Abstract: In this high-speed economic and social development, science and technology sectors of innovation requires increasingly strong, while producing increasingly broad impact on people's daily lives. Which of logistics enterprises have gradually highlights the importance is the logistics and distribution logistics companies daily production one of the most important aspects, however the level will directly affect the efficiency of logistics and distribution to the operational efficiency of the entire logistics enterprises, but for e-commerce logistics and distribution also essential.
Logistics and distribution problems to be solved is how to get a minimum cost of vehicle routing and distribution of goods to each customer, namely vehicle routing problem (VRP). Optimizing vehicle routing problem (VRP) is required to optimize the speed of delivery, quality of service, distribution costs and other decisive factors, involved in these issues to a wide variety optimization. Discrete Particle Swarm Optimization (PSO) algorithm which swarm intelligence to better address these diverse problems faster, rapid convergence of the algorithm is to acquire the best is obtained by simulating the foraging birds.
Applied to the vehicle routing problem discrete particle swarm algorithm also overcomes the deficiencies and shortcomings of other algorithms, discrete particle swarm algorithm coded genetic algorithm is relatively simple to overcome the complexity and the algorithm has the general characteristics for the vast majority of objective optimization problem. And groups of particles based on their own experience to optimize the update, with memory and learning ability, to overcome the problems of many other parameters of the algorithm. Therefore discrete particle swarm algorithm suitable for applications in vehicle routing problem.
Keywords:Particle Swarm Optimization; Discrete Particle Swarm Optimization; Vehicle Routing Problem; Logistics Problem; Path Optimization Problem
第一章绪论
1.1 课题背景
根据中国入世承诺，使得物流行业和服务行业成为中国最早的开放的行业其中之一。从而在经济全球化的趋势下，我国的经济得到了迅猛的发展，在高水平经济的平台上科学技术同时也得到了进步。因此物流产业也得到了发展并成为了国家经济发展中一个重要的行业，同时在全球飞速发展延伸，成为象征一个国家综合国力的标志之一,并在我国开始慢慢成为国家经济的基础产业和主力军。
对于物流产业而言，物流配送是其中重要的环节，然而在这个环节中车辆路径的选择则会起着关键性的作用。现实生活的交通中，对于车辆的行驶会有着各种的影响因素，比如天气的变化、突发的交通事故、交通流量等等各种的非主观的因素，因此配送的时间也会相应的被改变，于是研究在诸多的不确定的因素下得出一条最优的或者最优的路径是非常具有意义的。
该问题自1959年被首先提出，到现在目前已经有将近五十多年的的研究历史，它已经是组合优化问题领域和运筹学研究的热点和重点。在互联网和电子商务发展的带动下，物流产业得到了飞速的发展，VRP问题模型已经建立在现实生活和生产的各个方面，比如水运的船舶、公共汽车、火车和飞机等的调度问题以及邮政投递的问题，还有电力的调度问题也同样能抽象为车辆路径问题。简而言之，深入对车辆路径问题的研究，很具有工程和科学的应用价值。
1.2 课题意义
随着物流产业的发展，产业中同时也产生了诸多的问题引人注目，其中运输配送的成本占物流配送总成本中的60%，所以对于物流行业最急需解决的问题便是运输配送的成本的问题。然而影响运输配送的成本的最主要的问题便是车辆路径问题(VRP)，以现代的物流产业的发展的重要性可见的车辆路径问题的显著，因此成功地合理地规划处理车辆路径问题会带来可喜可赞的经济的效益和科学
的效益。车辆路径问题(VRP)属于一个NP难题，离散粒子算法能较好的解决这一类问题，特别地适合于应用在处理那些复杂的和线性的传统的搜索方法却又很难以解决的疑难问题上，PSO算法（粒子群优化算法）[1]可以提高配送中的物流配送的效率质量等关键问题。
应用于车辆路径问题中离散粒子群算法同时也克服了其他算法的不足和缺点，离散粒子群算法编码比较简单克服遗传算法实现的复杂性，并且该算法具有一般的特性，适用于绝大多数的目标优化问题。粒子依据自身和群体经验进行优化更新，具有记忆和学习能力，克服其他算法的众多参数的问题，因此离散粒子群算法适合应用在车辆路径问题。
1.3 国内外研究现状
1.3.1国外的研究现状
1959年的时候有学者Dantzig与Ramser二人第一次提出了车辆问题(Vechicle Routing Problem，VRP)[33],当时提出该问题的背景是运输汽油，然后给出了出数学模型和求解的具体方法。到目前为止已经提出了很多的只能算法和启发式算法应用在辆路径问题中,从提出到现在VRP的研究经过了近50年的发展，在此过程中已经出现众多的模型和求解算法。从提出的改进版的模拟的退火算法到动态的蚁群算法再到改进的粒子群算法等算法来解决车辆路径问题。由于研究重点的不同模型存在不同的方式。
标准的车辆路径问题其实是指带装载限制的车辆路径问题(Capacitatied VRP，CVRP)，其他的各类型的问题都是从此问题延伸展开。一个典型的VRP 的基本特征包括：目标、派送点、用户点、道路和车辆。同时VRP也可以如此分类：
在研究目标方面，可以最小化总的运输成本；可以将顾客的等待时间最小化；可以最小化行驶的路程和将服务的效率最大化等。
在限定的条件方面，单一的配送点；多个配送点；带有时间窗口的和没有时间窗口的；开放型的和封闭型的；单一车型配送的和多个车型配送的等。
按任务的性质，有确定信息的和不确定的；需求的动态性和静态性等等。
随着生活和生产不断地在进步和发展，为了满足这其中的各种的需求，车辆
路径问题(VRP)需要不断地进行扩展和完善。通过调整标准的VRP的不同的建设条件，从而来扩宽VRP的研究。当前最普遍的车辆路径问题是带有时间窗的静态车辆问题，世界各国的研究学者通过对基本的VRP的研究得出了基本的模型，使用得出的基本的模型做出各种类型的题库，比如Fisher题库等。
将不同的扩宽元素再与标准的VRP相结合,然后可以构造出不同的车辆路径问题,比如：有能力约束的VRP(CVR)、有时间窗的约束的VRP(VRPTW)、带取送货的VRP(VRPPD)、周期性的VRP(PVRP)、分散配送VRP(SDVRI)和带回程载货的VRP(VRPB)等[3-16]。
同时针对不同的主要的约束条件，针对不同实际公司和企业中的不通风情况又能衍生出一些衍生模型：多仓库型的车辆路径问题(MVRP)、多车型的车辆路径问题（HVRP)、随机的车辆路径问题(SVRP）、模糊的车辆路径问题(FVRP)。总结得出VRP扩展问题及关系图如图1.1所示。
标准的车辆路径问题
带时间窗口车
辆路径问题
随机车辆路径
为问题
动态需求车辆
路径问题
依赖时间车辆
路径问题
时间窗口约束
需求剧透统计性
需求统计规律
旅行时间约束
随机需求车辆
路径问题
模糊需求车辆
路径问题
概率统计
模糊语言
图 1.1VRP扩展问题以及关系
1.3.2国外的研究现状
从上个世纪的90年代开始，国内也开始对VRP进行研究。到目前为止，可
以在国内的各大期刊网站上都能搜索到有关VRP的研究成果近千篇，同时着也说明了VRP这个问题的研究价值和重要性，同时还说明了国内学者对不同类型的VRP的研究做出了不可磨灭的贡献。其中这些研究主要有取送货问题[17]，多需求点调度问题[18]，装卸一体化问题[19]等。同时为了解决VRP的各种确定性问题用了各类型的不同算法，如遗传算法[20]、混合算法[21]等。对VRP的研究国内已经达到了相当的规模，虽然如此，但是VRP仍然存在很多的问题值得我们进一步的研究，同时对于VRP的复杂性和解决工具还需要更进一步的完善。主要的问题有如下：
①、首先VRP的问题是一个NP的难题。因此在求解的过程中如何优化计算时间和结果的精确性是解决问题的重点同时也是难点。于是对VRP的求解研究快速的高效的智能算法是一个很有价值的研究方向。
②、其次VRP的信息存在不确定性。因此必须对不确定的信息进行预先的处理，于是每次使用的智能算法都需要根据具体的问题进行变化。分析和优化不确定因素的解决策略也是VRP的另一研究方面。
③、还有用于求解动态的VRP的仿真环境仍然需要开发研究。仿真环境中关于如何产生一条符合实际情况的的路径，以及计算机模拟等问题都需要我们继续不断的努力。
④、最后在实际的物流配送任务中，对于城市的道路的同行状况的了解和掌握，因此我们可以考虑在VRP的框架下更进一步的研究。
1.4 论文的结构
为了便于阅读，本论文的章节是这样安排的。
首先，在本论文的第一章，对本课题的研究背景、目前国内外的研究动态进行简要地概述。
第二章，介绍本课题研究设计所需的基础算法粒子群算法的理论知识，介绍离散粒子群算法，其中包括离散粒子群算法的基本原理以及离散粒子群算法在各个领域中的广泛应用。
第三章，介绍物流配送，由物流配送引入车辆路径问题，深入地剖析车辆路径问题。
第四章，介绍基于离散粒子群算法的车辆路径问题的建模和总体的算法思路，并且对算法的实现做了详细的设计，展示设计结果。
第五章，对本论文的工作做了回顾和总结，归纳出了本论文的主要工作、取得的成果以及不足，并对本研究课题做了分析以及对今后的进一步研究工作做了展望。
第二章离散粒子群算法
2.1粒子群优化算法
2.1.1算法介绍
粒子群优化算法(particle swarm optimization , PSO)算法是1995年提出来的，由Kennedy和Eberhart二人提出的[1]，算法的起源灵感是来源于对鸟类等其他各类生物的饮食习惯观察、研究并将其简化而产生所得。自然界中各种各类的生物体基本上都会有着一定的群体的行为，因此为人类生命的研究的领域的讨论——群体生物行为所产生的生物学的特性提供了立体的直观的模型，同时为在计算机上建立和模拟群体概念提供了模型。其中包括近邻的速度匹配、多维的搜索以及加速距离的概念，从而形成了关于PSO的初始的版本。在此之后引进了Shi这个概念到惯性权重的算法中来平衡开发和挖掘的能力，才形成目前标准的版本。由于粒子群算法（PSO）的计算较简单、速度快的收敛性等优点使得算法在近十年内得到了较快的发展，并在很多领域得到了广泛的应用，成为了智能计算领域的宠儿。粒子群优化算法作为启发式的全局搜索的算法与此同时也是一个新的建立在群体基础上的智能算法，只需要用过粒子群中的粒子在相互之间进行相互地竞争和相互的合作，这样便能达到优化的效果，并较快速地在一未知或特定的空间中寻找到最优的一点从而达到空间全局最优。粒子群算法和其他的进化算法大体上是相同的，都是在进化和种群的基础概念之上的，然后使得群体中的个体之间竞争和合作配合相结合实现在复杂环境下最优的搜索。
PSO算法（粒子群优化算法）作为新的智能的优化技术，它是来自于人工的生命与演化计算的理论知识：对群体中的每一个都进行一次初始化，初始化后的粒子都将作为一个可能存在的解或预备方案，然后不断地更新搜索迭代出空间里最优的解空间。首先PSO算法（粒子群优化算法）会对随机的一群粒子进行初始化，再利用获得的最优解进行迭代在找到解的空间的一过程中追踪两个所谓的极值——个别的极端、全局的极值以此来不断地更新自己的位置和速度等。
2.1.2 算法原理
在PSO 算法（粒子群优化算法）当中，存在的每种需要优化的问题都对应
着在搜索空间里存在的鸟，而在DSPO （离散粒子群算法）中这些优化问题被称作粒子。这些粒子全部是需要被函数所确定的适应值，并且会存在一个各自的速度来计算他们运动的距离和方向。由此便会产生一个最优粒子，然后群体中的粒子们便会依据此最优粒子开始在解空间里搜索最优。于是每次的计算迭代，粒子都会依据来个极值来使自己的值保持最新状态。首先PSO 算法（粒子群算法）会对随机的一群粒子进行初始化，再利用获得的最优解进行迭代在找到解的空间的一过程中追踪两个所谓的极值——个别的极端、全局的极值以此来不断地更新自己的位置和速度等。由于这样粒子在整个的更新过程不会总得出比较好的值，于是很好的解决了某些问题。以上便是PSO （粒子群算法）的原理内容。
以上对PSO （粒子群算法）的原理分析，下面就PSO （粒子群算法）的原
理阐述PSO （粒子群算法）具体的算法过程：首先，需要对群体中的所有的粒子进行一个随机的初始化，初始化他们的位置和他们的速度，这样便能使群体均匀地分布在解空间当中。分别使用)v ,...,v ,(v V id i2i11=和)x ,...,x ,(x X id i2i11=来描述群体中的i 粒子在解空间中的速度与位置。然后再通过上述的迭代方法得出得出最优的解再利用这个最优的解来得出新的关于速度与位置的值。在这个迭代的过程产生的个体极值用)P ,...,P ,(P P bd b2b1bi =来表示。然后通过粒子间的领域得出另一个全局极值，即为整个群体中的一个最优的粒子用
)Nbest ,...,Nbest ,(Nbest Nbest d 21i =来表示。
最后粒子根据以下的两个计算公式得到最后具体的关于粒子的速度与位置。
)(*()*)(()21i i i i i i X Nbest rand c X Pbest rand c V V -+-**+=
i i i V X X +=
上述的公式中的c 1和c 2是用来表示加速度的常数，这两个参数可以用来调
整在全局中最优的粒子与个体中最优的粒子的步长。这两个常数不能太小也不能太大，如果它们的值太小则会使得粒子们远离我们的目标区域，但是如果太大便会使得粒子突然就向目标的区域飞过去或者甚至可能使得粒子飞出我们的目标区域。因此只有选择两个适当的值赋予c 1和c 2，适当的c 1和c 2能够加快整个算法的收敛速度并且也只有这样才能使得算法得出的最优解释一个局部的最优解。
Rand()函数能产生0~1的随机数。但是粒子的速度不能超过算法在每一维中设定的最大的速度V max 。算法设置这样的一个V max 的值的目的在于这样能确保粒子在群体中能达到的全局的搜索能力，在算法的整个运算的过程中若将V max 的值设置的越小就会越增加粒子在算法中的局部的搜索的能力。
由于PSO 算法（粒子群算法）的思想是来自于鸟群的觅食，在对算法的使
用过程中，众多的学者们发现很多的时候使用动物或者是生物的认知来展示算法的原理这样会显得更加的具体和完善，并且更容易让人理解和应用。由之前提到的更新速度的公式可将其大致地分为三个部分，首先一部分是关于V i ——一种粒子会按照原来的方向和形同的速度完成搜索过程的趋势，而这可以转换为用人的认知习惯来解释这一原理。其次一部分为)(*()*1i i X Pbest rand c -，这一部分的内容可以解释为粒子在过去寻找到的最优解中继续搜索的趋势，同样这也可以用人在认知的过程使用中所积累的经验来解释。最后一部分为)(*()*1i i X Nbest rand c -，而这一部分可以表示为粒子能在整个空间中的领域中以前遇到到过的那些最优的解中再次进行搜索的可能方向，这个有可以类比于人类可以通过从他人的所学会的知识中而获得一些经验。综上所述，PSO 实质上就是通过人或者动物的学习和认知的习惯过程总结出寻找到最优的解。
通过上述对PSO （粒子群算法）原理的分析和概述因而可以总结出PS 的几大显著的优点：①、由于PSO 算法的来源贴近人的惯性思维所以PSO 是较容易便能进行描述的；②、因为PSO 原理和内容是简洁易懂的所以将其实现的过程也是较为轻松的。③、在利用PSO 来计算时用到的参数的数量也是较少的，并且这些参数都为常数，所以基本上不需要费太多的心思在调整参数上。④、在算法应用的整个过程中由于群体的规模相比较而言稍微小一点，并且较少次数的利用到评估的函数，由此一来收敛速度便快了。⑤、在该过程中由于用到的计算较少因此对设备的CPU 与内存的要求也不那么严格。由以上的优点可以显然地得出目前解决全局的优化的问题PSO 是很有效果的。
2.1.3 算法流程
算法的流程：首先，需要对群体中的所有的粒子进行一个随机的初始化，初
始化他们的位置和他们的速度，这样便能使群体均匀地分布在解空间当中。然后再通过上述的迭代方法得出得出最优的解再利用这个最优的解来得出新的关于速度与位置的值。最后粒子根据以下的两个计算公式得到最后具体的关于粒子的速度与位置（如图2-1所示）。
开始
初始化粒子
群
计算粒子适
应度值
否
求解pBeat和
gBest
是否满足
是
输出求解
gBest值
结束
图2-1粒子群算流程图
2.1.4 本节小结
本章对PSO算法(粒子群优化算法)进行了深入浅出的介绍，首先大概介绍了PSO算法的来源、形成和发展。然后展开对PSO算法详细描述，对PSO算法原理进行深刻的剖析和认识，同时对PSO算法应用的优点进行了具体的阐述。最后为了能更好的对PSO算的理解，画出了PSO算法直观的流程图，使得算法便于理解和后面的实现。
2.2 离散粒子群算法
2.2.1 算法引入
PSO算法开始只是用于处理一些连续性的问题，然而随着近些年的发展，此算法被越来越广泛地使用在处理和完善离散问题中,从而逐渐地频繁地出现在人们的视线中并开始得到关注，因此在离散问题中衍生出来的PSO算法被称为离散粒子群算法(discrete PSO, DPSO)[22]。在关注DPSO这个过程中，人们对DPSO 这个算法的了解也愈深刻，尤其是在我们中国有一些研究者对DPSO的研究特别重视。该课题先描述了PSO算法的原理和内容，然后在基于离散化的情况对PSO 算法进行进一步的说明和阐述并基于离散映射不同的方法PSO算法，将DPSO 算法的离散空间进行划分，再将衍生出来的DPSO算法应用到VRP问题中，最后就该课题现状的客观分析以及讨论发展趋势和在该领域内的前景展望。
在DPSO的问题中逐渐出现两条主要的技术方法：一种方法是依据以往经典的连续的PSO算法，然后再将这个连续运动的粒子映射到离散空间中并适当修改算法使之适应能够解决离散问题。另一种方法是离散优化问题，用PSO为基础来更新各种新信息，用经典的算法的思想和框架重新定义DPSO中的粒子的表达和求解方式。利用离散空间上的位操作的独特载体，以取代传统的矢量的计算，从信息的流动的机制的角度上来计算，依然保存着PSO的具体的信息交换伴随流动的机制。而这两种方式的差别在于：第一种是在以连续空间的基础上的DPSO，而第二种则是在以离散空间为基础的DPSO。
根据现实生活中遇到的各类型的问题而言，以上的两种方法可以分别应用于在生活中的不同领域。就连续空间上研究的DPSO形成了二进制的PSO主要被应用在规划类型的问题中，除此之外还建立了专属于改算法的新的计算的模型还包括了些可能会被常用到的关于离散化的研究方法策略。
但是现实生活中的问题不全是都能在连续型的模型上建立起来并得到解决，因此BPSO在一些离散化的情况中将不再是那么适用。虽然现在急于离散化的PSO的研究还是不多的，但是仍然存在着一些这样的算法应用与离散化的相关的问题中。例如旅行商问题（TSP），在以离散空间为基础的前提下DSPO通过利
用位运算，这样虽然可能会增加一些计算的时间，但是这样便不会产生多余的搜索的问题，这样还能自然地描述离散的问题，并能和其他的演化算法紧密地结合起来，如此使得其有更好的发展前景。但是由于研究还是不是特别的多，因此缺乏一个通用的、统一的和标准的模型。
2.2.2 算法原理
二进制PSO 利用粒子的速度作为粒子的位置的变化的概率，这个观点由Kennedy 和Eberhart 两位博士首次提出的，专门用于解决0~1类型的规划的问题，在这个算法中，仅仅就是使用二进制的量来代表每个粒子并且利用二进制空间来代替超立方的空间，然后用二进制的量之间的转化来使得粒子在超空间中移动。于是得出更新速度的公式为：
)()(id gd id id id id x p x p v v -+-+=??
公式中的v id 为粒子的位置的变化的概率；x id 代表了当前粒子的确切的位置的值；φ则为常数因子，即为该粒子的学习因子；公式中的p id 和p gd 则分别代表了在空间中的粒子的局部的最优的位置和全局的最优的位置。由于此算法为二进制的空间中的算法因此以上的参数中的x id 、p id 和p gd 的值都只能为0或者是1。于是根据速度的变化的公式可以得到粒子的位置的公式为：
???<=)
(0()))()((1esle sig rand if x id 其中)
exp(11)(id id v v sig -+=. 在上述公式中的sig(v id )表示的是用于限制转换的函数，目的是为让v id 的值始终能保持在0-1之间的一个随机的数。其中v id 的值的选着直接关系到x id 的确切的值的大小，若v id 的值偏大，粒子的x id 则为1的概率非常的大，反之，粒子的x id 则为0的概率非常大。
随着DPSO 在各个领域的广泛的应用，算法的不足之处也慢慢的不断的涌现
出来，比如在组合式的优化问题当中表现的更为的突出，于是研究学家们便直接对连续的PSO 离散化，将粒子的非整的位置近似的等于整数，其余的部分保持和连续的PSO 中一致。虽然在算法中出现了近似的取整的情况，并利用这些近
似的解得可行的解，但是得到的可行解在高维的规划问题中仍能式算法具有较高的稳定性，并使得算法不会轻易地陷入停止的搜索状态。因此可得离散粒子群算法（DPSO ）的流程图如图3-1所示。 开始
初始化粒子的位置
和速度
寻找个体最优和全
局判断是否满足的
约束条件
利用公式更新粒子
的位置和速度
寻找当前个体最优
和全局最优
计算粒子的群体相
似度
判断群体相似度
是否大于给定的
伐值
启用排斥算子
判断是否满足结
束条件
结束是
是
否
否
否
图3-1 离散粒子群算法流程图
2.2.3 算法应用
由于PSO 的众多的优点，目前它已经应用在生活、工业和科学等的各个领
域中，并且成为了解决实际的工程与科学问题热门算法。同时DPSO 也得到了广泛的研究应用，比如在组合性的优化难题上，超大规模的集成电路上，电力系统上，无线的传感器的网络中和用于挖掘数据等等。通过不断的研究和应用，算法将会被更加广泛的应用，给我们的生活、工业和科学带来更多的便利和突破。
以下我们对常见的DPSO 的应用简单的分析与介绍：
①、典型性的组合型的优化问题——该问题属于运筹学的一个重要的部分，其中主要包括了TSP的问题、0-1背包的问题、工作的排序问题还有最小生成树的问题等。用重新总结定义的PSO来操作算式的方法得出了一种TSP-DPSO的算法，于是根据这一改进和突破，更多的学者以典型性的组合型的优化问题为基础提出了解决TSP的问题[23-24]、0-1背包的问题[25-26]、工作的排序问题还有最小生成树的问题等一系列的的算法。
②、电力体统——在该领域中，需要解决的是在最低成本的情况下进行发电扩张的问题，利用DPSO能很有效的处理该种有强约束力的组合型的优化问题。由于近几年来DPSO算法得到了有力地发展，解决这一问题的方法也随之越来越多，比如可以使用改进的BPS来恢复配电网出现的故障；或者可以根据配输电网的扩展规划的问题与电网的重构问题来设计适合的DPSO；又或者可以用DPSO处理电力系统中满足发电机的约束的经济的调度问题；亦或是就给出的电力市场中盈利区间内的约束问题改进我们的DPSO；亦或者是关于热备、停开机等约束的机组的调度问题与组合机组的等问题利用DPSO可以很好地将其解决。
③、VLSI——VLSI的设计中的布置线路、布值全局与布置图形是整个VLSI 设计的最重要的环节同时也是整个设计的核心关键所在。然而其中的布置线路、布值全局与布置图形又是整个设计中最为复杂最为困难的，该问题也以被证实为NP的难题。如若使用传统的算法来优化这个问题要么会因为爆炸量的计算要么就会因为得出的结果是局部性的而非全局的，很显然传统的算法已经是不能很好解决这些棘手的问题了。于是为了解决这一抽象性的难题研究学者们想到了在集成的电路中间使用启发式的算法来进行优化。但是PSO拥有更容易被实现的优点和更厉害的全局性的优化能力，学者们转而开始在VLSI的设计中使用PSO，于是辨得出了更多有效的关于解决布置线路[27-28]、布值全局[29-30]与布置图形问题的DPSO。
④、WSN——WSN作为新的网络出现，它不需要事先配置那些基础的网络的设施便能实现传感器之间节点的自由组网间的通信，还拥有应用空间的广阔性。虽然WSN拥有很多的优点，但是它同时也存在着不足之处，比如它自身带有的电能是有限的，它的的通讯能力也存在很大的局限性，在节点之间的计算能力也略显不足和它的存储能力也十分的有限。以上WSN这些不足会使得无线的
传感器网络之间的游泳资源相对的缺乏例如，因此要解决这些问题就显得有些迫不及待了。这几年来，表示已经有一些研究学者对WSN的各种问题展开了研究并且已经抽离出了它的数学模型来进行优化了，同时还建立了对应的PSO。很多的文献都已分别提出了PSO在WSN领域中的应用。还有一些学者将会深入的进一步在WSN中的任务的调度中与WSN的容错拓扑的控制中应用PSO来求解并得到最优的结果。
⑤、数据挖掘——它的属性的选择使用了BPSO得到了解决；并已有文献提出在DPSO基础之上的特征子集的选择方法；还有文献为传统的特征的选择的不足引入了粗超的简约的模型，同时还给了结合了PSO和领域粗超集的模型得出新的一种新的特征的选择的算法。
⑥、图像处理——有文献提出将PSO与模糊的理论相结合得出图像匹配、识别的混合算法；有文献提出使用混合的PSO与局部的搜索相结合可以对生物学中的图像进行标准匹配；有文献利用了混沌的优化的搜索得出以混沌搜索为基础的PSO，而且使的它与图像匹配的问题有较好的求解效果；还有文献表示可以在使用PSO的基础上利用红外的图像的分割的技术得到另一种快速的二维的熵算法。
⑦、VRP——虽然VRP是TSP的一种拓展的问题，但是在利用PSO求解释VRP时用到了全不一样的的技术。现有文献提出了可以通过将连续空间里的粒子进行仅是的离散化然后再加粒子的位置映射到离散的排序空间中，这样便能得到粒子在离散状态下的变化情况。与其他的遗传的算法相比较，在搜索的时候RPSO拥有更高的成功率，更高的最优解的质量与更优的时间复杂度。
⑧、Job2Shop——该问题一直都是调度和柔韧性制造的系统中人们时刻关注的一个问题之一。其用意在于利用现在拥有的资源来达到满足任务需要的约束，并且使得所有的人物能尽量在规定的时间之内较好的完成。Cagnina等研究学者曾在使用PSO处理单机的调度问题时，边用到了随机的键来显示粒子的具体的位置。然后再利用粒子的键值对作业排序，这需要先将粒子的具体位置影射到一种合法的调度上，只有这样才能更为便捷地使用连续PSO来计算出粒子具体的速度和具体的位置。在各个领域还广泛的存在很多关于PSO在Job2Shop的应用。
⑨、其他领域——综合以上所叙述的关于DPSO的应用，此外，DPSO在神经元