论文部分内容阅读
摘 要：为了丰富解决车辆路径优化问题的方式，提出一种融入了局部搜索的离散型细菌菌落优化算法。首先设计了算法的个体编码方式和进化模式；然后融入局部搜索方式来加速算法寻优的效率；最后将该算法应用于带时间窗的车辆路径问题，并采用solomon数据验证，通过与其他算法进行比较，验证算法的可行性。
关键词：细菌菌落算法；车辆路径问题；离散型优化；局部搜索
中图分类号：TP312
随着物流业在现代经济中地位的上升，物流配送系统的完善与发展已经成为众多国内外学者研究的热点。车辆路径优化问题是影响物流配送水平的重要因素，合理的车辆行驶路径可以在提高服务质量的同时，降低企业的运营成本。为此，Dantzig和Ramser于1959年首次提出车辆路径优化问题（Vehicle Routine Problem，简称VRP）。VRP问题已被证明是np难题，经过广大学者的多年研究，求VRP问题
1 问题描述与数学模型
车辆路径中的客户点作为细菌位置矢量的编码，去除中间的编码转换，使得细菌可以直接在路径问题的解空间中对最优解进行优化搜索。所以，要用细菌算法来解绝问题，就必须设计出合适的个体表达方式。在文献[6-8]中采用了LOV编码方式，该规则先根据个体位置分量在连续空间中的大小进行排序，并将排序后的序列作为问题的一个可行解，因此算法本质上还是在连续空间中对最优解进行搜索。由于算法搜索空间和实际排序问题的离散解空间之间不存在严格的对应关系，所以个体在连续空间中所得到解的优劣性无法通过LOV编码直接反映到排序问题的解空间中。车辆路径问题本质上也是一种排序问题，显然这些算法还是利用连续函数优化的方法解决这类问题，不可避免地存在一定程度的不足。
根据群集优化算法的基本原理，个体会向群体或个体历史最优位置移动，在连续空间中，可以通过简单的向量加减来实现优化，但无法直接将其运用到离散空间中。因此，本文需要对离散个体的这种移动方式重新定义。
图1反应的是适应值fitness与迭代次数的关系。由图可看出，迭代初始时适应值随迭代次数的增加有所减小在200次时趋于平稳，此时算法有陷入局部最优的可能，通过设置最大迭代数可突破这种状态，跳出局部最优进而找到更好的解。本文的迭代进程除了可以设置精度要求和最大迭代次数来结束外，还可以通过设置细菌寿命自然结束算法。
图2反应的是最大种群规模数SN与k之间的关系。由图可看出，种群数量的变化基本与培养基中细菌菌落规模的变化一致。
4 结束语
本文的离散细菌聚落优化算法，可以在解空间中直接对最优解进行优化，并且具有一定的搜索能力和稳定性。通过Solomon数据对算法进行验证，与S-PSO和I-PSO算法的对比中可以看出算法具有一定的优越性。但算法的各参数还有待进一步调试，算法的进化机制有一定的进步空间，各种算法的间优点的融合必然会提高解决问题的效率和精度。
参考文献：
[1]李琳，刘士新，唐加福.改进的蚁群算法求解带时间窗的车辆路径问题[J].控制与决策.2010（09）：1379-1383.
[2]徐杰，黄德先.基于混合粒子群算法的多目标车辆路径研究[J].计算机集成制造系统，2007（03）：573-584.
[3]蒋忠中，汪定伟.物流配送车辆路径优化的模糊规划模型与算法[J].系统仿真学报，2006（11）：3301-3304.
[4]李明，杨成梧.细菌菌落优化算法[J].控制理论与应用，2011（02）：223-228.
[5]宋德罗，孔德福等.一种离散细菌菌落优化算法研究[J].软件导刊，2013（12）：52-54.
[6]Yue-Jiao Gong， Jun Zhang， Ou Liu， et al. Optimizing the Vehicle Routing Problem With Time Windows： A Discrete Particle Swarm Optimization Approach .IEEE Transactions on Systems[J]，2012（02）：254-267.
[7]PASSINO K M.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems Magazine， 2002（03）：52-67.
[8]C.-H. Chen and C.-J. Ting， “A hybrid ant colony system for vehicle routing problem with time windows，” J. Eastern Asia Soc. Transp. Stud. ，vol.6，pp.2822-2836，2005.
作者简介：孔德福（1987-），男，安徽人，硕士研究生，研究方向：智能控制、群集智能优化算法；李明（1977-），男，江苏人，博士，副教授，研究方向：智能控制、群集智能优化算法。
作者单位：西南林业大学 机械与交通学院，云南昆明 650224；平顶山学院 电气信息工程学院，河南平顶山 467000
基金项目：国家自然科学基金项目（31100424）；云南省自然科学基金项目（2009CD070）；云南省教育厅科学研究基金项目（2012J047）。
关键词：细菌菌落算法；车辆路径问题；离散型优化；局部搜索
中图分类号：TP312
随着物流业在现代经济中地位的上升，物流配送系统的完善与发展已经成为众多国内外学者研究的热点。车辆路径优化问题是影响物流配送水平的重要因素，合理的车辆行驶路径可以在提高服务质量的同时，降低企业的运营成本。为此，Dantzig和Ramser于1959年首次提出车辆路径优化问题（Vehicle Routine Problem，简称VRP）。VRP问题已被证明是np难题，经过广大学者的多年研究，求VRP问题
1 问题描述与数学模型
车辆路径中的客户点作为细菌位置矢量的编码，去除中间的编码转换，使得细菌可以直接在路径问题的解空间中对最优解进行优化搜索。所以，要用细菌算法来解绝问题，就必须设计出合适的个体表达方式。在文献[6-8]中采用了LOV编码方式，该规则先根据个体位置分量在连续空间中的大小进行排序，并将排序后的序列作为问题的一个可行解，因此算法本质上还是在连续空间中对最优解进行搜索。由于算法搜索空间和实际排序问题的离散解空间之间不存在严格的对应关系，所以个体在连续空间中所得到解的优劣性无法通过LOV编码直接反映到排序问题的解空间中。车辆路径问题本质上也是一种排序问题，显然这些算法还是利用连续函数优化的方法解决这类问题，不可避免地存在一定程度的不足。
根据群集优化算法的基本原理，个体会向群体或个体历史最优位置移动，在连续空间中，可以通过简单的向量加减来实现优化，但无法直接将其运用到离散空间中。因此，本文需要对离散个体的这种移动方式重新定义。
图1反应的是适应值fitness与迭代次数的关系。由图可看出，迭代初始时适应值随迭代次数的增加有所减小在200次时趋于平稳，此时算法有陷入局部最优的可能，通过设置最大迭代数可突破这种状态，跳出局部最优进而找到更好的解。本文的迭代进程除了可以设置精度要求和最大迭代次数来结束外，还可以通过设置细菌寿命自然结束算法。
图2反应的是最大种群规模数SN与k之间的关系。由图可看出，种群数量的变化基本与培养基中细菌菌落规模的变化一致。
4 结束语
本文的离散细菌聚落优化算法，可以在解空间中直接对最优解进行优化，并且具有一定的搜索能力和稳定性。通过Solomon数据对算法进行验证，与S-PSO和I-PSO算法的对比中可以看出算法具有一定的优越性。但算法的各参数还有待进一步调试，算法的进化机制有一定的进步空间，各种算法的间优点的融合必然会提高解决问题的效率和精度。
参考文献：
[1]李琳，刘士新，唐加福.改进的蚁群算法求解带时间窗的车辆路径问题[J].控制与决策.2010（09）：1379-1383.
[2]徐杰，黄德先.基于混合粒子群算法的多目标车辆路径研究[J].计算机集成制造系统，2007（03）：573-584.
[3]蒋忠中，汪定伟.物流配送车辆路径优化的模糊规划模型与算法[J].系统仿真学报，2006（11）：3301-3304.
[4]李明，杨成梧.细菌菌落优化算法[J].控制理论与应用，2011（02）：223-228.
[5]宋德罗，孔德福等.一种离散细菌菌落优化算法研究[J].软件导刊，2013（12）：52-54.
[6]Yue-Jiao Gong， Jun Zhang， Ou Liu， et al. Optimizing the Vehicle Routing Problem With Time Windows： A Discrete Particle Swarm Optimization Approach .IEEE Transactions on Systems[J]，2012（02）：254-267.
[7]PASSINO K M.Biomimicry of bacterial foraging for distributed optimization and control[J].IEEE Control Systems Magazine， 2002（03）：52-67.
[8]C.-H. Chen and C.-J. Ting， “A hybrid ant colony system for vehicle routing problem with time windows，” J. Eastern Asia Soc. Transp. Stud. ，vol.6，pp.2822-2836，2005.
作者简介：孔德福（1987-），男，安徽人，硕士研究生，研究方向：智能控制、群集智能优化算法；李明（1977-），男，江苏人，博士，副教授，研究方向：智能控制、群集智能优化算法。
作者单位：西南林业大学 机械与交通学院，云南昆明 650224；平顶山学院 电气信息工程学院，河南平顶山 467000
基金项目：国家自然科学基金项目（31100424）；云南省自然科学基金项目（2009CD070）；云南省教育厅科学研究基金项目（2012J047）。