基于粒子群优化算法的逆向物流中心选址模型的研究.doc

重庆大学硕士学位论文基于粒子群优化算法的逆向物流中心选址模型的研究姓名：王德志申请学位级别：硕士专业：计算机系统结构指导教师：刘卫宁2010-04 重庆大学硕士学位论文中文摘要摘要推进可持续发展战略的优选模式就是发展循环经济，而实施循环经济的必由之路又是发展逆向物流，所以逆向物流优化问题被提上了日程。但在国内逆向物流的研究还处在初级阶段，逆向物流发展还不成熟，还有逆向物流的配送时间过长，成本过高等原因，对于大多数企业来说建立逆向物流系统成本过高从而忽略了逆向物流网络的建设。如何提高逆向物流的配送效率，最小化逆向物流成本是本文研究的重点。本文对逆向物流进行了介绍，列出了目前比较普遍认可的逆向物流模型，由于目前回流品对环境的影响越来越大的原因，并重点研究分析了环保再利用逆向物流网络中心选址的意义、选址的原则及选址的影响因素；研究分析了连续点选址模型和离散点选址模型；通过和正向物流的比较，总结了独立逆向物流选址模型的特点；提出了一个在一定假设下的独立逆向物流网络的一般化模型，并通过对这个网络模型的运行进行分析，建立了该网络在一定约束条件下的数学模型；物流选址模型属于组合优化问题，计算难度比较大，而且当备选物流中心达到一定数量的时候会产生组合爆炸得问题，因此单纯的优化算法难以得到最优解，本文主要研究怎样使用粒子群优化算法来解决独立逆向物流网络选址这类网络优化 NP难题，鉴于独立逆向物流模型的离散性，采用离散二进制粒子群优化算法对独立逆向物流模型进行求解，填补了粒子群算法在独立逆向物流选址中应用的空白；在求解过程中，针对粒子群容易陷入局部最优解及粒子多样性不够高等问题，使用动态的惯性权重系数、收缩因子等方法对粒子群优化算法进行优化。根据以上的研究分析，把离散二进制粒子群优化算法应用在独立逆向物流网络选址模型中。最后，通过一个具体的独立逆向物流网络选址模拟算例，对粒子进行编码，对粒子的每一维根据精度的需要采用八位二进制编码，使用 matlab工具，编程实现了上述过程，得出了适应值的收敛曲线，选出了较为合理的回收中心及各节点间的运输量。论文所建立的模型以及求解方法与步骤对于实际独立逆向物流网络的选址具有一定的实际意义。关键词：逆向物流，独立逆向物流模型，粒子群优化算法，物流选址I 重庆大学硕士学位论文英文摘要ABSTRACTCircular economy is the preference pattern to promote the sustainable developmentstrategy, and reverse logistics is the only way to implement circular economy, So the reverselogistics optimization problem was put on the agenda. However, the domestic researches onreverse logistics are still in the primary stage, reverse logistics is premature. And due to thelong delivering time in reverse logistics, high cost for the construction of reverse logisticssystem, etc., most enterprises ignore the establishment of reverse logistics network. Hence,the paper emphasizes on how to improve the efficiency of reverse logistics distribution andminimize the reverse logistics cost.This paper introduces the reverse logistics, The list is widely recognized by the reverselogistics model , Owing to the influence of environment on backflow bigger , analyzes thesignificance and influence factors of Reuse Reverse Logistics Network Center Location;researches and analyzes the continuous and discrete location model; summarizes the featuresof independent reverse logistics location by comparing reverse logistics with forwardlogistics ; proposes a generalized model of independent reverse logistics network, andestablish the mathematical model under certain constraint conditions by analyzing theoperation of the model; Logistics location model belongs to the combinatorial optimizationproblem, the calculation difficult ,solves the problem of combinatorial explosion when thequantity of back up logistics centers reaches a certain amount, which can hardly achievedoptimum solution through traditional optimization algorithm .The paper mainly focuses on how to use the particle swarm optimization algorithm tosolve such NP problems as the site selection in independent reverse logistics network. Giventhe discrete nature of independent reverse logistics model, the author solves the problem ofindependent reverse logistics model using discrete binary particle swarm optimizationalgorithm, which fill up the blank of applying the swarm algorithm to the independentReverse Logistics Location. During the solving process, the paper introduces several methodssuch as dynamic inertia weight factor, shrinkage factor, etc. to avoid falling into a partialoptimal solution and the low particle diversity.Based on the research achievements，particle swarm optimization algorithm is appliedinto independent reverse logistics network location model. Finally, to realize the wholeII 重庆大学硕士学位论文英文摘要process, Code of particles in each dimension, according to the needs of precision by eightbinary coding, the paper simulates a specific independent reverse logistics network exampleby programming in Matlab. The value of curve, the convergence to choose reasonablerecycling center and the traffic between each node. The model, the solving method and steps,proposed by the paper, have some practical significance toward independent reverse logisticslocation in real world.Keywords: Reverse Logistics, Model of Independent Reverse Logistics, Particle SwarmOptimization Algorithm, Location Selection of LogisticsIII 重庆大学硕士学位论文1绪论1 绪论1.1论文研究的目的与意义高速增长的经济与短缺的资源及日益恶化的环境产生了尖锐的矛盾，资源与生态问题严重制约着中国经济社会的可持续发展，要想解决这些问题，必须改变以前的经济增长模式，即以发展循环经济实施可持续发展来代替高投入、高排放的粗放式经济增长模式。2008年 8月 29日全国人大第十一届常委会第四次会议通过了循环经济促进法，此法以“减量化、再利用、资源化”为主线。再制造产品的重复使用和材料的再利用，都离不开逆向物流系统的建立与良性运作做支持。可持续发展的定义就是指既满足当代人的需求又不损害后代人满足需求的能力。可持续发展的核心是在严格控制人口、提高人口素质和保护环境、资源永续利用的前提下进行经济和社会的全面发展。以循环生产模式替代线性增长模式为基础的循环经济，表现为“从资源到产品再到再生资源”和最有效利用资源及保护环境，做到生产和消费 “污染排放最小化、废物资源化和环境无害化 ”，以最小成本获取最大的经济效益、社会效益和环境效益。循环经济的发展模式符合可持续发展战略的要求，循环经济的目标是可持续发展战略的重要组成部分，实施循环经济的可操作性策略组合是落实可持续发展战略的优选途径。因此，发展循环经济是推进可持续发展战略的优选模式。产品退回、物料替代、物品再利用、废弃物处理、再处理、维修与再制造等流程的物流活动就是逆向物流。我国将逆向物流分解为回收物流和废弃物物流两大类1：回收物流是指不合格物品的返修、退货以及周转使用的包装容器从需方返回到供方所形成的物品实体流动；废弃物物流是将经济活动中失去原有使用价值的物品，根据实际需要进行收集、分类、加工、包装、搬运、储存，并分送到专门处理场所时所形成的物品实体流动。“3R原则”即减量化(Reduce)、再利用(Reuse)、资源化(Recycle)为循环经济的行为准则。“减量化”实施的重点在于落实事前的绿色设计、事中的节能与事后的减排工作，“再利用”实施的重点在于再制造产品或部件的重复使用， “资源化”实施的重点在于材料的再利用。推进可持续发展战略的优选模式就是发展循环经济，而实施循环经济的必由之路又是发展逆向物流。建立逆向物流系统需要完善的逆向物流网络做支撑，再加上高效的信息管理系统，然而我国处于初级阶段的电子商务，物流业的专业化社会化程度还比较低，过长的逆向物流配送时间，成本过高，以及由于逆向物流本身在时间和空间上的不确定1 重庆大学硕士学位论文1绪论性等原因，大多数企业都觉得是一种负担，所以多数企业忽略逆向物流的建设。要想使公司甩开逆向物流成本这个包袱，以提高客户的满意度而增强公司自身的竞争优势，就必须控制或减小逆向物流成本。优化逆向物流的回收网络可以提高配送效率，在最短的时间、最短的距离，以最低的成本完成回收。逆向物流的最终目的是对回流品的再利用，利用回流产品创造新的利润，所以逆向物流实施前提是对物品的回收。逆向物流是具有不确定性的，即在单位时间内发生的逆向物流的数量不确定，在现实生活中很难形成规模回流，也就说逆向物流的发生具有突发性的特点，如果每次逆向物流都发一次车，那么管理成本就会增加，所以，运输成本的控制是降低逆向物流成本的一个极其关键的因素；又由于运输成本的大小与距离成正比的，即与所选择的物流路径有直接联系，除了单位时间的固定出车成本外，还应该把逆向物流的机会成本包括在内，所以，物流路线越长，固定成本、机会成本越高，逆向物流运作的成本也就越高，因此，怎样选择最优的逆向物流路径是降低运输成本的关键，它对于控制逆向物流的成本，优化逆向物流网络，加强逆向物流网络的运作管理，改变供应链结点的利益博弈，以及实施管理信息系统搭建，都具有重要的意义。我国物流行业发展处于初级发展阶段，包括对正向物流的研究、实践与探索都方兴未艾，多数物流企业对逆向物流的认识还存在一定的不足，系统的逆向物流研究与发展尚未提上日程。主要表现为：第一，生产厂商对商品逆向回收还不够重视，认为销售出去的商品，只需要提供质保、维修等售后服务，对于商品回收的问题从来没有考虑过；第二，很多企业认为逆向物流能带来的不是经济效益，反给企业带来了带来负面效应，所以对待退货和回收等逆向物流处于消极态度；第三，部分企业虽然意识到了逆向物流的重要性，往往却忽视了逆向物流活动的复杂性，对逆向物流缺乏管理，异想天开的认为一点儿的时间和精力的投入就可以处理逆向物流。逆向物流已经收到世界各国企业的重视，因为他对于促进可持续发展和实施循环经济有支撑作用。早在上个 20世纪 90年代初期，西方国家就已经对逆向物流开始了系统科学的研究，而且已经取得了一定的理论成果和实际效益。在我国对逆向物流还不够重视，无论是政府有关主管部门、从事逆向物流理论研究的人以及物流从业人员，对 “逆向物流”的研究还没有纳入日程。特别是物流业界，还没有认识到逆向物流是物流业的“第三利润源泉” 2。很少由企业能够具备逆向物流所需要的条件，即回收产品处理与再利用所需要的大量资金、技术、设备与专业人才。即使部分企业具备雄厚的资金实力，但出于投资回报率、竞争、品牌形象的考虑通常不会考虑生产和销售再制造产品。另外，逆向物流与正2 重庆大学硕士学位论文1绪论向物流业务在加工、库存、配送等环节都可能会发生冲突，因此很多企业考虑到逆向物流成本与收益，选择放弃逆向物流。在逆向物流系统中，回收产品的数量、质量及回收时间等是由产品的拥有者决定的，他们不能像原材料或零配件供应商一样，在制造商有需求时提供所需，而是要等到不再使用这个产品的时候才能把回收品提供出来。这种情况下回收品供应很难预测，进而导致企业生产的波动性，会增加企业的生产与物流成本，导致管理的复杂化和资源利用的低效率。这样，多数企业自主经营决策的结果必然是满足企业利益需求而放弃环境利益3。基于我国物流配送的现状，积极探索逆向物流回收网络优化的理论和方法，对降低逆向物流成本、提高服务质量、改善环境质量、树立企业形象，进而提高企业的经济效益和社会效益都具有重要的意义。这既是我国经济和社会发展的需要，也是增强企业竞争优势，使企业健康发展的重要保证。1.2选题的国内外研究现状分析1.2.1 国外研究现状从二十世纪九十年代很多学术界已经开始对逆向物流进行了研究，在研究过程中特殊性比较强，往往是针对某一类具体产品进行研究。下面简单介绍别人的研究成果。1997年 Berger和 Deballhe将一个现有的生产分销网络扩展成一个网络结构，该网络结构具有拆卸、检测等功能。该研究的关键在于各部分的处理能力还有设施定位。在已有设施的个数和坐标确定的情况下建立了 MILP模型。1998年，Angeline使用锦标赛选择算子，把选择机制引了进来，将个体按适应度值进行升序排列，选择最优的二分之一个体并进行复制，再取代较差的的其余百分之五十个体。九八年，作者又提出杂交 PSO算法，为每个粒子赋予一个杂交的概率。在每次迭代中，依据杂交概率选取符合条件的粒子放入杂交池中，随机地进行相互交配，产生相同数目的下一代。1998年 Barros把粒子群优化算法带到了建筑工地，为了对建筑工地上用不完的泥沙进行循环利用，作者采用多级选址定位模型进行了网络设计，通过网络模型确定了仓库的容积以及设备的选址。该网络模型包括四个方面：第一个是具有过滤和粉碎功能的粉碎公司、第二个就是包括分类和储存的区域仓库、第四个就是包括清晰和储存的处理装置、最后一个层次就是再利用的基建工地。1999年，针对欧洲大陆所产生的大量的废旧地毯，各国政府出于环保的考虑，为了提高环境质量，以及地毯中含有大量的尼龙原料，因此很多企业开始和化工单位联合起来建立逆向物流网络。Louwers等抓住这个特点设计了地毯回收的连续位置模型，在计3 重庆大学硕士学位论文1绪论算成本的时候使用了线性近似值法，最后利用非线性模型来求解最优化的问题。1999年，Suganthan提出了一种新的粒子群优化算法思想，按照空间把粒子分类，对于处于同一空间邻域不同粒子进行优化，在优化的过程中随机地改变阀值，这样就能保证粒子具有多样性，这就是所谓的邻域思想。Kenndy又把拓扑和邻域结合起来，给出了一个新的概念：邻域拓扑，它的思想大体是，将空间邻域与邻域拓扑中的拓扑思想和社会信念结合来增加邻域间的信息互换，从而提高群体的多样性。1999年 kikke等人根据影印机的再利用价值，为了对影印机进行再加工利用，构建了多层次逆向物流网络设计的混合整数线性规划模型。2003年，MinHokey建立一个双层的逆向物流系统，这个系统有初始回收点和回收中心构成。在这个双层的逆向物流系统中，回流产品首先从第一层的所有者手中集中到初始收集点，在初始回收点这个环节汇总后运往回收中心，在回收中心处理，这个模型中假定初始回收点具有限制能力的特点，回收中心的容量也是有限制的。围绕着初始回收点以及回收中心的选址和数量，作者提出了单目标、非线性的混合整数线性规划模型，对模型进行了优化，然后利用智能搜索算法进行求解，给出了基于遗传算法的程序。最后，通过一个实例对遗传算法的参数进行了灵敏度分析，该算例有五个待定的回收中心，十个待选的初始回收点，以及十五个供给客户，对库存成本、选址及容量等进行了优化。1.2.2 国内研究现状国内在逆向物流领域的深入研究相对较少，比较有代表性的有：2001年，ShihLi-Hsing对台湾地区的家用电器和计算机的逆向物流进行了分析研究，在六种不同的回收策略的基础上建立家用电器的逆向物流回收网络系统。在建立该网络结构的时候考虑了很多指标，一是运输成本的多少，二是物流中心的运行成本，第三是设施的固定成本，四是固定投入费用，第五点就是沉淀成本，第六点是回流产品的处理成本，最后考虑了回流产品的再利用价值即回流品的销售收入以及政府的政策性补贴。通过混合整数线性规划模型的优化，得到最优的设计方案。郑金华等提出了一种改进的粒子群算法，该方法引进了惩罚函数，作者使用了新的变异方法，在粒子的搜索过程中将周围临近的粒子抱成一团，从而形成了把粒子向新的搜索区域引导，根据惩罚函数的约束机制，使算法具有更强的全局搜索能力和效率。作4 重庆大学硕士学位论文1绪论者的结论表明，这个改进非常有效，在求解非线性约束优化问题是稳定性很高。2005年，侯云章等根据正向物流和逆向物流各自的特点，设计了混合整数设计模型，建立了正逆向结合的物流网络结构，建立了相应的模型，借助于模拟退火算法综合求解，在求解过程中，对算法的参数进行适当的变化，然后对结果进行比较，得出最小成本的正逆向物流网络结构。马祖军在 2005年，在传统正向物流网络基础上建立了一种基于单一产品的逆向物流网络，这个模型是有能力限制的产品回收逆向物流网络，属于混合整数线性规划。利用 Benders分解算法求解了模型，得出了各个设施的固定成本和运营成本的最优值，并给出了各个环节的合理的物流量，并对设施选址及设施数量给出了合理的答案，以Benders分解算法的高效性，对文中的算例经行了合理的求解。任杰在 2008年的企业逆向物流网络模型设计与优化研究中，对逆向物流的研究现状、逆向物流的定义、逆向物流的构成等相关内容做了详细阐述，并分析了逆向物流系统的流程，分析了正向物流和逆向物流的特点，给出了两者的区别与联系，给出了理论化系统化的定义。从逆向物流的结构特征出发，从不同的角度对逆向物流系统做了详细的研究，最后分析了构建逆向物流网络的环境、以及逆向物流网络的类型，并提出逆向物流网络模型设计的框架并对模型进行优化。在此基础上，论文分别以独立的逆向物流网络和整合的逆向物流网络为对象，进行了网络设计与优化的模型研究。建立整合的逆向物流网络设计与优化模型，并把该模型应用于一个算例，验证了模型的有效性。张昊在 2008年的遗传算法在再制造逆向物流网络选址模型中的应用中，论文介绍了我国逆向物流系统现状，继而分析了再制造逆向物流的基本结构；通过分析建立了结合正向物流的再制造逆向物流网络的一般化数学模型，该数学模型能很好的给出逆向物流网络的特点和运行过程的描述，然后对数学模型进行了优化，为了能够对该逆向物流系统进行合理的优化，作者采用了遗传算法对模型进行了求解，在求解过程中，对算法经行了很多改进，第一就是二进制的使用、第二采用了浮点数混合编码方式，第三就是轮盘赌选择策略，使用了简单的罚函数，以及单点交叉法，单点变异等，详述了遗传算法在该 NP难选址模型中的具体应用。最后，通过一个具体的模拟算例，用机器语言在计算机上实现了上述过程。5 重庆大学硕士学位论文1绪论1.3论文的主要研究内容本文试图在前人关于逆向物流配送、粒子群算法的求解方面所做的大量工作的基础上，力图对逆向物流中心选址模型进行探索和改进。具体研究内容如下：介绍逆向物流及逆向物流在我国的发展状况和存在的问题。总结逆向物流的特点及逆向物流中心选址的考虑因素。介绍粒子群算法的概念和原理，并对其进行优化以适应离散化问题的求解。构建独立逆向物流中心选址的数学模型并对模型求解1.4章节安排本文由六个章节和参考文献、附录组成，正文的内容组织安排如下：第一章：绪论。介绍了论文研究的目的与意义，并分析了国内外的研究现状，得出的结论是：目前我国发展循环经济并实施的可持续发展战略，以及家电回收的政策，逆向物流越来越受到重视，目前对逆向物流的研究还不够成熟；所以研究的逆向物流，并建立数学模型有研究的意义。最后说明了本课题的主要研究内容、创新点。第二章：粒子群优化算法的研究。详细介绍了粒子群优化算法的基本理论，研究了几种对粒子群改进的粒子群优化算法。重点分析了离散粒子群优化算法，因为本文的模型是离散型模型，要使用离散二进制粒子群优化算法对模型求解，鉴于粒子群优化算法大部分用在连续性模型的求解上，本文尝试用到离散型模型的求解上来，算是一个大胆的尝试。第三章：环保再利用逆向物流选址的研究。本章开始介绍了逆向物流的概念，接下来研究了主要的逆向物流网络结构，本文研究的模型基于环保再利用逆向物流网络模型，分析了环保再利用逆向物流网络模型的选址的意义及基本原则，最后重点研究了环保再利用逆向物流网络模型的选址影响因素。第四章：独立逆向物流选址模型的研究。本章节主要研究了选址模型，把选址模型分为连续选址、离散选址及网格选址三种类型，分析了选址成本的六个分类；详细分析了连续点选址模型及离散点选址模型的求解方法重心法和鲍姆尔沃尔夫法；根据逆向物流和正向物流之间的关系，给出了独立逆向物流模型的定义，并研究了该类模型的特6 重庆大学硕士学位论文1绪论点、独立逆向物流网络结构；建立在一定假设条件下的独立逆向物流模型。第五章：本章节针对独立逆向物流模型的特点，为了解决组合爆炸问题，采用粒子群优化算法对模型求解；鉴于模型是离散型模型，选取离散二进制粒子群优化算法对模型求解，并对模型进行了改进包括：引入了概率变量 C1、C2、C3、C4，通过粒子位置的判断，用翻转操作代替飞行向量，从而得到粒子的最优位置；动态的改变惯性权重系数；入收缩因子对粒子群优化算法改进；在迭代后期引入变异因子改变粒子的多样性。第六章：实例分析。本章节根据一个实例，编码实现了模型的求解，得到相对合理的结果，验证了离散二进制粒子群优化算法对模型优化的可行性。第七章：研究成果与展望。本章对论文工作进行了总结，对课题的进一步工作进行了展望。1.5小结本章介绍了论文研究的目的与意义，并分析了国内外的研究现状，得出的结论是：目前我国发展循环经济并实施的可持续发展战略，以及家电回收的政策，逆向物流越来越受到重视，目前对逆向物流的研究还不够成熟，特别是逆向物流，所以本文研究的对象就是独立逆向物流模型，建立数学模型并对模型求解；尝试把粒子群优化算法运用在离散模型上，运用离散二进制粒子群优化算法对模型进行求解。7 重庆大学硕士学位论文2粒子群优化算法的研究2粒子群优化算法的研究2.1粒子群优化算法的概述粒子群优化(Particle Swarm Optimization - PSO)算法是近年来发展起来的一种新的进化算法( Evolutionary Algorithm - EA)。粒子群优化算法属于进化算法的一种。在 1995年，Eberhart博士和 kennedy博士提出了该算法；这种算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。这种算法源于对鸟群捕食的行为。粒子群优化算法是一种基于基于迭代的优化工具，它同遗传算法类似，和遗传算法的区别就是没有“交叉”和“变异”操作，是一种基于群体的优化工具。它从随机解出发，通过迭代搜寻最优值，通过粒子在粒子空间追随最优的粒子进行搜索，迭代出最优解，寻求全局最优值。与其它进化算法比较，粒子群优化算法的优势在于易于实现同时又有扎实的智能理论背景，不管是工程应用还是科学研究都是很合适。因此，粒子群优化算法的提出，立刻引起了演化计算等领域的学者们的广泛关注，并在最近几年时间里相继出现大量的成熟的研究成果，形成为一个研究热门算法。鸟搜寻食物的场景描述如下：一群鸟在寻找食物，目前已知食物只有一块，所有的鸟儿又不知食物的具体位置在哪，已知的条件就是鸟儿知道当前的位置和食物还有多少远距离。那么怎么才能找到食物呢？我们假定鸟儿有学习的功能，这样鸟儿就能找到和食物距离最近的鸟的位置，然后飞向那里，通过这个不断学习的过程就能找到食物。粒子群算法就是从这里得到启发并用来解决优化问题。待优化的问题的解都被表述为粒子，然后粒子的适应值通过一个优化的函数来表示，粒子具有飞行的功能，其速度决定他们飞向的方向和距离，粒子们学习当前最有粒子在空间寻找最优解。每个粒子改变当前位置的驱动因素：粒子目前位置；粒子目前速度；粒子目前位置与其最好位置之间的距离；粒子目前位置与群体最好位置之间的距离。优化搜索是这样进行的：粒子群在初始化的时候位置是随机的，各个粒子以迭代的方式进行。和以往的优化算法相比，粒子群优化算法具有更强的全局搜索能力，能够全局优化，能在较短的时间里使粒子收敛于可接受解。粒子群优化算法不像遗传算法那样进行编码和解码，又不需要交叉变异等遗传操作，因此算法的参数少，效率高。粒子群算法目前已经在函数优化、人工神经网络的训练、模糊系统控制等应用领域。8 重庆大学硕士学位论文2粒子群优化算法的研究粒子群优化算法的运动方程为：Vi, j(t +1) = (t)Vi, j(t)+C1Rand()(Xpi, j Xi, j)+C2Rand()(Xgt, j Xi, j)(2.1)(2.2)Xi, j(t +1) = Xi, j(t)+Vi, j(t +1)其中 t为迭代次数，也就是粒子所处的不同时刻；i代表粒子，j代表粒子的空间。Vi, j(t)为粒子速度；Xi, j(t)为粒子的位置；惯性权重系数；加速因子 Cl，C2为正常数，取值通常为 Cl=C2=2.0； Rand()为随机数，取值0，l之间，另外，粒子根据 V和 X在搜索时，粒子的速度是受到限制的，最大值为 Vimax， Vimax一般为维数的 5%到 30%，当 Vi超过 Vimax时将被限制为 Vimax。即 Vi，j(t)-Vimax， Vimax。粒子群初始位置和速度随机产生，然后按式 2.1、式 2.2进行迭代，直至满足终止条件。公式(2.1)由三部分组成，第一部分为粒子当前的速度；第二部分为“认知”部分，表示粒子思考过程，促使自己飞向曾经发现的最好的地方；第三部分为“社会学习”部分，表示粒子间的信息共享与相互合作，鼓励自己飞向整个群体当前发现的最好的地方。粒子群优化算法计算过程如下：第一步：初始化粒子群(群体规模用 m表示)，包括各个粒子的随机位置和速度；第二步：计算每个粒子的适应值；第三步：对每个粒子，将粒子的适应度值与其经历过的最好位置 pBest的值作比较，如果较好，则将粒子的适应值作为当前的最好位置 pBest，否则 pBest不变；第四步：对每个粒子，将粒子的适应度值和全局所经历最好位置 gBest的值作比较，如果较好，则重新设置 gBest的索引号；第五步：根据式(2.1)和式(2.2)更新粒子的速度和位置；第六步：检查结束条件，若满足，结束寻优；否则，回到第二步。粒子群优化算法一个最大的优点就是参数比较少，但是这几个参数也会影响算法的性能和收敛性，所以明确参数的取值范围是很重要的。目前，PSO算法的理论研究尚处起步阶段，所以算法参数设置在很大程度上还依赖于前人的经验。粒子群优化参数包括：群体规模 m，粒子的维度 1，粒子范围-Xmax，Xmax，粒子最大速度 Vmax，惯性权重 ，加速常数 C1和 C2。下面是这些参数的作用及其设置经验。群体规模 m：即粒子数目，一般取 20到 40之间。大量试验表明，对于大多数优化问题来讲，30个粒子就可以取得很好的结果，对于个别特殊的问题，粒子数目可以取到100或 200。群体规模越大，算法搜索的空间范围就越大，也就更容易发现全局最优解。当然，这个以算法长时间运行为代价的。粒子维度 1：即每个粒子的维数，要具体问题具体分析。粒子范围-Xmax，Xmax：粒子范围由具体优化问题决定，通常将问题的参数取值范9 重庆大学硕士学位论文2粒子群优化算法的研究围设置为粒子的范围。同时，可以为粒子的不同维度设置不同的范围。粒子最大速度 Vmax速度不能大于这个速度。如果 Vmax如果 Vmax：粒子最大速度限制粒子在飞行过程中的速度，也就是说粒子的太大，粒子飞的过快，或许在一瞬间就飞过了好解；太小，在迭代过程中粒子始终在一个小的范围内搜索，所以会错过全局最优解，陷入局部最优值。通常设定 Vdmax = k*Xdmax，0.1k1.0，对粒子的每个维度都采用这个设置方法。惯性权重 ： 使粒子保持运动惯性，因为运动的惯性，所以粒子很容易飞到新的区域去探索，这样使粒子具有扩展搜索空间的能力，新的区域探索最优值。一般取值为0.2，1.2之间。前人的试验将 固定为 1.0发现，在搜索的过程中动态的改变 的值比 值一成不变能够得到更好的寻优结果，使算法在全局搜索的开始就具备探索合适粒子的能力，也就是说动态惯性权重因子比 保持固定值优越。动态惯性权重因子改变方式很多：搜索过程中线性的改变粒子群优化算法的 值，也可以根据某个函数来动态的改变 值，比如模糊规则系统。目前采用较多的动态惯性权重因子是线性递减权值策略，如式( 2.3 )。它能使 由 0.9随迭代次数线性递减到 0.4。=(ini-end) (Tmax-t) +end(t)(2.3)Tmax式中，Tmax为迭代的最大次数，ini为 的初始值，end为迭代到 Tmax时 的值。通常情况下 ini=0.9，end=0.4。加速常数 C1和 C2：C1和 C2是两个系数，他们的大小关系到粒子的学习的能力，C1的大小决定粒子学习自己的历史较优状态所占的比重；C2的大小决定粒子在“社会”上学习全局较优状态的能力，也就是说 C1和 C2代表将每个粒子推向 pBest和 gBest位置的统计加速项的权值。如果加速常数的值比较低，则粒子在被拉回之前可以在不属于目标区域的地方徘徊；如果加速常数的值过高，会导致粒子瞬间冲向或越过目标区域。C1和 C2是常数，早期的研究很多事取值为 24。有些研究论文5采用其他值，但大部分都在0，4范围内。2.2粒子群优化算法的改进粒子群优化算法以其实现容易、精度高、收敛快等优点引起了学术界的重视，并且在解决实际问题中展示了其优越性。算法的核心代码很少，这是其他算法无法比拟的。所以短短几年的时间粒子群优化算法获得了很大的发展，并在很多应用领域中发挥了优势。但是这个算法也有他的缺陷：很容易陷入局部极小点，不能寻求到全局最优。因此很多研究者对他进行了五花八门的研究和改进，以提高算法搜索的精度。现在已经出现10 重庆大学硕士学位论文2粒子群优化算法的研究了很多改进的粒子群优化算法，下面加以介绍。2.2.1 自适应粒子群算法大量的研究表明惯性因子对粒子群优化算法的优化性能的影响非常大，表现如下：如果得值比较大，搜索的过程中有利于跳出局部极小点，但是较大的不利于算法的收敛。在选择时提出了自适应调整的策略，随着迭代的进行， 的值线性地减小。有人提出利用模糊规则动态地修改的值，有人构造出模糊推理机来动态地修改惯性因子，模糊推理机有两个输入，一个输出，这两个输入分别是当前的值，以及规范化的当前最好性能演化(the normalized current best performance evalution，NCBPE )；而输出是的增量。目前粒子群优化算法利用的最好性能测度就是 CBPE，CBPE的定义方式很多，通常情况下 CBPE被定义最好候选解的适应值。CBPE用式 2.4计算：CBPE CBPEminNCBPE = CBPEmax CBPEmin(2.4)其中CBPEmax是 CBPE的可能最大值、CBPEmin是 CBPE的可能最小值。集合 LOW的模糊隶属度函数是 leftTriangle(模糊隶属度函数参见式 2.5)、集合 MEDIUM模糊隶属度函数是 Triangle(模糊隶属度函数参见式 2.6)、集合 HIGH模糊隶属度函数是rightTriangle(模糊隶属度函数参见式 2.7)，这三个集合分别是模糊推理机的输入、输出的论域，文献6给出了这些模糊隶属度函数的定义分别如下：1 if x x20 if x x20 if x x22文献6定义了 9条规则进行模糊推理，使模糊推理机在决定当前的增量时更加正11 重庆大学硕士学位论文2粒子群优化算法的研究规。研究证明：自适应 PSO ( Adaptive Particle Swarm Optimization，APSO)算法对许多问题都能取得满意的结果。这类算法在求解线性优化问题时能自适应地调整全局系数，并能兼顾搜索效率和精度，是很有效地智能算法。但是对很多繁琐的非线性优化问题，自适应粒子群优化算法的搜索精度和效率是非常有限的。2.2.2 混合粒子群算法混合粒子群优化算法的提出借鉴了遗传算法的思想，文献7对混合粒子群优化算法的概念作了描述。把基本的粒子群优化算法和选择机制相结合就是混合粒子群优化算法，因为基本粒子群优化算法在搜索过程中过多的依赖 pbest和 gbest，导致了搜索区域受到 pbest和 gbest的限制。如果能在优化过程中，采取选择机制，把好的区域留下来同时淘汰较差的区域，这样就能更合理地分配有限的资源，提高算法的搜索效率和精度。混合粒子群优化算法的选择机制和遗传算法的选择机制十分相似，混合粒子群优化算法在计算每个粒子的在某个位置的适应值时，对所有粒子的适应值进行排序，交换规则如下：筛选出粒子群体中适应值差的一半粒子，保留这些粒子最好位置 pbest的同时将其当前位置和速度替换为具