引入拥挤度概念的人工蜂群算法及其应用

发布时间：2018-04-03 22:47

本文选题：蜂群算法　切入点：拥挤度　出处：《曲阜师范大学》2017年硕士论文

【摘要】：人工蜂群算法是一种稳定、高效的群体智能优化算法,它受到蜜蜂集体觅食行为的启发,在解决大多数问题时均表现出良好的性能。相较其它优化算法,它在寻优等方面有着收敛速度快、鲁棒性好、全局收敛、适用范围宽等优势,适用于多种类的优化,对有约束和无约束条件下的优化问题均有很强的应用价值。本论文对基本人工蜂群算法的相关知识进行了阐述。该算法需要设置的参数少、鲁棒性强、复杂度低,而且算法执行时能兼顾全局搜索和局部搜索,增加了获取最优极值的概率。本章也讨论了该算法存在的弊端,如:收敛易早熟、搜索精度较低、难以跳出局部极值等。本文首次引入“拥挤度”这一概念来改进基本人工蜂群算法。我们将通过定义一个拥挤度公式来调配人工蜂,限制采蜜峰的数量,并借此参数合理调控邻域搜索。当拥挤度低值时蜂群不需要进行任何调整,而当拥挤度高时将调用改进的观察蜂跟随公式,适当减少本区域采蜜蜂的数量;随后会增加侦查蜂的数量以扩大对解空间的全局搜索,这样就能在某种程度上帮助算法避免早熟现象,同时在后期提高算法的收敛速度。本文另一个改进思路是设定蜂群中侦查蜂始终存在,一般使其比例保持在蜂群总数的5%-10%左右,以此维持蜂群的多样性,以便继续保持对解空间的不断搜索。此方案的实施有助于人工蜂全局检索能力的提升,进一步加速算法执行后期的收敛。文章中讨论了网络服务质量(QoS)的由来,以及QoS度量、QoS服务体系模型、QoS路由分类等。QoS路由即端到端传输时选择传输链路,此链路要求符合QoS度量中的各条件限制。这些概念和相关的研究背景将为下一章打下基础。本文把改进的人工蜂群算法用于解决实际网络的QoS路由问题。该算法将通过人工蜂检索全部符合丢包率、带宽、延迟抖动、时延、等限定情况下的可行链路,以此确定组播路由的最优链路。我们通过仿真实验观察两种算法在实际应用中的表现,先通过Dijkstra前N条路径算法构建非劣解集,人工蜂在非劣解集中执行邻域搜索行为以获取适应度更高的优质解。最后对比这两种算法求解最优链路时所花费的代价、平均迭代次数等指标,以此证明引入拥挤度参数后的改进算法实用性良好。
[Abstract]:Artificial bee colony algorithm is a stable and efficient swarm intelligence optimization algorithm. It is inspired by the collective foraging behavior of bees and shows good performance in solving most of the problems.Compared with other optimization algorithms, it has the advantages of fast convergence speed, good robustness, global convergence, wide application range and so on. It is suitable for many kinds of optimization.Both constrained and unconstrained optimization problems have strong application value.In this paper, the basic knowledge of artificial bee colony algorithm is described.The algorithm needs few parameters, strong robustness, low complexity, and the algorithm can take into account the global search and local search, thus increasing the probability of obtaining the optimal extremum.In this chapter, we also discuss the disadvantages of this algorithm, such as premature convergence, low searching precision and difficulty to jump out of the local extremum and so on.In this paper, the concept of "crowding degree" is introduced for the first time to improve the basic artificial bee colony algorithm.We will define a crowding formula to allocate artificial bees to limit the number of honey peaks collected and use this parameter to regulate the neighborhood search reasonably.When the crowding degree is low, the colony does not need any adjustment, but when the crowded degree is high, the improved observation bee follow formula will be called to reduce the number of bees collected in this area.Subsequently, the number of detection bees will be increased to expand the global search of the solution space, which can help the algorithm to avoid precocity to some extent and improve the convergence speed of the algorithm in the later stage.In this paper, another way of improving is to set the detection bee in the colony to always exist, and generally keep its proportion at about 5- 10% of the total number of bees, so as to maintain the diversity of the colony, so as to keep the continuous search of the solution space.The implementation of this scheme is helpful to enhance the global retrieval ability of human worker bees and further accelerate the convergence of the algorithm in the later stage of execution.This paper discusses the origin of QoS (quality of Service) in network, and the choice of transmission link when end-to-end transmission, such as QoS metrics, QoS routing classification and so on. This link needs to meet the constraints of QoS metrics.In this paper, the improved artificial bee colony algorithm is used to solve the QoS routing problem in real networks.In order to determine the optimal link of multicast routing, the algorithm will retrieve all feasible links under limited conditions such as packet loss rate, bandwidth, delay jitter, delay, etc.We observe the performance of the two algorithms in practical application through simulation experiments. First, we construct the non-inferior solution set by the N-path algorithm before Dijkstra, and the worker bee performs neighborhood search behavior in the non-inferior solution set to obtain a higher fitness solution.Finally, the cost and the average number of iterations of the two algorithms are compared to prove the practicability of the improved algorithm.
【学位授予单位】：曲阜师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】