原文传递
改进的萤火虫算法及其在车辆路径规划中的应用与研究
| 论文题名： | 改进的萤火虫算法及其在车辆路径规划中的应用与研究 |
| 关键词： | 群智能算法;路径规划;萤火虫优化算法;车辆路径问题;NP-Hard问题 |
| 摘要： | 萤火虫优化算法（FireflyAlgorithm,FA）是群智能优化算法领域中新出现的一种优化算法，它是通过模拟自然界中的萤火虫发光特性及生物行为所设计的一种启发式优化方法。由于其搜索能力强、算法结构简单、参数调整量小等优点，受到了国内外学者的广泛关注。目前广泛应用于工程、计算机、管理、经济等领域。然而，和其他许多群智能优化算法一样，它具有一定的随机性。因此，萤火虫优化算法也难免会有一些常见的问题和缺陷。比如：算法容易陷入局部最优，后期收敛速度慢等，导致求解精度不高。 在分析了萤火虫优化算法的基础上，本文从不同角度提出了几种改进算法，并将其应用于车辆路径问题（VehicleRoutingProblem,VRP）。以下是本文的主要研究工作和成果： （1）本文在原始经典萤火虫算法的基础上做了参数的改进。首先是步长参数，为了平衡算法的全局搜索能力和局部搜索能力，本文采用了步长随迭代次数逐渐递减的动态步长策略，并在此基础上，加入了一个控制结构，在控制结构中，利用当前一代最优个体与上一代最优个体之间的目标函数值的差值变化来决定是否减小步长以适应下一代的进化需要。如果两者之间的目标函数值相差不大，则本文认为算法陷入了局部最优，此时取较大的步长来帮助算法跳出局部最优；如果两者相差较大，那么这两代之间的位置相差比较远，有可能跳过了全局最优点，那么取较小的步长来提高算法的局部搜索能力。 （2）本文对于萤火虫算法的吸引机制也进行了相应的调整。由于经典萤火虫优化算法的初始吸引力为1，本文经过数学推导发现，如果初始吸引力设为1的话，萤火虫群体会快速收敛到一个局部最优解，这大大减少了种群的多样性。因此，在大量实验及前人经验的基础上，本文把初始吸引力设为0.4。这在一定程度上避免了算法陷入局部最优，使得萤火虫种群按照一定比例趋向于最优解，提高了种群多样性，增加了算法的搜索能力。 （3）最后，本文将改进的萤火虫优化算法应用到带时间窗的车辆路径问题中（VRPTW）。VRP是一个NP-Hard问题，且其研究的对象是离散化的。因此，本文重新对萤火虫个体进行了离散化编码，并对实验中可能产生的小数进行了整数化和越界处理。通过以上方法使得萤火虫个体有效地表达了问题的解，并利用国际上公认的Solomon测试集对算法进行了测试，测试结果验证了算法的有效性和高效性。 |
| 作者： | 宋甫祺 |
| 专业： | 软件工程 |
| 导师： | 汪靖 |
| 授予学位： | 硕士 |
| 授予学位单位： | 江西财经大学 |
| 学位年度： | 2021 |
检索历史
应用推荐
