DNA-蚁群算法在车辆路径优化问题中的应用

2015-07-19湖南人文科技学院湖南娄底417100

中国新技术新产品 2015年5期

刘波（湖南人文科技学院，湖南娄底 417100）

刘波
（湖南人文科技学院，湖南娄底 417100）

摘要：随着我国经济和科技的发展，物流配送已经成为促进经济发展的重要环节，在物流的配送过程中如何使用车辆路径的优化问题是长期困扰人们的难题，随着群智能算法发展的今天，已经有多种算法能够应用到车辆路径的最优化模拟的建立和计算中。本文通过对蚁群算法在路径最优模型的过程中的优缺点进行介绍。

关键词：蚁群算法；最优优化；DNA算法

通过使用蚁群算法能够建立起车辆路径问题的模型，来解决长期困扰着人们的车辆路径问题，但是在使用过程中发现，蚁群算法在建立模型的过程中会出现过早收敛局部最优解以及收敛时间周期长等缺点，同时在使用蚁群算法时需要对参数进行相应的选用，不然，为解决这一问题，通过使用DNA算法的精髓与蚁群算法向结合，在原有蚁群算法的基础上进一步发展，形成了DNA-蚁群算法。通过对改进型的蚁群算法进行了系统测试，发现其建立解决车辆路径优化问题的速度大幅提升，并且将原先蚁群算法存在的较早收敛于局部最优解以及收敛速度较慢等问题加以解决。

1 蚁群算法简介

蚁群算法是一种模拟蚂蚁觅食行为的模拟优化算法. 蚁群算法是一种基于种群的启发式仿生进化系统。蚁群算法最早成功应用于解决著名的旅行商问题（TSP），该算法采用了分布式正反馈并行计算机制，易于与其他方法结合，而且具有较强的鲁棒性。蚁群算法具有如下一些优点：①通用性较强，能够解决很多可以转换为连通图结构的路径优化问题；②同时具有正负反馈的特点，通过正反馈特点利用局部解构造全局解，通过负反馈特点也就是信息素的挥发来避免算法陷入局部最优；③有间接通讯和自组织的特点，蚂蚁之间并没有直接联系，而是通过路径上的信息素来进行间接的信息传递，自组织性使得群体的力量能够解决问题。但是，基本蚁群算法也存在一些缺点：①从蚁群算法的复杂度来看，该算法与其他算法相比，所需要的搜索时间较长；②该算法在搜索进行到一定程度以后，容易出现所有蚂蚁所发现的解完全一致这种“停滞现象”，使得搜索空间受到限制。

蚁群算法原理图如图1、图2、图3和图4所示。

图1蚂蚁正常行进，突然环境改变，增加了障碍物

图2蚂蚁以等同概率选择各条路径，较短路径信息素浓度高，选择该路径的蚂蚁增多

图3蚂蚁选路过程示例

图3蚂蚁最终绕过障碍物找到最优路径

2 最优路径所需研究的问题

最优路径所需要研究的问题主要是：在物流配送环境，在已知客户的位置、货物的种类和装量的条件下，物理配送人员在给定的运力条件下，如何使每一辆运输车辆从同一起点出发在完成所有运输任务的条件下能够使用最少的车辆和行驶里程来完成配送任务，在这一过程中车辆的行驶路线不能重复。

3 蚁群算法中参数对于算法的影响

在蚁群算法中参数取值的不同会对算法的效率产生重大的影响，Q参数会对算法的收敛速度产生影响，如果其值过大将会使算法收敛于局部最小值，如果过小将会影响算法的收敛速度，而随着问题规模的扩大Q值也会随着扩大，α值大的小表明留在每个结点上的信息量受重视的程度，其值越大，蚁群选择以前选过的点的可能性越大，但是如果值过大会使搜索过早陷入局部最小点，β的大小表明启发式信息受重视的程度，如果值越大表明选择路径时越依赖启发式信息，ρ值表明挥发程度，对收敛的结果有着重大的影响，经过试验表明，在取值过大或者是过小的情况下运行的结果都不理想，其值一般去在0.5左右。

4 DNA-蚁群算法在车辆最优路径中的问题求解

以上对蚁群算法的原理以及参数对于算法的影响，可以看出蚁群算法在求解车辆优化路径中的优越性，但是在试验过程中发现，蚁群算法存在着收敛于局部最优解且收敛速度较慢等问题。使用DNA算法能够解决这一难题，DNA似乎脱氧核糖核酸的简称，其主要是由核苷酸组成，而DNA通常是由2条核苷酸组成，形成了双螺旋结构。DNA是由A、T、C、G组成的，在DNA算法中使用A、T、C、 G交叉配对且用一定的概率实现两点交叉的方法，意思就是说通过对一段DNA片段更换任意一部分核苷酸来形成新的DNA链，DNA算法具有良好的替换性，同时采用DNA算法与蚁群算法进行结合来提高了蚁群算法中对于参数的控制，提高了算法的效率，其具体的DNA-蚁群算法的求解步骤如下：（1）使用DNA算法来优化参数，建立起蚁群算法中参数的参数矩阵，（2）使用DNA算法对这些参数进行变异交叉对比，（3）使用蚁群算法进行车辆最优路径的模型建立以及问题求解。（4）在试验时选用不同的参数进行变异交叉对比来选用合理的蚁群算法参数。