论文部分内容阅读
摘 要： 研究在不使用局部搜索情况下参数组合对改进型蚁群算法的影响。以带时间窗的车辆路径问题为例，针对基于最大最小蚁群算法的改进蚁群算法中的五个参数，运用均匀设计法对最优参数配置问题进行了研究。仿真实验表明改进的蚁群算法效果明显，能有效解决Solomon数据集中的R类和RC类问题，且具有较强的鲁棒性。对最优参数的局部调整没有明显提高算法获取最优解能力的问题，分析了其可能的原因。
关键词： 最大最小蚁群算法； 均匀设计； 有时间窗车辆路径问题； Solomon数据集
中图分类号：TP301.6 文献标志码：A 文章编号：1006-8228（2014）06-53-03
0 引言
车辆路径问题（Vehicle Routing Problem，VRP）属于组合优化问题，其理论涉及到运筹学、管理学、交通运输、计算机应用等多个学科。VRP问题中加入节点可访问的时间窗约束即成为有时间窗车辆路径问题（Vehicle Routing Problem with Time Windows， VRPTW）。由于现实生活中很多问题可以归结为VRPTW，因此VRPTW的研究受到学术界的广泛重视。
蚁群算法虽然具有较强鲁棒性，但存在搜索速度慢和容易出现停滞的缺点。为此，学术界除了引进其他算法来加强其搜索能力外，还从蚁群算法本身的参数设置角度来克服其弱点，目前有三种方式。第一种是用其他算法来自动筛选参数，例如刘利强[1]等利用粒子群优化算法，将离子当前位置作为算法参数来优选ACS算法的参数。第二种是动态调整蚁群算法参数，如蔺媛媛等[2]采用自适应调整q参数，刘武阳等[3]采用自适应调整信息素增量和信息素挥发率都属于此类。第三类是通过研究参数与最优解的关系，如王明芳[4]通过数据仿真来研究全局最优解与参数的关系，甘屹[5]则是通过正交优化实验来研究算法之间的交互作用以提高求解精度和收敛速度。
本文通过基于最大最小蚁群算法（MMAS）的改进来研究参数设置在有时间窗车辆路径问题上的应用。通过均匀设计法，找出参数的最优组合。对Solomon标准数据集的计算，验证了算法和参数设置的有效性。
1 有时间窗车辆路径问题的定义
VRPTW的一般定义如下：从某一物流中心用多台配送车辆从多个客户取货，每个客户的位置和需求量和需求时间一定，每个客户只能由一台车辆服务一次，要求合理安排车辆配送路线，使目标函数得到最优，即在不违背约束条件下所用车辆数最少和行走路线长度最短。本文将最小化车辆数量作为第一目标，最小化车辆行驶路线长度作为第二目标。
2 最大最小蚁群算法及其在有时间窗车辆路径问题中的应用
MMAS对AS的关键改进在于将路径上的信息素浓度限定[τmin，τmax]之间，这较好地避免了搜索陷入局部最优解。因为在搜索过程中，随着信息素的挥发和累积，某些路径上的信息素浓度会远远高于其他路径，从而导致搜索过早停滞。
2.1 状态转移概率
蚂蚁在选择下一个节点时，在满足容量约束和时间窗约束下，需要考虑如下三个因素：①通往下个节点的路径长度以及路径上的信息素浓度[6]；②时间窗因素的择优性[6]，由下个客户j的时间窗宽度和所在客户i到达下个客户j的时间等因素决定，这种择优性的优先原则为，需等待时间较短优先原则和时间窗较小优先原则；③基于Wissner-Gross，A.D.[7]的事物倾向于向自由度大的方向进化的理论，潜在下一可行节点数多的节点有优先权。
其中，Ω={vj|vj为可被访问的客户}，v0为配送中心。为客户j的时间窗；tij为从客户i到达客户j的时间（等于开始为客户i服务的时刻+客户i所需服务时间+从客户i到客户j的时间）；VCij为客户j的下一潜在可被访问客户数，由所有满足LTi+Si+Lij?LTj的客户组成。τij为vi和vj之间路径上的信息素；ηij为路径可见性，这里ηij=1/dij，dij为客户i与j之间路径长度。α和β为路径上信息素与路径可见性的权重。
2.2 动态启发式信息更新
因为VRPTW问题的第一目标值是最小化车辆数量，因此为强化改进蚁群算法构建最小化车辆数量路径的能力，本文对上面状态转移概率中的信息素和路径长度启发式做如下改变：
该式中，antTypei为信息素更新的蚂蚁类型，rand（）为随机值，t为信息素更新随机因子。因为ηij为路径值启发式信息，因此将其以t的概率增加蚂蚁构建更优的车辆数量的解集合。
3 数值试验分析
3.1 均匀设计优化参数
蚁群算法参数优化是一个多因素多水平优化设计问题，对于参数设定不可能遍历所有可能。利用均匀设计和均匀设计表，选取具有代表性的样本进行试验，能极大减少试验的次数，而且能取得较好的参数配置。
本文的改进蚁群算法有五个需要优化的算法参数：①信息素权重α；②路径可见性权重β；③信息素挥发率ρ；④最好可能信息素量PBest；⑤信息素更新随机因子t。
参照原始MMAS取值，并经过逐步改进，这里首先选取以下参数组合进行初步计算：α=1；β=2；ρ=0.02；PBest=0.05；t=0.5。
通过比较原始MMAS结果和参数未优化前结果（见表4的4-7列），可知改进的蚁群算法在C类数据集上不具有优势，在R类和RC类数据集上比较有优势。为最大限度获取解的优化，本文选取R103和RC104进行参数优化试验，同时确定试验的参数范围为：α∈（0，2]；β∈[1，3]；ρ∈[0.01，0.03]；PBest∈[0.04，0.06]；t∈[0，1]。
根据因素数量，可以选择、和，从它们的使用表可以查到，当s=5时，它们的偏差分别为0.2414，0.4286和0.2272。因此这里选择作为本文的均匀设计表。根据该表，对各因素取12个水平如表1。
3.2 实验结果及分析
受限于篇幅，我们只将每类数据的前三项结果列出，见表4。
4 结束语
研究表明，本文对最大最小蚁群算法的改进效果明显，由于蚁群算法本身的鲁棒性，加上初期算法参数的逐步改良，后期蚁群算法参数在一定范围内的波动不会明显改变计算结果。同时，蚁群算法受到两大因素的制约，一是必须达到运能和时间窗瓶颈才能返回，二是时间窗大的节点拥有更为灵活的组合方式。这使得局部搜索算法成为构造高效蚁群算法的必要组成部分，这也是我们下一步研究的关键性问题。此外，尽量改善C类问题的计算效能也是值得研究的问题。
参考文献：
[1] 刘利强，戴运桃，王丽华.蚁群算法参数优化[J].计算机工程，2008.34（11）：208-210
[2] 蔺媛媛，朱耀庭，贾雯.蚁群算法的参数优化[J].天津工程师范学院学报，2009.19（3）：30-33
[3] 刘武阳，于世伟，陈英武等.带有动态参数决策模型的改进蚁群优化算法[J].科学技术与工程，2010.10（2）：435-440
[4] 付明，王丽芳.蚁群算法中最优参数设置研究[J].科技信息，2010.20：765-766
[5] 甘屹，李胜.蚁群算法的参数优化配置研究[J].制造业自动化，2011.33（3）：66-69
[6] 万旭，林建良，杨晓伟.改进的最大最小蚂蚁算法在有时间窗车辆路径问题中的应用[J].计算机集成制造系统，2005.11（4）： 572-576
[7] Wissner-Gross，A.D.， C.E.Freer. Causal Entropic Forces[J].PhysicalReview Letters 110，168702（2013）.
关键词： 最大最小蚁群算法； 均匀设计； 有时间窗车辆路径问题； Solomon数据集
中图分类号：TP301.6 文献标志码：A 文章编号：1006-8228（2014）06-53-03
0 引言
车辆路径问题（Vehicle Routing Problem，VRP）属于组合优化问题，其理论涉及到运筹学、管理学、交通运输、计算机应用等多个学科。VRP问题中加入节点可访问的时间窗约束即成为有时间窗车辆路径问题（Vehicle Routing Problem with Time Windows， VRPTW）。由于现实生活中很多问题可以归结为VRPTW，因此VRPTW的研究受到学术界的广泛重视。
蚁群算法虽然具有较强鲁棒性，但存在搜索速度慢和容易出现停滞的缺点。为此，学术界除了引进其他算法来加强其搜索能力外，还从蚁群算法本身的参数设置角度来克服其弱点，目前有三种方式。第一种是用其他算法来自动筛选参数，例如刘利强[1]等利用粒子群优化算法，将离子当前位置作为算法参数来优选ACS算法的参数。第二种是动态调整蚁群算法参数，如蔺媛媛等[2]采用自适应调整q参数，刘武阳等[3]采用自适应调整信息素增量和信息素挥发率都属于此类。第三类是通过研究参数与最优解的关系，如王明芳[4]通过数据仿真来研究全局最优解与参数的关系，甘屹[5]则是通过正交优化实验来研究算法之间的交互作用以提高求解精度和收敛速度。
本文通过基于最大最小蚁群算法（MMAS）的改进来研究参数设置在有时间窗车辆路径问题上的应用。通过均匀设计法，找出参数的最优组合。对Solomon标准数据集的计算，验证了算法和参数设置的有效性。
1 有时间窗车辆路径问题的定义
VRPTW的一般定义如下：从某一物流中心用多台配送车辆从多个客户取货，每个客户的位置和需求量和需求时间一定，每个客户只能由一台车辆服务一次，要求合理安排车辆配送路线，使目标函数得到最优，即在不违背约束条件下所用车辆数最少和行走路线长度最短。本文将最小化车辆数量作为第一目标，最小化车辆行驶路线长度作为第二目标。
2 最大最小蚁群算法及其在有时间窗车辆路径问题中的应用
MMAS对AS的关键改进在于将路径上的信息素浓度限定[τmin，τmax]之间，这较好地避免了搜索陷入局部最优解。因为在搜索过程中，随着信息素的挥发和累积，某些路径上的信息素浓度会远远高于其他路径，从而导致搜索过早停滞。
2.1 状态转移概率
蚂蚁在选择下一个节点时，在满足容量约束和时间窗约束下，需要考虑如下三个因素：①通往下个节点的路径长度以及路径上的信息素浓度[6]；②时间窗因素的择优性[6]，由下个客户j的时间窗宽度和所在客户i到达下个客户j的时间等因素决定，这种择优性的优先原则为，需等待时间较短优先原则和时间窗较小优先原则；③基于Wissner-Gross，A.D.[7]的事物倾向于向自由度大的方向进化的理论，潜在下一可行节点数多的节点有优先权。
其中，Ω={vj|vj为可被访问的客户}，v0为配送中心。为客户j的时间窗；tij为从客户i到达客户j的时间（等于开始为客户i服务的时刻+客户i所需服务时间+从客户i到客户j的时间）；VCij为客户j的下一潜在可被访问客户数，由所有满足LTi+Si+Lij?LTj的客户组成。τij为vi和vj之间路径上的信息素；ηij为路径可见性，这里ηij=1/dij，dij为客户i与j之间路径长度。α和β为路径上信息素与路径可见性的权重。
2.2 动态启发式信息更新
因为VRPTW问题的第一目标值是最小化车辆数量，因此为强化改进蚁群算法构建最小化车辆数量路径的能力，本文对上面状态转移概率中的信息素和路径长度启发式做如下改变：
该式中，antTypei为信息素更新的蚂蚁类型，rand（）为随机值，t为信息素更新随机因子。因为ηij为路径值启发式信息，因此将其以t的概率增加蚂蚁构建更优的车辆数量的解集合。
3 数值试验分析
3.1 均匀设计优化参数
蚁群算法参数优化是一个多因素多水平优化设计问题，对于参数设定不可能遍历所有可能。利用均匀设计和均匀设计表，选取具有代表性的样本进行试验，能极大减少试验的次数，而且能取得较好的参数配置。
本文的改进蚁群算法有五个需要优化的算法参数：①信息素权重α；②路径可见性权重β；③信息素挥发率ρ；④最好可能信息素量PBest；⑤信息素更新随机因子t。
参照原始MMAS取值，并经过逐步改进，这里首先选取以下参数组合进行初步计算：α=1；β=2；ρ=0.02；PBest=0.05；t=0.5。
通过比较原始MMAS结果和参数未优化前结果（见表4的4-7列），可知改进的蚁群算法在C类数据集上不具有优势，在R类和RC类数据集上比较有优势。为最大限度获取解的优化，本文选取R103和RC104进行参数优化试验，同时确定试验的参数范围为：α∈（0，2]；β∈[1，3]；ρ∈[0.01，0.03]；PBest∈[0.04，0.06]；t∈[0，1]。
根据因素数量，可以选择、和，从它们的使用表可以查到，当s=5时，它们的偏差分别为0.2414，0.4286和0.2272。因此这里选择作为本文的均匀设计表。根据该表，对各因素取12个水平如表1。
3.2 实验结果及分析
受限于篇幅，我们只将每类数据的前三项结果列出，见表4。
4 结束语
研究表明，本文对最大最小蚁群算法的改进效果明显，由于蚁群算法本身的鲁棒性，加上初期算法参数的逐步改良，后期蚁群算法参数在一定范围内的波动不会明显改变计算结果。同时，蚁群算法受到两大因素的制约，一是必须达到运能和时间窗瓶颈才能返回，二是时间窗大的节点拥有更为灵活的组合方式。这使得局部搜索算法成为构造高效蚁群算法的必要组成部分，这也是我们下一步研究的关键性问题。此外，尽量改善C类问题的计算效能也是值得研究的问题。
参考文献：
[1] 刘利强，戴运桃，王丽华.蚁群算法参数优化[J].计算机工程，2008.34（11）：208-210
[2] 蔺媛媛，朱耀庭，贾雯.蚁群算法的参数优化[J].天津工程师范学院学报，2009.19（3）：30-33
[3] 刘武阳，于世伟，陈英武等.带有动态参数决策模型的改进蚁群优化算法[J].科学技术与工程，2010.10（2）：435-440
[4] 付明，王丽芳.蚁群算法中最优参数设置研究[J].科技信息，2010.20：765-766
[5] 甘屹，李胜.蚁群算法的参数优化配置研究[J].制造业自动化，2011.33（3）：66-69
[6] 万旭，林建良，杨晓伟.改进的最大最小蚂蚁算法在有时间窗车辆路径问题中的应用[J].计算机集成制造系统，2005.11（4）： 572-576
[7] Wissner-Gross，A.D.， C.E.Freer. Causal Entropic Forces[J].PhysicalReview Letters 110，168702（2013）.