基于淘汰机制的果蝇优化算法求解车辆路径问题

发布时间：2017-12-12 00:27

  本文关键词：基于淘汰机制的果蝇优化算法求解车辆路径问题

  更多相关文章： 车辆路径问题 群智能 果蝇优化算法 旅行商问题 淘汰机制 算子

【摘要】：近些年来,随着社会节奏的加速、电子商务的蓬勃发展以及各大O2O平台的异军突起,越来越多的人开始选择网上购物、网上订餐,作为这些活动中的重要环节,物流开始在现实社会中扮演越来越重要的角色,但与之而来的则是物流代价的不断增加,因此,如何有效的减少物流代价,越来越成为人们关注的热点问题。在现实生活中,整个物流活动包括运输、储存、装卸、包装、流通加工、配送、信息处理等基本过程。根据相关统计,在整个物流成本中,配送成本所占比例约为53%,占比超过一半,因此,减少物流代价的关键在于减少配送代价。车辆路径问题(VRP)正是对物流配送活动的抽象,该问题是一个组合优化问题,也是一个典型的NP难问题,由Dantzing和Ramser两位科学家于1959年首次提出。目前求解VRP问题主要有两类方法:一类是可以求得确切解的精确算法,例如动态规划法、分支限定法、线性规划法等;另一类是可以在较短时间内求得近似最优解的启发式算法,例如禁忌搜索算法、遗传算法、蚁群算法等。果蝇优化算法是台湾学者潘文超根据果蝇觅食行为于2011年提出的一种新的群智能算法,该算法易于理解、实现简单,而且果蝇的嗅觉搜索过程对于解空间具有很好的扩展能力,但是果蝇的视觉搜索过程很容易使算法陷入局部最优。在充分研究了果蝇算法的优缺点之后,本文提出了一种改进的果蝇优化算法,并将其用于求解旅行商问题(TSP)和VRP问题,最后在相关数据集上进行了仿真实验,证明了算法的可行性和有效性。本文的主要工作有以下几点:(1)介绍了VRP问题的研究背景与意义,VRP问题的描述、数学模型及其分类,以及该问题的国内外研究现状。(2)充分研究了果蝇优化算法的基本原理,并基于该算法提出了一种改进的果蝇优化算法。改进后的算法加强了果蝇的视觉搜索能力,在其他果蝇向最优果蝇靠近的过程中,是缓慢的向最优果蝇靠近,而不是立刻到达最优果蝇所在的位置,这样就有效的减小了算法陷入局部最优的可能性。同时,改进后的算法还引入了淘汰机制,在算法的每次迭代过程中,会淘汰掉一部分表现较差的个体,并随机的加入相同数量的新的个体,这样就有效的增加了种群的多样性,增强了算法对于解空间的扩展能力。(3)利用改进的果蝇优化算法求解TSP问题。在求解过程中,定义了两个算子:逆序算子和乘法算子,分别用于模拟果蝇在嗅觉搜索过程中对于解空间的拓展和在视觉定位过程中向最优解的靠近。并且用TSPLIB中的10个基准数据集对于改进后的果蝇优化算法进行了仿真实验,实验结果证明了算法的可行性和有效性。(4)利用改进后的果蝇优化算法求解VRP问题。详细介绍了求解过程中的种群初始化、嗅觉搜索以及视觉搜索过程,并且在两组标准数据集上进行了仿真实验,实验结果证明了算法的可行性和有效性。
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：F724.6;TP18

【相似文献】

中国期刊全文数据库 前10条

1 任庆生,叶中行,曾进;进化算法的收敛速度[J];上海交通大学学报;1999年06期

2 唐浩;;蚁群算法的研究与展望[J];牡丹江教育学院学报;2009年06期

3 邓小波;曹聪聪;龙伦海;康耀红;;蚁群算法搜索熵研究[J];海南大学学报(自然科学版);2007年04期

4 张康;顾幸生;;全局组搜索优化算法及其应用研究[J];青岛科技大学学报(自然科学版);2012年05期

5 李东晓;蒋珉;柴干;;蚁群算法优化及其在高速公路紧急救援中的应用[J];计算机技术与发展;2010年11期

6 _5文龙 ,黄，

本文编号：1280497