1、I硕士学位论文基于共轭梯度的微粒群算法及在车辆路径优化中的应用Particle Swarm Optimization based on conjugate gradient and is applied to Vehicle Routing Optimization 学科专业： 工程专业学位专业领域： 软件工程作者姓名 ：指导教师 ：中南大学软件学院2017 年 5 月II中图分类号 TP311.5 学校代码 10533 UDC 004.11 学位类别 专业学位 硕士学位论文基于共轭梯度的微粒群算法及在车辆路径优化中的应用Particle Swarm Optimization based on
2、 conjugate gradient and is applied to Vehicle Routing Optimization 作者姓名：学科专业： 工程专业学位专业领域： 研究方向：软件工程软件工程技术学院（系、所）： 软件学院指导教师： )副指导教师：论文答辩日期 答辩委员会主席 中 南 大 学2017 年 5 月 I学位论文原创性声明本人郑重声明，所呈交的学位论文是本人在指导教师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他教育机构的学位或证书而使用过的材料。与我共同工
3、作的同志对本研究所作的贡献均已在论文中作了明确的说明。申请学位论文与资料若有不实之处，本人承担一切相关责任。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者和指导教师完全了解中南大学有关保留、使用学位论文的规定：即学校有权保留并向国家有关部门或机构送交学位论文的复印件和电子版；本人允许本学位论文被查阅和借阅；学校可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用复印、缩印或其它手段保存和汇编本学位论文。保密论文待解密后适应本声明。作者签名： 指导教师签名 日期： 年 月 日 日期： 年 月 日II基于共轭梯度的微粒群算法及在车辆路径优化中的应用摘要：微粒群算法是
4、通过模拟鸟群搜索食物而进行设计的。算法寻优机理是粒子个体间信息交互和协作来进行寻优，通过迭代而搜索到全局最优解。微粒群算法的算法结构简单、全局搜索能力强，已被广泛应用于优化控制领域。本文主要工作是对微粒群算法进行改进研究并将其应用于车辆路径优化问题，研究内容有：1、针对微粒群算法因惯性权重恒定而出现局部寻优能力不高，本文应用函数优化问题来测试惯性权重对算法收敛能力的作用。通过在惯性权重中引入动态调整参数，以此来调节算法的全局和局部寻优能力；针对算法在运行后期出现种群多样性减弱而导致求解精度不高的不足，在算法中引入共轭梯度法以增强算法的搜索精度。通过在惯性权重中引入动态调整参数并融入共轭梯度策略
5、，设计了改进的的微粒群算法。2、为验证本文改进算法的收敛性能，用函数来测试基于参数调整共轭梯度的微粒群算法的性能，函数仿真实验表明，该算法在收敛精度和收敛速度上有所提高。3、最后，以车辆路径优化问题作为研究对象，将本文改进的微粒群算法来求解车辆路径优化问题，实验结果表明，该算法可以找到最优路径，收敛效果比较好。图 12 副，表 6 个，参考文献 61 篇关键词：微粒群算法；共轭梯度法；函数优化；车辆路径优化问题分类号：TP311.5IIIParticle Swarm Optimization based on conjugate gradient and is applied to Vehic
6、le 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 implemen
7、t, 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、 Acc
8、ording 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 cap
9、abilities 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 improvem
10、ents.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
11、、 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； Con
12、jugate Gradient Algorithm； Function Optimization； Vehicle Routing ProblemClassification TP311.5IV目 录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 离散型微粒群
13、算法 .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 函数优化问题 .26V4.2 函数优化测试 .274.2
14、.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 绪论 11 绪论优化问题是控制科学
15、和运筹学领域中一个重要研究课题，国民经济和生产实践中有着广泛应用。优化问题的求解有两种，即确定性和不确定性。确定性的算法要求优化问题的目标函数可导，寻优结果与初值有关且不能够解决大规模优化问题。而不确定性算法就是当前主流优化算法即模拟生物的智能优化算法，具有寻优速度快、收敛精度高且对目标函数要求不高的特点。设计一种收敛性能高效的智能优化算法是优化领域的研究热点。1.1 研究背景 及意义优化技术是为了解决各种组合优化问题和工程实践中的优化问题而产生的一门以数学为基础的科学。通过对优化问题进行建模，通过对建模函数进行优化来找到目标函数的最优值。在经济生产中，有许多问题可以看出为优化问题。在经济决策
16、中求利润最大化问题，货物配送路径最小问题。这些都是优化问题，通过对优化问题进行建模，形成了目标函数，从而应用优化进行求解以求得目标函数的最值。随着技术的进步，经济生活中越来越多的问题可以通过数学方法转换为优化问题，最终通过优化技术来加以解决。因此，优化问题和优化技术越来越受到科学家的重视。社会进步，生产力的发展，优化问题变得越来越棘手，表现在优化问题的参数多、规模大而且由传统的线性优化问题发展为非线性优化问题。解决优化问题的优化技术，也变得形式多样。传统优化算法主要依靠按步进行迭代优化，当优化问题规模变大，传统优化方法显得力不从心。典型的TSP 问题当规模达到 200 多个城市时，传统优化算法
17、几乎无法求解出问题的解。求解这类优化问题需要更加高效的优化算法。因此，具有智能特点的优化算法就产生了。具有智能特点的优化算法在求解大规模、非线性优化问题时具有很强的优势。这类算法可以在比较短时间内收敛到全局最好解。所以迅速发展起来。在自然界中生物系统社会系统中，鱼群、鸟群、蜂群觅食行为，这些群体是具有一定群体智能特点的称为“群智能”(swarm intelligence)1。具有智能特性的优化算法一般是通过赋初值,即在解空间中给定一个初始点,然后按照一定寻优规则进行搜索。一般是带有概率性质的寻优而有别于传统优化算法的逐点搜索，这样就大大减少了寻优时间。算法在更新自身状态比较高效，所以工程硕士学
18、位论文 1 绪论 2能够搜索到全局的最好解。这类具有智能特点的优化算法在解决大规模、非线性优化问题具有先天优势。主要表现在迅速收敛、效率高。这类智能优化算法有：人工蜂群算法、人工神经网络等。这类算法主要是模拟自然界的生物行为而实现进化寻优，因此也叫做群智能优化算法。这类算法是按照概率寻优，在搜索全局最优解的时候也是具有概率性的。优化技术在工程领域，工业控制和经济管理等领域都是一个十分重要课题。微粒群优化算法 2 (Particle Swarm Optimization, PSO)，这个算法是由 Kennedy和 Eberhart 两个博士对鸟群在无序的情况下搜索到食物源的寻优策略进行研究，即鸟
19、群在搜索食物时，时而聚集、时而分散，鸟儿不断调整自身运行速度和飞行的位置。最后，这个群体一起找到食物源。这两个博士经过长期研究和论证，在 1995 年设计了基于鸟群觅食寻优思想的仿生算法，即微粒群算法，微粒群算法在工业控制、模式识别、电力系统优化、经济管理、生物医学、组合优化问题 TSP 等领域都有着广泛应用。传统的优化算法有单纯形法和共轭梯度法，这类算法求解规模小的优化问题，表现出较好的收敛性能。现代的优化算法即近来提出的智能优化算法，如：遗传算法、人工蜂群算法等。现代优化算法在解决大规模优化时，可以有效的找到的全局最好解。随着生产力的发展，工程领域中的优化问题越来越常见，参数也越来越多，复
20、杂度越来越大。因此，通过研究寻优精度高、收敛速度快的群智能优化算法来解决大规模复杂的优化问题具有非常有用的价值。物流已被视为企业的第三个利润的来源，它是企业降低成本的主要的工具。实现最短距离的物流配送，对降低企业成本有着重要作用。因此，研究车辆路径优化问题对物流企业是非常有帮助的。车辆路径优化问题在物流货物配送中应用相当广泛，是一种典型的 NP 难问题。对车辆路径优化问题进行转化就可以将车辆路径优化问题变为最优化问题。即在一定的约束条件下，对所有有货物需求的客户进行遍历，求其最短的配送路径。车辆路径优化的目标函数就是求配送路径的最小值。对车辆路径优化问题的求解的优化算法有：遗传算法、人工蚁群算
21、法及微粒群算法等一些群智能优化算法。目前对车辆路径优化问题求解的智能优化算法主要是以上几种单一的智能优化算法，单纯一种智能优化算法在求解车辆路径优化问题时候存在一些缺陷和局限性。即在当车辆路径优化问题中配送客户的数量比较多、规模大时，单一的智能优化算法表现出收敛精度不高、收敛速度较慢的缺陷。如何提高求解车辆路径优化问题智能优化算法的求解精度和收敛速度，是车辆路径优化问题中一个非常值得研究的课题。对单一的智能优化算法进行改进以提高求解车辆路径优化问题收敛速度和求解工程硕士学位论文 1 绪论 3精度是非常必要的，因此，对智能优化算法进行改进研究可以极大降低企业的物流成本，在物流配送等优化领域具有一
22、定价值。在求解车辆路径优化问题时，各个群智能优化算法寻优优缺点各有不同，具体如下表 1-1 所示：表 1-1 各种算法求解车辆路径优化问题的优缺点智能优化算法 特点 不足模拟退火算法算法鲁棒性强且算法的全局寻优能力较强，算法机理易于理解算法收敛性能比较差，运行效率不高且收敛速度比较慢遗传算法遗传算法的并行性比较强且算法的全局寻优能力较强算法收敛能力不强，出现早熟而找不到全局最优解。人工神经网络算法 算法实现较为简单且算法运行速度快 算法收敛精度不高，极易陷入局部最优值蚁群算法蚁群算法的算法自适应能力比较强，算法的正反馈机制和群体个体的组织能力较强算法的收敛性能较差、收敛速度比较慢且容易陷入局部
23、最优值微粒群算法微粒群算法迭代公式比较简单、容易实现且算法比较容易实现，算法的收敛速度也比较快算法中的参数依赖经验值，参数的设置影响算法的收敛能力，不好控制1.2 本文主要的研究内容本文阐述了微粒群算法的算法机理和算法实现，分析了微粒群算法的迭代公式和惯性权重等参数，惯性权重可以调节迭代公式的速度，惯性权重取值大小直接决定粒子个体飞行的速度，飞行的速度大就影响算法的在解空间中寻优范围，速度小就有利于算法在某个小区域内寻优，惯性权重会影响粒子个体在寻优过程的速度，进而对微粒群算法的全局收敛能力和局部收敛能力产生影响。微粒群算法的惯性权重恒定，导致算法在寻优后期的基本寻优能力不强而使算法错过全局最优解，从而导致算法陷入局部最优解。针对微粒群算法在寻优后期因惯性权重恒定而导致算法的不能够很好平衡全局寻优和局部寻优能力，通过引入一个动态参数来动态调整算法的惯性权重。以控制好算法在解空间的全局寻优的能力以及在最优解附近的局部寻优能力。针对微粒群算法在寻优后期出现种群多样性减弱而找不到最好解，在算法加入了共轭梯度法进行搜索寻优。应用函数优化问题啦测试基于参数调整策略共轭梯度的微粒群算法的收敛性能
