人工蜂群算法研究及其在车辆路径问题的应用

发布时间：2019-06-20 00:57

【摘要】：目前,工程上的优化问题越来越棘手,传统的解决方法已经无法高效地解决这些难题。生活中常见的现象,比如说鸟群协作进行的捕食行为、蚂蚁能找到偏僻角落的甜食以及头脑简单的蜜蜂却构造出世界上最神奇的建筑等,都是由简单生物表现出的群智能,人类从中获得灵感提出了群智能算法,人工蜂群算法正是其中的一种。该算法一经提出,由于其结构简单易实现、性能优越,越来越多研究人员对其进行研究。人工蜂群算法虽然优秀,但是其存在很多优化算法都存在的缺点——收敛速度慢。本文通过分析其收敛速度慢的原因,并针对分析结果进行改进提出了基于局部和全局信息交互的人工蜂群算法(ABCLGII)。本文首先描述了人工蜂群算法的研究背景及发展,然后分析了人工蜂群算法存在的不足,设计了ABCLGII算法,之后通过在数值优化问题及在车辆路径问题上的应用去验证ABCLGII算法的有效性。本文的主要工作如下:1)本文分析人工蜂群算法存在的不足,设计了基于局部和全局信息交流的人工蜂群算法(ABCLGII)。该算法主要的创新点在于增强同类蜜蜂之间的信息交互,充分利用优秀个体的信息对种群的搜索进行引导。ABCLGII通过三个新颖的搜索公式以及一个自适应选择策略去实现上述机制,通过这种方式使得蜂群从原来盲目独立的搜索变为有方向性的合作式搜索,提升了种群全局收敛速度,由此改善算法搜索性能。通过ABCLGII与其它算法在22个标准测试函数的数据对比,验证了ABCLGII算法存在一定的优势。2)本文将改进的人工蜂群算法应用到车辆路径问题上,通过将种群个体向量进行离散化,使得一个个体即代表一条路径,然后使用ABCLGII算法进行不断地迭代进化,找出以运输成本最低为目标的最优车辆路径。通过ABC、遗传算法和ABCLGII算法的运行数据对比,验证了ABCLGII算法在实际应用问题的优势。
[Abstract]:At present, the optimization problems in engineering are becoming more and more difficult, and the traditional solutions can not solve these problems efficiently. The common phenomena in life, such as the predation behavior of birds, the ability of ants to find sweets in remote corners and the construction of the most magical buildings in the world by bees with simple minds, are all swarm intelligence shown by simple creatures. Human beings get inspiration from them and propose swarm intelligence algorithm. Artificial bee swarm algorithm is one of them. Once the algorithm is proposed, because its structure is simple and easy to implement, and its performance is superior, more and more researchers have studied it. Although the artificial bee swarm algorithm is excellent, it has many shortcomings, that is, the convergence speed is slow. In this paper, an artificial beehive algorithm (ABCLGII). Based on local and global information interaction is proposed by analyzing the reasons for its slow convergence and improving the analysis results. In this paper, the research background and development of artificial beehive algorithm are described, then the shortcomings of artificial beehive algorithm are analyzed, and the ABCLGII algorithm is designed. Then, the effectiveness of ABCLGII algorithm is verified by its application in numerical optimization problem and vehicle routing problem. The main work of this paper is as follows: 1) in this paper, the shortcomings of artificial beehive algorithm are analyzed, and an artificial beehive algorithm (ABCLGII). Based on local and global information exchange is designed. The main innovation of the algorithm is to enhance the information interaction among the same kind of bees, and make full use of the information of excellent individuals to guide the search of the population. ABCLGII realizes the above mechanism through three novel search formulas and an adaptive selection strategy, which makes the bee colony change from blind and independent search to directional cooperative search, which improves the global convergence speed of the population. Thus, the search performance of the algorithm is improved. By comparing the data of ABCLGII with other algorithms in 22 standard test functions, it is verified that the ABCLGII algorithm has some advantages. 2) in this paper, the improved artificial bee swarm algorithm is applied to the vehicle routing problem. By discretizing the individual vector of the population, an individual represents a path, and then the ABCLGII algorithm is used for continuous iterative evolution to find the optimal vehicle path with the lowest transportation cost. By comparing the running data of ABC, genetic algorithm and ABCLGII algorithm, the advantages of ABCLGII algorithm in practical application are verified.
【学位授予单位】：深圳大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【相似文献】