蚁群算法的研究及其在路径寻优中的应用

发布时间：2020-05-23 22:38

【摘要】：当今全球的汽车保有量一直保持着极高的增长速度,越来越多的人依赖私家车出行,这不仅为道路运输带来了巨大的负担,还造成了严重的环境污染。路径寻优技术通过对路径的合理规划,不仅能够在一定程度上降低通行的时间成本和经济成本,有效地缓解机动车对空气带来的污染,为出行者提供一个安全、绿色的出行环境,还能够提高交通利用率,减少交通拥堵现象的发生。蚁群算法作为经典的智能优化算法,已经在路径寻优技术甚至智能交通系统中得到广泛应用,但是仍存在运算效率不高、优化效果不好、性能不够稳定等明显不足。本文对蚁群算法及其在路径寻优中的应用进行了研究。首先描述了基本蚁群算法的原理和特征,详细分析了基本蚁群算法的优缺点以及它们出现的原因。其次对蚁群算法中蚂蚁数量、信息素挥发系数、信息启发因子和期望启发因子四个重要参数对算法性能的影响进行了分析,通过实验得到了它们合理的取值范围;研究了期望函数自适应调整、带蚂蚁死亡策略、带惩-赏机制和基于鸟群算法实现对初始信息素优化的改进蚁群算法,提高了算法在不同使用环境下的寻优能力。然后研究了结合以上四种改进策略的复合改进蚁群算法,并且引入路况参考系数,将实时交通路况纳入对道路优劣的评判因素中,实现了复合改进蚁群算法在车辆导航中的应用。最后,针对蚁群算法局部路径规划性能弱的问题,研究了一种带扇形搜索策略的改进蚁群算法,通过对搜索区域的合理划分,提高蚁群算法的局部路径规划能力。仿真实验表明,相比基本蚁群算法而言,期望函数自适应调整的改进蚁群算法具备更强的局部搜索能力,并且收敛速度更快,路径优化的质量更高。搜索环境中存在带有凹陷空间的障碍物时,带死亡策略的改进蚁群算法对路径的搜索能力远远高于基本蚁群算法,而在大型迂回道路中,带惩-赏策略的蚁群算法能够得到更短的路径。通过与蚁群算法、鸟群算法、粒子群算法的对比,带初始信息素优化策略的蚁群算法具备较高的运算效率和路径优化能力,并且在障碍物分布复杂的大型搜索环境中优势更加明显,而复合改进蚁群算法在存在多种类型障碍物的环境中拥有较高的寻优能力。在环境未知的情况下,扇形搜索策略提高了蚁群算法的路径寻优性能,在障碍物未知的条件下能够获得更短的路径,更适合在车辆的自主避障中使用。
【图文】：

虚拟力场,作用原理

局部最优解的寻优算法[26]。SA 是一种概率型启发式算法，能够通过限制条件下的随机决策解决复杂的组合优化问题。SA 随机搜索技术模拟了金属从高温冷却到最后冻结，其晶体结构从无序到有序的过程，并在内能从较高值降到最低值的平衡态中获得了寻找最小值的方法。在搜索过程中，SA 不仅接受较好值，还有一定概率接受较差值，通过这种办法使得算法拥有了跳出局部最优的可能性。因此，SA 有较强的有效性和可靠性。但是，它也存在收敛缓慢、随机性太强等不足。（2）人工势场法人工势场法（APF）主要模拟了物体之间的引力和斥力对可移动物体运动轨迹的影响。APF 中，目标点、障碍物和运动体之间存在相互作用的引力和斥力，其中，目标点对运动体有吸引作用，其吸引力场覆盖整个地图范围，而障碍物对运动体有排斥作用可以让运动体远离它们附近的位置。两种力的大小均与物体之间的距离成反比，运动体在它们的控制下绕过障碍物向目标点靠近。图 1-1 表示了 APF 中虚拟力场的作用原理。APF 的优点是原理简单，生成的路径平滑度较高，缺点是容易出现早熟现象。

食物源,巢穴,直线路径

蚁群算法在人工智能[33-39]、交通运输[40-41]、医疗救助、国防军事[42]等行业都发挥着重要的作用。本章首先介绍蚁群算法的原理和数学模型，然后分析蚁群算法的系统学特征及存缺陷，最后针对四个重要参数对算法性能的影响进行研究，找出它们合理的取值范.1 蚁群算法的原理正如现实中所看到的，蚂蚁是一种群居动物，它们不会单独出行，，无论是觅食还息，都以团体的形式实现。相比其他群居动物而言，蚂蚁又很特殊，它们的视力范常小，仅能看到相当近距离内的物体。即便如此，蚂蚁在群体活动时仍然能够在相间传递信息，达到团队协作的效果，并且总是延直线前进，从巢穴出发以最短的时达食物源。图 2-1 表示了在没有障碍物的情况下，蚁群会径直往返于巢穴和食物源。
【学位授予单位】：太原理工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP18

【参考文献】