基于共轭梯度的微粒群算法及在车辆路径优化中的应用.doc

硕士学位论文基于共轭梯度的微粒群算法及在车辆路径优化中的应用Particle Swarm Optimization based on conjugate gradient and is applied to Vehicle Routing Optimization 学科专业： 工程专业学位 专业领域： 软件工程 作者姓名 ： 指导教师 ：中南大学软件学院2017年 5 月中图分类号 TP311.5 学校代码 10533 UDC 004.11 学位类别 专业学位 硕士学位论文基于共轭梯度的微粒群算法及在车辆路径优化中的应用Particle Swarm Optimization based on conjugate gradient and is applied to Vehicle Routing Optimization 作者姓名：学科专业： 工程专业学位专业领域： 研究方向： 软件工程 软件工程技术学院（系、所）： 软件学院指导教师：)副指导教师：论文答辩日期 答辩委员会主席 中 南 大 学2017年 5月 II学位论文原创性声明本人郑重声明，所呈交的学位论文是本人在指导教师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他教育机构的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。申请学位论文与资料若有不实之处，本人承担一切相关责任。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者和指导教师完全了解中南大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交学位论文的复印件和电子版；本人允许本学位论文被查阅和借阅；学校可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用复印、缩印或其它手段保存和汇编本学位论文。保密论文待解密后适应本声明。作者签名： 指导教师签名 日期： 年 月 日 日期： 年 月 日基于共轭梯度的微粒群算法及在车辆路径优化中的应用摘要：微粒群算法是通过模拟鸟群搜索食物而进行设计的。算法寻优机理是粒子个体间信息交互和协作来进行寻优，通过迭代而搜索到全局最优解。微粒群算法的算法结构简单、全局搜索能力强，已被广泛应用于优化控制领域。本文主要工作是对微粒群算法进行改进研究并将其应用于车辆路径优化问题，研究内容有：1、针对微粒群算法因惯性权重恒定而出现局部寻优能力不高，本文应用函数优化问题来测试惯性权重对算法收敛能力的作用。通过在惯性权重中引入动态调整参数，以此来调节算法的全局和局部寻优能力；针对算法在运行后期出现种群多样性减弱而导致求解精度不高的不足，在算法中引入共轭梯度法以增强算法的搜索精度。通过在惯性权重中引入动态调整参数并融入共轭梯度策略，设计了改进的的微粒群算法。2、为验证本文改进算法的收敛性能，用函数来测试基于参数调整共轭梯度的微粒群算法的性能，函数仿真实验表明，该算法在收敛精度和收敛速度上有所提高。3、最后，以车辆路径优化问题作为研究对象，将本文改进的微粒群算法来求解车辆路径优化问题，实验结果表明，该算法可以找到最优路径，收敛效果比较好。图12副，表6个，参考文献61篇关键词：微粒群算法；共轭梯度法；函数优化；车辆路径优化问题分类号：TP311.545Particle Swarm Optimization based on conjugate gradient and is applied to Vehicle Routing Optimization Abstract：Particle Swarm Optimization(PSO) is obtained by simulating the natural foraging birds. Its optimization mechanism is to find the global optimal solution in the solution space through competition and collaboration between individual particles. PSO is easy to implement, and algorithm structure of PSO is simple.The optimization ability of PSO is strong. PSO is widely used in the field. Improvement of particle swarm optimization algorithm and Its application in Vehicle Routing Problem are mainly researched in this thesis.The major innovations are as follows：1、According to The constant inertia weight appear to local search ability, inertia weight is relate to the particle swarm algorithm convergence performance by function test. Dynamically adjusting the parameters is introduced to the inertia weight, which is to balance the global and local optimization capabilities of algorithm; According to the optimizing accuracy is not high in the latter part,conjugate gradient method to enhance searching precision is introduced in the algorithm. particle swarm algorithm based on the parameter adjustment and conjugate gradient (ACGPSO)is proposed by these improvements. 2、To verify the improved algorithm, particle swarm algorithm based on the parameter adjustment and conjugate gradient is applied to the function test, simulation results show that the improved algorithm can effectively improve the optimization accuracy and convergence speed of the algorithm; 3、Finally, Vehicle Routing Problem (VRP)is used as the application object, The improved PSO is applied to VRP,The experimental results show that the optimal path is found and good optimization results is received.12 graphs, 6 tables, 61 referencesKey Words：particle Swarm Optimization Algorithm；Conjugate Gradient Algorithm；Function Optimization； Vehicle Routing ProblemClassification TP311.5目 录1 绪论11.1 研究背景及意义11.2 本文主要的研究内容31.3 本文章节结构42 群智能优化算法52.1 优化算法和最优解52.1.1 算法分类52.1.2 局部最优解52.1.3 全局最优解52.2 智能优化算法62.2.1 遗传算法62.2.2 微粒群算法72.3 研究现状112.3.1 连续性微粒群算法112.3.2 离散型微粒群算法132.3.3 微粒群算法的改进132.4 本章小结153 参数调整与共轭梯度策略163.1 算法的参数163.1.1 参数设定163.1.2 惯性权重取值测试173.1.3 惯性权重的调整算子193.2 共轭梯度机制203.2.1 共轭梯度法203.2.2 适应度函数223.3 基于参数调整共轭梯度的微粒群算法223.3.1算法思想223.3.2 算法描述233.3.3 收敛性分析243.4 本章小结254 基于参数调整的共轭梯度微粒群算法的函数优化264.1 函数优化问题264.2 函数优化测试274.2.1 算法流程274.2.2 测试实验274.2.3 实验结果与分析294.3 本章小结325 基于参数调整的共轭梯度微粒群算法在车辆路径优化中的应用335.1 车辆路径优化335.1.1 车辆路径优化模型335.1.2 车辆路径优化的现状345.2 车辆路径优化345.2.1 车辆路径优化的数学建模345.2.2 车辆路径优化求解355.3 本章小结376 总结与展望386.1 总结386.2 下一步的研究方向39参考文献40攻读学位期间主要的研究成果44致 谢45工程硕士学位论文 1 绪论 1 绪论优化问题是控制科学和运筹学领域中一个重要研究课题，国民经济和生产实践中有着广泛应用。优化问题的求解有两种，即确定性和不确定性。确定性的算法要求优化问题的目标函数可导，寻优结果与初值有关且不能够解决大规模优化问题。而不确定性算法就是当前主流优化算法即模拟生物的智能优化算法，具有寻优速度快、收敛精度高且对目标函数要求不高的特点。设计一种收敛性能高效的智能优化算法是优化领域的研究热点。1.1 研究背景及意义优化技术是为了解决各种组合优化问题和工程实践中的优化问题而产生的一门以数学为基础的科学。通过对优化问题进行建模，通过对建模函数进行优化来找到目标函数的最优值。在经济生产中，有许多问题可以看出为优化问题。在经济决策中求利润最大化问题，货物配送路径最小问题。这些都是优化问题，通过对优化问题进行建模，形成了目标函数，从而应用优化进行求解以求得目标函数的最值。随着技术的进步，经济生活中越来越多的问题可以通过数学方法转换为优化问题，最终通过优化技术来加以解决。因此，优化问题和优化技术越来越受到科学家的重视。社会进步，生产力的发展，优化问题变得越来越棘手，表现在优化问题的参数多、规模大而且由传统的线性优化问题发展为非线性优化问题。解决优化问题的优化技术，也变得形式多样。传统优化算法主要依靠按步进行迭代优化，当优化问题规模变大，传统优化方法显得力不从心。典型的TSP问题当规模达到200多个城市时，传统优化算法几乎无法求解出问题的解。求解这类优化问题需要更加高效的优化算法。因此，具有智能特点的优化算法就产生了。具有智能特点的优化算法在求解大规模、非线性优化问题时具有很强的优势。这类算法可以在比较短时间内收敛到全局最好解。所以迅速发展起来。在自然界中生物系统社会系统中，鱼群、鸟群、蜂群觅食行为，这些群体是具有一定群体智能特点的称为“群智能”(swarm intelligence)1。具有智能特性的优化算法一般是通过赋初值,即在解空间中给定一个初始点,然后按照一定寻优规则进行搜索。一般是带有概率性质的寻优而有别于传统优化算法的逐点搜索，这样就大大减少了寻优时间。算法在更新自身状态比较高效，所以能够搜索到全局的最好解。这类具有智能特点的优化算法在解决大规模、非线性优化问题具有先天优势。主要表现在迅速收敛、效率高。这类智能优化算法有：人工蜂群算法、人工神经网络等。这类算法主要是模拟自然界的生物行为而实现进化寻优，因此也叫做群智能优化算法。这类算法是按照概率寻优，在搜索全局最优解的时候也是具有概率性的。优化技术在工程领域，工业控制和经济管理等领域都是一个十分重要课题。微粒群优化算法2 (Particle Swarm Optimization, PSO)，这个算法是由Kennedy和Eberhart两个博士对鸟群在无序的情况下搜索到食物源的寻优策略进行研究，即鸟群在搜索食物时，时而聚集、时而分散，鸟儿不断调整自身运行速度和飞行的位置。最后，这个群体一起找到食物源。这两个博士经过长期研究和论证，在1995年设计了基于鸟群觅食寻优思想的仿生算法，即微粒群算法，微粒群算法在工业控制、模式识别、电力系统优化、经济管理、生物医学、组合优化问题TSP等领域都有着广泛应用。传统的优化算法有单纯形法和共轭梯度法，这类算法求解规模小的优化问题，表现出较好的收敛性能。现代的优化算法即近来提出的智能优化算法，如：遗传算法、人工蜂群算法等。现代优化算法在解决大规模优化时，可以有效的找到的全局最好解。随着生产力的发展，工程领域中的优化问题越来越常见，参数也越来越多，复杂度越来越大。因此，通过研究寻优精度高、收敛速度快的群智能优化算法来解决大规模复杂的优化问题具有非常有用的价值。物流已被视为企业的第三个利润的来源，它是企业降低成本的主要的工具。实现最短距离的物流配送，对降低企业成本有着重要作用。因此，研究车辆路径优化问题对物流企业是非常有帮助的。车辆路径优化问题在物流货物配送中应用相当广泛，是一种典型的NP难问题。对车辆路径优化问题进行转化就可以将车辆路径优化问题变为最优化问题。即在一定的约束条件下，对所有有货物需求的客户进行遍历，求其最短的配送路径。车辆路径优化的目标函数就是求配送路径的最小值。对车辆路径优化问题的求解的优化算法有：遗传算法、人工蚁群算法及微粒群算法等一些群智能优化算法。目前对车辆路径优化问题求解的智能优化算法主要是以上几种单一的智能优化算法，单纯一种智能优化算法在求解车辆路径优化问题时候存在一些缺陷和局限性。即在当车辆路径优化问题中配送客户的数量比较多、规模大时，单一的智能优化算法表现出收敛精度不高、收敛速度较慢的缺陷。如何提高求解车辆路径优化问题智能优化算法的求解精度和收敛速度，是车辆路径优化问题中一个非常值得研究的课题。对单一的智能优化算法进行改进以提高求解车辆路径优化问题收敛速度和求解精度是非常必要的，因此，对智能优化算法进行改进研究可以极大降低企业的物流成本，在物流配送等优化领域具有一定价值。在求解车辆路径优化问题时，各个群智能优化算法寻优优缺点各有不同，具体如下表1-1所示：表 1-1 各种算法求解车辆路径优化问题的优缺点智能优化算法特点不足模拟退火算法算法鲁棒性强且算法的全局寻优能力较强，算法机理易于理解算法收敛性能比较差，运行效率不高且收敛速度比较慢遗传算法遗传算法的并行性比较强且算法的全局寻优能力较强算法收敛能力不强，出现早熟而找不到全局最优解。人工神经网络算法算法实现较为简单且算法运行速度快算法收敛精度不高，极易陷入局部最优值蚁群算法蚁群算法的算法自适应能力比较强，算法的正反馈机制和群体个体的组织能力较强算法的收敛性能较差、收敛速度比较慢且容易陷入局部最优值微粒群算法微粒群算法迭代公式比较简单、容易实现且算法比较容易实现，算法的收敛速度也比较快算法中的参数依赖经验值，参数的设置影响算法的收敛能力，不好控制1.2 本文主要的研究内容本文阐述了微粒群算法的算法机理和算法实现，分析了微粒群算法的迭代公式和惯性权重等参数，惯性权重可以调节迭代公式的速度，惯性权重取值大小直接决定粒子个体飞行的速度，飞行的速度大就影响算法的在解空间中寻优范围，速度小就有利于算法在某个小区域内寻优，惯性权重会影响粒子个体在寻优过程的速度，进而对微粒群算法的全局收敛能力和局部收敛能力产生影响。微粒群算法的惯性权重恒定，导致算法在寻优后期的基本寻优能力不强而使算法错过全局最优解，从而导致算法陷入局部最优解。针对微粒群算法在寻优后期因惯性权重恒定而导致算法的不能够很好平衡全局寻优和局部寻优能力，通过引入一个动态参数来动态调整算法的惯性权重。以控制好算法在解空间的全局寻优的能力以及在最优解附近的局部寻优能力。针对微粒群算法在寻优后期出现种群多样性减弱而找不到最好解，在算法加入了共轭梯度法进行搜索寻优。应用函数优化问题啦测试基于参数调整策略共轭梯度的微粒群算法的收敛性能和算法的有效性，应用函数测试仿真来检测基于参数调整共轭梯度的微粒群算法，仿真实验表明，在求解函数优化问题中改进微粒群算法在收敛速度和精度方面有所提高。算法研究的目的是解决应用问题，将本文提出的基于参数调整共轭梯度的微粒群算法的应用于车辆路径优化问题中，实验结果表明，改进的微粒群算法能够在比较合理时间内找到物流配送的最佳路径。1.3 本文章节结构第一章阐述了优化问题、优化技术及其智能优化算法，对当前几种智能优化算法在对车辆路径优化问题进行求解的优缺点，并分析了几种智能优化算法在求解具体优化问题的特长和不足。第二章是微粒群算法的遗传算法等一些智能优化算法的的综述，详细阐述了连续性微粒群算法、离散型微粒群算法以及微粒群算法的改进研究。第三章通过函数仿真实验来测试惯性权重在微粒群算法寻优过程中起到的作用，对于微粒群算法在寻优后期找不到全局最优解的缺陷。在算法迭代公式引入惯性权重调整参数中。针对算法在寻优后期出现的早熟而导致算法极易陷入局部极值的缺陷，将共轭梯度法的寻优策略引入到基本微粒群算法中以克服算法在后期因种群多样性减弱的不足，设计了基于参数调整策略和共轭梯度寻优策略的微粒群算法。第四章为验证种基于参数调整策略和共轭梯度的微粒群算法的收敛能力，通过仿真实验来进行测试。主要应用改进的微粒群算法来求解函数优化问题以测试算法的寻优能力。第五章选取车辆路径优化问题为算法的应用对象，将本文提出的基于参数调整共轭梯度的微粒群算法来求解车辆路径优化问题。第六章是总结，主要介绍了本文的研究内容和主要创新点，并阐述了下一步研究内容。工程硕士学位论文 2 群智能优化算法 2 群智能优化算法在介绍研究智能优化算法意义的。本章主要探讨了两种智能优化算法的寻优机理，综述了微粒群算法当前研究情况，主要集中在对算法的改进，为算法的改进做铺垫。2.1 优化算法和最优解2.1.1 算法分类优化算法通过一种迭代方法，采用一定的寻优规则对优化问题进行搜索寻优的一种方法3。通常的可以将优化算法划分为以下几类：1、无约束的优化算法：无约束优化算法主要有坐标轮换法、最速下降法和单纯形法。这类算法运算效率相对较高，而且不需要目标函数的导数信息，在程序设计方面也相对简单。这类算法比较精准而且逐步迭代寻优，计算相对比较复杂，运算量也较大。2、按照优化算法求解空间的目标可以划分为：解空间中的全局搜索寻优算法和解空间中的局部搜索寻优算法2.1.2 局部最优解如果，的某一个领域，那么对所有的，都有，那么就是优化问题的局部最优解。局部寻优算法是指就在目标函数的解空间中每个领域内通过迭代寻优随机搜索到解空间内的一个点，如果搜索到一个解使得比当前寻优而得到的解的适应度值更好，而这个点的适应度函数值符合以上条件，就用这点的值来代替当前状态。这类算法在解空间中搜索寻优仅仅可以找到赋初值位置的最好解。2.1.3 全局最优解如果，对于所有的，都有，那么就是优化问题的全局最优解。全局优化算法是建立在局部优化算法的基础之上，全局优化算法通过这种方式进行寻优即先进行局部寻优操作，在局部搜索的基础上搜索到局部最优解。全局最优算法也可能搜索不到全局最好解，能够找到全局最好解附近的局部最优解也符合要求，因此，当算法迭代次数和迭代时间足够可以搜索到目标函数的最优解。2.2 智能优化算法群智能优化算法是模拟生物群体的行为特性，根据其寻优思想而设计的一种具有生物智能性质的算法。这类算法在求解复杂且规模大的优化问题具有一定的优势，群智能优化算法按照生物自然规律特点进行设计，通过一定的寻优规则对解空间进行搜索寻优4。群智能优化算法具备如下特性：1、不确定性和方便性不确定性是指群智能优化算法是通过模拟自然界生物寻优机制，自然界生物寻优机制就具有不确定性。群智能优化算法在寻优过程是基于概率寻优，是否找到全局最优解也是具有概率性。因此，群智能优化算法具有不确定性。方便性是指群智能优化算法对优化问题的目标函数没有做太多的限制。2、算法并行性强主要是实现算法的并行寻优，大规模并行才使得算法高效。突现性主要表现在群智能优化算法的寻优结果是通过群体中个体行为在寻优过程中而得到。3、自组织能力强和稳定性强群智能优化算法是基于生物群体行为而实现寻优，生物都具有进化能力而适应外部环境，群智能优化算法也是一样。它通过不断学习而适应复杂的目标函数寻优。因此，群智能优化算法具备了相当强的自组织能力。在求解优化问题时，群智能优化算法对目标函数需要太多的限制，它对目标函数没有过多限制，只要可以构造出目标函数就可以利用群智能优化算法进行优化寻优。群智能优化算法的稳定性具体是指算法可以不同条件下，不同的数学性质和特征都可以实现寻优。2.2.1 遗传算法遗传算法模拟生物界的进化规律而得出了一种智能优化算法。而演化出来的一种随机搜索方法。它的工作机理是构造生物的染色体的遗传行为，染色体是由基因而组成 5。遗传物质的染色体是承载着多个基因，基因之间相互结合通过基因表达而表现出不同的外部特征。在遗传算法实现中，首先进行初始化即进行二进制编码，根据保留最优解而淘汰较差的解即优胜劣汰的原理，逐代进行优化寻优从而得到愈来愈好的近似解，在每一代的进化中，通过求出目标函数的当前个体的函数适应度值来选取状态好的粒子个体，遗传算法主要寻优手段是交叉和变异操作，通过交叉和变异而实现进化，进而产生新的解集种群。这种通过进化的种群比上一代更加适应环境，经过反复进化寻优得到的最优个体经过解码，来找到目标函数的最好解。遗传算法在求解优化问题时，对优化问题的目标函数没有太多要求（比如：函数可导和函数连续等），多个基因进行交叉和变异操作，算法并行处理能力和搜索解空间中最好解的能力也非常强大。初始化遗传算法种群时，需要选取一个种群，算法在进化中具有一定概率性，遗传算法模拟自然界生物的进化机制，因而具有概率性和不确定性。遗传算法是一种进化算法，可以基于启发式信息进行搜索寻优。可以用来得出有用的解决方案来进行优化，运用了遗传规律中的交叉和变异机制。遗传算法当算法的目标函数即适应度函数取值不合适的情况下，容易出现算法提前收敛而没有找到全局最优解。遗传算法寻优机理是：第一步对欲求解的优化问题进行二进制编码，即用染色体来表示解空间中解。第二步求目标函数的适应度值，对适应度值进行选取，将适应度值高的染色体进行融合即交叉和变异。第三步也是最后一步逐代逐代进行进化，以此来得到优化问题的最优解。遗传算法操作中主要确定算法关键点：1、为优化问题选择合适的适应度函数，一般选取优化问题的数学函数的解析式。2、对函数的各个参数进行初始化。4、算法的终止条件。遗传算法进行迭代寻优的算法流程图，如下图2.1所示。2.2.2 微粒群算法1. 算法机理鸟儿在搜索食物的过程中时而聚集时而分散，一群鸟儿最终一起飞到食物源处，从而找到食物。美国的两个博士在经过长期观察、模拟鸟群进行觅食建立了鸟群觅食模型，再进行反复试验，将鸟群觅食引入到优化问题求解，鸟儿即微粒群的粒子个体。粒子个体通过信息交互即相互交流解空间的信息，粒子不断更新自身的位置，以状态好的位置来取代当前状态位置从而实现从无序到有序的转变。经过一次次迭代进而找到全局最好值。遗传算法和微粒群算法都是进行迭代寻优的算法，两种算法都是开始进行初始化对算法进行赋初值。而微粒群算法是模拟鸟群在飞行过程中觅食操作而进行设计，算法是通过更新自身状态位置和速度，粒子个体在搜索寻优过程中跟踪状态最好的粒子个体进行搜索寻优。相比较而言，微粒群算法需要调整的参数不多且容易实现。微粒群算法中，将解空间中的每一个点即优化问题的解当作一只鸟，在微粒群算法中粒子个体状态好坏就是由目标函数的适应度值来决定，决定粒子个体状态的还有两个参数即粒子飞行的方向和粒子飞行的距离。粒子进行寻优的机理是这样的：微粒群算法中的群体的位置进行更新，粒子个体变换自身位置主要通过两个极值大小的判定。一个是粒子个体在自己的寻优轨迹中所找到的最好值pBest。另外一个极值就是鸟群群体中最好状态下的最好解称为群体最优解gBest。微粒群算法中将群体中的每个个体看着是D维解空间中一个没有质量也没有体积的粒子。微粒群群体中的每一个粒子个体都按照既定的方向和算法运行时赋予的初始值进行求解，通过信息交互来不断变换自己的所处位置状态。经过一代一代迭代搜索，最后找到解空间中的最好解。微粒群算法则是通过群体中粒子个体间信息交互，粒子不断交互信息并及时更新自身位置和状态进而实现迭代寻优。算法寻优过程中按照以下规则寻优的：(1)粒子间不发生碰撞。(2)领域内个体速度要一致。(3)粒子个体通过群体内信息交互，都趋向于最优状态的位置。2.算法模型和迭代公式微粒群算法通过调整粒子个体来实现粒子个体的迭代寻优，其数学迭代公式如下所示 6： (2.1) (2. 2)上式2.1表示速度迭代公式，式2.2表示位置更换的数学迭代公式。上式中，和都是常数。表示为学习算子。算法运行的流程图如图2.2所示。在微粒群算法中，每个粒子个体都设置一个适应度值，适应度值是由优化问题的目标函数所决定。迭代公式中粒子个体还有粒子运行速度和当前所处位置这两个参数。粒子个体就是相互传递各自所处的状态信息，进行相互交流，粒子都朝着最好位置飞行，通过迭代来找到最好解。鸟群是由N个粒子组成，鸟群规模就是N个个体，第i个粒子的飞行过程中位置信息可以表示如下。，。 第i个粒子在飞行过程中的飞行速度表示如下： ，。图2-1算法流程图第个粒子的当前状态的最优状态称之为局部最优值表示为： ，。鸟群在寻优过程中的最优状态就是全局最优值，表示如下：图2-2 PSO算法流程图3.具体的算法步骤可以描述如下：Step 1 初始化操作，微粒群的数目，每一个粒子的初始速度和位置。对各个参数赋初值，微粒群种群规模为N，算法的粒子个体的初始运行速度、粒子个体初始化的位置表示为。Step 2 计算适应度值，按照优化问题的目标函数即适应度函数，来逐个计算适应度值。Step 3 通过Step 2计算得到每个粒子个体的适应度值和个体最好状态的极值作比较，如果果 ，则用取代。Step 4 算法中的每个粒子都用其自身的适应度函数值与当前最好状态的全局极值作比较，如果自身适应度值要比最好状态的极值大，就用搜索到最优解代替当前状态的最好值。Step 5 求出粒子所处位置和速度，并得出解空间中运行的速度和粒子个体当前所处的位置。Step 6 判断算法是否达到了设定的最大迭代寻优代数，达到则终止，否则调至Step 2。4. 微粒群算法的优点(1)数学迭代公式表征意义明确，一是表示粒子个体的惯性，二是表示粒子自身寻优的状态。三是表示粒子间相互交换信息和进行信息共享的机制。(2)算法在运行之初，当迭代次数不断增加时解集合表现出更多的随机性，每迭代一次粒子信息共享能力和解集的质量会越来越高。(3)运用实数进行编码。5. 带惯性权重因子的微粒群算法智能优化算法都是基于搜索进行寻优的优化算法，其目的就是通过以前寻优路径中搜索到最好解。局部寻优能力是通过在以前的一个较好解的基础上，以此为基础继续搜索原来的解以找到解集中的更好解。在算法寻优过程中平衡好算法的局部寻优能力和全局寻优能力以找到全局最优解是算法收敛能力一个至关重要的隐私，文献7在1998年通过研究在基本微粒群算法中引入惯性权重的微粒群算法，该算法可以用一下迭代公式来描述： （2.3） （2.4）上式（2.1）也可以分成3个小部分，第一个表示粒子个体保持初始化赋初值的速度，第一部分表征的意思是算法在解空间中的全局寻优能力；第二个和第三个表示算法的一般的搜索能力。当w=1时，式(2.1)与式(2.3)是一个迭代公式，则算法表示的意义也相同。仿真实验表明，当惯性权重w取值在0.8-1.2这个区间时，算法搜索能力和搜索效率也是最高的。惯性权重W大于1.2时，算法过早收敛概率大。2.3 研究现状2.3.1 连续性微粒群算法文献8分析了微粒群算法的特点，得出了微粒群算法随机搜索寻优需要满足的条件。并分析微粒群算法中的各个参数，分析得出了算法中的各个参数在优化寻优过程中起到的作用。为算法的改进提供了支撑，运行时间趋向于无穷时就可以搜索到全局最优值。应用离散理论对基本微粒群算法进行了收敛性能分析，得到了算法参数赋值的规则，为以后微粒群算法的参数设置提供了方法。文献9对基本微粒群算法模型了进行了分析，并进行仿真实验，分析得出结论微粒群算法的迭代公式在优化寻优时较为简单，算法收敛能力比较有限。文献10对微粒群算法中迭代公式进行了改进即通过一种模糊规则来调整惯性权值，通过对微粒群算法当前状态来决定惯性权重和隶属度函数，通过惯性权重和隶属度函数来动态改变算法的惯性权重。测试表明，惯性权重动态调整不好对算法搜索到全局最好解是有帮助的，比固定权重的惯性权重有较好的收敛性能。惯性权重可以改变微粒群算法粒子个体的寻优速度，在一定程度上影响着算法的全局寻优能力，即开始寻优时加大算法的全局搜索能力，再在算法迭代寻优一定时间后即使算法保持较大的局部领域搜索力度。当算法继续运行一段时间后，种群多样性也就变得越来越弱了，算法搜索错过全局最优值。为克服算法因多样性减弱的不足而搜索不到全局最优解的不足。专家学者提出了用种群多样性来提高算法的收敛性能，微粒群算法过早陷入局部极值是算法的多样性减弱而导致的，种群多样性越强则算法搜索能力越强。文献11通过对算法的种群多样性进行控制，从而提高了算法的收敛性能。文献12为更好解决微粒群算法的粒子个体发生聚集和碰撞，对基本微粒群算法进行了改进，当算法运行时，对粒子个体的半径R进行判断，粒子间半径小于R，则认为粒子发生了碰撞，为增强算法的种群多样性采用弹离法来实现，运用多峰函数来测试改进的微粒群算法的寻优性能，仿真实验表明，改进微粒群算法提高了算法的种群多样性和算法搜索精度。文献13分析了方差和均值在不同取值时，并进行高斯变异操作，实验结果表明，进行高斯变异操作对微粒群算法的收敛性能有一定的影响。在提高算法的种群多样性方面，有量子方法、混沌法，还有高斯变异发和分层法以提高微粒群算法种群多样性。引入这些方法可以改变算法的种群多样性，但是这些改变种群多样性因子的引入会增加算法的收敛速度。文献14依据不同优化问题而设计不同更新粒子状态的模型，还将其他的寻优机制融入到基本微粒群算法中以提高算法的收敛性能，对粒子更新策略适合解决离散问题。将遗传算法的寻优机制融合到微粒群算法当中，通过仿真实验，引入遗传算法的变异操作的微粒群算法具有较好收敛能力。文献15为克服算法的种群多样性会慢慢减弱的不足，在微粒群算法中加入了模拟退火的寻优思想以此来保证算法的种群多样性，提高了微粒群算法的收敛能力。连续性微粒群算法也应用于液压系统、汽车离合器设计，结构设计以及web数据库偏移定位仿真等领域16-19。2.3.2 离散型微粒群算法微粒群算法在连续函数的解空间求解具有较好收敛性能，研究微粒群算法的专家和学者，试图将其应用于求解组合优化问题，文献20用微粒群算法来求解组合优化问题，应用二进制进行编码，用0和1来不是表示离散型的位置，通过这些操作就将微粒群算法从求解连续性函数解空间拓展到离散空间中，这种基于离散型的微粒群算法在求解组合优化问题时，可以搜索到组合优化问题中的最好解，离散型微粒群算法求解取得较好效果21-23。微粒群算法还在数据挖掘，在数据挖掘这方面研究主要集中应用算法进行海量数据采集和优化挖掘24-26。生物信息27-29、图形学领域中也有着相当广泛的应用30-31。2.3.3 微粒群算法的改进1、 微粒群初始化 根据微粒群算法在赋初值时的位置，保证微粒群群体中的粒子运动具有正交性的运动轨迹，设计了一种具有正交特点且可以动态调整的微粒群算法，文献32用均匀分布的一组随机数来对多维空间进行优化寻优，通过与其他三种方式初始化的方法进行比较，其优化效果明显好于其他三种初始化。2、 邻域拓扑 文献33提出了一种动态等级树的邻域结构，该结构将寻优过程中的位置最好的粒子置于上层。文献34将微粒群算法的群体分成两个种群，即基于主群体和仆群体的微粒群算法，该算法将微粒群算法中的群体分成两个群体，一个群体进行寻优，然后另外一个群体在这个群体的基础上进行寻优，以此来搜索到全局最优解。3、 融合策略 通过构造微粒群算法模型，提出了算法的迭代公式，在对优化问题进行优化寻优过程中，微粒群算法中的粒子个体不断调整自身的位置和速度，以不断进化迭代的方式进行搜索寻优。迭代公式和个体对信息进行处理的能力决定着算法的收敛性能，微粒群算法通过速度迭代公式和位置迭代公式来不断调整粒子个体的运行速度和位置。文献35设置了微粒群种群感知活性因子来对微粒群群体进行感知，该群体感知因子可以感知群体当前所处的状态，然后根据所处的状态来调整算法的迭代方式和粒子个体的拓扑结构，函数测试表明，算法在处理函数优化问题时，可以找到函数优化问题的最好解。基本的微粒群算法仅仅粒子间的引斥力来实现搜索寻优，单纯使用一种引斥力会容易导致算法出现早熟收敛。基于算法不同寻优阶段需要采用不同的引斥力，文献36将物理学中引斥力引入到微粒群算法中以保持算法粒子的多样性，即算法在接近全局最优解附近时加大引力，将引力和斥力引入到算法中，函数测试实验表明，基于混合引斥力的混合型的微粒群算法收敛性能有所提高。沙成满,边丹,杨冬梅等人37将单纯形算法的寻优机理融入到基本微粒群算法中，设计了一种基于单纯形寻优策略的微粒群算法。将改进的微粒群算法应用于路堤地基整体稳定性能的评价，实验结果表明，基于单纯形的微粒群算法在搜索寻优的效率上有所提升。马立新,王继银,栾健等人38利用微粒群种群的适应度方差来评价微粒群个体的聚集情况，并通过扰动对群体个体进行变异和对迭代公式的惯性权值进行自适应调节，为测试算法的收敛性能，通过仿真实验，实验结果表明，改进的微粒群算法在求解电力系统无功优化问题中取得较好的收敛精度。文献39通过分析微粒群算法中寻优机理，分析了微粒群算法的稳定性的条件，再利用几何速度的稳定性分析了微粒群算法稳定性的充分条件，并得出了微粒群算法的稳定性条件，函数仿真实验表明，改进的算法寻优性能有所提升。岳颀40通过分析了微粒群算法的和神经网络非线性系统算法存在的缺陷，提出了将优化神经网络的联合化网络和参数初始化，通过系统辨识来测试算法的收敛性能，改进的微粒群算法提高了辨识精度并有效提高了算法的收敛速度，克服了算法早熟收敛现象。微粒群算法因出现早熟现象而陷入局部极值的不足，将模拟退火的寻优机制引入到基本的微粒群算法中41，该算法通过设置罚函数方式对优化问题的目标函数进行初步优化，在应用动态权值的策略，并将模拟退火和异常算法的选择过程进行有机的结合。仿真实验表明，融入模拟退火寻优思想的微粒群算法是比较成功的，改进的微粒群算法有很好的收敛能力。李杰,刘长意,任柯等人42将微粒群算法中粒子个体分成普通粒子和精英粒子，精英粒子将搜索过程中所处的最好位置信息共享给普通粒子，以加速微粒群算法收敛。通过函数仿真来测试算法的收敛能力，实验数据表明，融合协同算子的微粒群算法具有不错的收敛性能。2.4 本章小结本章详细介绍了优化算法及其分类，并对算法求解的全局最优解和局部最优解进行了描述，介绍了全局最优解的定义和局部最优解的定义。阐述了遗传算法和微粒群算法的寻优思想和起源。分连续性微粒群算法和离散型微粒群算法进行综述，并对微粒群算法在工程实践中的应用做了比较详细的综述。主要是对本文研究内容做一个前期的研究铺垫，综述算法的研究背景和现状。最后，并对算法的改进方面的研究做了详细阐述。工程硕士学位论文 3 参数调整与共轭梯度策略3 参数调整与共轭梯度策略通过分析微粒群算法的寻优策略以及对算法的改进。对本章微粒群算法的改进工作打下了基础。本章主要通过对微粒群算法的迭代公式和融入其它高效的寻优算法以克服微粒群算法不能够很好平衡算法全局收敛能力和局部收敛能力、收敛精度不高的缺陷。3.1 算法的参数3.1.1 参数设定微粒群算法的迭代公式相对比较简单，其主要参数有：惯性权重、初始位置、初始速度、两个加速常数和最大速度等。 1、最大速度值的确定。粒子飞行速度影响着算法的寻优能力，粒子飞行速度大那么算法的粒子可以在全盘的解空间中进行搜索，这意味着算法的全局搜索能力是相当强的。当粒子飞行速度比较小那么算法的粒子则在一个相对比较小的区域内进行优化搜索，而此时算法在一个比较小的邻域内搜索能力会很强，这就是算法的局部搜索能力加强。文献43通过仿真实验，得出取值在欲求函数空间左右。2、加速度参数值的确定。和是决定粒子个体向自身或其解空间中最优位置移动。文献44得出结论，在一般求解中。将设置加速常数取值为大于0正数的或是小于0的负数，并设置粒子群群体状态为聚集和发散状态。以此来减少算法出现早熟而过早收敛而陷入局部极值。3、惯性权重值的确定。在微粒群算法中引入惯性权重，下式表示速度迭代公式： （3.1）上式中表示为惯性权重。文献45通过测试实验得出结论，惯性权重可以设置为一个与迭代次数线性减小的值，将惯性权重取值为0.9慢慢的一路减小直到线性变为0.4。惯性权重是直接作用于粒子飞行的速度，通过迭代公式可以得出，惯性权重较大则影响粒子飞行速度也大。粒子个体运行的速度大则在函数的解空间中寻优的范围相对也就变大。这个对算法进行全局寻优是有益处的。当惯性权重较小，而一个较小的系数影响粒子运行速度就会小点。这对算法在一个小区域内寻优是有好处的。算法的寻优速度比较小就在附近小区域内进行搜索，这样有利于算法在一个范围相对狭窄的区域内寻优。因此，算法的局部搜索能力就会相应得到加强。3.1.2 惯性权重取值测试为了测试微粒群算法中惯性权重取值的不同，对算法的寻优能力的影响。以为例。其中惯性权重，学习因子，取不同的值，以此来测试各个参数对算法寻优精度的影响。(1)当，惯性权重w取值分别为、进行测试，通过仿真测试其寻优结果如下：图3-1 第(1)情况下寻优结果函数最优的适应度值（1）是：0.51752775253302函数最优的适应度值（2）是：0.28263222635368 (2)当，惯性权重，应用函数进行测试，通过仿真测试其寻优结果如下：图3-2 第(2)情况下寻优结果应用函数作为测试对象，来测试惯性权重取值大小对微粒群算法收敛精度以及收敛性能产生的影响。对，取值不同来验证惯性权重取值对算法收敛性的影响，应用函数优化问题来进行测试：通过应用函数优化进行测试，实验数据表明，惯性权重取值较大则微粒群算法在解空间内进行搜索，算法就可以在整个空间内寻优；当惯性权重取值比较小，惯性权重影响粒子运行的速度就会比较小，算法在范围较小的空间内进行搜索，有利于在局部小空间内搜索。粒子在寻优过程中需要平衡好算法的全局收敛能力和局部收敛能力，在算法运行之初，需要较强的全局收敛能力而当算法运行一段时间后，算法如继续保持恒定的寻优速度，可能会在全局最优解附近来回搜索，从而没有找到全局最好解。因此，算法在寻优的过程需要调整算法的全局和局部寻优能力。平衡策略是：即当算法在运行初期，算法在解空间中进行全局寻优，此时需要算法保持较强的全局收敛能力以在解空间中进行搜索寻优，而当算法运行到一定时期，算法渐渐的靠近全局最优解的区域，如果算法的惯性权重较大，容易导致算法错过全局最优解。此时对算法的惯性权重赋予一个较小的值，使得算法的寻优速度减小，保证算法局部寻优能力加强，以帮助